Trên mặt phẳng tọa độ, bạn hãy chọn ra ~n~ điểm phân biệt sao cho thỏa mãn hai điều kiện sau:

• Với mỗi điểm, tọa độ của các điểm đều là các số nguyên không âm ~x_i, y_i\ (0 \leq x_i, y_i \leq 100)~.

• Từ ~n~ điểm trên ta chọn được ~4~ điểm phân biệt để dựng ~2~ đoạn thẳng sao cho toàn bộ ~n~ điểm đều thuộc ít nhất 1 trong 2 đoạn thẳng đó, và 2 đoạn thẳng ấy cắt nhau tại một giao điểm có tọa độ không nguyên (cả tung độ và hoành độ).

Input

Gồm 1 dòng duy nhất chứa một số nguyên ~n\ (4 \leq n \leq 100)~ - số lượng điểm mà bạn cần chọn.

Output

Gồm ~n+2~ dòng:

• ~n~ dòng đầu tiên: Mỗi dòng gồm ~2~ số nguyên ~x~, ~y~ chỉ tọa độ các điểm mà bạn chọn.

• ~2~ dòng cuối: Mỗi dòng gồm 4 số nguyên ~x_1\ y_1\ x_2\ y_2~ - tọa độ của các đầu mút của đoạn thẳng mà bạn chọn.

Scoring

Sample Input 1

4

Sample Output 1

0 0
3 1
1 0
0 3
0 0 3 1
1 0 0 3

Cho số tự nhiên ~N~ có thể được biểu diễn dưới dạng ~a^2 \times b~ với ~a, b~ là hai số nguyên tố. Từ số ~N~ được cho, hãy tìm ~a~ và ~b~.

Input

• Dòng đầu tiên chứa số nguyên dương ~T~ là số bộ test (~T \leq 20~).

• ~T~ dòng tiếp theo, mỗi dòng chứa ~1~ số nguyên dương ~N~ miêu tả một bộ test (~N \leq 10^{18}~).

Output

Gồm ~T~ dòng, mỗi dòng chứa ~2~ số nguyên ~a~ ~b~ là câu trả lời cho bộ test tương ứng.

Scoring

• Subtask ~1~ (~30~ điểm): ~N \leq 2 \times 10^9~.

• Subtask ~2~ (~70~ điểm): không có ràng buộc gì thêm.

Sample Input 1

2
604
45

Sample Output 1

2 151
3 5

Notes

~604 = 2^2 \times 151~.

~45 = 3^2 \times 5~.

Cho một dãy số ~N~ số nguyên dương ~A_1, A_2, ..., A_N~.

Xét thao tác: chọn hai số nguyên ~i, j~ ~(1 \leq i, j \leq N, i \neq j, A_i, A_j > 0)~ và cập nhật ~A_i := A_i - A_j~. Sau một số thao tác, dãy ~A~ chỉ còn duy nhất một số dương. Tìm giá trị nhỏ nhất có thể của số đó.

Input

Dòng đầu tiên gồm một số nguyên dương ~N~ ~(1 \leq N \leq 10^5)~. Dòng thứ hai gồm ~N~ số nguyên dương ~A_1, A_2, ..., A_N~ ~(1 \leq A_i \leq 10^9)~.

Output

In ra một số nguyên dương duy nhất là giá trị nhỏ nhất của thể của số dương cuối cùng trong dãy.

Scoring

• Subtask ~1~ (~30~ điểm): ~N = 2~.

• Subtask ~2~ (~70~ điểm): Không có ràng buộc gì thêm.

Sample Input 1

3
2 3 4

Sample Output 1

1

Sample Input 2

2
4 10

Sample Output 2

2

Notes

Một dãy thao tác có thể cho ví dụ 1 là

• ~A_3~ -= ~A_2~, ~A = [2, 3, 1]~

• ~A_2~ -= ~A_1~, ~A = [2, 1, 1]~

• ~A_2~ -= ~A_3~, ~A = [2, 0, 1]~

• ~A_1~ -= ~A_3~, ~A = [1, 0, 1]~

• ~A_1~ -= ~A_3~, ~A = [0, 0, 1]~

Một dãy thao tác có thể cho ví dụ 2 là

• ~A_2~ -= ~A_1~, ~A = [4, 6]~

• ~A_2~ -= ~A_1~, ~A = [4, 2]~

• ~A_1~ -= ~A_2~, ~A = [2, 2]~

• ~A_1~ -= ~A_2~, ~A = [0, 2]~

Xét xâu ~S~ chỉ gồm các kí tự 0,1,?. Trong đó, các kí tự ? có thể được thay thế bằng 0 hoặc 1.

Gọi ~f(T,k)~ là số lượng xâu con liên tiếp độ dài ~k~ của xâu ~T~ sao cho xâu con này chứa toàn bộ kí tự ~1~.

Nhập vào xâu ~S~ và giá trị ~k~. Tính ~\sum f(S,k)~ với mọi xâu ~S~ có thể tạo ra. Dễ thấy có ~2^{cntQ}~ xâu ~S~ có thể có, với ~cntQ~ là số kí tự ? trong xâu ~S~.

Input

• Dòng thứ nhất chứa 2 số nguyên ~n~ và ~k~ ~(1 \le k \le n \le 10^5)~ - tương ứng với độ dài xâu ~S~ và hằng số ~k~.

• Dòng thứ hai nhập vào xâu ~S~ gồm kí tự 0,1,?.

Output

• In ra kết quả cần tìm. Vì kết quả có thể rất lớn, hãy in ra số dư sau khi chia cho ~10^9 + 9~.

Scoring

• Subtask ~1~ (~30~ điểm): ~n \le 1000~.

• Subtask ~2~ (~30~ điểm): ~cntQ \le 20~.

• Subtask ~3~ (~40~ điểm): không có ràng buộc gì thêm.

Sample Input 1

3 1
?01

Sample Output 1

3

Notes

• ~f(~001~, 1) = 1~

• ~f(~101~, 1) = 2~

Tại Earth-2729, có ~n~ quốc gia, quốc gia thứ ~i~ có sức mạnh quân sự ~c_i~. Hiện tại, đang có ~m~ cuộc xung đột quân sự diễn ra trên toàn cầu, cuộc xung đột thứ ~i~ giữa hai quốc gia ~u_i~ và ~v_i~.

Nhóm Azenzers muốn có những động thái để tránh tình hình chiến sự leo thang, tuy nhiên đây không phải là truyện truyện tranh Marvel, họ không hề có siêu năng lực nào cả. Vậy nên nhóm muốn thành lập một liên minh gồm một số quốc gia để hợp tác quân sự, sao cho tổng sức mạnh quân sự của các nước này là lớn nhất và không có cuộc xung đột nào đang diễn ra giữa các quốc gia được lựa chọn để hợp tác.

Hãy giúp nhóm Azenzers tìm được liên minh quân sự tốt nhất.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n,m~ ~(1 \le n \le 40; 0 \le m \le \frac{n \times (n-1)}{2})~.

• Dòng thứ hai gồm ~n~ số nguyên dương miêu tả dãy ~c_i~ là sức mạnh quân sự của từng quốc gia ~(1 \le c_i \le 10^9)~.

• Trong ~m~ dòng sau, mỗi dòng gồm hai số nguyên dương ~u_i, v_i~ miêu tả xung đột thứ ~i~. ~(1 \le u_i,v_i \le n; u_i \neq v_i)~

Output

• Gồm một số nguyên dương miêu tả tổng sức mạnh quân sự lớn nhất của liên minh thỏa mãn.

Scoring

• Subtask ~1~ (~20~ điểm): ~n \le 20~

• Subtask ~2~ (~30~ điểm): ~n \le 30~

• Subtask ~3~ (~50~ điểm): không có ràng buộc gì thêm.

Sample Input 1

4 2
4 9 2 1
1 4
2 4

Sample Output 1

15

Notes

Chọn quốc gia ~1~, ~2~ và ~3~.