Cho một dãy ~a~ gồm ~n~ số nguyên ~a_1, a_2, a_3, \ldots, a_n~. Bạn cần thực hiện ~Q~ truy vấn thuộc một trong ~2~ loại sau:

• Truy vấn loại ~1~: Tính tổng các số nguyên từ ~l~ đến ~r~ trong dãy ~a~ ban đầu.
• Truy vấn loại ~2~: Tính tổng các số nguyên từ ~l~ đến ~r~ trong dãy ~a~ đã sắp xếp không giảm.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~ (~1 \leq n \leq 2 \times 10^5~).
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, a_3, \ldots, a_n~ (~|a_i| \leq 10^9~).
• Dòng thứ ba chứa số nguyên dương ~Q~ (~1 \leq Q \leq 10^5~) - số lượng truy vấn.
• ~Q~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~t, l, r~ biểu diễn truy vấn loại ~t~.

Output

• In ra ~Q~ dòng, mỗi dòng lần lượt chứa đáp án của mỗi truy vấn.

Sample Tests

Cho ~q~ truy vấn. Mỗi truy vấn gồm ~2~ số nguyên dương ~l~ và ~r~. Hãy đếm số lượng số nguyên tố từ ~l~ đến ~r~.

Input

• Dòng đầu tiên chứa số nguyên ~q~ (~q \leq 10^5~) - số lượng truy vấn.
• ~q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~l~ và ~r~ (~1 \leq l \leq r \leq 10^6~).

Output

• In ra ~q~ dòng, dòng thứ ~i~ chứa kết quả của truy vấn ~i~.

Sample Test

Input:

5
4 20
2 10
1 18
1 100
1 1000

Output:

6
4
7
25
168

Cho một dãy ~A~ gồm ~n~ số nguyên sắp xếp không giảm. Hãy in ra dãy mới gồm bình phương của các phần tử trong dãy ~A~ theo thứ tự không giảm.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~ (~1 \leq n \leq 10^6~).
• Dòng tiếp theo chứa các số nguyên của dãy ~A~ (~|A_i| \leq 2^{15}~).

Output

• In ra các phần tử bình phương theo thứ tự không giảm.

Sample Tests

Cho một dãy số ~A~ gồm ~N~phần tử ~A_1, A_2, ..., A_N~. Một dãy con liên tiếp từ ~L~ đến ~R~ của dãy số ~A~ là các phần tử ~A_L, A_{L+1}, ..., A_R~ ~(1 ≤ L ≤ R ≤ N)~. Cho một số nguyên dương ~T~, hãy đếm xem có bao nhiêu dãy con của ~A~có tổng các phần tử không quá ~T~.

Dữ liệu vào từ file văn bản DEMDAYCON.INP:

• Dòng đầu tiên gồm hai số nguyên dương ~N~ và ~T~ là số lượng phần tử của dãy số ~A~và số ~T~ cho trước ~(N \leq 10^6; T \leq 10^9)~.
• Dòng thứ hai gồm ~N~số nguyên dương ~A_i~ mô tả các phần tử của dãy ~A~ ~(1 ≤ i ≤ N; A_i \leq 10^9)~.

Kết quả ghi ra file văn bản DEMDAYCON.OUT:

• Một số nguyên duy nhất là số lượng dãy con thỏa mãn yêu cầu đề bài.

Ràng buộc:

• Có 50% số test tương ứng với 50% số điểm có ~N \leq 100~;
• Có 30% số test khác tương ứng với 30% số điểm có ~N \leq 5000~;
• 20% số test còn lại tương ứng với 30% số điểm không có ràng buộc gì thêm.

Ví dụ:

Khôi có một loại nước uống yêu thích, và loại nước uống này được bán tại ~N~ cửa hàng tạp hóa khác nhau, cừa hàng thứ ~i~ bán loại nước này với giá ~a_i~ đồng. Vì tài chính có hạn, nên dù khát nước đến mấy thì trong ~Q~ ngày, ngày thứ ~i~ Khôi chỉ có ~x_i~ đồng để mua nước. Khôi muốn thử hết loại nước này ở cả ~N~ cửa hàng, nên với mỗi ngày ~i~, anh ấy muốn biết mình có thể mua nước từ bao nhiêu cửa hàng khác nhau. Vì còn đang bận đu càng xà nên bạn hãy giúp Khôi nhé!

Input

• Dòng đầu chứa một số nguyên dương ~N~ ~(1 \le N \le 10^5)~.
• Dòng sau chứa ~N~ số nguyên dương ~a_1, a_2, \dots, a_N~ ~(1 \le a_i \le 10^9)~.
• Dòng tiếp chứa một số nguyên dương ~Q~ ~(1 \le Q \le 10^5)~.
• Dòng cuối cùng chứa ~Q~ số nguyên dương ~x_1, x_2, \dots, x_Q~ ~(0 \le x_i \le 10^9)~.

Output

• In ra ~Q~ số nguyên, là đáp án cho ngày thứ ~i~.

Sample Input 1

5
1 3 10 7 9
4
6 0 12 7

Sample Output 1

2 0 5 3

Notes

• Ngày đầu tiên, Khôi có thể mua nước ở cửa hàng ~1~ và ~2~, có giá lần lượt là ~1~ và ~3~.
• Ngày thứ hai, Khôi không thể mua nước ở bất kì cửa hàng nào.
• Ngày thứ ba, Khôi có thể mua nước ở tất cả cửa hàng.
• Ngày thứ tư, Khôi có thể mua nước ở cửa hàng ~1~, ~2~ và ~4~.

don't click

Xâu HMOOZ là một xâu được tạo thành từ các xâu con ~t_1, t_2, t_3, ...~ như sau :

Xâu ~t_1~ là HMOOZ.

Xâu ~t_2~ là HHMMOOOOZZ.

Xâu ~t_3~ là HHHMMMOOOOOOZZZ.

~...~

Như vậy một xâu HMOOZ sẽ là HMOOZHHMMOOOOZZHHHMMMOOO....

Cho một số nguyên dương ~N~ ~(N \leq 10^9)~. Hãy tìm kí tự thứ ~N~ của xâu HMOOZ.

Input

Một số nguyên dương ~N~ ~(N \leq 10^9)~.

Output

Một kí tự là kết quả của bài toán.

Sample

Input

8

Output

M

Subtask

• ~40~% số test có ~N~ ~\leq 10^3~.

• ~60~% số test còn lại có ~N~ ~\leq 10^9~.

Mạng của Syrjälä có ~n~ máy tính và ~m~ kết nối. Nhiệm vụ của bạn là tìm hiểu xem Uolevi có thể gửi tin nhắn cho Maija hay không, và nếu có thể, số lượng máy tính tối thiểu trên một đường tuyền như vậy là bao nhiêu.

Input

• Dòng đầu vào đầu tiên có hai số nguyên ~n~ và ~m~: số lượng máy tính và kết nối. Các máy tính được đánh số ~1,2,\ldots,n~. Máy tính của Uolevi là ~1~ và máy tính của Maija là ~n~.
• Sau đó, có ~m~ dòng mô tả các kết nối. Mỗi dòng có hai số nguyên ~a~ và ~b~: có một kết nối giữa các máy tính đó.
• Mỗi kết nối là giữa hai máy tính khác nhau và có nhiều nhất một kết nối giữa hai máy tính bất kỳ.

Output

• Nếu có thể gửi tin nhắn, trước tiên hãy in ~k~: số lượng máy tính tối thiểu trên một đường truyền hợp lệ. Sau này, in một ví dụ về một đường truyền như vậy. Bạn có thể in bất kỳ giải pháp hợp lệ nào.
• Nếu không có đường truyền, in IMPOSSIBLE.

Constraints

• ~2 \leq n \leq 10 ^ 5~
• ~1 \leq m \leq 2 \cdot 10 ^ 5~
• ~1 \leq a, b \leq n~

Example

Sample input

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

Sample output

3
1 4 5

Marisa có một khu vườn trồng thảo dược, có thể được biểu diễn bởi một ma trận ~A~ gồm ~n~ hàng ~m~ cột.

Ma trận ~A~ chứa những kí tự sau:

• # là hàng rào.
• . là khu đất trông.
• x là một cái cây.

2 khu đất cùng một khu vực nếu chúng được kết nối bởi đường đi không đi qua hàng rào và chỉ gồm các bước đi ngang hay đi dọc.

Input

• Dòng đầu tiên gồm 2 số nguyên ~n, m~.
• ~n~ dòng tiếp theo, mỗi dòng gồm một xâu ~m~ kí tự, khu vườn của Marisa.

Output

• Đếm số lượng cây ở mỗi khu vực. In ra các các số theo thứ tự tăng dần (bỏ qua các khu vực không có cây).

Điều kiện

• ~1 \le n, m \le 10^3~.

Ví dụ

Input:

6 6
.....x
...x..
######
..x.#.
x...#.
xx.x#.

Output:

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 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 đê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 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

Có ~N~ đồ vật được đánh số từ ~1~ đến ~N~. Đồ vật thứ ~i~ ~(1 \le i \le N)~ có khối lượng là ~w_i~ và giá trị là ~v_i~.

Taro quyết định chọn một số đồ vật bỏ vào chiếc túi của anh mang về. Sức chứa tối đa của chiếc túi là ~W~, nghĩa là tổng khối lượng các đồ vật có thể mang tối đa là ~W~.

Hãy tìm tổng giá trị các đồ vật lớn nhất mà Taro có thể mang về nhà.

Input

• Dòng đầu tiên chứa hai số nguyên ~N~ ~(1 \le N \le 100)~ và ~W~ ~(1 \le W \le 10^9)~ - số lượng đồ vật và sức chứa tối đa của chiếc túi.
• ~N~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~w_i~ ~(1 \le w_i \le W)~ và ~v_i~ ~(1 \le v_i \le 10^3)~ - lần lượt là khối lượng và giá trị của đồ vật thứ ~i~.

Output

Xuất ra tổng giá trị các đồ vật lớn nhất mà Taro có thể mang về nhà.

Sample Test 1

Input:

3 8
3 30
4 50
5 60

Output:

90

Chọn đồ vật ~1~ và ~3~. Tổng khối lượng sẽ là ~3 + 5 = 8~ và tổng giá trị là ~30 + 60 = 90~.

Sample Test 2

Input:

1 1000000000
1000000000 10

Output:

10

Sample Test 3

Input:

6 15
6 5
5 6
6 4
6 6
3 5
7 2

Output:

17

Chọn đồ vật ~2, 4~ và ~5~. Tổng khối lượng sẽ là ~5 + 6 + 3 = 14~ và tổng giá trị là ~6 + 6 + 5 = 17~.

Một ngày, OG Loc đã mời CJ dự một buổi tiệc rap của anh ta. Và hôm nay buổi tiệc sẽ diễn ra, nhưng CJ vì mải mê công việc, mà khi nhìn vào đồng hồ và lịch thì … CJ mới chợt nhớ ra về bữa tiệc của OG Loc. Mà còn khoảng ~2~ tiếng nữa là buổi tiệc rap của OG Loc sẽ diễn ra.

CJ nhìn vào bản đồ trong vùng. Bản đồ đấy gồm ~N~ ngôi nhà, đánh số từ ~1~ tới ~N~ và ~M~ con đường hai chiều nối hai ngôi nhà. Ngôi nhà của CJ có số hiệu là ~s~, ngôi nhà có bữa tiệc của OG Loc có số hiệu là ~t~. Vì không muốn tới trễ nên CJ quyết định tìm đường đi ngắn nhất từ nhà của mình tới buổi tiệc tại ngôi nhà của OG Loc và sẽ di chuyển theo đường đi đó.

Input

• Gồm ~M + 1~ dòng:
• Dòng đầu tiên chứa bốn số nguyên dương ~N~, ~M~, ~s~, ~t~ ~(1 \leq s, t \leq N, s \neq t)~.
• ~M~ dòng tiếp theo, dòng thứ ~i~ chứa ba số ~u_i~, ~v_i~, ~c_i~ thể hiện có đường hai chiều nối hai ngôi nhà ~u_i~ và ~v_i~, và độ dài là ~c_i~ (~u_i \neq v_i~).

Output

• Ghi ra hai dòng:
• Dòng đầu tiên ghi ra độ dài đường đi ngắn nhất.
• Dòng thứ hai là số hiệu trên đường đi ngắn nhất tìm được theo thứ tự di chuyển, bắt đầu từ ~s~ và kết thúc ở ~t~.

Scoring

• Subtask ~1~ (~30\%~ số điểm): ~N \leq 10^3, M \leq 2.10^3~
• Subtask ~2~ (~70\%~ số điểm): ~N \leq 10^5, M \leq 2.10^5~

Example

Sample input

3 3 1 3
1 2 3
1 3 5
2 3 1 

Sample output

4
1 2 3

Cho một đồ thị vô hướng liên thông gồm ~n~ đỉnh đánh số từ ~1~ đến ~n~ và ~m~ cạnh.
Mỗi cạnh nối đỉnh ~u~ và ~v~ có trọng số ban đầu là ~w~.

Với mỗi cạnh, ta có thể tăng trọng số lên một lượng bất kỳ sao cho trọng số mới trở thành số nguyên tố.
Chi phí tăng chính là phần giá trị được cộng thêm (~x~).

Yêu cầu

Tìm đường đi từ đỉnh ~s~ đến đỉnh ~t~, chỉ đi qua các cạnh có trọng số là số nguyên tố,
sao cho tổng chi phí tăng trọng số là nhỏ nhất.

Dữ liệu nhập vào từ bàn phím

• Dòng 1: Bốn số nguyên dương ~n, m, s, t~ (~1 \leq n, m \leq 10^5~, ~1 \leq s, t \leq n~)
• ~m~ dòng tiếp theo: Mỗi dòng chứa ba số nguyên dương ~u, v, w~ (~1 \leq u, v \leq n~, ~1 \leq w \leq 10^6~)

Kết quả ghi ra màn hình

• Một số nguyên là tổng chi phí tối thiểu để đi từ ~s~ đến ~t~ qua các cạnh nguyên tố.
• Nếu không thể đi được, in ra -1.

Ví dụ

Ràng buộc

• Subtask 1 (40% số điểm): ~n, m \leq 2000~
• Subtask 2 (60% số điểm): ~2000 < n, m \leq 10^5~