Problem Description

There is a road of length $l$ meters (a number line). There are $n$ charging stations along the road. Every day, the entire road (coordinates $[0, l]$) is covered with snow.

A machine is available to clear the snow. After being charged, it can clear up to $k$ meters of snow. Snow clearing and movement occur simultaneously, as detailed in the sample explanation. The machine can move one meter per second, and charging does not consume time.

In simple terms, moving without clearing snow does not consume electricity and takes one second; moving while clearing snow consumes $\frac{1}{k}$ of the maximum battery capacity and takes one second; clearing snow must be done while moving.

Given the initial position of the machine each day, which starts with no charge, the task is to determine the minimum time required to clear all the snow each day. The final destination is arbitrary.

The problem involves modifications, meaning charging stations may break down or be repaired (all were functional before the first day), but it is guaranteed that there is at least one functional charging station each day (so there is always a solution).

Input Format

The first line contains four integers $n, l, k, d$.

The second line contains $n$ integers $x_1, x_2, \dots, x_n$, representing the positions of the charging stations, with $0 \leq x_1 < x_2 < \dots < x_n \leq l$.

The next $3d$ lines describe the events for $d$ days:

• The first line contains three integers $z, u, p$, representing the number of charging stations repaired last night, the number that broke down, and the initial position of the machine.
• The second line contains $z$ integers, indicating the repaired charging stations' indices.
• The third line contains $u$ integers, indicating the broken charging stations' indices.

Output Format

Output $d$ lines, each containing a single integer, representing the minimum time required each day.

Sample Input and Output

Input Sample #1

3 5 2 1
2 3 5
0 1 3

Output Sample #1

9

Input Sample #2

5 12 1 5
1 3 6 9 11
0 1 1
1
1 1 3
1
2
1 1 6
2
3
1 1 9
3
4
1 1 11
4
5

Output Sample #2

33
33
36
33
33

Input Sample #3

11 100 1 26
0 10 20 30 40 50 60 70 80 90 100
0 5 0
2 4 6 8 10
5 6 4
2 4 6 8 10
1 3 5 7 9 11
6 5 8
1 3 5 7 9 11
2 4 6 8 10
5 6 12
2 4 6 8 10
1 3 5 7 9 11
6 5 16
1 3 5 7 9 11
2 4 6 8 10
5 6 20
2 4 6 8 10
1 3 5 7 9 11
6 5 24
1 3 5 7 9 11
2 4 6 8 10
5 6 28
2 4 6 8 10
1 3 5 7 9 11
6 5 32
1 3 5 7 9 11
2 4 6 8 10
5 6 36
2 4 6 8 10
1 3 5 7 9 11
6 5 40
1 3 5 7 9 11
2 4 6 8 10
5 6 44
2 4 6 8 10
1 3 5 7 9 11
6 5 48
1 3 5 7 9 11
2 4 6 8 10
5 6 52
2 4 6 8 10
1 3 5 7 9 11
6 5 56
1 3 5 7 9 11
2 4 6 8 10
5 6 60
2 4 6 8 10
1 3 5 7 9 11
6 5 64
1 3 5 7 9 11
2 4 6 8 10
5 6 68
2 4 6 8 10
1 3 5 7 9 11
6 5 72
1 3 5 7 9 11
2 4 6 8 10
5 6 76
2 4 6 8 10
1 3 5 7 9 11
6 5 80
1 3 5 7 9 11
2 4 6 8 10
5 6 84
2 4 6 8 10
1 3 5 7 9 11
6 5 88
1 3 5 7 9 11
2 4 6 8 10
5 6 92
2 4 6 8 10
1 3 5 7 9 11
6 5 96
1 3 5 7 9 11
2 4 6 8 10
5 6 100
2 4 6 8 10
1 3 5 7 9 11

Output Sample #3

1090
1096
1098
1092
1094
1100
1094
1092
1098
1096
1090
1096
1098
1092
1094
1100
1094
1092
1098
1096
1090
1096
1098
1092
1094
1100

Notes

Sample explanation: $3 \rightarrow 2_{charge} \Rightarrow 0 \rightarrow 2_{charge} \Rightarrow 4 \rightarrow 5_{charge} \Rightarrow 4$. $\rightarrow$ denotes movement, $\Rightarrow$ denotes movement while clearing snow.

For all data, $1 \leq n \leq 250000$, $1 \leq l \leq 10^9$, $1 \leq k \leq l$, $1 \leq d \leq 250000$, $\sum z, \sum u \leq 500000$.

见题面 Input 部分

见题面 Output 部分