Tài là một người nông dân gương mẫu và đang sở hữu một nông trại với các cây táo được trồng trên một cung đường hình vòng cung độ dài ~L~. Vị trí của ~M~ cây táo được xác định bằng các chỉ số ~B_1, B_2, \dots, B_M~ sao cho mỗi cây táo ~i~ có vị trí ~B_i~ trên vòng tròn này, với ~0 \leq B_i < L~.

Ngoài ra, Tài có ~N~ nông dân làm việc cho mình, mỗi người đang đứng tại vị trí ~A_1, A_2, \dots, A_N~ trên vòng tròn. Ban đầu, mỗi cây táo đều có quả và có thể thu hoạch được.

Mỗi giây, các nông dân sẽ di chuyển tới vị trí kế tiếp trên vòng tròn, cụ thể: từ vị trí ~i~ sẽ di chuyển tới vị trí ~(i + 1) \% L~. Khi một nông dân đến cây táo, nếu cây táo có quả, người nông dân sẽ thu hoạch quả táo đó.

Sau ~C~ giây kể từ khi quả táo được thu hoạch, quả táo mới sẽ mọc trên cây. Nếu một nông dân đến đúng lúc quả mới mọc, họ cũng có thể thu hoạch quả đó.

Cho ~Q~ truy vấn, mỗi truy vấn cung cấp hai số ~V~ và ~T~, yêu cầu bạn tính số quả táo mà người nông dân thứ ~V~ đã thu hoạch sau ~T~ giây.

Input

Dòng đầu tiên gồm bốn số nguyên ~N~, ~M~, ~L~ và ~C~ (~1 \leq N, M \leq 2 \times 10^5~, ~N + M \leq L, C \leq 10^9~) — số lượng nông dân, số lượng cây táo, độ dài vòng tròn và thời gian để quả táo mới mọc sau khi được thu hoạch.

Dòng tiếp theo gồm một dãy ~N~ số nguyên ~A_1, A_2, \dots, A_N~ (~0 \leq A_i < L~, ~A_1 < A_2 < \dots < A_N~) — vị trí của ~N~ nông dân trên vòng tròn.

Dòng tiếp theo gồm một dãy ~M~ số nguyên ~B_1, B_2, \dots, B_M~ (~0 \leq B_i < L~, ~B_1 < B_2 < \dots < B_M~) — vị trí của ~M~ cây táo trên vòng tròn.

Dòng tiếp theo gồm một số nguyên ~Q~ (~1 \leq Q \leq 2 \times 10^5~) — số lượng truy vấn.

~Q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~V_i~ và ~T_i~ (~1 \leq V_i \leq N~, ~1 \leq T_i \leq 10^{18}~) — yêu cầu bạn tính số quả táo mà nông dân thứ ~V_i~ đã thu hoạch sau ~T_i~ giây.

Output

Với mỗi truy vấn, in ra một số nguyên — số quả táo mà nông dân thứ ~V_i~ đã thu hoạch sau ~T_i~ giây.

Scoring

Sample Input 1

3 2 7 3
1 4 6
0 5
3
1 7
2 3
3 8

Sample Output 1

2
1
1

Sample Input 2

5 3 20 6
0 4 8 12 16
2 11 14
9
4 1932
2 93787
1 89
5 98124798
1 2684
1 137598
3 2
3 8375
4 237

Sample Output 2

146
7035
7
7359360
202
10320
0
628
18