Cho hai dãy ~a~ và ~b~ cùng có ~n~ phần tử nguyên. Ta định nghĩa hàm ~sum(x,y)~ ~(1 \le x,y \le n)~ như sau:

• Nếu ~x \le y~ thì ~sum(x,y) = a_x + a_{x+1} + a_{x+2} + ... + a_y~.
• Nếu ~x > y~ thì ~sum(x,y) = b_x + b_{x-1} + b_{x-2} + ... + b_y~.

Nhiệm vụ của bạn là, hãy chọn ra hai đoạn ~[x,y]~ ~(1 \le x \le y \le n)~ và ~[c,d]~ ~(1 \le c \le d \le n)~ sao cho ~S = \sum sum(i,j)~ với mọi ~x \le i \le y~ và ~c \le j \le d~ là lớn nhất.

Constraint

• ~1 \le n \le 400~.
• ~-10^6 \le b_i, a_i \le 10^6~.

Input

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

Output

• In ra ~S~ lớn nhất tìm được.

Subtask

• ~30\%~ số test có ~n \le 10~
• ~40\%~ số test có ~n \le 50~.
• ~30\%~ số test có ~n \le 400~.

Sample Input 1

5
1 4 2 -1 -2
-2 -1 1 2 -1

Sample Output 1

45

Explanation 1

• Chọn đoạn ~[1,5]~ và ~[2,5]~.

Gọi ~f(l,r)~ của dãy ~a~ là giá trị ~i~ nhỏ nhất thỏa mãn ~1 \le i \le r~ và ~a_i = max (a_l,a_{l+1},...,a_r)~.

Bạn được cho dãy ~a = [a_1,a_2,...,a_n]~ với độ dài ~n~. Hãy đếm số lượng dãy ~b = [b_1,b_2,...,b_n]~ với độ dài ~n~ thỏa mãn những điều kiện sau:

• ~1 \le b_i \le m~ ~\forall 1 \le i \le n~;
• ~\forall \{l,r\} (1 \le l \le r \le n)~, giá trị ~f(l,r)~ của dãy ~b~ bằng với giá trị ~f(l,r)~ của dãy ~a~.

Do kết quả có thể rất lớn, hãy in ra nó sau khi lấy modulo ~10^9+7~.

Input

• Dòng đầu tiên gồm hai số nguyên dương ~n,m~ ~(2 \le n,m \le 2\times 10^5, n \times m \le 10^6)~
• Dòng thứ hai gồm ~n~ số nguyên dương ~a_1,a_2,...,a_n~ ~(1 \le i \le m)~ - miêu tả dãy ~a~.

Output

• In ra số dãy ~b~ thỏa mãn theo modulo ~10^9+7~.

Subtask

• Subtask ~1~ ~(25\%)~: ~n,m \le 7~
• Subtask ~2~ ~(25\%)~: ~n \le 100, m \le 10~.
• Subtask ~3~ ~(50\%)~: Không có ràng buộc gì thêm.

Sample Input 1

5 3
1 3 2 3 1 

Sample Output 1

18

Sample Input 2

7 5
4 1 3 5 5 2 1

Sample Output 2

440

Cho hai dãy số nguyên ~a, b~ có cùng độ dài ~n~ và một số nguyên ~S~. Có ~Q~ truy vấn thuộc một trong hai dạng sau:

• ~1~ ~x~ ~y~: Gán ~a_i = x, b_i = y~
• ~2~ ~H~: Cần tìm ~1 \le L \le H~ sao cho ~a_L + a_{L+1} + ... + a_H \ge S~ và ~b_L + b_{L+1} + ... + b_H~ đạt giá trị nhỏ nhất có thể.

Input

• Dòng đầu tiên chứa hai số nguyên ~n, S~ ~(1 ≤ n ≤ 10^5, -10^{18} ≤ S ≤ 10^{18})~.
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, . . . , a_n (-10^9 ≤ a_i ≤ 10^9)~
• Dòng thứ ba chứa ~n~ số nguyên ~b_1, b_2, . . . , b_n~ ~(-10^9 ≤ b_i ≤ 10^9)~
• Dòng thứ tư chứa số nguyên dương ~Q~ ~(1 ≤ Q ≤ 10^5)~
• ~Q~ dòng tiếp theo, mỗi dòng ghi một truy vấn: ~1~ ~i~ ~x~ ~y~ ~(1 ≤ i ≤ n; -10^9 ≤ x, y ≤ 10^9)~ hoặc ~2~ ~H~ ~(1 ≤ H ≤ n)~

Output

• Với mỗi truy vấn, in ra trên một dòng là giá trị nhỏ nhất có thể của ~b_L + b_{L+1} + . . . + b_H~ hoặc ~-1~ nếu không tồn tại ~L~ thoả mãn.

Subtask

• Subtask ~1~ ~(25\%)~: ~a_i = 1~ tại mọi thời điểm.
• Subtask ~2~ ~(25\%)~: ~b_i = 1~ tại mọi thời điểm.
• Subtask ~3~ ~(25\%)~: Chỉ tồn tại các truy vấn loại ~2~.
• Subtask ~4~ ~(25\%)~: Không có ràng buộc nào thêm.

Sample Input 1

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

Sample Output 1

2
4
10

Trong bài thi Tin học cuối kì, thầy giáo cho Bảo bài kiểm tra gõ mười ngón. Trước hôm thi một tuần, Bảo được thầy cho một từ điển để ôn tập. Từ điển gồm ~n~ từ đôi một phân biệt chỉ gồm các chữ cái in thường. Bảo có thể gõ một số từ lên màn hình soạn thảo văn bản, mỗi thao tác Bảo có thể thực hiện một trong hai hành động sau:

• Gõ thêm một chữ cái in thường vào cuối văn bản đang gõ.
• Xóa chữ cái cuối cùng của văn bản đang gõ, nếu văn bản có ít nhất một chữ cái.

Trong giờ kiểm tra, thầy giáo cho Bảo số nguyên ~m~. Ban đầu màn hình soạn thảo không có chữ cái nào.

Nhiệm vụ của Bảo là chọn ra ~m~ từ phân biệt trong từ điển thầy đã cho, và gõ tất cả các từ đấy theo thứ tự bất kì. Bài thi được coi là hoàn thành nếu tất cả các từ đều được gõ ít nhất một lần, và sau khi gõ xong màn hình soạn thảo trở về trạng thái ban đầu (không có chữ cái nào). Từ ~S~ được coi là đã được gõ nếu trong một thời điểm nào đó, văn bản hiển thị trên màn hình soạn thảo trùng khớp với từ ~S~.

Vì muốn đạt điểm cao, với mọi ~m~ từ ~1~ đến ~k~, Bảo muốn biết số thao tác ít nhất để hoàn thành bài thi nếu được chọn m từ phân biệt trong từ điển để gõ.

Input

• Dòng đầu chứa hai số nguyên ~n, k~ ~(1 ≤ k ≤ n)~.
• ~n~ dòng tiếp theo, mỗi dòng chứa một xâu kí tự chỉ gồm các chữ cái in thường mô tả một từ trong từ điển.

Dữ liệu đảm bảo tất cả các từ đôi một phân biệt, và tổng số chữ cái của tất cả các từ không vượt quá ~10^6~.

Output

• In ra ~k~ dòng, dòng thứ ~m~ chứa một số nguyên là số thao tác ít nhất để Bảo hoàn thành bài thi nếu Bảo chọn ra ~m~ từ trong từ điển để gõ.

Subtask

• Subtask ~1~ ~(10\%)~: ~n ≤ 18~, tổng số chữ cái của tất cả các từ không vượt quá ~100~.
• Subtask ~2~ ~(20\%)~: ~n \le 100, k ≤ 50~, tổng số chữ cái của tất cả các từ không vượt quá ~500~.
• Subtask ~3~ ~(20\%)~: ~n \le 1000, k ≤ 100~, tổng số chữ cái của tất cả các từ không vượt quá ~4 \times 10^5~.
• Subtask ~4~ ~(30\%)~: ~n \le 2000, k ≤ 200~, tổng số chữ cái của tất cả các từ không vượt quá ~4 \times 10^5~.
• Subtask ~5~ ~(20\%)~: ~n \times k \le 10^6~.

  Sample Input 1

3 3
a
b
abkc

Sample Output 1

2
4
10

Explanation 1

Ở ví dụ đề bài ta xét hai trường hợp:

• ~m = 1:~ Chọn từ ~"a"~. Thao tác: ~"" \rightarrow "a" \rightarrow ""~
• ~m = 2:~ Chọn hai từ ~"a"~ và ~"b"~. Thao tác: ~"" \rightarrow "a" \rightarrow "" \rightarrow "b" \rightarrow ""~
• ~m = 3:~ Chọn cả ba từ. Thao tác: ~"" \rightarrow "a" \rightarrow "ab" \rightarrow "abk" \rightarrow "abkc" \rightarrow "abk" \rightarrow "ab" \rightarrow "a" \rightarrow "" \rightarrow "b" \rightarrow ""~