Cho một mảng ~a~ gồm ~n~ số nguyên dương ~a_1, a_2, ..., a_n~. Gọi trọng số của mảng là tổng của các (~a_i + a_j~) ~(1 \le i \le j \le n~) thỏa mãn ~a_i + a_j~ lẻ. Bạn hãy tìm trọng số của mảng ~a~.

Vì trọng số có thể rất lớn, hãy in ra kết quả ~\mod 10^9+7~.

Input

Dòng đầu tiên gồm số nguyên dương ~n~ (~1 \le n \le 10^6~).

Dòng thứ hai gồm ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ (~1 \le a_i \le 10^9~).

Output

Gồm một dòng duy nhất là trọng số của mảng ~a~ ~\mod 10^9+7~.

Scoring

Sample Input 1

5
3 7 2 1 9

Sample Output 1

28

Sample Input 2

5
6 8 2 2 10

Sample Output 2

0

Notes

Trong test ví dụ đầu tiên, các cặp số thỏa mãn là (~1, 3~), (~2, 3~), (~3, 4~), (~3, 5~). Vậy trọng số là ~(a_1 + a_3) + (a_2 + a_3) + (a_3 + a_4) + (a_3 + a_5)~ = ~3 + 2 + 7 + 2 + 2 + 1 + 2 + 9 = 28~.

Trong test ví dụ thứ hai, không có bất kì cặp nào có tổng là số lẻ nên trọng số của mảng ~[6, 8, 2, 2, 10]~ là ~0~.

Cho bốn số nguyên dương ~N~, ~A~, ~B~, ~C~. Đếm số lượng ước nguyên dương của ~N~ chia hết ít nhất hai trong ba số ~A~, ~B~, ~C~.

Input

Gồm ~4~ số nguyên dương ~N~, ~A~, ~B~, ~C~ ~(A, B, C, N \leq 10^{18})~.

Output

Ghi ra kết quả tìm được.

Scoring

Sample Input 1

100 2 3 5

Sample Output 1

4

Sample Input 2

20 1 2 5

Sample Output 2

5

Notes

Ở ví dụ 1, ta sẽ có những số thoả mãn là ~10, 20, 50, 100~.

Ở ví dụ 2, ta sẽ có những số thoả mãn là ~2, 4, 5, 10, 20~.

Cho một dãy các ô màu gồm ~n~ ô, mỗi ô trên dãy được gán một giá trị ~a_i~ và có màu ~c_i~. Có ~q~ truy vấn:

• 1 col x (~1 \le col\le 10^5,1\le x \le 10^8~): Những ô có màu khác col sẽ được tăng giá trị lên một lượng ~x~.

• 2 col y (~1 \le col\le10^5,1\le y \le 10^{15}~): Xét dãy gồm các ô có màu col (thứ tự các ô trong dãy này là thứ tự các ô trong dãy ban đầu), tìm độ dài ~l~ lớn nhất sao cho tổng của ~l~ phần tử đầu tiên trong dãy này có giá trị không lớn hơn ~y~.

Input

Dòng đầu tiên gồm một số nguyên dương ~n~ (~1 \le n \le 2 \cdot 10^5~) — số lượng phần tử trong dãy.

Dòng thứ ~i~ trong ~n~ dòng tiếp theo, mỗi dòng gồm hai số nguyên dương ~a_i~ và ~c_i~ (~1 \le a_i\le 10^8,1\le c_i \le 10^5~) — lần lượt là giá trị và màu của ô thứ ~i~.

Dòng thứ ~n+2~ gồm một số nguyên dương ~q~ (~1 \le q \le 2 \cdot 10^5~) — số lượng truy vấn cần thực hiện.

Mỗi dòng trong ~q~ dòng tiếp theo chứa 1 trong 2 loại truy vấn trên.

Output

Với mỗi truy vấn thuộc loại 2, in ra một số nguyên ~l~ sao cho tổng của ~l~ phần tử đầu tiên trong dãy oo có màu ~i~ có giá trị không lớn hơn ~y~.

Scoring

Sample Input 1

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

Sample Output 1

2
1
1

Notes

Ban đầu, dãy ô của ta sẽ có các giá trị sau:

Ở truy vấn 1, chỉ có 2 ô đầu tiên trong dãy là có màu ~2~, tổng giá trị của 2 ô này ~1+3=4 \le 6~ nên độ dài ~l~ lớn nhất của truy vấn là ~2~.

Sau truy vấn 2, dãy ô hiện tại là:

Ở truy vấn 3, xét dãy các ô có màu ~1~, ta không thể lấy cùng lúc 2 ô ~3~ và ~4~ hoặc nhiều hơn vì ~2+5 = 7 > 6~, vì thế đáp án của truy vấn này là ~1~.

Ở truy vấn cuối cùng, ta cũng không thể lấy hết 2 ô có màu ~2~ vì ~5+7 = 12 > 6~, vì thế đáp án là ~1~.

Có ~n + m + 1~ ứng cử viên xin việc tại một công ty. Ứng cử viên thứ ~i~ có kỹ năng code là ~a_i~ và kỹ năng test là ~b_i~. Bạn cần chọn ra ~n~ coder và ~m~ tester sao cho tổng hiệu suất của cả công ty là lớn nhất. Mỗi ứng viên sẽ đóng góp vào hiệu suất tổng là ~a_i~ nếu như được chọn làm coder, ~b_i~ nếu được chọn làm tester, và ~0~ nếu họ không được chọn vào công ty. Để thấy được tương quan giữa tất cả các khả năng chọn, bạn cần in ra tổng hiệu suất lớn nhất khi ứng cử viên thứ ~i~ bị loại.

Input

Dòng đầu tiên chứa số nguyên dương ~t~ thể hiện số test (~1 \le t \le 5 \cdot 10^5~).

~t~ nhóm dòng sau có dạng:

• Dòng đầu tiên chứa hai số nguyên không âm ~n~ và ~m~ thể hiện số coder và tester cần tuyển (~0 \le n,m \le 5 \cdot 10^5~; ~2 \le n + m + 1 \le 5 \cdot 10^5~);

• Dòng tiếp theo chứa ~n + m + 1~ số nguyên dương ~a_1,a_2,...,a_{n + m + 1}~(~1 \le a_i \le 10^9~), với ~a_i~ là hiệu suất của người thứ ~i~ nếu được chọn làm coder.

• Dòng cuối cùng chứa ~n + m + 1~ số nguyên dương ~b_1,b_2,...,b_{n+m+1}~ (~1 \le b_i \le 10^9~), với ~b_i~ là hiệu suất của người thứ ~i~ nếu được chọn làm tester.

Dữ liệu vào đảm bảo tổng các (~n + m + 1~) trong tất cả các test không vượt quá ~5 \cdot 10^5~.

Output

Với mỗi test case: ghi ra ~n + m + 1~ số nguyên trên một dòng, trong đó số nguyên thứ ~i~ là hiệu suất tối đa của công ty nếu người thứ ~i~ không được chọn vào công ty.

Scoring

Đặt ~N~ = ~\sum n + m + 1~ trong tất cả các testcases.

Sample Input 1

1
1 1
3 2 3
1 2 3

Sample Output 1

5 6 5

Sample Input 2

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

Sample Output 2

1 2 
5 6 9 
9 12 11 12 
13 13 14 13 16

Notes

Giải thích bộ test ví dụ đầu tiên:

Nếu người thứ ~1~ nghỉ, ta có thể cho người thứ ~2~ làm tester, người còn lại làm coder. Khi đó tổng hiệu suất là ~2 + 3 = 5~

Nếu người thứ ~2~ nghỉ, ta có thể cho người thứ ~3~ làm tester, người còn lại làm coder. Khi đó tổng hiệu suất là ~3 + 3 = 6~

Nếu người thứ ~3~ nghỉ, ta có thể cho người thứ ~2~ làm tester, người còn lại làm coder. Khi đó tổng hiệu suất là ~2 + 3 = 5~

Shine đang ôn luyện để chuẩn bị cho kì thi ICPC sắp tới, chủ đề ôn luyện hôm nay của Shine là các bài liên quan tới mảng và các truy vấn. Thấy bạn mình đang học như vậy, QioCas liền đánh đố một bài toán cho bạn mình giải quyết, bài toán được phát biểu như sau:

• Cho một mảng gồm ~N~ phần tử ~a_1, a_2, \dots, a_N~. Ta có ~Q~ truy vấn có dạng l r x với ý nghĩa ~a_i = max(a_i, x)~ với mọi ~l \le i \le r~.

Nếu bài toán chỉ dừng lại ở việc sau mỗi truy vấn ta cần in ra tổng của các phần tử trong mảng (hay ~\sum_{i = 1}^N a_i~) thì bài toán lại quá dễ để giải quyết. Do đó ở bài toán này, với truy vấn thứ ~i~, QioCas muốn biết tổng của các phần tử trong mảng khi thực hiện mỗi truy vấn thứ ~i~ và tổng của các phần tử trong mảng khi thực hiện tất cả truy vấn ngoại trừ truy vấn thứ ~i~.

Shine rất giỏi nên nhìn phát ra đã luôn cách làm tuy nhiên do rất lười phải cài một bài toán dễ như vậy nên Shine muốn nhờ các bạn giúp đỡ Shine. Các bạn hãy giúp Shine giải quyết bài toán nhé.

Input

• Dòng đầu tiên gồm ~2~ số nguyên ~N, Q\ (1 \le N, Q \le 2 \cdot 10^5)~.

• Dòng thứ ~2~ gồm ~N~ số nguyên ~a_1, a_2, \dots, a_N\ (1 \le a_i \le 2 \cdot 10^9)~

• ~Q~ dòng tiếp theo có dạng l r x ~(1 \le l \le r \le N, 1 \le x \le 2 \cdot 10^9)~

Output

• Gồm ~Q~ dòng, mỗi dòng gồm ~2~ số nguyên là kết quả bài toán.

Scoring

Sample Input 1

5 4
1 2 3 4 5
1 3 3
4 4 4
2 3 4
5 5 10

Sample Output 1

18 23
15 25
18 23
20 20

Notes

Mảng khi thực hiện mỗi truy vấn ~1~, ~a = [3, 3, 3, 4, 5]~.

Mảng khi thực hiện tất cả truy vấn trừ truy vấn ~1~, ~a = [1, 4, 4, 4, 10]~.

Mảng khi thực hiện mỗi truy vấn ~2~, ~a = [1, 2, 3, 4, 5]~.

Mảng khi thực hiện tất cả truy vấn trừ truy vấn ~2~, ~a = [3, 4, 4, 4, 10]~.

Mảng khi thực hiện mỗi truy vấn ~3~, ~a = [1, 4, 4, 4, 5]~.

Mảng khi thực hiện tất cả truy vấn trừ truy vấn ~3~, ~a = [3, 3, 3, 4, 10]~.

~\cdots~