Tuấn đang chuẩn bị một trò chơi cho chương trình truyền hình như sau: Có một số người chơi được chọn và ngồi thành vòng tròn. Mỗi người có ~2~ lá cờ: một cờ xanh và một cờ đỏ. Khi có hiệu lệnh, tất cả mọi người sẽ đồng loạt phất lên đúng một lá cờ.

Một cấu hình được coi là chiến thắng nếu:

• Có đúng ~K~ người phất lá cờ màu xanh.

• Giữa hai người phất cờ xanh liên tiếp trong vòng tròn có ít nhất ~P~ người phất cờ đỏ.

Số người chơi có thể nằm trong khoảng từ ~L~ đến ~R~. Ban sản xuất muốn biết đối với mỗi trường hợp ~(L, R, K, P)~ có bao nhiêu cách chiến thắng, tính trên tất cả số người chơi ~n~ thỏa mãn ~L \le n \le R~, hai cách được coi là khác nhau nếu tồn tại một người phất lên cờ có màu khác.

Cho ~q~ câu hỏi, mỗi câu hỏi gồm bốn số nguyên ~L, R, K, P~. Với mỗi câu hỏi, hãy tính tổng số cấu hình chiến thắng xét trên tất cả ~n~ thỏa mãn ~L \le n \le R~.

Vì số lượng cấu hình có thể rất lớn, hãy in ra kết quả lấy dư với ~10^9+7~.

Input

Dòng đầu tiên ghi số nguyên ~q~ ~(1 \le q \le 10^5)~ — số lượng câu hỏi. Mỗi câu hỏi gồm ~4~ số ~L, R, K, P~ ~(1 \le L \le R \le 10^6, 0 \le K, P \le 10^6)~.

Output

Gồm ~q~ dòng, dòng thứ ~i~ in ra một số nguyên — số cách chiến thắng ứng với tình huống thứ ~i~, lấy dư theo mod ~10^9+7~.

Scoring

Sample Input 1

2
6 6 3 1
10 20 4 2

Sample Output 1

2
2277

Notes

Trong câu hỏi có ~6~ người chơi, ~3~ người phất cờ xanh và có ít nhất ~1~ cờ đỏ giữa mỗi người, có ~2~ cấu hình thỏa mãn với những người phất cờ xanh:

• Cấu hình ~1~: ~1, 3, 5~

• Cấu hình ~2~: ~2, 4, 6~

Cho một cây có ~n~ ~(n \le 50000)~ đỉnh, mỗi đỉnh có ghi một giá trị không âm ~a_i~ ~(a_i \le 255)~. Các đỉnh được đánh số từ ~1~ đến ~n~. Đỉnh số ~1~ là gốc.

Cho ~q~ truy vấn có dạng ~x, i~ ~(i \le n, x \le 255)~. Với mỗi truy vấn, đếm số lượng đường đi đi qua đỉnh ~i~ mà phép toán OR của các giá trị ghi trên các đỉnh thuộc đường đi là ~x~.

Input

Dòng đầu tiên ghi ~2~ số ~n~ và ~q~.

Dòng thứ ~2~ ghi ~n~ số nguyên không âm ~a_1, a_2, \dots, a_n~.

Dòng thứ ~3~ mô tả cây ghi ~n-1~ số nguyên ~b_2, b_3, \dots, b_n~ với số ~b_i~ là số thứ tự của đỉnh là cha của nút ~i~. ~(b_i < i)~

Mỗi dòng trong ~q~ dòng tiếp theo ghi một truy vấn, có dạng ~x, i~.

Output

Với mỗi truy vấn, ghi ra trên một dòng kết quả phải tìm.

Scoring

Sample Input 1

3 3
1 2 3
1 2
3 1
2 2
3 3

Sample Output 1

2
1
3

Cho một bảng ~n \times m~ cùng với ~k~ mũi tên song song với cạnh của bảng. Mỗi mũi tên sẽ đi qua một số ô của bảng và được biểu diễn bởi ~2~ ô ~(x_1, y_1), (x_2, y_2)~ lần lượt là ô bắt đầu và kết thúc của mũi tên. Xét một mũi tên bắt đầu tại ~(x_1, y_1)~ và kết thúc tại ~(x_2, y_2)~, ta định nghĩa:

• Mũi tên thuộc loại U nếu ~x_1>x_2, y_1=y_2~.

• Mũi tên thuộc loại R nếu ~x_1=x_2, y_1<y_2~.</p>

• Mũi tên thuộc loại D nếu ~x_1<x_2, y_1=y_2~.</p>

• Mũi tên thuộc loại L nếu ~x_1=x_2, y_1>y_2~.

Đề bài đảm bảo rằng cả ~k~ mũi tên đều thuộc ~1~ trong ~4~ loại trên. Dễ thấy mỗi mũi tên đều là một đoạn thẳng, mỗi mũi tên sẽ "chiếm" mọi ô nằm trên đoạn thẳng của mũi tên, đề bài đảm bảo rằng mỗi ô chỉ bị "chiếm" bởi tối đa ~1~ mũi tên.

Nhiệm vụ của bạn là phải bỏ được tất cả ~k~ mũi tên ra khỏi bảng sau đúng ~k~ lượt chơi. Tại mỗi lượt chơi bạn sẽ được bỏ đúng một mũi tên nếu mũi tên đó thỏa mãn điều kiện dưới đây (giả sử mũi tên bắt đầu tại ~(x_1, y_1)~ và kết thúc tại ~(x_2, y_2)~):

• Nếu mũi tên thuộc loại U, tất cả các ô ~(x, y)~ thỏa mãn ~x<x_2, y=y_2~ đều không được phép bị "chiếm".</p>

• Nếu mũi tên thuộc loại R, tất cả các ô ~(x, y)~ thỏa mãn ~x=x_2, y>y_2~ đều không được phép bị "chiếm".

• Nếu mũi tên thuộc loại D, tất cả các ô ~(x, y)~ thỏa mãn ~x>x_2, y=y_2~ đều không được phép bị "chiếm".

• Nếu mũi tên thuộc loại L, tất cả các ô ~(x, y)~ thỏa mãn ~x=x_2, y<y_2~ đều không được phép bị "chiếm".</p>

Input

Dòng đầu tiên lần lượt gồm ~3~ số nguyên dương ~n, m, k~ ~(1 \le n, m \le 2 \cdot 10^5, 1 \le k \le 10^5, 1 \le n \cdot m \le 2 \cdot 10^5)~, các số được cách nhau bởi một dấu cách.

Dòng thứ ~i~ trong ~k~ dòng tiếp theo gồm ~4~ số lần lượt là ~x_1, y_1, x_2, y_2~ được cách nhau bởi một dấu cách, biểu thị cho mũi tên có index ~i~, bắt đầu tại ~(x_1, y_1)~ và kết thúc tại ~(x_2, y_2)~ ~(1 \le x_1, x_2 \le n, 1 \le y_1, y_2 \le m, x_1=x_2~ hoặc ~y_1=y_2~, ~x_1 \ne x_2~ hoặc ~y_1 \ne y_2)~.

Output

In ra ~k~ số trên cùng một dòng, các số cách nhau bởi một dấu cách. Trong đó, số thứ ~i~ theo thứ tự từ trái sang là index của mũi tên được bỏ tại lượt chơi thứ ~i~. Đề bài đảm bảo rằng luôn có ít nhất một cách để loại bỏ được cả ~k~ mũi tên.

Scoring

Sample Input 1

2 2 2
1 1 1 2
2 1 2 2

Sample Output 1

1 2

Tàu thăm dò của Alice đang thực hiện một nhiệm vụ thu thập ~n~ mẫu vật. Mẫu vật thứ ~i~ ~(1 \le i \le n)~ có khối lượng ~m_i~ ~(i = 1, 2, \dots, n)~. Sau khi thu thập xong mẫu vật thứ ~i~, tàu thăm dò có thể thực hiện một trong hai hành động sau:

1. Quay về trung tâm cất để bảo quản các mẫu vật đã thu thập;

2. Tiếp tục di chuyển đến vị trí mẫu vật tiếp theo nếu còn, mẫu vật thứ ~(i + 1)~. Hành động này chỉ thực hiện được nếu tổng khối lượng các mẫu vật mà tàu thăm dò đang mang không vượt quá ~W~.

Cho biết ~d_i~ ~(1 \le i < n)~ là thời gian để tàu thăm dò di chuyển từ vị trí mẫu vật thứ ~i~ đến vị trí mẫu vật thứ ~(i + 1)~. Còn ~g_i~ ~(1 \le i \le n)~ là thời gian để tàu thăm dò di chuyển từ vị trí trung tâm đến vị trí mẫu vật thứ ~i~ cũng như là thời gian để tàu thăm dò di chuyển từ mẫu vật thứ ~i~ về trung tâm. Alice muốn điều khiển tàu thăm dò, xuất phát từ trung tâm đi thu thập ~n~ mẫu vật và cuối cùng kết thúc tại trung tâm với tổng thời gian nhỏ nhất. Giả thiết rằng, khi tàu thăm dò đã tới vị trí mẫu vật thì thời gian thu thập mẫu vật là không đáng kể.

Yêu cầu: Có ~Q~ câu hỏi, mỗi câu hỏi tương ứng với một giá trị ~W~, hãy lập trình tính thời gian nhỏ nhất để thu thập ~n~ mẫu vật theo yêu cầu.

Input

• Dòng đầu tiên ghi số nguyên dương ~n~ ~(n \le 10^5)~;

• Dòng tiếp theo chứa ~n~ số nguyên dương ~m_1, m_2, \dots, m_n~ ~(m_i \le 10^9)~;

• Dòng tiếp theo chứa ~n - 1~ số nguyên dương ~d_1, d_2, \dots, d_{n-1}~ ~(d_i \le 10^9)~;

• Dòng tiếp theo chứa ~n~ số nguyên dương ~g_1, g_2, \dots, g_n~ ~(g_i \le 10^9)~;

• Tiếp theo là số nguyên ~Q~ ~(Q \le 100)~;

• ~Q~ dòng cuối, mỗi dòng gồm một số nguyên ~W~ ~(W \le 10^9)~ mô tả một câu hỏi.

Output

Ghi ra ~Q~ dòng, mỗi dòng một số nguyên là câu trả lời tương ứng với câu hỏi trong dữ liệu vào.

Scoring

Sample Input 1

4
2 1 1 2
1 1 1
2 2 1 1
2
4
2

Sample Output 1

7
10

Thành phố công nghệ Cyberland đang vận hành một hệ thống truyền tin đặc biệt gồm ~N~ trạm phát tín hiệu được đánh số từ ~1~ đến ~N~. Các trạm được kết nối với nhau bởi ~M~ kênh truyền tin hai chiều, kênh truyền tin thứ ~i~ ~(1 \le i \le M)~ kết nối hai trạm ~u_i, v_i~, có độ trễ truyền tải là ~w_i~ và tần số hoạt động là ~f_i~.

Để gửi một gói tin từ trạm nguồn ~S~ đến trạm đích ~T~ ~(1 \le S, T \le N; S \ne T)~, gói tin có thể đi qua một dãy các kênh truyền tin nối tiếp nhau. Tổng thời gian mà gói tin cần để đi từ ~S~ đến ~T~ được tính bằng tổng các yếu tố sau:

• Độ trễ đường truyền: Là tổng độ trễ ~w~ của tất cả các kênh mà gói tin đi qua.

• Thời gian chuyển đổi tần số: Khi gói tin đi đến một trạm trung gian, nếu chuyển từ kênh có tần số ~f_x~ sang kênh có tần số ~f_y~ thì phải tốn thêm một khoảng thời gian bằng chênh lệch tần số giữa hai kênh, được tính bằng ~|f_x - f_y|~.

Yêu cầu: Biết rằng tại trạm nguồn ~S~ và trạm kết thúc ~T~ gói tin có thể ở bất kì tần số nào mà không tốn thêm thời gian chuyển đổi. Hãy tính thời gian ngắn nhất mà gói tin có thể được chuyển từ ~S~ đến ~T~.

Input

• Dòng đầu gồm bốn số nguyên dương ~N, M, S, T~ ~(N \le 2 \cdot 10^5; M \le 3 \cdot 10^5)~;

• ~M~ dòng tiếp theo, dòng thứ ~i~ gồm bốn số nguyên dương ~u_i, v_i, w_i, f_i~ mô tả một kênh truyền tin ~(1 \le u_i, v_i \le N; u_i \ne v_i; 1 \le w_i, f_i \le 10^9)~.

Output

Ghi ra một dòng chứa một số là thời gian ngắn nhất tìm được. Nếu không tồn tại đường đi từ ~S~ đến ~T~, ghi ra ~-1~.

Scoring

Sample Input 1

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

Sample Output 1

17

Notes

Gói tin có thể được truyền qua các trạm ~1 \rightarrow 2 \rightarrow 4~ qua các kênh ~1~ và ~2~.

Cho một cây gồm ~n~ đỉnh, các đỉnh được đánh số từ ~1~ tới ~n~, trong đó đỉnh ~1~ là đỉnh gốc. Mỗi cạnh của cây có trọng số là một số nguyên dương không quá ~10^9~. Ban đầu, mỗi đỉnh nhận một trong hai màu: đen hoặc trắng.

Có ~q~ thao tác cần được thực hiện một cách tuần tự, mỗi thao tác thuộc một trong ba loại sau:

1. Thao tác loại ~1~: Nhận vào một đỉnh ~u~, tiến hành đổi màu đỉnh ~u~, nếu đỉnh ~u~ đang là màu trắng thì đổi thành màu đen và ngược lại, nếu đỉnh ~u~ đang là màu đen thì đổi thành màu trắng;

2. Thao tác loại ~2~: Nhận vào một đỉnh ~u~, xét cây con gốc ~u~, xây dựng một đồ thị vô hướng đầy đủ, có trọng số, trong đó mỗi đỉnh của đồ thị này tương ứng với một đỉnh màu đen thuộc cây con gốc ~u~. Trọng số của cạnh nối hai đỉnh trên đồ thị đầy đủ này là khoảng cách giữa hai đỉnh màu đen tương ứng trên cây. Khoảng cách giữa hai đỉnh được tính bằng tổng trọng số các cạnh nằm trên đường đi đơn duy nhất giữa hai đỉnh trên cây. Trên đồ thị đầy đủ vừa xây dựng, tiến hành tìm một chu trình có độ dài nhỏ nhất. Chu trình xuất phát từ một đỉnh bất kì, đi qua tất cả các đỉnh còn lại, mỗi đỉnh qua đúng một lần và quay về đỉnh xuất phát. Độ dài chu trình được tính bằng tổng trọng số của các cạnh thuộc chu trình;

3. Thao tác loại ~3~: Nhận vào một đỉnh ~u~, xét cây con gốc ~u~, xây dựng một đồ thị vô hướng đầy đủ, có trọng số tương tự như trong thao tác loại ~2~. Trên đồ thị đầy đủ vừa xây dựng, tiến hành tìm một đường đi có độ dài nhỏ nhất. Đường đi xuất phát từ một đỉnh bất kì, đi qua tất cả các đỉnh còn lại, mỗi đỉnh đi qua đúng một lần. Độ dài của đường đi được tính bằng tổng trọng số của các cạnh thuộc đường đi.

Yêu cầu: Hãy viết một chương trình xử lý ~q~ thao tác được cho.

Input

• Dòng thứ nhất chứa một số nguyên dương ~n~ ~(n \le 2 \cdot 10^5)~;

• Dòng thứ hai chứa một xâu nhị phân độ dài ~n~ trong đó kí tự thứ ~i~ là 1 nếu ban đầu đỉnh ~i~ có màu đen, ngược lại kí tự thứ ~i~ là 0;

• Tiếp theo là ~n - 1~ dòng, mỗi dòng chứa ba số nguyên dương ~u, v, c~, mô tả có một cạnh nối giữa hai đỉnh ~u, v~ trên cây với trọng số ~c~. Dữ liệu bảo đảm ~n - 1~ cạnh này tạo thành một cây;

• Dòng tiếp theo chứa một số nguyên dương ~q~ ~(q \le 2 \cdot 10^5)~;

• Tiếp theo là ~q~ dòng, mỗi dòng chứa hai số nguyên dương ~t~ và ~u~ ~(1 \le u \le n)~ mô tả một thao tác, trong đó ~t = 1~ hoặc ~t = 2~ hoặc ~t = 3~ tương ứng là loại thao tác loại ~1~ hoặc loại ~2~ hoặc loại ~3~ và ~u~ là đỉnh được cho trong thao tác hiện tại. Dữ liệu bảo đảm đối với thao tác loại ~2~ và loại ~3~ có ít nhất một đỉnh màu đen thuộc cây con gốc ~u~.

Hai số liên tiếp trên cùng một dòng được ghi cách nhau bởi dấu cách.

Output

Ghi ra một số dòng, mỗi dòng là kết quả của các thao tác loại ~2~ hoặc loại ~3~ theo đúng thứ tự trong dữ liệu vào.

Scoring

Sample Input 1

6
001110
1 2 1
1 4 2
4 6 3
2 5 2
2 3 4
9
2 1
1 4
2 1
1 6
2 1
2 2
1 4
2 2
2 5

Sample Output 1

18
12
24
12
12
0

Sample Input 2

6
001110
1 2 1
1 4 2
4 6 3
2 5 2
2 3 4
9
3 1
1 4
3 1
1 6
3 1
3 2
1 4
3 2
3 5

Sample Output 2

11
6
14
6
6
0