Cho một dãy số ~A~ gồm ~N~ số nguyên ~A_1, A_2, \ldots, A_N~. Hãy tìm dãy con tăng dài nhất thuộc dãy ~A~.

Một dãy con tăng độ dài ~k~ thuộc dãy ~A~ có dạng là dãy ~A_{i_1}, A_{i_2}, A_{i_3}, \ldots, A_{i_{k - 1}}, A_{i_k}~ với

• ~1 \leq i_1 < i_2 < \ldots < i_k \leq N~;
• ~A_{i_1} < A_{i_2} < \ldots < A_{i_k}~.

Input

• Dòng thứ nhất gồm một số nguyên dương ~N~ - kích thước dãy ~A~ (~1 \leq N \leq 10^3~)
• Dòng thứ hai gồm ~N~ số nguyên ~A_1, A_2, \ldots, A_N~ (~|A_i| \leq 10^3~).

Output

• Dòng thứ nhất in ra độ dài của dãy con tăng dài nhất của dãy ~A~.
• Dòng thứ hai in ra các vị trí trong dãy ~A~ của các phần tử thuộc dãy con nói trên, các số tăng dần và cách nhau ít nhất ~1~ khoảng trắng. Nếu có nhiều dãy con thoả mãn, in ra các vị trí có thứ tự từ điển nhỏ nhất.

Sample Test 1

Input:

8
2 -1 1 4 1 -5 2 3

Output:

4
2 3 7 8

Sample Test 2

Input:

5
1 2 -10 0 3

Output

3
1 2 5

Một phòng họp do bạn quản lý được ~N~ cuộc họp đặt lịch. Cuộc họp thứ ~i~ có thời gian bắt đầu là ~A_i~ và kết thúc tại thời điểm ~B_i~ (~A_i < B_i~). Hai cuộc họp không thể cùng đồng thời diễn ra, nói cách khác cuộc họp thứ ~j~ chỉ có thể được bố trí sau cuộc họp thứ ~i~ nếu ~B_j \leq A_i~.

Là người quản lý phòng họp, bạn hãy sắp xếp lịch để bố trí nhiều cuộc họp diễn ra nhất có thể.

Input

• Dòng thứ nhất gồm một số nguyên dương ~N~ (~1 \leq N \leq 10^3~).
• Trong ~N~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên dương ~A_i~ và ~B_i~ (~A_i < B_i \leq 10^3~).

Output

• In ra số lượng cuộc họp nhiều nhất có thể bố trí.

Sample Test

Input:

5
1 2
3 7
2 5
4 6
6 8

Output:

3

Note:

• Chọn cuộc họp ~1, 3, 5~.

Một phòng họp do bạn quản lý được ~N~ cuộc họp đặt lịch. Cuộc họp thứ ~i~ có thời gian bắt đầu là ~A_i~, kết thúc tại thời điểm ~B_i~ và trả tiên thuê là ~C_i~ (~A_i < B_i~). Hai cuộc họp không thể cùng đồng thời diễn ra, nói cách khác cuộc họp thứ ~j~ chỉ có thể được bố trí sau cuộc họp thứ ~i~ nếu ~B_j \leq A_i~.

Là người quản lý phòng họp, bạn hãy sắp xếp lịch bố trí các cuộc họp để thu được lợi nhuận lớn nhất có thể.

Input

• Dòng thứ nhất gồm một số nguyên dương ~N~ (~1 \leq N \leq 10^3~).
• Trong ~N~ dòng tiếp theo, dòng thứ ~i~ chứa ba số nguyên dương ~A_i, B_i, C_i~ (~A_i < B_i; B_i, C_i \leq 10^3~).

Output

• In ra lợi nhuận lớn nhất có thể thu được.

Sample Test

Input:

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

Output:

7

Note:

• Chọn cuộc họp ~1, 2, 5~.

Cho một dãy số ~A~ gồm ~N~ số nguyên ~A_1, A_2, \ldots, A_N~. Hãy tìm dãy con đổi dấu dài nhất thuộc dãy ~A~.

Một dãy con đổi dấu độ dài ~k > 1~ thuộc dãy ~A~ có dạng là dãy ~A_{i_1}, A_{i_2}, A_{i_3}, \ldots, A_{i_{k - 1}}, A_{i_k}~ với các điều kiện sau:

• Các phần tử liên tiếp khi so sánh lần lượt "đổi dấu" liên tục: ~A_{i_1} < A_{i_2}, A_{i_2} > A_{i_3}, A_{i_3} < A_{i_4}, \ldots~ hoặc ~A_{i_1} > A_{i_2}, A_{i_2} < A_{i_3}, A_{i_3} > A_{i_4}, \ldots~;
• Các phần tử có chỉ số tăng dần và cách nhau ít nhất ~L~ đơn vị: ~i_2 - i_1 \geq L~, ~i_3 - i_2 \geq L, \ldots, i_k - i_{k - 1} \geq L~;
• Các phần tử liên tiếp có chênh lệch không quá ~U~: ~|A_{i_1} - A_{i_2}| \leq U, |A_{i_2} - A_{i_3}| \leq U, \ldots, |A_{i_{k - 1}} - A_{i_k}| \leq U~.

Dãy gồm một phần tử cũng được coi là một dãy đổi dấu.

Input

• Dòng thứ nhất gồm 3 số nguyên dương ~N, L, U~ (~L < N \leq 10^3~, ~U \leq 10^3~)
• Dòng thứ hai gồm ~N~ số nguyên ~A_1, A_2, \ldots, A_N~ (~|A_i| \leq 10^3~).

Output

• In ra độ dài của dãy con đan dấu dài nhất.

Sample Test 1

Input:

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

Output:

3

Note

• Chọn dãy con ~-1, 1, 3~ (vị trí ~2, 5, 8~).

Một đêm nọ, một tên trộm nọ quyết định đột nhập vào một siêu thị nọ. Siêu thị có ~N~ đồ vật, vật thứ ~i~ có trọng lượng ~A_i~, giá trị ~B_i~. Tên trộm mang theo một cái túi chứa được trọng lượng tối đa ~W~. Hỏi tổng giá trị tối đa tên trộm có thể lấy được là bao nhiêu?

Input

• Dòng thứ nhất gồm hai số nguyên dương ~N~ và ~W~ (~1 \leq N, W \leq 10^3~).
• Trong ~N~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên dương ~A_i~ và ~B_i~ (~A_i, B_i \leq 10^3~).

Output

• In ra tổng giá trị lớn nhất có thể được lấy đi.

Sample Test

Input:

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

Output:

15

Cho một dãy số ~A~ gồm ~N~ số nguyên dương ~A_1, A_2, \ldots, A_N~ và một số nguyên dương ~S~. Hãy tìm ~1~ dãy con có tổng ~S~ thuộc dãy ~A~.

Một dãy con tổng ~S~ thuộc dãy ~A~ có dạng là dãy ~A_{i_1}, A_{i_2}, A_{i_3}, \ldots, A_{i_{k - 1}}, A_{i_k}~ với

• ~1 \leq i_1 < i_2 < \ldots < i_k \leq N~;
• ~A_{i_1} + A_{i_2} + \ldots + A_{i_k} = S~.

Input

• Dòng thứ nhất gồm hai số nguyên dương ~N~ và ~S~ (~N, S \leq 10^3~)
• Dòng thứ hai gồm ~N~ số nguyên dương ~A_1, A_2, \ldots, A_N~ (~A_i \leq 10^3~).

Output

• Nếu dãy con tổng ~S~ tổn tại, in ra các chỉ số trong ~A~ của phần tử thuộc dãy con đó. Nếu có nhiều dãy con thoả mãn thì in ra các chỉ số có thứ tự từ điển nhỏ nhất. Ngược lại, nếu không có dãy con thoả mãn thì in ra Does not exist.

Sample Test 1

Input:

5 7
1 3 5 9 3

Output:

1 2 5

Sample Test 2

Input:

4 17
1 3 5 7

Output:

Does not exist

Có ~N~ gói kẹo, gói thứ ~i~ chứa ~A_i~ viên kẹo. Hãy chia các gói thành ~2~ phần sao cho chênh lệch số viên kẹo giữa 2 phần là ít nhất.

Input

• Dòng thứ nhất gồm một số nguyên dương ~N~ (~1 \leq N \leq 100~).
• Dòng tiếp theo chứa ~N~ số ~A_1, A_2, \ldots, A_N~ (~A_i \leq 50~).

Output

• In ra chênh lệch nhỏ nhất số viên kẹo giữa ~2~ nhóm kẹo.

Sample Test 1

Input:

5
2 4 9 3 5

Output:

1

Cho 1 xâu nguồn ~X~ và một xâu đích ~F~. Bạn có thể thực hiện ba thao tác sau trên xâu ~X~:

• Chèn ~1~ kí tự vào sau kí tự thứ ~i~.
  • Ví dụ: ~abcd \rightarrow abecd~.
• Thay thế kí tự ở vị trí thứ ~i~ bằng kí tự C.
  • Ví dụ: ~abcd \rightarrow abce~.
• Xoá kí tự ở vị trí thứ ~i~.
  • Ví dụ: ~abcd \rightarrow abd~.

Tính số lượng thao tác ít nhất để biến đổi xâu ~X~ thành xâu ~F~.

Input

• Dòng thứ nhất chứa xâu ~X~.
• Dòng thứ hai chứa xâu ~F~.
• Hai xâu chỉ gồm các chữ cái thường và độ dài hai xâu không vượt quá ~10^3~.

Output

• In ra số lượng thao tác ít nhất.

Sample Test

Input:

abcd
bde

Output:

3

Cho ~2~ xâu ~A~ và ~B~. Tìm dãy con chung dài nhất của ~2~ xâu này.

Một dãy con của một xâu là xâu thu được sau khi xoá một số kí tự (có thể xoá ~0~ kí tự hoặc xoá toàn bộ kí tự) và giữ nguyên thứ tự của các kí tự còn lại.

Input

• Dòng thứ nhất chứa xâu ~A~.
• Dòng thứ hai chứa xâu ~B~.
• Hai xâu chỉ gồm các chữ cái thường và độ dài hai xâu không vượt quá ~10^3~.

Output

• In ra số lượng thao tác ít nhất.

Sample Test 1

Input:

bbus
uii

Output:

1

Sample Test 2

Input:

uapjhvvjlrilrkuleah
faoipjzllkluegle

Output:

9

Cho một xâu ~S~, hãy tìm số kí tự ít nhất cần thêm vào ~S~ để ~S~ trở thành xâu đối xứng.

Một xâu gọi là xâu đối xứng (palindrome) nếu xâu đó đọc từ trái sang phải hay từ phải sang trái đều như nhau.

Input

• Gồm một xâu S duy nhất chứa các kí tự thường (~|S| \leq 1000~).

Output

• In ra số lượng kí tự ít nhất cần thêm.

Sample Test 1

Input:

bbubbs

Output:

1

Có ~n~ người xếp hàng mua vé một trận bóng theo thứ tự ~1~ đến ~n~. Mỗi người cần mua một vé, nhưng người bán vé lại có thể bán cho mỗi người tối đa hai vé. Do đó, 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 ~t_i~ là thời gian cần thiết để người thứ ~i~ mua vé cho mình. Nếu người thứ ~i+1~ rời hàng và nhờ người ~i~ mua hộ vé thì mất ~r_i~ thời gian để mua cho cả hai.

Hãy xác định thời gian mua vé nhỏ nhất.

Input

• Dòng đầu chứa số nguyên dương ~n~ ~(n \le 6*10^4)~
• Dòng thứ hai chứa ~n~ số nguyên dương miêu tả dãy ~t[1], t[2], ..., t[n]~.~(t[i] \le 30000)~
• Dòng thứ ba chứa ~n-1~ số nguyên dương miêu tả dãy ~r_[1], r_[2], ..., r_[n-1]~. ~(r[i] \le 30000)~

Output

• In ra thời gian ít nhất để mua vé cho ~n~ người.

Sample Test

Input

5
2 5 7 8 4
4 9 10 10

Output

18

Alice Margatroid cần dọn tuyết trên mái nhà. Cô sẽ dùng chọn ra ~m~ con búp bê của mình để thực hiện nhiệm vụ. Alice có ~n~ thùng đựng búp bê, thùng thứ ~i~ có ~a_i~ con, và cô muốn mỗi thùng chỉ được chọn ra tối đa 1 con búp bê. Hỏi có bao nhiêu cách để chọn ra ~m~ con búp bê.

Input

• Dòng đầu tiên gồm 2 số tự nhiên ~n, m~ ~(1 \le m \le n \le 1000)~
• Dòng tiếp theo gồm ~n~ số tự nhiên là số lượng búp bê của từng thùng. (~1 \le a[i] \le 10^9~)

Output

• Gồm 1 số tự nhiên duy nhất là số cách chọn búp bê modulo ~10^9 + 7~

Sample Test

Input:

3 2
1 2 1

Output:

5

Giải thích:

• Có 5 cách chọn là: ~\{1, 2.1\}, \{1, 2.2\}, \{1, 3\}, \{2.1, 3\}, \{2.2, 3\}~ với ~x.y~ là con búp bê thứ ~y~ của thùng thứ ~x~

Cho dãy gồm ~n~ số nguyên ~a_1, a_2, \dots, a_n~ chỉ gồm các số ~1~, ~2~ và ~3~. Đếm số cách xoá một vài phần tử của dãy (có thể không xoá) để nhận được một dãy thoả mãn hai yêu cầu sau:

1. Dãy còn ít nhất ~3~ phần tử
2. Phần tử đầu tiên của dãy có giá trị ~1~, tiếp theo là một số phần tử có giá trị ~2~ (ít nhất một số ~2~), kết thúc bằng đúng một phần tử có giá trị ~3~.

Ví dụ: các dãy ~\{1, 2, 2, 3\}~ và dãy ~\{1, 2, 3\}~ thoả mãn yêu cầu, các dãy ~\{1, 2, 3, 3\}~ và dãy ~\{1, 1, 2, 3\}~ không thoả mãn yêu cầu.

Vì số cách xoá có thể rất lớn, hãy in ra số cách xoá chia lấy dư cho ~10^9+7~.

Input

Dòng đầu chứa số nguyên ~n~ (~1 \le n \le 10^6~) là số lượng phần tử của dãy.

Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ (~1 \le a_i \le 3~) mô tả các phần tử của dãy.

Output

Gồm một dòng duy nhất chứa một số nguyên là số cách xoá thoả mãn yêu cầu đề bài, chia lấy dư cho ~10^9+7~.

Example

Input

8
1 2 1 2 3 1 2 3

Output

15

Một xâu ~S~ được gọi là xâu đối xứng nếu ~S = S'~ với ~S'~ là xâu nhận được từ xâu ~S~ khi đọc từ phải qua trái. Ví dụ: Xâu ~'aba'~ là xâu đối xứng, còn xâu ~'abc'~ là xâu không đối xứng.

Cho một xâu ~S~ gồm ~1 \le n \le 1000~ kí tự.

Yêu cầu: Hãy tìm cách chia xâu ~S~ thành ít nhất các đoạn mà mỗi đoạn đều là các xâu đối xứng.

Input

• Dòng đầu gồm một số nguyên ~n~ là độ dài của xâu ~S~.
• Dòng thứ hai là nội dung xâu ~S~.

Output

• Dòng đầu ghi một số nguyên ~k~ (số đoạn ít nhất tìm được).
• ~K~ dòng sau, mỗi dòng ghi một số nguyên ~t_i~, với ~t_i~ là vị trí kết thúc của đoạn thứ ~i~.

Sample Input 1

 8
 abbacdcb

Sample Output 1

3
4
7
8

Phát minh mới nhất của của Nitori là một chiếc máy bay ném bom điều khiển từ xa. Ba nàng tiên ánh sáng đã đặt một chiếc cho kế hoạch khủng bố đền Hakurei.

Dĩ nhiên để máy bay có thể hoạt động thì cần có pin. Mỗi cục pin có 3 thông tin: ~e_i, w_i, c_i~ lần lượt và mức năng lượng, khối lượng và giá thành. Thời gian bay của máy bay được xác định bằng công thức: ~E\over{W}~ trong đó ~E~ là tổng mức năng lượng và ~W~ là tổng khối lượng của tất cả pin và khối lượng của máy bay.

Để đảm bảo kế hoạch thành công, máy bay cần hoạt động lâu nhất có thể. Ba nàng tiên có ngân sách ~b~ và khối lượng của máy bay là ~w~, hãy giúp họ chọn pin sao cho thời gian bay là lâu nhất!

Input:

• Dòng đầu chứa số ~n,b,w (1≤n×b≤10^5,1≤w≤1000)~.

• ~n~ dòng tiếp theo mỗi dòng chứa ba số ~e_i,w_i,c_i (0≤e_i,w_i≤1000,0≤c_i≤b)~ là mức năng lượng, khối lượng và giá thành của cục pin thứ ~i~.

Output:

• In ra tổng thời gian bay của máy bay, sai số không quá ~10^{-3}~.

Sample Test:

Input:

10 1000 20
40 40 40
1 1 1
70 30 60
100 20 700
80 50 200
30 1 200
100 100 1
20 1 500
30 20 100
70 50 100

Output:

3.1707

Giới hạn

• 25% số điểm ~n≤20~.
• 25% số điểm ~w_i=0~.
• 25% số điểm ~c_1=c_2=...=c_n~.
• 25% số điểm không có ràng buộc gì thêm.

Cho một số nguyên dương ~n~, hãy phân tích số ~n~ thành tổng của một số số nguyên dương sao cho bội chung nhỏ nhất của chúng là lớn nhất có thể.

Input

• Gồm một số nguyên dương ~n~, ~(1 \le n \le 340)~

Output

• In ra bội chung nhỏ nhất tìm được.

Sample Test

Input:

10

Output:

30

Giải thích: Số ~10~ được phân tích thành tổng của ~3~ số ~{2,3,5}~, bội chung nhỏ nhất của ba số đó bằng ~30~, đây là kết quả lớn nhất có thể.