巴伊托尼亚（Bajtocja）今年的冬天非常适合堆雪人。然而，这对我们的雪人爱好者朋友来说是好事，但对道路维护人员来说却不然，尤其是对负责清理城市主干道的巴伊塔扎（Bajtazar）而言。

全长 $\ell$ 米的道路每晚都会被积雪覆盖。勇敢的巴伊塔扎拥有一台电动除雪机，单次充电可清理 $k$ 米长的道路。道路沿线有 $n$ 个充电站可供巴伊塔扎使用。不幸的是，每个夜晚都会带来意外，大雪可能会损坏充电站，或者以某种神秘的方式修复已损坏的充电站（但每次至少会有一个充电站保持正常工作）。在第一次暴风雪之前，所有的充电站都是完好的。每天晚上，风也会带来麻烦，将除雪机吹到不同的位置。经过一夜，除雪机的电量会耗尽，必须重新充电。巴伊塔扎永远不知道第二天会发生什么。

我们将道路上的位置定义为距离道路起点的距离（以米为单位）；第 $i$ 个充电站位于点 $x_i$。巴伊塔扎走过一米道路（无论是否在除雪）需要一秒钟。除雪机仅在清除积雪时消耗电量，巴伊塔扎手动移动它。在正常的充电站，除雪机的充电时间可以忽略不计。巴伊塔扎可以在道路上的任何点掉头。

巴伊塔扎每天早上清理整条道路所需的最短时间是多少？巴伊塔扎每天开始工作时都在除雪机所在的位置，但他可以在道路上的任意一点结束工作。

输入格式

第一行包含四个整数 $n, \ell, k$ 和 $d$ ($1 \le n \le 250\,000, 1 \le \ell \le 10^9, 1 \le k \le \ell, 1 \le d \le 250\,000$)，分别表示充电站的数量、道路长度、除雪机电池容量以及巴伊塔扎需要除雪的天数。

第二行包含 $n$ 个整数 $x_1, x_2, \dots, x_n$ ($0 \le x_1 < x_2 < \dots < x_n \le \ell$)，表示各充电站的位置。

接下来的 $3d$ 行包含 $d$ 个夜晚和白天的描述；每个描述由三行组成。

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

第二行包含一个递增序列，包含 $z$ 个整数 $a_1, \dots, a_z$ ($1 \le a_i \le n$)，表示当天晚上被修复的充电站编号。这些充电站之前是损坏的。

第三行包含一个递增序列，包含 $u$ 个整数 $b_1, \dots, b_u$ ($1 \le b_i \le n$)，表示当天晚上损坏的充电站编号。这些充电站之前是正常的。

对于每个夜晚，集合 $\{a_1, \dots, a_z\}$ 和 $\{b_1, \dots, b_u\}$ 是不相交的。请注意，描述中的第二行和/或第三行可能为空。

所有夜晚中 $z$ 和 $u$ 的总和不超过 $500\,000$。

输出格式

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

样例

输入 1

3 5 2 1
2 3 5
0 1 3
2

输出 1

9

说明 1

在工作的第一天（也是唯一的一天），巴伊塔扎在点 $3$ 处的损坏充电站旁找到了除雪机，然后走到点 $2$，在那里给除雪机充电并向左清理了长度为 $2$ 的路段，然后回到点 $2$，充电并向右清理了长度为 $2$ 的路段，接着走到点 $5$，给除雪机充电并向左清理了长度为 $1$ 的路段。他在点 $4$ 结束工作；这总共花费了他 $9$ 秒。

子任务