Cho dãy số nguyên dương ~a[1], a[2], …, a[N]~. Xét cách chia dãy số ~a~ thành ~K~ nhóm sao cho mỗi nhóm chứa một đoạn liên tiếp các phần tử của ~a~. Gọi trọng số của một cách chia là tổng các phần tử lớn nhất của mỗi nhóm

Yêu cầu: Tìm cách chia dãy số ~a~ thành ~K~ nhóm sao cho trọng số của cách chia là nhỏ nhất

Dữ liệu

• Dòng 1: 2 số nguyên dương ~N~ và ~K~ (~K \le N~)
• Dòng 2: Gồm ~N~ số nguyên dương ~a[1], a[2], …, a[N]~

Kết quả:

• Ghi ra 1 số nguyên duy nhất là trọng số tìm được

Input 1

5 1
1 2 3 4 5   

Output 1

5

Input 2

5 2
1 2 3 4 5   

Output 2

6

Giới hạn:

• 14% số điểm: ~1\le N\le100, K\le min(N, 5)~
• 18% số điểm: ~1\le N\le20~
• 21% số điểm: ~1\le N\le100~
• 47% số điểm: ~1\le N\le100000, K\le min(N, 100).~

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

Bạn được cho hai mảng có độ dài ~n~ .

• Phần tử thứ ~i~ của mảng thứ nhất là ~a_i~ .
• Phần tử thứ ~i~ của mảng thứ hai là ~b_i~ .

Một cách chia cả hai mảng thành các mảng con không rỗng được gọi là tốt nếu thỏa mãn các điều kiện sau:

• Mỗi phần tử thuộc đúng một mảng con duy nhất.
• Số lượng mảng con của cả hai mảng bằng nhau, tức là nếu mảng thứ nhất được chia thành đúng ~k~ mảng con, thì mảng thứ hai cũng phải được chia thành đúng ~k~ mảng con.
• Với mọi ~1 \leq i \leq k~, trung bình cộng của mảng con thứ ~i~ bên trái mảng thứ nhất phải nhỏ hơn hoặc bằng trung bình cộng của mảng con thứ ~i~ bên trái mảng thứ hai.

Yêu cầu: Tính số cách để chia cả hai mảng thành các mảng con không rỗng thỏa mãn các điều kiện trên. Kết quả phải được chia dư với ~10^9 + 7~. Hai cách được xem là khác nhau nếu số lượng mảng con khác nhau hoặc nếu một phần tử thuộc về mảng con khác nhau.

Dữ liệu vào từ tệp văn bản: TRUNGBINHCONG.INP

• Dòng đầu tiên chứa số nguyên ~n~ ~(1 \leq n \leq 500)~.
• Dòng tiếp theo chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ ~(1 \leq a_i \leq 10^6)~.
• DDòng cuối cùng chứa ~N~ số nguyên ~b_1, b_2, \dots, b_n~ ~(1 \leq b_i \leq 10^6)~.

Kết quả ghi ra tệp văn bản: TRUNGBINHCONG.OUT

• In ra số cách chia mảng thỏa mãn các điều kiện, chia dư với ~10^9 + 7~.

Scoring

• Subtask ~1~ (~20\%~ số điểm): ~n \le 10~
• Subtask ~2~ (~30\%~ số điểm): ~n \le 80~
• Subtask ~3~ (~30\%~ số điểm): ~n \le 300~
• Subtask ~4~ (~20\%~ số điểm): Không giới hạn gì thêm.

Example

Sample Input 1

3
1 3 2
2 2 2

Sample Output 1

3

Note

Ba cách hợp lệ là:

• Chia mảng thứ nhất thành ~[1, 3], [2]~ và mảng thứ hai thành ~[2, 2], [2]~.
• Chia mảng thứ nhất thành ~[1, 3], [2]~ và mảng thứ hai thành ~[2], [2, 2]~.
• Chia mảng thứ nhất thành ~[1, 3, 2]~ và mảng thứ hai thành ~[2, 2, 2]~.

Dãy con của một dãy là dãy thu được bằng cách xóa đi một số phần tử của dãy ban đầu (có thể không xóa phần tử nào) và giữ nguyên thứ tự của các phần tử còn lại. Một dãy số được gọi là dãy tăng kép nếu có thể tách nó ra thành hai dãy con khác rỗng, sao cho mỗi phần tử của dãy ban đầu thuộc vào đúng dãy con đó, và các phần tử trong cùng một dãy con thì tăng nghiêm ngặt.

Cho dãy số nguyên ~a~ có ~n~ phần tử, hãy đếm số dãy con của ~a~ là dãy tăng kép.

Input

• Dòng đầu tiên gồm số nguyên ~n~
• Dòng thứ hai chứa ~n~ số nguyên ~a_1,a_2,...,a_n~ ~(1 \le a_i \le n)~

Output

• In ra số lượng dãy tăng kép là dãy con của ~a~, sau khi chia lấy dư cho ~1000000007~

Subtask :

• Subtask ~1~: ~n \le 20~ ~(20\%)~
• Subtask ~2~: ~n \le 200~ ~(20\%)~
• Subtask ~3~: ~n \le 2000~ và ~a_i \le 200~ ~(25\%)~
• Subtask ~4~: ~n \le 2000~ ~(35\%)~

Sample Input 1:

4
3 3 4 2

Sample Output 1:

9

Cho hai dãy số nguyên ~a_1,a_2,...,a_n~ và ~b_1,b_2,...,b_n~. Bạn cần sử dụng thao tác sau đúng một lần:

• Chọn hai chỉ số ~[L,R]~ thỏa mãn ~1 \le L \le R \le n~ và hoán đổi vị trí hai dãy con ~a_L,a_{L+1},...,a_R~ với ~b_L,b_{L+1},...,b_R~.

Hãy đếm số cách thực hiện thao tác trên sao cho sau khi thực hiện, ít nhất một trong hai dãy ~a~ hoặc ~b~ trở thành hoán vị của các số từ ~1~ đến ~n~.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~.
• Dòng thứ hai gồm ~n~ số nguyên dương miêu tả dãy ~a~.
• Dòng thứ ba gồm ~n~ số nguyên dương miêu tả dãy ~b~.

Constraints

• ~2 \le n \le 2*10^5~

Subtask:

• Subtask ~1~ (~30\%~ số điểm): ~n \le 300~
• Subtask ~2~ (~40\%~ số điểm): ~n \le 5000~
• Subtask ~3~ (~30\%~ số điểm): Không ràng buộc gì thêm.

Output

• In ra số cách thực hiện thao tác trên.

Sample Input 1

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

Sample Output 1

8

Cho một dãy ~p_1,p_2,...,p_n~ là một hoán vị của ~1,2,...,n~. Bạn được thực hiện hai phép biến đổi sau:

• Chọn hai phần tử bất kì và tráo đổi,loại phép biến đổi này chỉ được thực hiện nhiều nhất một lần.
• Chọn hai phần tử kề nhau và tráo đổi, loại phép biến đổi này được thực hiện nhiều lần.

Yêu cầu: Tính số phép biến đổi ít nhất để đưa dãy hoán vị ~p_1,p_2,...,p_n~ về dãy hoán vị ~1,2,3...,n~.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~.
• Dòng thứ hai gồm ~n~ số nguyên dương ~p_1,p_2,...,p_n~.

Output

• In ra số bước ít nhất để đưa dãy ~p~ về hoán vị ~1,2,3,...,n~.

Constraints .

• ~1 \le N \le 10^5~.

Subtask

• Sub ~1~ ~(10\%)~: ~n = 3~.
• Sub ~2~ ~(20\%)~: ~n \le 30~.
• Sub ~3~ ~(20\%)~: ~n \le 300~.
• Sub ~4~ ~(20\%)~: ~n \le 1000~.
• Sub ~5~ ~(15\%)~: ~n \le 10^4~.
• Sub ~6~ ~(15\%)~: ~n \le 10^5~.

Sample Input 1

5
5 3 4 2 1

Sample Output 1

3

Hệ thống giao thông của thành phố mà DN được quy hoạch có dạng một lưới hình chữ nhật gồm ~m \times n~ ô vuông đơn vị với các con đường ngang và dọc chạy xuôi theo các ô của lưới. Các con đường ngang bắt đầu từ bên trái sang bên phải của lưới, song song với nhau và được đánh số từ 1 đến ~m + 1~ theo thứ tự từ trên xuống dưới. Các con đường dọc bắt đầu từ phía trên xuống phía dưới của lưới, song song với nhau và được đánh số từ 1 đến ~n + 1~ theo thứ tự từ trái sang phải. Giao của đường ngang thứ ~u~ với đường dọc thứ ~v~ gọi là địa điểm ~(u, v)~.

Nơi ở hoặc nơi làm việc của người dân là một địa điểm trên lưới. Ban quy hoạch đô thị đã khảo sát được hằng ngày có một số lượng lớn người dân có thói quen ghé qua siêu thị sau giờ làm rồi mới về nhà. Căn cứ vào dữ liệu của ~d~ người dân có nơi ở là các địa điểm lần lượt tương ứng là ~A_1, A_2, ..., A_d~ và có nơi làm việc tương ứng là ~B_1, B_2, ..., B_d~ (người ở địa điểm ~A_i~ làm việc tại địa điểm ~B_i~, ~1 \leq i \leq d~). Bạn quy hoạch quyết định chọn một tuyến phố thương mại xuôi theo một con đường ngang để xây dựng một số lượng ~k~ siêu thị phục vụ người dân thuận tiện sinh hoạt, tiết kiệm chi phí và thời gian đi lại. Các siêu thị được đặt tại các địa điểm trên lưới và có thể trùng với địa điểm nơi ở hoặc nơi làm việc của người dân.

Yêu cầu: Hãy giúp ban quy hoạch chọn một con đường ngang và ~k~ địa điểm trên con đường ngang này để xây dựng các siêu thị sao cho tổng tất cả độ dài quãng đường từ nơi làm việc của từng người đến một siêu thị và từ siêu thị đó trở về nơi ở là nhỏ nhất. Độ dài quãng đường từ địa điểm ~(u, v)~ đến địa điểm ~(u', v')~ tính bằng ~|u - u'| + |v - v'|~.

Input

• Dòng đầu tiên chứa bốn số nguyên dương ~m, n, d, k~, với ~m, n \leq 10^9; k \leq 15~.
• Dòng thứ hai chứa ~d~ cặp số nguyên dương ~a_1, b_1, a_2, b_2, ..., a_d, b_d~ với ~1 \leq a_i \leq m + 1~ và ~1 \leq b_i \leq n + 1~ với mọi ~1 \leq i \leq d~ là địa điểm nơi ở của người dân.
• Dòng thứ ba chứa ~d~ cặp số nguyên dương ~x_1, y_1, x_2, y_2, ..., x_d, y_d~ với ~1 \leq x_i \leq m + 1~ và ~1 \leq y_i \leq n + 1~ với mọi ~1 \leq i \leq d~ là địa điểm nơi làm việc của người dân.

Output

• Ghi ra thiết bị ra chuẩn một số nguyên duy nhất là tổng độ dài quãng đường nhỏ nhất cần thiết khi đặt ~k~ siêu thị trên cùng một đường ngang.

Subtask

• Có ~15\%~ số test ứng với ~15\%~ số điểm của bài thỏa mãn ~d \leq 300~ và ~b_i = y_i~ (với mọi ~1 \leq i \leq d~);
• ~20\%~ số test tiếp theo ứng với ~20\%~ số điểm của bài thỏa mãn ~d \leq 3000~ và ~b_i = y_i~ (với mọi ~1 \leq i \leq d~);
• ~20\%~ số test khác ứng với ~20\%~ số điểm của bài thỏa mãn ~d \leq 300~;
• ~25\%~ số test khác ứng với ~20\%~ số điểm của bài thỏa mãn ~d\leq 3000~;
• ~20\%~ số test còn lại ứng với ~20\%~ số điểm của bài thỏa mãn ~d \leq 5 \times 10^4~.

Example

Input 1

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

Output 1

24

Explanation 1

Giải thích ví dụ: Bạn quy hoạch đô thị chọn con đường ngang số 3 và hai siêu thị ~S_1~, ~S_2~ ở vị trí giao với đường dọc số 3 và số 4. Lịch trình di chuyển hằng ngày từ nơi làm việc về nhà của bốn người dân như sau:

• Người thứ nhất đi từ ~B_1~ đến ~S_2~, rồi về ~A_1~, với tổng quãng đường là ~8~;
• Người thứ hai đi từ ~B_2~ đến ~S_2~, rồi về ~A_2~, với tổng quãng đường là ~4~;
• Người thứ ba đi từ ~B_3~ đến ~S_1~, rồi về ~A_3~, với tổng quãng đường là ~6~;
• Người thứ tư đi từ ~B_4~ đến ~S_1~, rồi về ~A_4~, với tổng quãng đường là ~6~.