Xét một dãy ~A~ có ~N~ phần tử ~A_1, A_2, ..., A_N~. Dãy ~B~ được xây dựng như sau: Phần tử ~B_i~ có giá trị là trung bình cộng của ~i~ phần tử đầu tiên trong dãy ~A~.

Cho trước dãy ~B~, hãy tìm dãy ~A~.

Input

• Dòng đầu tiên chứa số nguyên dương ~N~ ~(1 \le N \le 10^6)~;
• Dòng thứ hai chứa ~N~ số nguyên ~B_1, B_2, ..., B_N~ ~(|B_i| \le 10^6)~.

Output

~N~ số nguyên tương ứng với ~N~ phần tử của dãy ~A~.

Scoring

• Subtask ~1 \ (50\%)~: ~N \le 5000~;
• Subtask ~2 \ (50\%)~: Không có ràng buộc gì thêm.

Ví dụ

Input

5
15 20 5 15 30

Output

15 25 -25 45 90

Xâu đẹp là xâu có nhiều nhất một ký tự có số lần xuất hiện là lẻ. Cho xâu ~S~ có độ dài ~n~ chỉ gồm các chữ cái thường ~S_0S_1 \dots S_{n-1}~. Một đoạn ~(i,j)~ của xâu ~S~ là xâu: ~S_iS_{i+1} \dots S_j~.

Yêu cầu: Với mỗi đoạn ~(i,j)~, hãy xác định số ký tự ít nhất cần thay đổi để đoạn ~(i,j)~ thành xâu đẹp.

Input

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~Q~ (~n,Q \leq 10^6~) - lần lượt là độ dài xâu và số lượng truy vấn.
• Dòng thứ hai chứa xâu ~S~.
• ~Q~ dòng tiếp theo, mỗi dòng chứa hai số ~i~ và ~j~ (~0 \leq i \leq j \leq n - 1~) - xác định một đoạn trong xâu ~S~ cần biến đổi.

Output

Gồm ~Q~ dòng lần lượt là kết quả của ~Q~ truy vấn.

Sample Test

Note

• Đoạn [~1,3~] của xâu ~S~ là "bca". Có thể thay đổi kí tự 'c' thành kí tự 'b', ta được xâu "bba" thỏa mãn.
• Đoạn [~2,7~] của xâu ~S~ là "caacba". Có thể thay đổi kí tự 'b' thành kí tự 'a', ta được xâu "caacaa" thỏa mãn.
• Đoạn [~1,6~] của xâu ~S~ là "bcaacb". Đây là xâu đẹp rồi nên không cần biến đổi.

dangheo đang bị làm khó bởi một bài toán cấp 2 và cần các bạn lớp 10 tin trợ giúp.

Bài toán như sau:

Trọng số của bộ ba có thứ tự ~(x, y, z)~ bằng ~(x + y) \times (y + z)~ nếu ~\max(x, z) \le y~; hoặc bằng ~0~ nếu ~\max(x, z) > y~.

Cho ba dãy số nguyên dương ~a=a_1, a_2, ..., a_n~; ~b = b_1, b_2, ..., b_m~; ~c=c_1, c_2, ..., c_q~.

Hãy tính tổng trọng số của tất cả các bộ ba ~(a_i, b_j , c_k)~ với ~1 ≤ i ≤ n, 1 ≤ j ≤ m, 1 ≤ k ≤ q~.

Các bạn hãy giúp anh ta giải bài toán trên nhé.

Input

• Dòng đầu tiên chứa ba số nguyên dương ~n, m, q~ ~(n,m,q ≤ 10^5) ~;
• Dòng thứ hai chứa ~n~ số nguyên dương: ~a_1, a_2, ..., a_n~ ~(a_i \le 10^9)~;
• Dòng thứ ba chứa ~m~ số nguyên dương: ~b_1, b_2, ..., b_m~ ~(b_i \le 10^9)~;
• Dòng thứ tư chứa ~q~ số nguyên dương: ~c_1, c_2, ..., c_q~ ~(c_i \le 10^9)~.

Output

Ghi một số nguyên là tổng trọng số sau khi chia lấy dư cho ~10^9+7~.

Sample Input

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

Sample Output

2300

MrTee là một người rất thích tiểu thuyết tu tiên vì vậy anh ta cho bạn bài toán sau

Anh ta có một cộng đồng tu sĩ ~n~ người, người thứ ~i~ tu luyện công pháp ~a_i~

Sức mạnh của 1 nhóm các tu sĩ liên tiếp từ ~l~ đến ~r~ là số cặp tu sĩ (~a_l~, ~a_r~) sao cho ~(l < r)~ và công pháp 2 người tu luyện là giống nhau.

Hãy giúp anh ta tính độ mạnh của mọi nhóm tu sĩ liên tiếp trong cộng đồng.

INPUT

• Dòng đầu tiên là số ~n~.
• Dòng thứ hai là ~n~ số nguyên dương ~a_i~.

OUTPUT

• In ra độ mạnh của mọi nhóm tu sĩ liên tiếp trong cộng đồng

Ví dụ

Input 1:

5
2 1 3 1 2

Output 1:

5

Input 2:

6
4 2 3 4 5 2

Output 2:

5

Giới hạn

• Trong mọi test ~a_i \le 10^9~
• Subtask 1 ~(50\%)~: ~n \le 1000~
• Subtask 2 ~(50\%)~: ~n \le 10^5~

Hôm nay Sủi shop được ~n~ bài để cho vào chên ninh contest. Mỗi bài có 2 chỉ số ~a_i~ là chủ đề của bài và ~b_i~ là độ khó, tất cả các bài đều khác nhau, nghĩa là không có 2 bài bất kì nào đều có cùng chủ đề và độ khó. Sủi cần chọn ra 3 bài thỏa mãn ít nhất 1 trong 2 điều kiện sau:

• Chủ đề của 3 bài khác nhau.
• Độ khó của 3 bài khác nhau.

Hãy đếm số cách để Sủi có thể chọn ra 3 bài như vậy.

Input

• Dòng đầu tiên gồm số nguyên không âm ~3 \le n \le 10^5~.
• ~n~ dòng tiếp theo mỗi dòng gồm 2 số ~1 \le a_i, b_i \le n~.

Output

• Hãy in ra số cách chọn.

Sample Test

Input:

4
2 4
3 4
2 1
1 3

Output:

3

Input:

5
1 5
2 4
3 3
4 2
5 1

Output:

10

Cho ba số nguyên dương ~c~, ~d~, ~x~. Bạn cần phải tìm số cặp ~(a,b)~ thỏa mãn ~c*lcm(a,b) - d*gcd(a,b) = x~. Ở đây, ~lcm(a,b)~ là bội chung nhỏ nhất của ~(a,b)~, ~gcd(a,b)~ là ước chung lớn nhất của ~(a,b)~.

Input

• Dòng đầu gồm số nguyên dương ~t~ ~(t \le 10^4)~ là số lượng test case.
• ~t~ dòng sau, mỗi dòng gồm ba số nguyên dương ~c~, ~d~, ~x~ miêu tả test case. ~(1 \le c,d,x \le 10^7)~

Output

• Với mỗi test case, in ra số lượng cặp ~(a,b)~ thỏa mãn.

Sample Test

Input

4
1 1 3
4 2 6
3 3 7
2 7 25

Output

4
3
0
8

Giải thích: Ở test case thứ nhất, có ~4~ cặp thỏa mãn là ~(1,4), (4,1), (3,6), (6,3)~

Phát minh mới nhất của của Nitori là một chiếc máy bay ném bom điều khiển từ xa. Ba nàng tiên ánh sáng đã đặt một chiếc cho kế hoạch khủng bố đền Hakurei.

Dĩ nhiên để máy bay có thể hoạt động thì cần có pin. Mỗi cục pin có 3 thông tin: ~e_i, w_i, c_i~ lần lượt và mức năng lượng, khối lượng và giá thành. Thời gian bay của máy bay được xác định bằng công thức: ~E\over{W}~ trong đó ~E~ là tổng mức năng lượng và ~W~ là tổng khối lượng của tất cả pin và khối lượng của máy bay.

Để đảm bảo kế hoạch thành công, máy bay cần hoạt động lâu nhất có thể. Ba nàng tiên có ngân sách ~b~ và khối lượng của máy bay là ~w~, hãy giúp họ chọn pin sao cho thời gian bay là lâu nhất!

Input:

• Dòng đầu chứa số ~n,b,w (1≤n×b≤10^5,1≤w≤1000)~.

• ~n~ dòng tiếp theo mỗi dòng chứa ba số ~e_i,w_i,c_i (0≤e_i,w_i≤1000,0≤c_i≤b)~ là mức năng lượng, khối lượng và giá thành của cục pin thứ ~i~.

Output:

• In ra tổng thời gian bay của máy bay, sai số không quá ~10^{-3}~.

Sample Test:

Input:

10 1000 20
40 40 40
1 1 1
70 30 60
100 20 700
80 50 200
30 1 200
100 100 1
20 1 500
30 20 100
70 50 100

Output:

3.1707

Giới hạn

• 25% số điểm ~n≤20~.
• 25% số điểm ~w_i=0~.
• 25% số điểm ~c_1=c_2=...=c_n~.
• 25% số điểm không có ràng buộc gì thêm.

Nhân dịp sinh nhật Alice được cha mẹ tặng ~n~ bộ xếp chữ, được đánh số từ ~1~ đến ~n~. Bộ xếp chữ thứ ~i~ có ~a_i~ chữ cái "A" và ~b_i~ chữ cái "B". Alice đưa ra một trò chơi như sau: chọn ra hai bộ xếp chữ trong ~n~ bộ, nhóm các chữ cái "A" và chữ cái "B" của hai bộ đã chọn, rồi xếp tất cả chúng thành một hàng ngang. Ví dụ là có ~3~ chữ cái "A" và ~4~ chữ cái "B" thì "ABABABB" và "BBBBAAA" là một trong các cách xếp hợp lệ, và "AAAABBB" là một trong các cách xếp không hợp lệ.

Alice muốn biết: có bao nhiêu cách chọn bộ và xếp chữ như vậy? Hai cách là khác nhau khi hai bộ xếp chữ được chọn ở hai cách là khác nhau, hoặc cách xếp nhận được là khác nhau.

Vì số cách chọn và xếp có thể rất lớn, bạn hãy in ra số cách tìm được chia lấy dư cho ~10^9+7~.

Input

Dòng đầu chứa số nguyên ~n~ (~2 \le n \le 2 \times 10^5~).

~n~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~a_i~, ~b_i~ (~1 \le a_i, b_i \le 2000~).

Output

In ra một số nguyên duy nhất là số cách chọn bộ và xếp chữ tìm được, modulo ~10^9+7~.

Scoring

• Subtask 1 (~20~ điểm): ~n \le 5~; ~a_i, b_i \le 10~.
• Subtask 2 (~20~ điểm): ~n \le 2000~.
• Subtask 3 (~30~ điểm): ~a_i, b_i \le 50~.
• Subtask 4 (~30~ điểm): Không có ràng buộc gì thêm.

Example

Input

2
1 1
2 1

Output

10