Alyona có con số yêu thích là ~k~ và vì cô còn nhỏ, ~k~ không vượt quá ~10~. Giờ đây, cô muốn chọn ~k~ ĐOẠN con không rỗng của chuỗi ~s~ sao cho các ĐOẠN này xuất hiện dưới dạng ĐOẠN con không giao nhau của chuỗi ~t~ và theo đúng thứ tự như trong chuỗi ~s~. Cô cũng quan tâm đến việc độ dài của chúng là lớn nhất có thể trong tất cả các biến thể.

Bạn cần tìm ~k~ ĐOẠN con không giao nhau và không thể rỗng trên dãy ~s~ (các ĐOẠN con cần chứa các phần tử liên tiếp nhau), sao cho cũng tồn tại ~k~ ĐOẠN con không giao nhau và không thể rỗng trên dãy ~t~ có giá trị tương tự. Bạn cần chọn ra ~k~ ĐOẠN con sao cho tổng độ dài của chúng là lớn nhất.

Note: Bạn toán này quy về đơn giản là bài toán LCS, nhưng thay vì mỗi phần tử ta lấy một kí tự, thì là lấy một đoạn con.

Input:

• Dòng đầu tiên chứa ba số nguyên dương ~n~, ~m~, ~k~ ~(1 \leq n, m \leq 1000, 1 \leq k \leq 10)~, lần lượt là độ dài của chuỗi ~s~, độ dài của chuỗi ~t~, và số yêu thích của Alyona.
• Dòng thứ hai chứa chuỗi ~s~, bao gồm các chữ cái tiếng Anh viết thường.

• Dòng thứ ba chứa chuỗi ~t~, bao gồm các chữ cái tiếng Anh viết thường.

  Output:

• In ra một số nguyên không âm duy nhất — tổng độ dài của các chuỗi trong dãy mong muốn.

Ví dụ

Input 1

5 5 1
abcde
bcdea

Output 1

4

Input 2

5 5 2
abcde
bcdea

Output 2

4

Note

Ta không thể tách ra thành a và bcde, ở dưới là bcde và a (vì cần đúng thứ tự so sánh)

Cho dãy số nguyên ~a~ gồm ~n~ phần tử. Hãy tìm cách chia dãy ~a~ ra thành ít dãy con (không nhất thiết liên tiếp) nhất, sao cho các dãy con đều là dãy không giảm và mỗi phần tử của ~a~ thuộc đúng một dãy con.

Input

• Dòng đầu tiên gồm số nguyên dương ~n~ ~(n \le 10^5)~

• Dòng thứ hai gồm ~n~ phần tử miêu tả dãy ~a~. (~a_i \le 10^9~)

  Output

• In ra số lượng dãy con ít nhất thỏa mãn.

Sample Test

Input:

4
1 5 4 6

Output:

2

Cho ~N~ đoạn gỗ, để xử lí chúng, ta cần:

• Thời gian xử lí đoạn gỗ đầu tiên là 1 phút.
• Sau khi xử lí xong đoạn gỗ có chiều dài ~l~ và trọng lượng ~w~, không mất thời gian xử lí nếu đoạn gỗ tiếp theo có chiều dài ~l'~ và trọng lượng ~w'~ thỏa mãn ~l \le l'~ và ~w \le w'~, ngược lại mất 1 phút để xử lí.

Tìm thời gian chuẩn bị ít nhất cho ~N~ đoạn gỗ.

Ví dụ có 5 đoạn: ~(9,4), (2,5), (1,2), (5,3), (4,1)~ thì thời gian ít nhất là 2 vì có thể xử lí theo thứ tự sau: ~(4,1), (5,3), (9,4), (1,2), (2,5)~.

Input

Dòng đầu là số lượng test ~T \le 100~, mỗi test gồm:

• Dòng đầu là số nguyên dương ~N \le 5000~.
• Sau đó ~N~ dòng tiếp theo gồm ~N~ cặp số nguyên dương ~(l_1,w_1), (l_2,w_2), ..., (l_N,w_N)~, ~l_i,w_i <= 10000~ là độ dài và trọng lượng khối gỗ.

Output

In ra T dòng, mỗi dòng là đáp án của test tương ứng.

Sample Test

Input:

3

5 
4 9 
5 2 
2 1 
3 5 
1 4

3 
2 2 
1 1 
2 2

3 
1 3 
2 2 
3 1

Output:

2
1
3

Trên hệ trục tọa độ ~OXY~, có ~n~ con robot, con robot thứ ~i~ ở tọa độ ~(x_i,y_i)~.

Giả sử một con robot đang ở vị trí ~(x,y)~, sau một giây, nó có thể đi tới ~4~ vị trí ~(x-1,y)~, ~(x,y-1)~, ~(x+1,y)~, ~(x,y+1)~.

Hãy tìm thời điểm ngắn nhất sao cho cả ~n~ con robot đều có thể cùng đứng ở một điểm nào đó trên hệ trục tọa độ.

Input

• Dòng đầu tiên gồm số nguyên dương ~n~ miêu tả số robot ~(1 \le n \le 3\times 10^5)~.
• ~n~ dòng sau, dòng thứ ~i~ gồm ~2~ số nguyên ~x_i,y_i~ miêu tả tọa độ ~(x_i,y_i)~ của robot thứ ~i~ ~(|x_i|,|y_i| \le 10^{18})~.

Output

• In ra thời điểm nhanh nhất để các robot cùng đứng tại một điểm.

Sample Input 1

3
0 0
0 3
3 3

Sample Output 1

3

Cho lưới ô vuông rộng vô tận, tâm của lưới ô vuông có tọa độ (0, 0). Có ~n~ ngôi nhà được xây dựng trên lưới ô vuông. Trong 1 đơn vị thời gian, người ~A~ có thể di chuyển đến các ô liền kề của lưới (8 ô liền kề). Khoảng cách giữa 2 ngôi nhà là thời gian ngắn nhất di chuyển từ nhà này đến nhà kia. Trong lúc nhàn rỗi, bạn Lương tính toán hết tất cả khoảng cách giữa 2 ngôi nhà và sắp xếp chúng thành dãy không giảm. Hãy tìm số thứ ~k~ trong dãy.

Input

• Dòng đầu tiên gồm 2 số nguyên dương ~n, k~ ~(2 \leq n \leq 10^5, k \leq \frac{n (n - 1)}{2})~.
• ~n~ dòng tiếp theo, dòng thứ ~i~ chứa 2 số nguyên ~x, y~ là tọa độ của nhà thứ ~i~ ~(|x|, |y| \leq 10^9)~.

Output

• In ra số nguyên là kết quả bài toán.

Scoring

• Subtask 1: ~\ n \leq 2000~
• Subtask 2: ~\ y_i = 0~ với mọi ~i~
• Subtask 3: ~\ k = 1~
• Subtask 4: không có dữ kiện gì thêm

Sample Input 1

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

Sample Output 1

4

Reimu cần phong ấn một cuốn sách. Cô có ~n~ lá bùa, trên lá bùa thứ ~i~ có số nguyên dương ~a_i~. Để phong ấn cuốn sách cô cần chọn một số lá bùa trong số ~n~ lá bùa sao cho tích của chúng kết thúc bằng chữ số ~d~ và để đạt được hiệu quả cao thì tích phải là lớn nhất có thể. Bạn hãy giúp cô tìm ra những lá bùa cần sử dụng nhé!

Input

• Dòng đầu gồm 2 số nguyên dương ~n, d (1 \le n \le 100000, 0 \le d \le 9).~
• Dòng tiếp theo gồm ~n~ số nguyên dương ~a_i~.

Output

• Dòng đầu tiên là số tự nhiên ~k~ là số lượng lá bùa được chọn hoặc không có cách chọn in ra ~-1~.
• Nếu có cách chọn thì dòng tiếp theo số trên những lá bùa được chọn (có thể theo thứ tự ngẫu nhiên).

Sample Test

Input:

6 3
8 9 4 17 11 5

Output:

3
9 11 17 

Nhắc lại ~F_n~ là số fibonacci thứ ~n~ với ~F_1 = F_2 = 1~.

Cho mảng ~a~ có ~n~ phần tử và ~q~ truy vấn có một trong 2 dạng sau đây:

• 1 l r, cộng thêm giá trị ~F_{i - l + 1}~ với mỗi phần tử ~l \le i \le r~.
• 2 l r, in ra ~\sum_{i=l} ^{r} a_i~ modulo ~10^9+9~.

Input

• Dòng đầu tiên gồm 2 số ~1 \le n, q \le 300000~.
• Dòng tiếp theo gồm ~n~ số tự nhiên của mảng ~a~ (~1 \le a_i \le 10^9~).

Output

• In ra kết quả của mỗi truy vấn 2.

Sample Test

Input:

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

Output:

17
12

Có ~k~ con mèo sống ở trên một cái cây do Ivan Tèo quản lý. Cái cây gồm ~n~ đỉnh được đánh số từ ~1~ tới ~n~, mỗi đỉnh chứa nhiều nhất một chú mèo.

Do lo sợ Khoi sẽ tới và ăn thịt các chú mèo của mình, Ivan Tèo quyết định thuê các robot MDuc về để bảo vệ các chú mèo. Cơ chế bảo vệ của robot MDuc rất đặc biệt, khi đặt robot ở một nút trên cây, robot ấy sẽ chỉ bảo vệ các chú mèo có khoảng cách gần nhất với cậu. MDuc cũng có thể được đặt ở chung nút với chú mèo, và trong trường hợp đó, tất nhiên anh ta sẽ chỉ bảo vệ chú mèo chung nút.

Do giá của một robot MDuc khá cao, hãy giúp Ivan Tèo tìm cách đặt ít robot nhất có thể sao cho tất cả các chú mèo đều được bảo vệ.

Input

• Dòng đầu chứa hai số nguyên ~n,k~ ~(k \le n \le 2 \times 10^5)~.
• ~n-1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u, v~ ~(1≤u,v≤n; u≠v)~ mô tả một cạnh của cây nối hai đỉnh ~u~ và ~v~.
• Dòng cuối cùng gồm ~k~ số nguyên dương phân biệt ~a_i~ là các nút có một chú mèo.

Output

• In ra số robot nhỏ nhất cần dùng.

Subtask

• Subtask ~1~: ~n \le 3\times 10^5~ và nút ~i~ nối với nút ~i+1~ trên cây. ~(20\%)~
• Subtask ~2~: ~k \le 15, n \le 3 \times 10^5~. ~(30\%)~
• Subtask ~3~: ~n \le 2000~. ~(25\%)~
• Subtask ~3~: ~n \le 3 \times 10^5~. ~(25\%)~

Sample Input 1

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

Sample Output 1

2

Explanation 1

Đặt ở đỉnh ~1~ và ~3~.