Cho xâu ~S~ chỉ gồm hai kí tự ~'a'~ và ~'b'~. Xâu ~XS~ là xâu được tạo bởi ghép ~X~ lần xâu ~S~ liền với nhau. Hãy đến xem có bao nhiêu xâu con ~"ab"~ xuất hiện trong xâu ~XS~.

Input

• Gồm hai dòng, dòng thứ nhất chứa xâu ~S~ có độ dài là ~N~ ~(0<N≤10^3)~.</li>
• Dòng thứ hai chứa số nguyên dương ~X~ ~(0<X≤10^9)~.</li>

Output

• Một số nguyên duy nhất là kết quả của bài toán.

Subtask

• Có ~50\%~ số test tương ứng với số điểm có với ~N,X \le 50~
• Có ~30\%~ số test khác tương ứng với số điểm có với ~N,X \le 10^3~
• Có ~20\%~ số test còn lại tương ứng với số điểm không có giới hạn gì thêm.

Ví dụ

Input 1

aabb
2

Output 1

2

Giải thích 1

• Xâu ~XS=aabbaabb~ có ~2~ xâu con ~"ab"~.

Input 2

baba
2

Output 2

3

Giải thích 2

• Xâu ~XS=babababa~ có ~3~ xâu con ~"ab"~.

Input 3

aaa
1

Output 3

0

Giải thích 3

• Xâu ~XS=aaa~ có ~0~ xâu con ~"ab"~.

Cho một mảng gồm ~n~ số nguyên, nhiệm vụ của bạn là đếm số lượng đoạn con có tổng ~x~.

Input

• Dòng đầu vào đầu tiên có hai số nguyên ~n~ và ~x~: kích thước của mảng và tổng ~x~.
• Dòng tiếp theo có ~n~ số nguyên ~a_1, a_2, \ldots, a_n~: nội dung của mảng.

Output

• In một số nguyên: số lượng đoạn con được yêu cầu.

Constraints

• ~1 \le n \le 2 \cdot 10^5~
• ~-10^9 \le x, a_i \le 10^9~

Sample Tests

Input

5 7
2 -1 3 5 -2

Output

2

Cho một mảng gồm ~n~ số nguyên, nhiệm vụ của bạn là tìm tổng giá trị lớn nhất trong một đoạn con liên tiếp với độ dài giữa ~a~ và ~b~.

Input

• Dòng đầu vào đầu tiên có ba số nguyên ~n~, ~a~ và ~b~: kích thước của mảng và độ dài tối thiểu và tối đa của đoạn con.
• Dòng thứ hai có ~n~ số nguyên ~x_1, x_2, \ldots, x_n~: các giá trị mảng.

Output

• In một số nguyên: tổng đoạn con lớn nhất.

Constraints

• ~1 \le n \le 2 \cdot 10^5~
• ~1 \le a \le b \le n~
• ~-10^9 \le x_i \le 10^9~

Sample Tests

Input

8 1 2
-1 3 -2 5 3 -5 2 2

Output

8

Cho hai số nguyên dương ~X~, ~Y~. Hãy tìm hai số nguyên dương ~A~, ~B~ thỏa mãn ~X \le A < B \le Y~ sao cho ~\gcd(A, B)~ là lớn nhất.

Input

• Gồm một dòng duy nhất gồm hai số nguyên dương ~X~, ~Y~ (~1 \le X < Y \le 2 \times 10^5~).

Output

• Gồm một dòng duy nhất là kết quả bài toán.

Example

Sample Input 1

4 7

Sample Output 1

2

Sample Input 2

19 20

Sample Output 2

1

Cho bảng ~a~ có kích thước ~n \times m~.

Hãy tìm một hình chữ nhật con có tổng lớn nhất trong bảng.

Input

• Dòng đầu tiên chứa ba số nguyên dương ~n,m~.
• ~n~ dòng sau, mỗi dòng gồm ~m~ số nguyên miêu tả bảng ~a~.

Output

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

Điều kiện

• ~1 \le n,m \le 400~.
• ~|a_{i,j}| \le 10^5~

Subtask

• ~50\%~ số điểm: ~n,m \le 40~
• ~50\%~ số điểm: ~n,m \le 400~.

Ví dụ

Input 1:

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

Output 1:

7

Hai anh em Tí và Tèo ở trên lớp được thầy giáo giao cho ~n~ bài tập về nhà, cụ thể như sau:

Có ~n~ bài tập, được đánh số từ ~1~ đến ~n~. Bài tập ~i~ thuộc loại ~t_i~.

• Nếu bài tập ~i~ được giao cho người đã hoàn thành bài tập ngay trước đó cùng loại thì thời gian thực hiện là ~b_{t_i}~.
• Nếu không, thời gian thực hiện là ~a_{t_i}~.

Mục tiêu của Tí và Tèo là phân chia công việc sao cho thời gian hoàn thành tất cả bài tập là nhanh nhẩt có thể. Các bạn hãy tính toán xem thời gian tốt nhất để hai anh em có thể hoàn thành tất cả các bài tập là bao nhiêu để hai anh em còn đi chơi.

Lưu ý:

• Bài tập phải được hoàn thành theo thứ tự đề cho.
• Trong quá trình thực hiện bài tập, không ai được nghỉ quá ~k~ bài liên tiếp.
• Mỗi bài tập chỉ cần một trong hai người hoàn thành.

Input

• Dòng đầu tiên gồm ba số nguyên dương ~n, m, k~ lần lượt là số lượng bài tập, số loại bài tập và khoảng nghỉ tối đa liên tiếp của một người (~1 \le n, m, k \le 5000~).
• Dòng thứ hai gồm ~n~ số nguyên dương ~t_1, t_2, \ldots, t_n~ là loại của của các bài tập ~(1 \le t_i \le m)~.
• Dòng thứ ba gồm ~m~ số nguyên dương ~a_1, a_2, \ldots, a_m~ là thời gian để hoàn thành công việc trong trường hợp thứ hai (~1 \le a_i \le 10^9~).
• Dòng cuối cùng gồm ~m~ số nguyên dương ~b_1, b_2, \ldots, b_m~ là thời gian để hoàn thành công việc trong trường hợp thứ nhất (~1 \le b_i \le a_i~).

Output

• Gồm một dòng là thời gian ngắn nhất để Tí và Tèo hoàn thành tất cả bài tập.

Subtasks

Example

Sample Input 1

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

Sample Output 1

21

Note

• Tí sẽ làm bài tập ~1, 3~ với thời gian là ~4 + 2 = 6~.
• Tèo sẽ làm bài tập ~2, 4~ với thời gian là ~8 + 7 = 15~.

Vậy tổng thời gian ngắn nhất để Tí và Tèo hoàn thành tất cả bài tập là ~21~.

Ngọc đang cần đi qua bốn khu phố ~A,B,C,D~. Mỗi một khu phố sẽ bao gồm một nhóm các ngôi nhà. Mỗi ngôi nhà có toạ độ (~x ,y~) trên mặt phẳng toạ độ thông thường. Ngọc sẽ bắt đầu ở một ngôi nhà thuộc ~A~, qua một ngôi nhà thuộc ~B~, đến một ngôi nhà thuộc ~C~ và cuối cùng kết thúc ở ~D~. Vì muốn tiết kiệm sức lực, Ngọc muốn tổng khoảng cách di chuyển là ít nhất có thể.

Khoảng cách khi đi từ một ngôi nhà toạ độ (~x_1,y_1~) đến một ngôi nhà có toạ độ (~x_2,y_2~) là ~(x_1- x_2 )^2 + (y_1 - y_2 )^2~.

Yêu cầu: Hãy tính tổng khoảng cách ngắn nhất để Ngọc di chuyển qua cả bốn khu phố ~A,B,C,D~ theo cách đã nêu ở trên.

Input

• Dòng 1 chứa bốn số nguyên dương ~n_a,n_b,n_c,n_d~ (~1 \le n_a,n_b,n_c,n_d\le 3000~) lần lượt là số ngôi nhà ở các khu phố ~A,B,C,D~.
• Dòng thứ hai chứa ~n_a~ cặp số nguyên ~(x_1,y_1),(x_2,y_2),(x_3,y_3),…,(x_(n_a ),y_(n_a ))~ lần lượt là toạ độ một ngôi nhà trong khu phố ~A~.
• Dòng thứ ba chứa ~n_b~ cặp số nguyên ~(x_1,y_1),(x_2,y_2),(x_3,y_3),…,(x_(n_b ),y_(n_b ))~ lần lượt là toạ độ một ngôi nhà trong khu phố ~B~.
• Dòng thứ tư chứa ~n_c~ cặp số nguyên ~(x_1,y_1),(x_2,y_2),(x_3,y_3),…,(x_(n_c ),y_(n_c ))~ lần lượt là toạ độ một ngôi nhà trong khu phố ~C~.
• Dòng cuối cùng chứa ~n_d~ cặp số nguyên ~(x_1,y_1),(x_2,y_2),(x_3,y_3),…,(x_(n_d ),y_(n_d ))~ lần lượt là toạ độ một ngôi nhà trong khu phố ~D~.

Các toạ độ của toàn bộ ngôi nhà có giá trị tuyệt đối không vượt quá ~10^8~

Output

• Ghi một số nguyên là kết quả bài toán.

Sample Input 1

1 1 1 2
-1 -1
0 0
1 1
3 3 2 2

Sample Output 1

6

Explanation 1

• Đi từ ngôi nhà ~(-1,-1)~ ở ~A~ đến ngôi nhà ~(0,0)~ thuộc ~B~, khoảng cách là ~(0 + 1)^2 + (0 + 1)^2 = 2~
• Đi từ ngôi nhà ~(0,0)~ ở ~B~ đến ngôi nhà ~(1,1)~ thuộc ~C~, khoảng cách là ~(1 - 0)^2 + (1 - 0)^2 = 2~
• Đi từ ngôi nhà ~(1,1)~ ở ~C~ đến ngôi nhà ~(2,2)~ thuộc ~D~, khoảng cách là ~(2 - 1)^2 + (2 - 1)^2 = 2~

Cho một hoán vị ~P = (p_1; p_2; … ;p_n)~ của tập hợp ~\{1; 2; … ; 𝑛\}~ và một số nguyên ~k~. Với mỗi số nguyên ~i = k; k + 1; … ; n~, hãy in ra giá trị lớn thứ ~k~ trong dãy con ~(p_1; … ;p_i)~. Chú ý: Giá trị lớn thứ ~𝐾~ trong một dãy là giá trị ở vị trí thứ ~k~ (đánh số vị trí từ ~1~) của dãy sau khi đã được sắp xếp giảm dần. Ví dụ, với dãy ~(1; 3; 2)~; ~k = 3~; sau khi sắp xếp giảm dần, dãy trở thành ~(3; 2; 1)~, giá trị lớn thứ ~3~ của dãy là ~1~.

Dữ liệu

• Dòng ~1~: chứa hai số nguyên ~𝑛, 𝐾 (1 ≤ 𝐾 ≤ 𝑛 ≤ 500 000)~;
• Dòng ~2~: chứa 𝑛 số nguyên ~p_1; p_2; … ;p_n~ là một hoán vị của ~\{1; 2; … ; 𝑛\}~.

Kết quả

• Ghi trên ~n - k + 1~ dòng, mỗi dòng là câu trả lời tương ứng với ~i = k, k + 1, … , n~.

Giới hạn

• Subtask ~1~: ~18\%~ số điểm có ~𝑛 = 2~;
• Subtask ~2~: ~22\%~ số điểm có ~𝑝_1 > 𝑝_2 > ⋯ > 𝑝_𝑛~;
• Subtask ~3~: ~20\%~ số điểm có ~𝑛 ≤ 1000~;
• Subtask ~4~: ~25\%~ số điểm có ~𝑛 ≤ 8000~;
• Subtask ~5~: ~15\%~ số điểm còn lại không có thêm ràng buộc bổ sung.

Sample Input 1

2 1
1 2

Sample Output 1

1
2

Explannation 1

• Với ~i=2~, giá trị lớn thứ hai trong dãy ~(1; 3)~ là ~1~;
• Với ~i=3~, giá trị lớn thứ hai trong dãy ~(1; 3; 2)~ là ~2~;

Sample Input 2

3 2
1 3 2

Sample Output 2

1
2

Explannation 2

• Với ~i=2~, giá trị lớn thứ hai trong dãy ~(1; 3)~ là ~1~;
• Với ~i=3~, giá trị lớn thứ hai trong dãy ~(1; 3; 2)~ là ~2~;

Cho một cây vô hướng gồm ~n~ đỉnh. Đỉnh thứ ~i~ có giá trị là ~a_i~.

Hai đỉnh ~u~ và ~v~ được gọi là chung nhóm nếu như giá trị ~a_u~ và ~a_v~ của chúng có chung số lượng bit ~1~. Ví dụ, nếu ~a_u = 6 = (110)_2~ và ~a_v = 9 = (1001)_2~ thì chúng chung nhóm do cùng có ~2~ bit ~1~. Ngược lại nếu cặp giá trị là ~(7,8)~ thì không.

Hãy tìm ra khoảng cách dài nhất giữa hai đỉnh bất kì chung nhóm, biết rằng độ dài đường đi từ ~u~ tới ~v~ chính bằng số cạnh trên đường đi đơn từ ~u~ tới ~v~.

Input

• Dòng đầu chứa hai số nguyên ~n~ ~(1 \le n \le 2 \times 10^5)~.
• Dòng thứ hai gồm ~n~ số nguyên dương miêu tả giá trị dãy ~a~, ~(a_i \le n)~.
• ~n-1~ dòng tiếp theo, mỗi dòng gồm hai số nguyên ~u~, ~v~ miêu tả cạnh của cây.

Output

• In ra kết quả của bài toán.

Sample Input 1

4
4 3 2 2
2 1
2 3
2 4

Sample Output 1

2

Bác John dạo này lười đến nỗi không muốn bảo trì các con đường dẫn bác đến thăm ~N\ (5 \le N \le 10.000)~ cánh đồng (đánh số từ 1 đến ~N~) nữa. Mỗi cánh đồng là nơi ở của một cô bò. Bác John có kế hoạch loại bỏ nhiều nhất ~P\ (N-1 \le P \le 100,000)~ con đường sao cho các cánh đồng vẫn liên thông.

Bạn phải xác định ~N-1~ con đường cần giữ lại.

Đường nối hai chiều ~j~ nối giữa cánh đồng ~S_j~ và ~E_j~ ~(1 \le S_j \le N; 1 \le E_j \le N;~ ~S_j \neq E_j)~ và cần ~L_j (0 \le Lj \le 1000)~ thời gian để di chuyển. Không có hai cánh đồng nào được nối trực tiếp bởi nhiều hơn một con đường.

Đàn bò buồn vì hệ thống giao thông của chúng sắp bị rút gọn. Bạn phải thăm mỗi cô bò ít nhất một lần trong ngày để động viên. Mỗi lần thăm cánh đồng ~i~ (dù chỉ đi ngang qua), bạn phải trò chuyện với cô bò trong thời gian ~C_i\ (1 \le C_i \le 1000)~.

Bạn sẽ nghỉ lại đêm trên cùng một cánh đồng (bạn sẽ được chọn) cho đến khi đàn bò đều đã hết bị suy sụp. Bạn sẽ trò chuyện với cô bò trong cánh đồng mà bạn nghỉ lại ít nhất 2 lần vào buổi sáng thức dậy và vào buổi tối khi trở về nghỉ.

Giả dụ bác John theo lời khuyên của bạn giữ lại một số con đường và bạn sẽ chọn cánh đồng tối ưu nhất để nghỉ lại, hãy xác định thời gian nhỏ nhất bạn cần để thăm tất cả đàn bò ít nhất một lần trong ngày.

Input

• Dòng 1: Hai số nguyên ~N~ và ~P~ cách nhau bởi khoảng trắng
• Dòng ~2..N+1~: Dòng ~i+1~ chứa một số nguyên duy nhất ~C_i~
• Dòng ~N+2..N+P+1~: Dòng ~N+j+1~ chứa ba số nguyên phân biệt: ~S_j, E_j~ và ~L_j~

Output

• Một số nguyên duy nhất, tổng thời gian cần để thăm tất cả đàn bò (bao gồm hai lần thăm cô bò ở nơi mà bạn nghỉ).

Sample Input 1

5 7
10
10
20
6
30
1 2 5
2 3 5
2 4 12
3 4 17
2 5 15
3 5 6
4 5 12

Sample Output 1

176