题目描述

一条长度为 $\ell$ 米的道路每晚都会被大雪覆盖。无畏的 Bajtazar 拥有一台电动除雪机，每次充满电可以清理 $k$ 米道路。沿路有 $n$ 个充电站可供他使用。然而，每晚的暴风雪都会带来意外，有些充电站可能会损坏，也有些会神奇地被修复（不过，每晚至少有一个充电站是可用的）。在第一次暴风雪之前，所有充电站都是完好的。每晚狂风还会把除雪机吹到道路上的随机位置。经过一夜后，除雪机的电量会完全耗尽，必须重新充电。Bajtazar 永远不知道明天会发生什么。

我们用距离道路起点的距离（单位：米）来表示道路上的位置，第 $i$ 个充电站位于位置 $x_{i}$。Bajtazar 每移动一米（无论是否除雪）需要一秒钟。除雪机只有在清除积雪时才会消耗电量，Bajtazar 手动移动它时不耗电。在完好的充电站充电所需时间可以忽略不计。Bajtazar 可以在道路上的任何位置掉头。

请你帮助 Bajtazar 计算，每天早上清理整条道路所需的最短时间是什么？Bajtazar 每天从除雪机所在位置开始工作，但可以在道路上的任意位置结束。

输入格式

输入的第一行包含四个整数 $n, \ell, k, d$ $(1 \leq n \leq 250000, 1 \leq \ell \leq 10^{9}, 1 \leq k \leq \ell, 1 \leq d \leq 250000)$，分别表示充电站数量、道路长度、除雪机电池容量和 Bajtazar 需要除雪的天数。

第二行包含 $n$ 个整数 $x_{1}, x_{2}, \ldots, x_{n}$ $(0 \leq x_{1} < x_{2} < \ldots < x_{n} \leq \ell)$，表示各个充电站的位置。

接下来的 $3d$ 行描述连续 $d$ 个夜晚和白天的情况，每天的描述占用三行：

第一行包含三个整数 $z, u, p$ $(0 \leq z, u \leq n, 0 \leq p \leq \ell)$，分别表示前一晚神奇修复的充电站数量、当晚损坏的充电站数量，以及除雪机被风吹到的位置。

第二行包含 $z$ 个递增的整数 $a_{1}, \ldots, a_{z}$ $(1 \leq a_{i} \leq n)$，表示当晚被神奇修复的充电站编号，这些充电站之前是损坏的。

第三行包含 $u$ 个递增的整数 $b_{1}, \ldots, b_{u}$ $(1 \leq b_{i} \leq n)$，表示当晚损坏的充电站编号，这些充电站之前是完好的。

对于每晚，集合 $\left\{a_{1}, \ldots, a_{z}\right\}$ 和 $\left\{b_{1}, \ldots, b_{u}\right\}$ 是互不相交的。注意，第二行和/或第三行可能是空的。

所有夜晚的 $z$ 和 $u$ 之和不超过 $500000$。

输出格式

你的程序应输出 $d$ 行，每行包含一个整数，表示每天清理整条道路所需的最短时间。

3 5 2 1
2 3 5
0 1 3

2

9

样例 2

见附加文件下 [sur1.in](file:sur1.in) 和 [sur1.out](file:sur1.out)。

该样例满足 $n=5, \ell=12, k=1, d=5, x=[1, 3, 6, 9, 11]$，第 $i$ 天只有第 $i$ 个充电站损坏，询问除雪机位于第 $i$ 个充电站的位置；

样例 3

见附加文件下 [sur2.in](file:sur2.in) 和 [sur2.out](file:sur2.out)。

该样例满足 $n=11, \ell=100, k=1, d=26, x_{i}=10(i-1)$，奇数天只有奇数编号的充电站可用，偶数天只有偶数编号的充电站可用，第 $i$ 天询问除雪机位于位置 $4(i-1)$；

样例 4

见附加文件下 [sur3.in](file:sur3.in) 和 [sur3.out](file:sur3.out)。

该样例满足 $n=45, \ell=2^{23}, k=4, d=2^{13}+1, x_{i}=[2^{0}, 2^{1}, \ldots, 2^{21}, 2^{22}, 2^{23}-2^{21}, 2^{23}-2^{20}, \ldots, 2^{23}-2^{0}]$，第 $i$ 天询问除雪机位于位置 $2^{10}(i-1)$；

样例 5

见附加文件下 [sur4.in](file:sur4.in) 和 [sur4.out](file:sur4.out)。

该样例满足 $n=250000, \ell=10^{9}, k=1, d=2, x_{i}=4000 \cdot (i-1)$，第一晚除第一个充电站外的所有充电站损坏，第二晚所有充电站修复，询问除雪机位于位置 $0$。

数据范围与提示

详细子任务附加限制及分值如下表所示。

子任务	附加限制	分值
$1$	$\ell \leq 12, d \leq 50$	$10$
$2$	$\ell \leq 500, d \leq 50, k=1$	$12$
$3$	$\ell \leq 5000000, d \leq 20$	$8$
$4$	充电站不损坏也不修复	$8$
$5$	每天不可用的充电站数量 $\leq 100, k \leq 50$	$20$
$6$	$k=1$	$18$
$7$	无附加限制	$24$