Hương hoa bay nhẹ nhàng qua kẽ lá.

Lời thì thầm của đá khẽ qua tai.

Không cần giới thiệu chắc hẳn bạn cũng không biết 2 câu thơ trên là của ai. Nhưng theo mình biết, thì 2 câu thơ đó chính là châm ngôn sống của Lành - 1 người đàn ông mạnh mẽ nhưng sống rất nội tâm. Hằng ngày khi không có việc gì làm, Lành thường có những biểu hiện như tay nhặt lá, chân đá ống bơ (đúng như châm ngôn sống của mình). Những lúc khác thì Lành lại tự nghĩ ra những câu đố hóc búa, thách thức chính bản thân mình cũng như mọi người. Hôm nay cũng như vậy, Lành đã nghĩ ra bài toán như sau:

• Cho một xâu kí tự chỉ chứa ~2~ kí tự '~a~' và '~b~', hãy ~1~ tìm xâu con liên tiếp sao cho tần suất xuất hiện là lớn nhất.
• Tần suất xuất hiện là số lần xâu con liên tiếp '~aba~' xuất hiện / độ dài.

Tuy nhiên các xâu kí tự thì có vẻ rất dài, vì vậy các bạn lập trình viên của ~Bedao \ Contest~ hãy giúp đỡ Lành nhé.

Input

• Dòng đầu tiên nhập số nguyên dương ~n \ (3 \le n \le 10^6)~ là độ dài của xâu kí tự.
• Dòng thứ 2 nhập xâu kí tự có độ dài ~n~ chỉ chứa ~2~ kí tự '~a~' và '~b~' (Dữ liệu đảm bảo có ít nhất 1 xâu '~aba~').

Output

• In ra 1 dòng duy nhất chứa xâu kí tự cần tìm. Nếu có nhiều xâu con có tần suất xuất hiện của xâu '~aba~' là lớn nhất thì in ra xâu có thứ tự từ điển nhỏ nhất.

Subtask

• ~20\%~ số test có ~n \le 10^2~.
• ~30\%~ số test có ~n \le 10^3~.
• Còn lại không có điều kiện gì thêm.

Sample Input

8
abaababa

Sample Output

ababa   

Note

Ta thấy xâu '~ababa~' có tần suất xuất hiện là ~2/5~ là lớn nhất, còn xâu '~abaababa~' có tần suất xuất hiện là ~3/8~ bé hơn ~2/5~.

Bạn được cho ~N~ thùng nước, thùng nước thứ ~i~ nằm ở vị trí ~X[i]~ và chứa ~W[i]~ lít nước ~(1 \le i \le n)~, các vị trí của những thùng nước được sắp xếp tăng dần . Chí phí vận chuyển thùng nước thứ ~i~ về thùng nước thứ ~j~ là ~W[i] \times (X[j] - X[i] ) ~ ~(1 \le i < j \le N)~.

Bạn có ~Q~ truy vấn mỗi truy vấn bạn cần phải tìm tổng chi phí để vận chuyển các thùng nước thứ ~l~ đến ~r-1~ về thùng nước thứ ~r~.

Input

Dòng đầu tiên chứa một số nguyên ~N~ ~(1 \le N \le 10^{6})~. ~N~ dòng tiếp theo, dòng thứ ~i~ ghi hai số cách nhau bới dấu cách là tọa độ ~X[i]~ và lượng nước ~W[i]~ của thùng nước thứ ~i~ ~(1 \le X[i] , W[i] \le 10^{6})~ .

Dòng thứ ~N + 1~ số lượng truy vấn ~Q~ ~(1 \le Q \le 10^{6})~. ~Q~ dòng tiếp theo mỗi dòng chứa hai số ~L~ và ~R~ cách nhau bởi dấu cách là dữ liệu cho từng truy vấn .

Output

Ghi ra ~Q~ dòng lần lượt là câu trả lời của từng truy vấn .

Subtask

• ~50\%~ số test có ~ 1 \le N , Q \le 1000~.
• Còn lại không có điều kiện gì thêm

Sample Input

3 
1 20
2 20
3 20
2 
1 2
1 3

Sample Output

20 
60 

Note

Truy vấn ~1~ ~(2 - 1) \times 20~.

Truy vấn ~2~ ~(3 - 1) \times 20 + (3 - 2) \times 20~.

Khánh rất thích đố mọi người giải đố, đặc biệt là với các dãy số. Cho dãy số nguyên ~a_1, a_2, a_3, ... a_n~ và ~Q~ thao tác thuộc ~1~ trong ~2~ loại sau:

• Cho ba số nguyên ~1, k, b~ và gán ~a_k = b~.
• Cho ba số nguyên ~2, l, r~. Hãy in ra số lượng đoạn con nằm trong đoạn ~[l, r]~ có tổng là số chẵn.

Input

• Dòng đầu chứa ~2~ số nguyên ~N~ và ~Q~ ~(1 \le N, Q \le 10^5)~
• Dòng tiếp theo chứa dãy số nguyên ~a_1, a_2, a_3, ... a_n~ ~(1 \le a[i] \le 10^5)~
• Dòng thứ ~i~ trong ~Q~ dòng tiếp theo gồm ~3~ số nguyên ~(1 \le k \le N,1 \le b \le 10^5,1 \le l \le r \le N \le 10^5)~ mô tả một trong hai thao tác nêu ở đầu bài.

Output

• Nếu là thao tác ~2~ hãy in ra số lượng đoạn con nằm trong đoạn ~[l, r]~ có tổng là số chẵn.

Sample Input

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

Sample Output

6
3

Note

• Thao tác ~1~, cập nhật ~a_1 = 4~.
• Thao tác ~1~, cập nhật ~a_2 = 3~.
• Thao tác ~2~, in ra số lượng đoạn con trong đoạn ~[1,4]~ có tổng là số chẵn.
• Thao tác ~1~, cập nhật ~a_3 = 3~.
• Thao tác ~2~, in ra số lượng đoạn con trong đoạn ~[4,6]~ có tổng là số chẵn.
• Thao tác ~1~, cập nhật ~a_2 = 7~.

Theo truyền thuyết xa xưa, có một năm khí hậu quá khô hạn vì không có đủ rồng để phun mưa. Chính vì vậy, Ngọc Hoàng đã mở một cuộc thi để tuyển chọn các con vật đủ khả năng cũng như phẩm chất hóa rồng để cứu nhân gian.

Thương xót trước tình cảnh những dòng sông cạn trơ đáy, cá tôm không còn chỗ để trú thân, người dân đói khổ, cây cối xác xơ, cá chép quyết tâm vượt qua cửa Vũ Môn để có thể hoá rồng, đem mưa tới cho nhân gian.

Để có thể đến được cửa Vũ Môn, cá chép phải bơi qua các thác nước cao lớn lên tận trời mây được mô tả giống như một ma trận kích thước ~n*m~. Nơi cá chép xuất phát là ô ~(1,1)~ và cổng vũ môn ở vị trí ~(n,m)~. Tại một thời điểm, cá chép chỉ chọn bơi sang trái, bơi sang phải hoặc bơi lên trên chứ không bao giờ bơi xuống. Sức lực cá chép cần bỏ ra để bơi từ ô ~(i,j)~ sang bên phải là ~r_{i,j}~, bơi sang trái là ~l_{i,j}~ và bơi lên trên là ~u_{i,j}~.

Cảm động trước sự quyết tâm và tấm lòng nhân hậu của cá chép, Ngọc Hoàng đã âm thầm giúp đỡ bằng cách tại mỗi hàng ~i~ của ma trận, Ngọc Hoàng sẽ thả xuống một hạt ngô thần tại vị trí ~p_i~. Khi cá chép bơi qua đây và ăn hạt ngô này, sức lực của cá chép sẽ được hồi phục lại ~c_i~.

Hãy giúp cá chép tính sức lực ít nhất mà cá chép cần bỏ ra để có thể đến được cửa Vũ Môn. Giá trị này có thể là một số âm.

Input

• Dòng đầu tiên gồm ~2~ số nguyên dương ~n,m~ (~2 \leq n,m \leq 1000~).

• ~n-1~ dòng tiếp theo, dòng thứ ~i~ gồm ~m~ số nguyên dương ~u_{i,1},u_{i,2},...,u_{i,m}~ là sức lực cá chép cần bỏ ra khi bơi từ ô ~(i,j)~ lên trên (~0 \leq u_{i,j} \leq 10^9~).

• ~n~ dòng tiếp theo, dòng thứ ~i~ gồm ~m-1~ số nguyên dương ~l_{i,2},l_{i,3},...,l_{i,m}~ là sức lực cá chép cần bỏ ra khi bơi từ ô ~(i,j)~ sang trái (~0 \leq l_{i,j} \leq 10^9~).

• ~n~ dòng tiếp theo, dòng thứ ~i~ gồm ~m-1~ số nguyên dương ~r_{i,1},r_{i,2},...,r_{i,m-1}~ là sức lực cá chép cần bỏ ra khi bơi từ ô ~(i,j)~ sang phải (~0 \leq r_{i,j} \leq 10^9~).

• ~n~ dòng cuối cùng, dòng thứ ~i~ gồm ~2~ số ~p_i~ và ~c_i~ (~1 \leq p_i \leq m~, ~0 \leq c_i \leq 10^9~).

Output

• In ra ~1~ số nguyên duy nhất là sức lực ít nhất cá chép cần bỏ ra để đến được cửa Vũ Môn.

Subtask

• ~10\%~ số test có ~2 \leq n,m \leq 5~.

• ~30\%~ số test khác có ~u_{i,j}=l_{i,j}=r_{i,j}=c_i=1~.

• ~20\%~ số test khác có ~c_i=0~.

• Còn lại không có điều kiện gì thêm.

Sample Input 1

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

Sample Output 1

2

Sample Input 2

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

Sample Output 2

-4

Sample Input 3

2 2
8 10
12
11
14
16
2 97
1 6

Sample Output 3

-73

Note

Ở ví dụ thứ hai, cá chép có thể có sức lực ban đầu là ~-4~:

• Từ ô ~(1,1)~ cá chép bơi sang phải ~1~ ô sang ô ~(1,2)~, mất ~2~ sức lực và ăn ngô hồi ~7~, sức lực hiện tại của cá chép là ~1~.

• Tiếp theo cá chép bơi sang trái về ô ~(1,1)~, mất ~2~ sức lực, hiện tại cá còn ~-1~ sức lực.

• Sau đó cá bơi lên ô ~(2,1)~, mất ~1~ sức lực và ăn ngô hồi ~3~, sức lực hiện tại của cá là ~1~. (Nếu cá bơi sang phải sang ô ~(1,2)~ một lần nữa, nó sẽ không được hồi ~7~ sức lực do mỗi ô chỉ có tối đa ~1~ hạt ngô được đặt, và cá đã ăn ngô ở đó từ trước).

• Cuối cùng cá bơi sang phải sang ô ~(2,2)~, là cửa Vũ Môn, mất ~1~ sức lực, còn ~0~ và vừa đủ để vượt cửa Vũ Môn.

Có thể chứng minh được cá không thể có sức lực ban đầu bé hơn ~-4~ để vượt cửa Vũ Môn.

Ta xét hoán vị ~a~ của ~n~ phần tử ~1, 2, ..., n~.

Một dãy con của ~a~ là dãy thu được nếu xóa đi một số phần tử (có thể không xóa) từ ~a~ và giữ nguyên thứ tự các phần tử còn lại. Ví dụ: ~\{1, 3, 4\}~ là dãy con của ~\{1, 2, 3, 4, 5\}~, còn ~\{2, 1\}~ và ~\{1, 5, 2\}~ thì không.

Khi đó, ta định nghĩa ~LIS(a)~ là độ dài dãy con tăng dần dài nhất của dãy ~a~; tương tự với ~LDS(a)~ là độ dài dãy con giảm dần dài nhất của ~a~.

Gọi ~g(n) = min\{max\{LIS(a), LDS(a)\}\}~ với mọi hoán vị ~a~ độ dài ~n~.

Yêu cầu: Cho ~q~ truy vấn dạng ~l~ ~r~. Với mỗi truy vấn bạn hãy tính ~g(l)+g(l+1)+...+g(r)~.

Input

• Dòng đầu chứa số nguyên dương ~q~ ~(q \le 10^5)~.

• ~q~ dòng tiếp, mỗi dòng chứa hai số nguyên ~l,r~ ~(1\le l \le r \le 10^9)~.

Output

In ra ~q~ dòng, mỗi dòng là đáp án cho truy vấn tương ứng.

Subtask

• Có ~25\%~ số test của bài với ~q,r \le 1000~.

• Có ~25\%~ số test khác của bài với ~1\le l \le r \le 10^6~ trong mọi truy vấn.

• Có ~25\%~ số test khác với ~q=1~.

• Còn lại không có điều kiện gì thêm.

Sample Input

5
1 2
3 5
30 50
150 200
1 1000000000

Sample Output

3
7
141
698
21082351068005

Note

Các dãy có ~max\{LCS, LDS\}~ là nhỏ nhất trong một số trường hợp:

• ~n = 1~: ~[1]~

• ~n = 2~: ~[2, 1]~

• ~n = 3~: ~[1, 3, 2]~

• ~n = 4~: ~[2, 4, 1, 3]~

• ~n = 5~: ~[5, 2, 4, 1, 3]~

Một lớp học nọ có ~n~ học sinh. Thầy giáo cho họ một túi kẹo ~U~ có ~m~ viên kẹo được đánh số từ ~1~ đến ~m~. Với học sinh ~i~, viên kẹo thứ ~k~ có độ ngon là ~v_i(k)~. Tương tự, một túi kẹo nhỏ bất kỳ ~S~ lấy từ ~U~ có độ ngon là tổng độ ngon (đối với học sinh ~i~) của các viên kẹo có trong túi ~S~.

Là một học sinh ưu tú của lớp học đề cao thực lực, bạn cần chia túi kẹo ~U~ thành ~n~ túi kẹo nhỏ ~S_1, S_2, \dots, S_n~ (học sinh ~i~ sẽ nhận túi ~S_i~) sao cho:

• Một viên kẹo phải được nằm trong duy nhất một túi nào đó.
• Mỗi túi phải có ít nhất ~1~ viên kẹo.
• Với mỗi học sinh ~i~, bạn ấy không muốn túi kẹo ~S_i~ của mình quá tệ so với những túi kẹo khác. Chi tiết hơn, bạn cần phải đảm bảo ~v_i(S_i) \ge v_i(S_j) - \max_{k \in S_j} v_i(k)~ với mọi ~i, j~ ~(1 \le i, j \le n, i \neq j)~.

Ta có thể chứng minh được là luôn có cách chia kẹo để thỏa mãn các điều kiện trên. Hãy tìm và in ra một cách chia kẹo như thế.

Input

• Dòng đầu tiên chứa ~2~ số nguyên dương ~n~ và ~m~ ~(1 \le n \le m \le 500)~.
• ~n~ dòng tiếp theo, dòng thứ ~i~ chứa ~m~ số nguyên ~v_i(1), v_i(2), \dots, v_i(m)~ ~(0 \le v_i(j) \le 10^9)~ tương ứng với độ ngon của ~m~ viên kẹo với học sinh ~i~.

Output

• Gồm ~n~ dòng, dòng thứ ~i~ chứa số nguyên ~k_i~ là số lượng kẹo của túi ~S_i~, tiếp đến là ~k_i~ số nguyên ngăn cách bởi dấu cách tương ứng là chỉ số của những viên kẹo trong túi ~S_i~.

Subtask

• Có ~10\%~ số test là ~m = n~.
• Có ~10\%~ số test là ~n = 2~.
• Còn lại không có ràng buộc gì thêm.

Sample Input

4 4
34 8 8 25
4 30 2 8
32 32 28 35
28 17 18 0

Sample Output

1 1
1 2
1 4
1 3