Cho số nguyên ~N~ và mảng ~a_1, a_2, \ldots, a_n~. Điểm của một đoạn liên tiếp bằng tổng giá trị lớn nhất và giá trị bé nhất trong đoạn. Cắt mảng đã cho thành ~K~ đoạn liên tiếp không giao nhau, không rỗng sao cho tổng điểm của các đoạn là lớn nhất. Mỗi phần tử phải nằm trong chính xác một đoạn.

Input

Dữ liệu vào từ file văn bản maximize.inp.

Dòng đầu tiên gồm số nguyên ~N~ – Số lượng phần tử của mảng (~1 \le N \le 10^5, 1 \le K \le \min(N, 20)~).

Dòng thứ hai gồm ~N~ số nguyên ~a_1, a_2, \ldots, a_n~ – Giá trị của mảng (~0 \le a_i \le 10^9, \forall 1 \le i \le N~).

Output

In ra file văn bản maximize.out một số nguyên duy nhất là kết quả bài toán.

Scoring

Sample Input 1

5 3
3 5 2 3 4

Sample Output 1

22

Sample Input 2

3 2
10 6 2006

Sample Output 2

4028

Notes

Ở ví dụ 1, ta chia thành 3 đoạn ~[1, 1], [2, 2]~ và ~[3, 5]~. Kết quả của cách chia này là ~3 + 3 + 5 + 5 + 2 + 4 = 22~.

Ở ví dụ 2, ta chia thành 2 đoạn ~[1, 2]~ và ~[3, 3]~. Kết quả của cách chia này là ~10 + 6 + 2006 + 2006 = 4028~.

Cho một cây có ~n~ đỉnh có gốc là đỉnh ~1~, đỉnh thứ ~i~ sẽ được phép gán một giá trị bất kỳ trong khoảng ~[L_i, R_i]~. Ta có ~m~ truy vấn dạng ~(A, B, C, D)~, một truy vấn được định nghĩa như sau:

Xem đường đi từ ~A~ đến ~B~ là dãy các đỉnh ~A = u_1, u_2, \dots, u_k = B~. Xem đường đi từ ~C~ đến ~D~ là dãy các đỉnh ~C = v_1, v_2, \dots, v_k = D~. Mỗi truy vấn là một ràng buộc: giá trị được gán ở đỉnh ~u_i~ phải bằng giá trị được gán với đỉnh ~v_i~ với mọi ~i = 1, 2, \dots, k~. Dữ liệu luôn đảm bảo độ dài của hai đường đi ~(A, B)~ và ~(C, D)~ là bằng nhau.

Yêu cầu: Sau mỗi truy vấn thứ ~i~, in ra số cách gán giá trị cho ~n~ đỉnh của cây, sao cho các giá trị này thỏa mãn toàn bộ điều kiện được đề ra từ ~i~ truy vấn đầu tiên của đề bài. Vì kết quả rất lớn nên cần phải được chia dư cho ~10^9 + 7~.

Input

Dòng đầu tiên gồm một số nguyên dương ~n~ (~1 \leq n \leq 2 \times 10^5~) — là số đỉnh của cây.

Dòng thứ hai gồm ~n - 1~ số nguyên ~p_2, p_3, ..., p_n~ (~1 \leq p_i \leq n~) với ~p_i~ là nút cha của đỉnh ~i~.

Trong ~n~ dòng tiếp theo, dòng thứ ~i~ gồm hai số nguyên ~L_i~ và ~R_i~ (~1 \leq L_i \leq R_i \leq 10^9~) — là khoảng giá trị có thể gán cho đỉnh thứ ~i~.

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

Trong ~m~ dòng cuối cùng là những truy vấn có dạng ~(A, B, C, D)~ (~1 \leq A, B, C, D \leq n~).

Output

Sau mỗi truy vấn, in ra đáp án của yêu cầu đề bài khi chia dư cho ~10^9 + 7~.

Scoring

Sample Input 1

5
1 1 3 3
1 7
2 5
4 9
2 8
5 10
3
4 5 3 2
4 3 1 3
1 5 4 1

Sample Output 1

4
4
1

Sample Input 2

8
4 1 3 8 4 3 6
1 10
3 9
2 8
5 7
4 9
1 6
1 6
3 8
5
3 7 8 6
6 2 2 6
1 1 1 1
8 6 6 8
4 1 3 2

Sample Output 2

45360
4320
4320
720
12

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