题目描述

题目译自 XXVIII Olimpiada Informatyczna – III etap Surawa zima

一条长度为 $\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)$，
  表示当晚损坏的充电站编号，这些充电站之前是完好的。

对于每晚，集合 $\{a_1, \ldots, a_z\}$ 和 $\{b_1, \ldots, b_u\}$ 是互不相交的。
注意，第二行和/或第三行可能是空的。

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

---

输出格式

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

---

样例 1

输入

3 5 2 1
2 3 5
0 1 3

2

输出

9

解释
在工作第一天（也是唯一一天），Bajtazar 发现除雪机位于损坏的充电站位置 $3$。他先走到位置 $2$，充电后向左清理 $2$ 米长的路段，然后返回位置 $2$ 再次充电，向右清理 $2$ 米长的路段，接着走到位置 $5$，充电后向左清理 $1$ 米长的路段，最后在位置 $4$ 结束工作，整个过程需要 $9$ 秒。

---

样例 2

见附加文件下 sur1.in 和 sur1.out。

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

---

样例 3

见附加文件下 sur2.in 和 sur2.out。

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

---

样例 4

见附加文件下 sur3.in 和 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 和 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	充电站不损坏也不修复
5	每天不可用的充电站数量 $\leq 100$, $k \leq 50$	20
6	$k=1$	18
7	无附加限制	24