题目描述

有一条长 $l$ 米的道路（数轴），路上有 $n$ 个充电站。每天整条路上（坐标区间 $[0,l]$）都会落满雪。

有一台机器能扫雪。充一次电可以扫至多 $k$ 米的雪。扫雪是和移动同时进行的：

• 移动但不扫雪：不消耗电，需要 1 秒；
• 移动并扫雪：消耗最大电量的 $\frac{1}{k}$，需要 1 秒；
• 扫雪必须移动（不能原地扫）。

给出每天机器的初始位置（机器初始没电），问每天清除所有雪的最少时间，终点位置任意。

带修：充电站可能损坏或修好（第一天之前都是好的），但保证每天至少有一个好的充电站（所以不会无解）。

输入格式

第一行四个整数 $n, l, k, d$。
第二行 $n$ 个整数 $x_1, x_2, \dots, x_n$ 表示充电站的位置，保证 $0 \le x_1 < x_2 < \cdots < x_n \le l$。

接下来 $3d$ 行描述 $d$ 天的事件：

• 第 1 行三个整数 $z, u, p$，分别表示昨晚修好的充电站数量、损坏的数量，以及机器的初始位置；
• 第 2 行 $z$ 个整数，表示被修好的充电站编号；
• 第 3 行 $u$ 个整数，表示损坏的充电站编号。

输出格式

输出 $d$ 行，每行一个整数，表示每天的答案。

样例输入 1 / 输出 1

3 5 2 1
2 3 5
0 1 3
2

9

样例输入 2 / 输出 2

2 9 2 1
0 9
0 0 0

25

样例输入 3 / 输出 3

3 22 2 1
1 10 21
0 0 1

69

样例输入 4 / 输出 4

5 12 1 1
0 5 7 9 11
0 0 1

30

样例解释

→ 表示移动，⇒ 表示移动并扫雪。
例如某一天的操作序列可以写成：

• $3 \rightarrow 2 \Rightarrow 0 \rightarrow 2 \Rightarrow 4 \rightarrow 5 \Rightarrow 4$

数据范围与提示

• 对于所有数据：$1 \le n \le 250000$，$1 \le l \le 10^9$，$1 \le k \le l$，$1 \le d \le 250000$，且 $\sum z,\sum u \le 500000$。

子任务