Trang trại IOI trồng táo và nổi tiếng vì nằm quanh một hồ nước lớn hình tròn. Trang trại có \(N\) nhân viên, đánh số từ \(1\) đến \(N\), và \(M\) cây táo, đánh số từ \(1\) đến \(M\). Chu vi hồ là \(L\) mét.

Ban đầu, nhân viên thứ \(i\) (\(1 \le i \le N\)) đứng cách điểm cực bắc của hồ \(A_i\) mét theo chiều kim đồng hồ. Các giá trị \(A_i\) đôi một khác nhau. Cây táo thứ \(j\) (\(1 \le j \le M\)) nằm cách điểm cực bắc của hồ \(B_j\) mét theo chiều kim đồng hồ. Các giá trị \(B_j\) đôi một khác nhau, và không có cây táo nào ở vị trí ban đầu của một nhân viên.

Nhờ cải tiến giống đặc biệt, mỗi cây có nhiều nhất một quả táo tại mỗi thời điểm. Sau khi một quả được hái, đúng \(C\) giây sau cây sẽ có một quả mới. Tại thời điểm \(0\), mỗi cây đều có một quả táo, và mọi nhân viên bắt đầu đi quanh hồ theo chiều kim đồng hồ với tốc độ \(1\) mét mỗi giây. Khi đến một cây đang có quả, nhân viên luôn hái quả đó. Nếu cây vừa có quả mới đúng lúc nhân viên đến, người đó cũng hái được quả. Bỏ qua thời gian hái táo.

Ngài K là cổ đông của trang trại IOI. Bạn là người quản lý trang trại, và ngài K yêu cầu bạn báo cáo hiệu suất của các nhân viên. Cụ thể, với mỗi truy vấn thứ \(k\) (\(1 \le k \le Q\)), hãy tính số quả táo nhân viên \(V_k\) hái được tính đến thời điểm \(T_k\), bao gồm cả quả hái đúng tại thời điểm \(T_k\) nếu có.

Cho số nhân viên, số cây táo, chu vi hồ, thời gian mọc quả mới, vị trí các nhân viên và cây táo cùng \(Q\) truy vấn, hãy trả lời từng truy vấn.

Dữ liệu vào

Đọc từ đầu vào chuẩn. Tất cả giá trị đều là số nguyên, theo định dạng:

N M L C
A_1 ... A_N
B_1 ... B_M
Q
V_1 T_1
...
V_Q T_Q

Dữ liệu ra

In ra \(Q\) dòng. Dòng thứ \(k\) (\(1 \le k \le Q\)) chứa đáp án cho truy vấn thứ \(k\).

Ràng buộc

• \(1 \le N,M \le 200\,000\).
• \(N+M \le L \le 1\,000\,000\,000\).
• \(1 \le C \le 1\,000\,000\,000\).
• \(0 \le A_i<L\) với \(1 \le i \le N\).
• \(A_i<A_{i+1}\) với \(1 \le i \le N-1\).
• \(0 \le B_j<L\) với \(1 \le j \le M\).
• \(B_j<B_{j+1}\) với \(1 \le j \le M-1\).
• \(A_i\ne B_j\) với \(1 \le i \le N\), \(1 \le j \le M\).
• \(1 \le Q \le 200\,000\).
• \(1 \le V_k \le N\) với \(1 \le k \le Q\).
• \(1 \le T_k \le 10^{18}\) với \(1 \le k \le Q\).

Phân nhóm

Các ràng buộc chung áp dụng cho mọi nhóm.

1. \(5\) điểm: \(N \le 3000\), \(M \le 3000\), \(Q \le 3000\)
2. \(20\) điểm: \(T_k \ge 10^{15}\) với mọi \(1 \le k \le Q\)
3. \(75\) điểm: Không có

Ví dụ

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

2
1
1

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

146
7035
7
7359360
202
10320
0
628
18

8 15 217 33608
0 12 71 96 111 128 152 206
4 34 42 67 76 81 85 104 110 117 122 148 166 170 212
14
2 223544052420046341
3 86357593875941375
4 892813012303440034
1 517156961659770735
7 415536186438473633
6 322175014520330760
7 557706040951533058
6 640041274241532527
5 286263974600593111
8 349405886653104871
1 987277313830536091
5 989137777159975413
2 50689028127994215
7 445686748471896881

33230868503053
3
5
1
123542793648997
8
165811220737767
8
7
1
1
7
7535161012043
132506837660717

Nguồn

JOI 2019/2020, Trại huấn luyện mùa xuân, ngày thi 3. Đề gốc của Ủy ban Olympic Tin học Nhật Bản, được cung cấp theo giấy phép CC BY-SA 4.0. Bản tiếng Việt được dịch từ đề tiếng Anh chính thức.