Một khu đất được chia thành ~N~ mảnh liền kề đánh số từ ~1~ đến ~N~. Mảnh thứ ~i~ có độ cao là số nguyên không âm ~H_i~.

Có ~M~ nhà đầu tư tham gia dự án. Nhà đầu tư thứ ~i~ muốn thuê toàn bộ các mảnh đất thuộc đoạn ~[L_i,R_i]~ và chỉ chấp nhận khi ~H_j=0~ ~(L_i \le j \le R_i)~. Các yêu cầu là độc lập, có thể nhiều nhà đầu tư muốn thuê cùng một đoạn.

Đội thi công nhận được ~Q~ chỉ thị liên tiếp. Mỗi chỉ thị chọn một vị trí ~x~ đang có ~H_x>0~ và thực hiện giảm ~H_x~ đi ~1~.

Yêu cầu: Sau mỗi chỉ thị, hãy cho biết số lượng nhà đầu tư đang được thỏa mãn.

Trong một số trường hợp để bảo mật thông tin, vị trí ~x_i~ có thể được mã hóa. Dữ liệu cung cấp giá trị ~y_i~ và tham số ~\theta~:

• Nếu ~\theta=0~, ~x_i=y_i~ (không mã hóa);

• Nếu ~\theta=1~, ~x_i=(y_i+lastans)\bmod N+1~, trong đó ~lastans~ là đáp án ngay trước chỉ thị thứ ~i~. Trước chỉ thị đầu tiên, ~lastans~ là số lượng nhà đầu tư thỏa mãn ở trạng thái ban đầu.

Input

• Dòng đầu tiên chứa bốn số nguyên ~N,M,Q,\theta~ ~(1 \le N,M,Q \le 5 \cdot 10^5;\ \theta \in \{0,1\})~;

• Dòng thứ hai chứa ~N~ số nguyên ~H_1,H_2,\dots,H_N~ ~(0 \le H_i \le 5 \cdot 10^5)~;

• ~M~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~L_i,R_i~ ~(1 \le L_i \le R_i \le N)~;

• Dòng cuối cùng chứa ~Q~ số nguyên ~y_1,y_2,\dots,y_Q~ ~(0 \le y_i < 10^9)~.

Dữ liệu bảo đảm sau khi giải mã luôn có ~1 \le x_i \le N~ và ~H_{x_i}>0~ ngay trước khi thực hiện chỉ thị.

Output

• In ~Q~ dòng; dòng thứ ~i~ là số lượng nhà đầu tư thỏa mãn sau chỉ thị thứ ~i~.

Scoring

Sample Input 1

6 4 6 0
1 1 1 2 1 1
2 6
3 4
5 5
4 4
4 3 4 2 5 6

Sample Output 1

0
0
2
2
3
4

Sample Input 2

5 5 6 1
4 1 1 1 0
3 3
3 4
2 2
4 4
3 4
5 0 6 1 1 0

Sample Output 2

0
0
1
2
5
5

Notes

Trong ví dụ thứ nhất, sau chỉ thị thứ ba, hai mảnh ~3~ và ~4~ đều có độ cao ~0~, nên hai nhà đầu tư có yêu cầu ~[3,4]~ và ~[4,4]~ được thỏa mãn.

Sau chỉ thị cuối cùng, các mảnh từ ~2~ đến ~6~ đều bằng ~0~ và cả bốn nhà đầu tư đều được thỏa mãn.

Trong ví dụ thứ hai, khi ~\theta=1~, trước chỉ thị đầu tiên, không có nhà đầu tư nào thỏa mãn nên ~lastans=0~, vị trí thực tế ~x_1=(5+0)\bmod 5+1=1~, ~H_1~ giảm từ ~4~ xuống ~3~.

Trước chỉ thị thứ tư, ~lastans=1~ nên vị trí thực tế là ~x_4=(1+1)\bmod 5+1=3~, ~H_3~ giảm từ ~2~ xuống ~1~.