Theo truyền thuyết, vua Sêram rất khâm phục và đã tặng thưởng cho nhà thông thái Sêta vì đã sáng tạo ra cờ vua. Phần thưởng mà Sêta mong muốn là tất cả các hạt lúa mì đặt trên bàn cờ theo quy tắc sau: Ô thứ nhất đặt một hạt, ô thứ hai đặt 2 hạt, ô thứ ba đặt 4 hạt, … , tiếp tục theo quy luật ô sau có số hạt gấp đôi số hạt của ô trước, cho tới khi đặt đến ô thứ 64 trên bàn cờ vua. Rất thích thú với truyền thuyết này, Long và Vân cùng nhau giải quyết bài toán sau:

Xét một bảng số kích thước ~m*n~, các hàng được đánh số từ 1 đến ~m~ từ trên xuống dưới, các cột được đánh số từ 1 đến ~n~ từ trái sang phải. Ô nằm giao giữa hàng ~i~ và cột ~j~ được gọi là ô ~(i,j)~. Với một số nguyên dương ~k~ ~(k \le 10)~, lần lượt điền các số vào các ô của bảng theo nguyên tắc sau:

• Bắt đầu điền từ ô ~(1,1)~ ghi số ~1~;
• Điền lần lượt từng ô từ trên xuống dưới, từ trái qua phải. Ô tiếp theo điền giá trị gấp ~k~ lần giá trị điền ô trước.

Với bộ 4 số nguyên dương ~(x,y,u,v)~ thỏa mãn ~1≤x≤u≤m~ và ~1≤y≤v≤n~, hai bạn Long và Vân muốn tính tổng các số nằm trong các ô ~(i,j)~ mà ~x≤i≤u~ và ~y≤j≤v~.

Yêu cầu: Cho ~7~ số nguyên dương ~m,n,k,x,y,u,v~, hãy tính tổng các số nằm trong các ô ~(i,j)~ mà ~x≤i≤u~ và ~y≤j≤v~ của bảng số được điền theo quy tắc trên.

Input

• Một dòng chứa 7 số nguyên dương ~m,n,k,x,y,u,v~. ~(1 \le n,m \le 10^9)~

Output

• Một dòng chứa một số là phần dư của phép chia tổng các số được tính chia cho ~111539768~.

Sample Test

Input:

4 4 2 1 2 2 3

Output:

102

Cho dãy số nguyên ~a_1, a_2, \ldots, a_n~, tính ~\sum_{1\le l\le r\le n} \max(a_l, a_{l + 1}, \ldots, a_{r})\times (r - l + 1)~.

Input

• Dòng đầu chứa số nguyên dương ~n~ ~(n \le 10^5)~.
• Dòng thứ hai chứa ~n~ số ~a_1, a_2, \ldots, a_n~ ~(1\le a_i\le 1000)~.

Output

• Ghi ra tổng tính được.

Example

Input

5
3 4 2 1 3

Output

124

Có ~n~ đồ vật được đánh số từ ~1~ tới ~n~. Đồ vật thứ ~i~ có trọng lượng là ~w_i~ và có giá trị là ~v_i~.

Bạn cần trả lời ~q~ truy vấn, truy vấn thứ ~i~ gồm ba số nguyên ~l_i~, ~r_i~ , ~W_i~, hỏi rằng giả sử nếu chỉ xét các đồ vật trong đoạn ~[l_i,r_i]~, thì với tổng trọng lượng tối đa là ~W_i~, bạn có thể thu được tổng giá trị lớn nhất là bao nhiêu? Biết rằng mỗi đồ vật trong đoạn đó bạn chỉ có thể lấy tối đa một lần.

Input

• Dòng đầu gồm số nguyên dương ~n~ ~(1 \le n \le 10^4)~
• ~n~ dòng sau, dòng thứ ~i~ gồm hai số nguyên dương miêu tả đồ vật thứ ~i~: ~w_i~ và ~c_i~ ~(1 \le w_i \le 100, c_i \le 10^4)~.
• Dòng tiếp theo gồm số nguyên dương ~q~ miêu tả số truy vấn ~(q \le 10^5)~.
• ~q~ dòng sau, dòng thứ ~i~ gồm ba số nguyên dương miêu tả truy vấn thứ ~i~: ~l_i~, ~r_i~, ~W_i~ ~(1 \le l_i \le r_i \le n; 1 \le W_i \le 100)~.

Output

• Gồm ~q~ dòng, dòng thứ ~i~ là kết quả của truy vấn thứ ~i~.

Subtask

• Subtask ~1~: ~r-l \le 100~ ~(40\%)~
• Subtask ~2~: ~q \le 10^4~ ~(30\%)~
• Subtask ~3~: Không giới hạn gì thêm ~(30\%)~

Example

Sample Input 1

4
2 15
2 20
4 36
1 4
3
1 2 4
1 4 7
3 4 2

Sample Output 1

35
60
4

Cho một tập các điểm trên mặt phẳng tọa độ Oxy, nhiệm vụ của bạn là tìm khoảng cách Euclid ngắn nhất giữa ~2~ điểm bất kì.

Một khoảng cách Euclid giữa ~2~ điểm ~(x_1, y_1)~ và ~(x_2, y_2)~ là ~\sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}~.

Input

• Dòng đầu tiên chứa một số nguyên ~n~: số lượng điểm.
• Sau đó, bao gồm ~n~ dòng chứa thông tin về các điểm. Mỗi dòng chứa 2 số nguyên ~x~ và ~y~.
• Đề đảm bảo không tồn tại một cặp điểm bất kì trùng vị strí nhau.

Output

• In ra một số nguyên duy nhất là ~d^2~ trong đó ~d~ là khoảng cách Euclid ngắn nhất (để đảm bảo rằng kết quả chắc chắn là một số nguyên).

Constraints

• ~2 \leq n \leq 2 \cdot 10^5~
• ~-10^9 \leq x, y \leq 10^9~

Example

Input

4 
2 1
4 4
1 2 
6 3

Output

2

Cho bảng số ~A~ kích thước ~n*m~, các hàng được đánh số từ trên xuống dưới, các cột được đánh số từ trái sang phải. Ô giao giữa hàng ~i~ cột ~j~ là ô ~(i,j)~ và có giá trị ~a(i,j)~. Hai ô có thể di chuyển tới nhau nếu chúng chung cạnh. Một đường đi sẽ bao gồm các ô sao cho hai ô liên tiếp chung cạnh, và nó có giá trị bằng tổng giá trị các ô trên đường đi.

Cho ~q~ truy vấn, truy vấn thứ ~i~ sẽ cho bạn hai ô ~(x,y)~ và ~(u,v)~ trong bảng. Kết quả của một truy vấn chính là giá trị của đường đi có trọng số nhỏ nhất giữa hai ô đã cho. Hãy in ra kết quả của từng truy vấn.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n,m~, ~(1 \le n \le 7; 1 \le m \le 5000)~.
• Tiếp theo là ~n~ dòng, mỗi dòng gồm ~m~ số nguyên không âm miêu tả bảng ~A~ ~n*m~, ~(0 \le a(i,j) \le 10^5)~ .
• Dòng tiếp theo là số nguyên dương ~q~, ~(q \le 30000)~.
• Ở ~q~ dòng tiếp theo mỗi dòng miêu tả một truy vấn, truy vấn thứ ~i~ có dạng ~x_i, y_i, u_i, v_i~ miêu tả ô ~(x_i,y_i)~ và ~(u_i,v_i)~. (Các ô đều nằm trong bảng).

Output

• In ra ~q~ dòng là kết quả của ~q~ truy vấn.

Sample Test

Input:

2 3
1 2 3
4 1 1
2
1 1 2 3
1 3 2 1

Output:

5
9

Ban đầu, Fran có một mảng rỗng ~a~. Fran thực hiện ~n~ truy vấn, mỗi truy vấn có dạng ~x~ — anh ta thêm ~x~ phần tử vào cuối mảng ~a~. Sau mỗi truy vấn, Fran muốn xác định phần tử nhỏ nhất trong mảng ~a~, và khi đã xác định được, anh ta sẽ loại bỏ phần tử đó khỏi mảng mà không làm thay đổi chỉ số của các phần tử còn lại.

Yêu cầu: Hãy xác định chỉ số của phần tử nhỏ nhất trong mảng sau mỗi truy vấn, bằng cách hỏi so sánh giữa các chỉ số.

Interaction

Đây là một bài toán tương tác. Nhiệm vụ của bạn là viết một chương trình tương tác để xử lý các truy vấn.

• Dòng đầu tiên chứa số nguyên ~n~ ~(1 \le n \le 40)~ — số lượng truy vấn.
• Sau đó là ~n~ dòng, mỗi dòng chứa một số nguyên ~x_i~ ~(1 \le x_i \le 2000)~, biểu thị số phần tử được thêm vào mảng trong truy vấn thứ ~i~.

Sau mỗi truy vấn, bạn có thể gửi các câu hỏi dạng:

? i j

Với điều kiện ~i \ne j~, và cả hai chỉ số ~i~, ~j~ phải là các chỉ số của phần tử hiện chưa bị loại bỏ.

Trình chấm sẽ phản hồi:

• ~0~ nếu ~a_i < a_j~
• ~1~ nếu ~a_i > a_j~

Sau khi xác định được phần tử nhỏ nhất hiện tại, bạn phải in ra:

! x 1

Trong đó ~x~ là chỉ số của phần tử nhỏ nhất hiện tại trong mảng ~a~ (chỉ số này chưa bị loại bỏ trước đó). Phần tử tại chỉ số ~x~ sẽ được loại bỏ ngay lập tức khỏi mảng.

Sau đó truy vấn tiếp theo sẽ bắt đầu. Sau truy vấn cuối cùng, chương trình kết thúc.

Tổng số phần tử được thêm vào qua tất cả các truy vấn sẽ không vượt quá ~2000~.

Scoring

Chương trình của bạn sẽ được chấm điểm dựa trên tổng số câu hỏi bạn đã hỏi. Gọi ~q~ là tổng số câu hỏi, điểm được tính như sau:

• Nếu ~q \le 2700~: được 120 điểm
• Nếu ~2700 < q \le 7000~: được 75 điểm
• Nếu ~7000 < q \le 20000~: được 35 điểm
• Nếu ~20000 < q \le 80000~: được 15 điểm

Sample Input 1

3
3
1
0
0
1
1
1
0

Sample Output 1

? 1 2
? 1 3
? 2 3
! 2 1
? 1 4
! 4 1
? 1 5
! 1 1

Note

Dãy là ~3, 2, 4, 1, 5~

Có ~N+2~ thị trấn xếp thẳng hàng. Các thị trấn được đánh số từ ~0~ đến ~N+1~ từ trái sang phải. Mỗi thị trấn ~i~ ~(1 \leq i \leq N)~ có một nơi trú ẩn có thể chứa tối đa ~A_i~ người.

Hiện tại, có ~S~ người đang di chuyển cùng nhau và ghé thăm một trong các thị trấn. Tuy nhiên, bạn không biết họ đang ghé thăm thị trấn nào.

Bạn vừa nhận được thông tin có ~Q~ thiên thạch có thể rơi xuống các thị trấn. Thiên thạch thứ ~i~ có thể rơi vào các thị trấn từ ~L_i, L_i+1, \cdots, R_i~. Để đảm bảo an toàn cho người đi đường, đối với mỗi thiên thạch, bạn cần tính chi phí sơ tán mà chính quyền cần bỏ ra.

Chi phí sơ tán cho một thiên thạch được tính như sau:

• Chi phí sơ tán là tổng chi phí tối thiểu cần thiết để đảm bảo tất cả người đi đường được an toàn bất kể họ đang ở thị trấn nào.
• Một người được coi là an toàn nếu người đó ở trong một nơi trú ẩn hoặc ở một thị trấn nằm ngoài khu vực ảnh hưởng của thiên thạch (vậy thì người đó sẽ không cần vào nơi trú ẩn ở thị trấn đó).
• Mỗi người cần ~1~ đơn vị chi phí để di chuyển đến thị trấn liền kề (hai thị trấn được coi là liền kề nếu chỉ chênh lệch nhau đúng ~1~ đơn vị số thứ tự).

Lưu ý rằng chỉ di chuyển người mới tốn chi phí, và các hành động khác (như cho người vào nơi trú ẩn) không tốn chi phí. Đảm bảo rằng các thị trấn ~0~ và ~N+1~ sẽ không bao giờ bị ảnh hưởng bởi thiên thạch, vì vậy luôn có cách để đảm bảo tất cả người đi đường an toàn.

Input

Dữ liệu được cho theo định dạng sau

~N~ ~S~

~A_1 A_2 ⋯ A_N~

~Q~

~L_1~ ~R_1~

~L_2~ ~R_2~

⋮

~L_Q~ ~R_Q~

Ràng buộc

• ~1 \leq N \leq 2 \times 10^5~
• ~1 \leq S \leq 10^{12}~
• ~0 \leq A_i \leq S~
• ~A_1 + A_2 + ⋯ + A_N \leq 10^{12}~
• ~1 \leq Q \leq 2 \times 10^5~
• ~1 \leq L_i \leq R_i \leq N~

Tất cả các giá trị trong đầu vào đều là số nguyên.

Subtask

• Subtask ~1~: ~n,q \le 100~ ~(20\%)~
• Subtask ~2~: ~n,q \le 2000~ ~(20\%)~
• Subtask ~3~: ~L_i = 1~ ~(30\%)~
• Subtask ~4~: Không giới hạn gì thêm ~(30\%)~

Output

• In ra ~q~ dòng, dòng thứ ~i~ là đáp án cho truy vấn thứ ~i~.

Example

Sample Input 1

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

Sample Output 1

13
4
15

Explanation

Ở truy vấn ~1~, nếu nhóm người đang ở thành phố ~3~ thì sẽ mất tổng số chi phí là ~13~.

Ở truy vấn ~2~, ~4~ người không có chỗ trú ẩn có thể đi hết sang thành phố ~6~ để thoát khỏi nguy hiểm.