P/S: Nếu có nhiều xâu con chung cùng độ dài và dài nhất, hãy in ra xâu cuối cùng tìm thấy

Cho 2 số nguyên dương n,m và 2 dãy lần lượt gồm n và m phần tử .

Yêu cầu: Hãy tìm dãy con chung dài nhất của 2 dãy số trên

Dữ liệu vào

• Dòng 1: Ghi 2 số nguyên ~n,m~.(~0 < n,m ≤ 1000~)
• Dòng 2. Ghi n số nguyên ~a_1,a_2,....a_n~.
• Dòng 3. Ghi m số nguyên ~b_1,b_2,....b_m~.

(~0< a_i,b_i ≤ 32000~)

Dữ liệu ra

• Dòng 1. Ghi số nguyên k là độ dài dãy con chung dài nhất.

Ví dụ

Input

4 5
1 2 3 4
1 6 3 8 4

Output

3

P/S: Ở ví dụ trên ta tìm được dãy chung dài nhất gồm 3 phần tử là: 1 3 4

Output:

• Dòng 1: Ghi số nguyên s là số lượng các phần tử của dãy con tìm được
• Dòng 2: Ghi s số nguyên là các phần tử trong dãy con tìm được.

Example

Input:

10
10 100 20 1 2 50 70 80 3 60

Output:

5
1 2 50 70 80

Cho một dãy số nguyên dương ~a_1, a_2,... a_N, 0 \le a_i \le 32000~. Hãy tỉa bớt một số ít nhất các phần tử của dãy số nguyên đó và giữ nguyên thứ tự các phần tử còn lại sao cho dãy số còn lại là một dãy chỉ bao gồm các số nguyên tố tăng dần. Ta gọi dãy số nguyên tố tăng dần còn lại sau khi đã tỉa bớt một số phần tử là dãy con của dãy đã cho.

Input:

- Dòng đầu ghi số N là số phần tử (1 ≤ N ≤ 10000)
- Dòng tiếp theo ghi N số là các số nguyên của dãy.

Output:

- Dòng 1: Ghi số nguyên số lượng phần tử của dãy con cực đại.
- Dòng 2: Ghi các phần tử trong dãy con đó (theo thứ tự tăng dần), mỗi phần tử cách nhau ít nhất 1 dấu cách.

Example

Input:

10
2 100 3 1 2 50 7 80 13 60

Output:

4
2 3 7 13

Cho n viên đá, viên đá thứ i có độ cao là ~h_i~. Con ếch đang đứng tại viên đá thứ nhất. Tại vị trí thứ i con ếch có thể nhảy sang hòn đá thứ i + 1 hoặc hòn đá thứ i + 2 với chi phí nhảy là |~h_i - h_j~| với j là vị trí đáp của chú ếch.

Yêu cầu: Hãy tìm chi phí ngắn nhất để chú ếch tới được hòn đá thứ n.

Input

• Dòng đầu gồm n là số lượng hòn đá ~(1 \le n \le 10^5)~
• Dòng sau gồm n số, số thứ i thể hiện hi là chiều cao của viên đá thứ i ~(1 \le h_i \le 10^4)~

Output

• Gồm một dòng duy nhất là đáp án cần tìm

Examples

Input

4
10 30 40 20

Output

30

Input

2
10 10

Output

0

Cho n viên đá, viên đá thứ i có độ cao là ~h_i~. Con ếch đang đứng tại viên đá thứ nhất. Tại vị trí thứ i con ếch có thể nhảy sang 1 trong k hòn đá thứ i + 1, i + 2,...,i + k với chi phí nhảy là ~|h_i - h_j|~ với j là vị trí đáp của chú ếch.

Yêu cầu: Hãy tìm chi phí ngắn nhất để chú ếch tới được hòn đá thứ n.

Input

• Dòng đầu gồm n là số lượng hòn đá và số k ~(1 \le n \le 10^5, 1 \le k \le 100)~
• Dòng sau gồm n số, số thứ i thể hiện hi là chiều cao của viên đá thứ i ~(1 \le hi \le 10^4)~

Output

• Gồm một dòng duy nhất là đáp án cần tìm

Examples

Input

5 3
10 30 40 50 20

Output

30

Input

3 1
10 20 10

Output

20

Note

Ở ví dụ 1 chú ếch sẽ nhảy 1 -> 2 -> 5 với chi phí là |10 - 30| + |30 - 20| = 30

Có N người sắp hàng mua vé dự buổi hoà nhạc. Ta đánh số họ từ 1 đến N theo thứ tự đứng trong hàng. Mỗi người cần mua một vé, song người bán vé được phép bán cho mỗi người tối đa hai vé. Vì thế, một số người có thể rời hàng và nhờ người đứng trước mình mua hộ vé. Biết ti là thời gian cần thiết để người i mua xong vé cho mình. Nếu người i + 1 rời khỏi hàng và nhờ người i mua hộ vé thì thời gian để người thứ i mua được vé cho cả hai người là ri.

Yêu cầu: Xác định xem những người nào cần rời khỏi hàng và nhờ người đứng trước mua hộ vé để tổng thời gian phục vụ bán vé là nhỏ nhất.

Input

• Dòng đầu tiên chứa số N ~(1 \le N \le 10^5)~.
• Dòng thứ 2 ghi N số nguyên dương t1, t2, ..., tN. ~(1 \le t_i \le 30000)~
• Dòng thứ ba ghi N - 1 số nguyên dương ~r_1, r_2, ..., r_{N - 1}. (1 \le r_i \le 30000)~

Output

• Gồm một dòng duy nhất là đáp án cần tìm

Examples

Input

5
2 5 7 8 4
4 9 10 10

Output

18

Input

4
5 7 8 4
50 50 50

Output

24

Bờm chơi trò chơi điện tử Lucky Luke đến màn phải điều khiển Lucky leo lên một cầu thang gồm n bậc. Các bậc thang được đánh số từ 1 đến n từ dưới lên trên. Lucky có thể đi lên một bậc thang, hoặc nhảy một bước lên hai bậc thang. Tuy nhiên một số bậc thang đã bị thủng do cũ kỹ và Lucky không thể bước chân lên được. Biết ban đầu, Lucky đứng ở bậc thang số 1 (bậc thang số 1 không bao giờ bị thủng). Chơi đến đây, Bờm chợt nảy ra câu hỏi: có bao nhiêu cách để Lucky leo hết được cầu thang? (nghĩa là leo đến bậc thang thứ n). Bờm muốn nhờ bạn trả lời câu hỏi này.

Input

• Dòng đầu tiên: gồm 2 số nguyên n và k, là số bậc của cầu thang và số bậc thang bị hỏng ~(0 \le k < n \le 10^5)~.
• Dòng thứ hai: gồm k số nguyên cho biết chỉ số của các bậc thang bị hỏng theo thứ tự tăng dần.

Output

• In ra phần dư của số cách Lucky leo hết cầu thang khi chia cho 14062008

Examples

Input

4 2
2 3

Output

0

Input

90000 1
49000

Output

4108266

Hôm nay Bờm đến thăm nhà A Phủ. A Phủ ở nhà sàn, để lên nhà A Phủ phải đi bằng cầu thang. Cầu thang nhà A Phủ có ~N~ bậc, trong đó có ~K~ bậc đã bị mục nên không thể bước lên được (nhà A Phủ rất nghèo, từ ngày cấm trồng cây anh túc thì nhà A Phủ sống rất khó khăn).

Chú ý:

• Bậc thứ ~N~ là sàn nhà A Phủ, bậc này không bị hỏng.

• Đường mệt nên Bờm chỉ có thể bước mỗi lần 1 hoặc 2 bậc mà thôi.

Vừa định bước lên cầu thang thì Bờm chợt nảy ra một câu hỏi: 👉 Có bao nhiêu cách bước từ sân lên nhà A Phủ?

Các em hãy tính giúp Bờm nhé!

Input

• Dòng đầu chứa hai số nguyên dương ~N~ và ~K~ cách nhau bởi một dấu cách; • Dòng thứ hai chứa K số nguyên dương ~b_1,b_2,...,b_K~, là chỉ số các bậc thang bị hỏng, mỗi số cách nhau bởi một dấu cách.

Giới hạn: ~1 ≤ N ≤ 10^5~, ~0 ≤ K ≤ N~, ~1 ≤ b_i <N~ </p>

Output:

• Một số nguyên duy nhất là số cách bước lên nhà A Phủ (do số cách có thể rất lớn nên ta chỉ lấy phần dư khi chia cho ~10^9+7~).

Example:

Input

5 1
2

Output

2

Cho một hình chữ nhật kích thước 2xN. Hãy đếm số cách lát các viên gạch nhỏ kích thước 1x2 và 2x1 vào hình trên sao cho không có phần nào của các viên gạch nhỏ thừa ra ngoài, cũng không có vùng diện tích nào của hình chữ nhật không được lát.

Input

• Gồm nhiều test, dòng đầu ghi số lượng test T ~(T \le 10^6)~.
• T dòng sau mỗi dòng ghi một số N ~(1 \le N \le 10^6)~.

Output

• Gồm T là T kết quả cần tìm chia dư cho ~10^9 + 7~

Example

Input

3
1
2
3

Output

1
2
3

Cho một dãy các số nguyên A có N phần tử, hãy tìm đoạn con gồm các phần tử liên tiếp có tổng lớn nhất của dãy A này.

Input:

• Dòng đầu chứa số N.
• Dòng thứ 2 chứa N số, là miêu tả dãy A.

Output:

• Tổng của đoạn con có tổng lớn nhất tìm được.

Example:

Input

6
1 2 3 -1 -1 -1

Output

6

Constraint:

~0 < N \le 10^5; |A_i| \le 10^9~

Nhà trường có một phòng hội trường. Có những yêu cầu muốn sử dụng phòng hội trường này, mỗi yêu cầu cho biết thời điểm bắt đầu và thời điểm kết thúc. Nhà trường có thể chấp nhận hoặc từ chối đối với một yêu cầu.

Yêu cầu: hãy giúp nhà trường chọn các yêu cầu sử dụng hội trường sao cho tổng thời gian hội trường được sử dụng là lớn nhất.

Input:

• Dòng đầu tiên chứa một số nguyên dương ~N(N \le 10000)~ số yêu cầu.

• Mỗi dòng trong số N dòng tiếp theo chứa 2 số nguyên dương p và k ~(0 \le p < k \le 30000)~, mô tả một yêu cầu bắt đầu tại thời điểm p và kết thúc tại thời điểm k.

Output:

• Gồm một dòng duy nhất là tổng thời gian lớn nhất mà hội trường được sử dụng

Example:

Input:

12
1 2
3 5
0 4
6 8
7 13
4 6
9 10
9 12
11 14
15 19
14 16
18 20

Output:

16

Trung tâm tính toán hiệu năng cao nhận được đơn đặt hàng của n khách hàng. Khách hàng i muốn sử dụng máy trong khoảng thời gian từ ~a_i~ đến ~b_i~ và trả tiền thuê là ~c_i~.

Yêu cầu: Hãy bố trí lịch thuê máy để tổng số tiền thu được là lớn nhất mà thời gian sử dụng máy của 2 khách hàng bất kì được phục vụ đều không giao nhau (cả trung tâm chỉ có một máy cho thuê).

Input

• Dòng đầu tiên chứa một số nguyên dương n (~n \le 10^4~)
• Mỗi dòng trong số n dòng tiếp theo, dòng thứ i chứa 3 số nguyên dương ~a_i, b_i, c_i (0 \le a_i < b_i \le 10^5, 1 \le c_i \le 10^5)~

  Output

Gồm một dòng duy nhất là tổng số tiền thu được lớn nhất

Examples

Input

3
4 11 10
1 5 4
5 10 5

Output

10

Input

4
4 11 1
1 5 1
5 10 1
1 100 1

Output

2

Vườn zayzen123 có một cây khế ngọt, năm lần bảy lượt chim thần cứ đến xin khế, hôm qua chim thần lại đến. Lần này chim thần chở zayzen123 đến đảo đá quý. Trên hòn đảo bây giờ chỉ còn N loại đá quý. Loại thứ i có trọng lượng là ~w_i~ có giá trị là ~v_i~. zayzen123 mang theo túi "mười lăm" gang có thể chứa tối đa trọng lượng là M. Hỏi tổng giá trị tối đa của các viên đá quý mà zayzen123 có thể mang về là bao nhiêu, biết rằng zayzen123 chỉ được phép lấy mỗi loại một viên?

Input:

• Dòng đầu tiên ghi hai số N và M ~(1 ≤ N,M ≤ 1000)~.

• N dòng tiếp theo, dòng thứ i ghi ba số ~w_i , v_i~ lần lượt là trọng lượng, giá trị và số lượng của loại đá quý thứ i ~(0 ≤ w_i, v_i ≤ 10^3)~

Output:

• Ghi ra một số nguyên duy nhất là tổng giá trị lớn nhất mà zayzen123 em có thể mang về.

Example:

input

3 50
10 60
20 100
30 120

output

220

Khác với lần trước, lần này chim thần chở zayzen123 đến một hòn đảo khác với vô số đá quý. Trên hòn đảo bây giờ có N loại đá quý. Loại thứ i có trọng lượng là ~w_i~ có giá trị là ~v_i~ và có số lượng là ~a_i~. Lần này Zayzen123 mang theo túi "năm trăm gang" có thể chứa tối đa trọng lượng là M. Hỏi tổng giá trị tối đa của các viên đá quý mà zayzen123 có thể mang về là bao nhiêu?

Input:

• Dòng đầu tiên ghi hai số N và M ~(1 ≤ N,M ≤ 1000)~.

• N dòng tiếp theo, dòng thứ i ghi ba số ~w_i , v_i , a_i~ lần lượt là trọng lượng, giá trị và số lượng của loại đá quý thứ i ~(0 ≤ w_i, v_i , a_i ≤ 10^3)~

Output:

• Ghi ra một số nguyên duy nhất là tổng giá trị lớn nhất mà zayzen123 em có thể mang về.

Example:

input

3 4 
1 4 2 
2 7 2 
3 6 1   

output

15

Năm lần bảy lượt chim thần đến nhà Zayzen123 để xin khế. Lần này trên cây chỉ còn 1 quả cuối cùng. Zayzen123 muốn giữ lại để chấm muối ớt vì từ đầu mùa đến giờ đã có quả nào bỏ vào bụng đâu. Khóc lóc, van xin một hồi lâu, cuối cùng Zayzen123 cũng xiêu lòng và đem quả khế cuối cùng cho chim thần. Lần này chim thần trả công cho Zayzen123 rất hậu hĩnh, chim thần chở zayzen123 đến một hòn đảo khác với vô số đá quý. Trên hòn đảo bây giờ có N loại đá quý. Loại thứ i có trọng lượng là ~w_i~ có giá trị là ~v_i~ và có số lượng mỗi loại nhiều vô kể. Khác với lần trước, lần này Zayzen123 mang theo túi "năm trăm gang" có thể chứa tối đa trọng lượng là M. Hỏi tổng giá trị tối đa của các viên đá quý mà zayzen123 có thể mang về là bao nhiêu? Biết rằng, zayzen1234 có thể chọn 1 loại đá quý với số lượng tuỳ thích.

Input:

• Dòng đầu tiên ghi hai số N và M ~(1 ≤ N,M ≤ 1000)~.

• N dòng tiếp theo, dòng thứ i ghi hai số ~w_i , v_i~ lần lượt là trọng lượng và giá trị của loại đá quý thứ i ~(0 ≤ w_i, v_i ≤ 10^3)~

Output:

• Ghi ra một số nguyên duy nhất là tổng giá trị lớn nhất mà zayzen123 em có thể mang về.

Example:

input

5 15
12 4
2 2
1 1
1 2
4 10

output

36

Dãy số nguyên ~a_1, a_2,…,a_n~ được gọi là dãy lõm nếu nó tăng dần từ ~a_1~ tới ~a_i~ nào đó, rồi giảm dần tới ~a_n~.

Ví dụ: dãy 2 4 5 4 3 1 là dãy lõm.

W là 1 dãy các số nguyên dương. Nó có các đặc điểm sau:

• Độ dài của dãy là 1 số lẻ: ~L = 2 * N + 1~

• ~N + 1~ số nguyên đầu tiên của dãy tạo thành 1 dãy tăng

• ~N + 1~ số nguyên cuối của dãy tạo thành 1 dãy giảm

• Không có 2 số nguyên nào cạnh nhau trong dãy có giá trị bằng nhau

Ví dụ: 1, 2, 3, 4, 5, 4, 3, 2, 1 là 1 dãy W độ dài 9. Tuy nhiên, dãy 1, 2, 3, 4, 5, 4, 3, 2, 2 không là 1 dãy W

Yêu cầu: Trong các dãy con của dãy số cho trước, tìm dãy W có độ dài dài nhất.

Input

• Dòng 1: số nguyên dương ~N(N \le 10^3)~, độ dài dãy số.
• Dòng 2: N số nguyên dương ~a_i (a_i ≤ 10^9)~.

Output

• Ghi 1 số nguyên dương duy nhất là độ dài dãy W dài nhất.

Examples

Input

10
1 2 3 4 5 4 3 2 1 10

Output

9

Input

19
1 2 3 2 1 2 3 4 3 2 1 5 4 1 2 3 2 2 1

Output

9

Ràng buộc:

• ~(1 ≤ N,M ≤ 1000; 0 ≤ u_i, k_i ≤ 10^3)~

Người ta định nghĩa: Một xâu được gọi là xâu đối xứng (palindrome) nếu như xâu đó đọc từ trái sang phải hay đọc từ phải sang trái đều như nhau. Cho một xâu ~S~, người ta định nghĩa một xâu con của ~S~ là xâu thu được khi xóa đi một số kí tự từ xâu ~S~ ban đầu.

Yêu cầu: Hãy tìm số kí tự ít nhất cần xoá để xâu con của ~S~ là xâu đối xứng ?

Input

• Dòng 1: Chứa xâu ~S~ chỉ gồm các chữ cái in thường, giới hạn độ dài không quá ~2000~.

Output

• Dòng 1: Ghi ra số lượng ký tự cần xoá ít nhất để thu được xâu con đối xứng trích từ xâu S.

Example

Input:

lmevxeyzl

Output:

4

Cho dãy ~A~ gồm 8 số nguyên có giá trị từ 1 đến 8. Có 2 phép biến đổi trên dãy số này: Phép quay trái ~L~ và phép quay phải ~R~. Phép biến đổi ~L~ là dời số trong dãy từ phải sang trái, số đầu dãy chuyển đến vị trí cuối dãy.

Ví dụ: Dãy A: 12345678, trạng thái dãy sau khi biến đổi ~L~ => 23456781 Tương tự, phép biến đổi R dời số trong dãy từ trái sang phải, số cuối dãy chuyển đến vị trí đầu dãy.

Ví dụ: Dãy ~A~: 12345678, trạng thái dãy sau khi biến đổi ~R~ => 81234567

Yêu cầu: Cho một dãy các phép biến đổi, sau khi thực hiện tuần tự các biến đổi đã cho, dãy ~A~ có trạng thái mới, biến đổi thành dãy ~B~. Hãy xác định dãy ~B~.

Dữ liệu vào:

• Gồm 1 hàng gồm các kí tự ~L~, ~R~ biểu diễn dãy tuần tự các phép biến đổi cho trước, chiều dài không quá ~10^6~ kí tự.

Dữ liệu ra:

• Ghi 1 dòng biểu diễn dãy ~B~ với các số viết liền nhau.

Ví dụ:

Input

RRRRRRR

Output

23456781

Ràng buộc:

• 30% test thỏa dãy kí tự ~L~, ~R~ dài không quá 4 kí tự.
• 40% test thỏa dãy kí tự ~L~, ~R~ dài không quá 50 kí tự.
• 30% test thỏa dãy kí tự ~L~, ~R~ dài không quá 250 kí tự.

Nhân dịp kỷ niệm ngày thành lập Đoàn thanh niên cộng sản Hồ Chí Minh, lớp bạn Tèo có tổ chức đi cắm trại ở khu du lịch sinh thái. Lớp của Tèo có N bạn, trong đó bạn thứ i được đánh giá có độ vui vẻ là 1 số nguyên ~a_i~. Để thuận tiện cho việc quản lý và phân công nhiệm vụ, cô giáo yêu cầu bạn Tèo chọn ra 1 nhóm bạn trong lớp có tổng độ vui vẻ là K.

Yêu cầu: Hãy giúp bạn Tèo tính xem có bao nhiêu cách chọn từ trong lớp một nhóm bạn có tổng độ vui vẻ đúng bằng K theo yêu cầu của cô giáo.

Lưu ý: Mỗi người cũng được xem như 1 nhóm bạn.

Input:

• Dòng đầu tiên: chứa 2 số nguyên N, K được ghi cách nhau 1 ký tự trắng.~( 1\le N \le 25, -10^5 \le K \le 10^5)~
• Dòng tiếp theo chứa N số nguyên ~a_i~ là độ vui vẻ của bạn thứ i ~(1 \le i \le N)~; các số lần lượt ghi cách nhau 1 ký tự trắng. ~(-10^4 \le a_i \le 10^4)~

Output:

• Ghi ra một số nguyên duy nhất là số cách chọn một nhóm bạn có tổng độ vui vẻ bằng k.

Example:

Input:

5  4 
2 3 2 4 2

Output:

4

Cho dãy ~a~ gồm ~n~ số ~a_1, a_2, ..., a_n~, hãy đếm số lượng dãy con có tổng là ~S~, vì đáp án có thể rất lớn hãy in chia dư cho ~10^9 + 7~

Input

• Dòng đầu gồm ~n~ và ~S~ (~1 ≤ n ≤ 100, 1 ≤ S ≤ 1000~)
• Dòng tiếp theo gồm ~n~ số, số thứ ~i~ là giá trị của ~a_i~ (~1 ≤ a_i ≤ S~)

Output

• Gồm một dòng duy nhất là đáp án cần tìm

Example

Input

3 2
1 1 1

Output

3

Cho ~n~ số nguyên ~a_i~. Hãy lập trình tìm ra độ dài dãy con đối xứng dài nhất. Lưu ý: Dãy con đối xứng có thể không liên tiếp nhau.

Input

• Dòng 1: Là số nguyên ~n~ (~1 \le n \le 10^3~)

• Dòng 2: Là ~n~ số nguyên ~a_i~ (~|a_i| \le 10^4~).

Output

• Là độ dài dãy con đối xứng dài nhất.

Ví dụ:

Input

8
1 2 3 3 2 1 5 7

Output

6