Mỗi lần bị kẹt trên đường vì tắc đường, An thường nghĩ ra trò chơi để giải trí. Một trong những trò chơi đó là An đọc ~N~ số từ các biển số xe và tìm số nguyên ~M~ ~(M>1)~ sao cho N số đã đọc đều có cùng số dư khi chia cho ~M~. An muốn tìm được càng nhiều số ~M~ như thế càng tốt. Bạn hãy giúp An tìm tất cả các số ~M~ thoả mãn yêu cầu.

Input

• Dòng đầu tiên chứa số nguyên ~N~ ~(2< N <100)~. ~N~ dòng tiếp theo, dòng thứ ~i~ chứa số nguyên ~B_i~ thuộc đoạn ~[1; 10^9]~. Tất cả các số nguyên đôi một khác nhau. Dữ liệu vào luôn đảm bảo tồn tại ít nhất một số ~M~ thoả mãn yêu cầu.

Output

• In ra tất cả các số ~M~ tìm được theo thứ tự tăng dần, các số ghi cách nhau ít nhất một dấu cách.

Subtask

• Có ~60\%~ số test tương ứng với ~0 < B_i \le 10^4~ ~(\forall i \in [1,N])~
• ~40\%~ số test còn lại không giới hạn gì thêm.

Sample Input 1

3
6
34
38

Sample Output 1

2  4

Sample Input 2

5
5
17
23
14
83

Sample Output 2

3

Cho dãy số ~A: 1, 4, 9, 16, 25, 36, 49, 64, …~

Chỉ lấy các số hàng đơn vị của dãy số ~A~ ta được dãy số ~B: 1, 4, 9, 6, 5, 6, 9, 4, …~

Yêu cầu: Nhập vào một số tự nhiên ~𝑁~. Hãy in ra tổng ~𝑁~ số hạng đầu tiên của dãy số ~B~.

Input

Gồm một số nguyên dương ~N~ ~(N \le 10^9)~.

Output

Một số nguyên duy nhất là kết quả của bài toán.

Sample Test

Input

4

Output

20

Ước số chung của dãy số nguyên dương là các số nguyên dương mà tất cả các số trong dãy đều chia hết cho nó. Hôm nay, Tuấn đang học về ước số chung và Tuấn được thầy giáo cho bài toán: Có một dãy số ~A~ gồm ~N~ số nguyên dương, hãy tìm ước số chung nhỏ nhất khác ~1~. Nói cách khác, Tuấn cần tìm số ~D~ nhỏ nhất, sao cho ~D > 1~ và các số trong dãy số ~A~ đều chia hết cho số ~D~ này.

Yêu cầu: Cho một số ~A~ gồm ~N~ số nguyên dương, hãy giúp Tuấn đưa ra số là Ước số chung nhỏ nhất khác ~1~.

Input

• Dòng đầu tiên chứa số nguyên dương ~N~ (~N\leq 10^5~)
• Dòng tiếp theo gồm ~N~ số nguyên dương ~A_i~ là các phần tử của dãy ~A~ (~A_i\leq 10^6~).

Output

• Một số nguyên dương ước chung nhỏ nhất của dãy số. Nếu không tồn tại số siêu nguyên dương nào, in ra ~-1~.

Scoring

• Subtask ~1~ (~60\%~ số điểm): ~N\leq 10^3~, ~A_i\leq 10^5~.
• Subtask ~2~ (~40\%~ số điểm): Không có ràng buộc gì thêm

Sample Input 1

3
1 2 3

Sample Output 1

-1

Sample Input 1

3
2 4 6

Sample Output 1

2

Cho dãy gồm ~n~ số nguyên dương ~a_1, a_2, ..., a_n~. Bạn được phép thay đổi bất kì một số trong dãy trên thành một số nguyên dương khác bất kì. Hãy tìm cách thay đổi tối ưu để ước chung lớn nhất của dãy trên lớn nhất có thể, hay ~gcd(a_1, a_2, ..., a_n)~ là lớn nhất.

Input

• Dòng đầu tiên gồm số nguyên dương ~n~ ~(1 \le n \le 10^5)~.
• Dòng thứ hai gồm ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ ~(1 \le a_i \le 10^9)~.

Output

• Gồm một số nguyên duy nhất là kết quả bài toán.

Sample Input

3
4 3 8

Sample Output

4

Note

Có thể thay đổi ~a_2=3~ thành ~a_2 = 16~. Từ đó ~gcd(a_1, a_2, a_3) = gcd(4, 16, 8) = 4~.

Cho số nguyên dương ~N~. Đếm xem có bao nhiêu cặp số nguyên ~[a,b]~ ~(0 < a \le b)~ để tổng các số nguyên trong đoạn ~[a,b]~ bằng ~N~. Hai đoạn khác nhau là hai đoạn có ít nhất một phần tử khác nhau.

Input

• Gồm một dòng duy nhất chứa số nguyên dương ~N~.

Output

• Gồm một dòng duy nhất là kết quả bài toán.

Subtask

• Subtask ~1~ (~40\%~ số điểm): ~n \le 10^4~
• Subtask ~2~ (~30\%~ số điểm): ~n \le 10^8~
• Subtask ~3~ (~30\%~ số điểm): ~n \le 10^{15}~

Sample Input 1

9

Sample Output 1

3

Explanation 1

~3~ đoạn thỏa mãn là : ~[2,4]~, ~[4,5]~, ~[9,9]~.

Bạn được cho một xâu ~S~ có độ dài ~n~ gồm các chữ cái từ a đến z. Nhiệm vụ của bạn là đếm số xâu con liên tiếp mà mỗi cặp kí tự đặc biệt trong xâu con đó có khoảng cách không nhỏ hơn ~k~ (~k \le n~).

Input

• Dòng đầu tiên gồm ba số nguyên dương ~n~, ~m~ và ~k~ ~(1 \le k \le n \le 10^5; 1 \le m \le 10)~ lần lượt là độ dài của xâu ~S~, số lượng kí tự đặc biệt và khoảng cách yêu cầu giữa hai kí tự đặc biệt bất kì.
• Dòng thứ hai chứa xâu ~S~ gồm các chữ cái từ a đến z.
• Dòng cuối cùng gồm ~m~ kí tự là các kí tự đặc biệt, dữ liệu đảm bảo ~k~ kí tự này phân biệt

Output

• Gồm một dòng duy nhất là số lượng xâu con liên tiếp thỏa mãn đề bài

Substask

• ~30\%~ số test: ~1 \le k \le n \le 10^3~.
• ~20\%~ số test: ~1 \le k \le n \le 10^5~, trong xâu chỉ có đúng ~2~ vị trí có kí tự đặc biệt.
• ~50\%~ số test: ~1 \le k \le n \le 10^5~.

Sample Input 1

6 2 2
acbabc
a b

Sample Output 1

10

Explanation 1

Các xâu con thỏa mãn là: a, c, b, a, b, c, ac, acb, cb, bc.

Cho số nguyên dương ~n~, hãy tìm số nguyên ~m~ nhỏ nhất sao cho ~m!~ có ít nhất ~n~ chữ số ~0~ ở cuối.

Input:

• Dòng đầu tiên: chứa số nguyên ~T~ (~1 ≤ T ≤ 10^5~ ) là số test
• ~T~ dòng tiếp theo: mỗi dòng chứa một số nguyên ~n~ (~1 ≤ n ≤ 10^{16}~).

Output :

• Gồm ~T~ dòng, dòng thứ ~i~ chứa kết quả của truy vấn thứ ~i~.

Scoring

• Có 50% số test ứng ~n ≤ 10^5,T=1~
• Có 50% số test còn lại không có ràng buộc gì thêm

Sample Input 1

2
1
3

Sample Output 1

5
15

Người ta đo độ giống nhau của hai xâu ~X~, ~Y~ có độ dài bằng nhau là số vị trí mà hai kí tự tương ứng trên hai xâu giống nhau, tức là số chỉ số ~i~ thỏa mãn ~X_i = Y_i~. Ví dụ: ~X = 'avbc'~; ~Y = 'avvv'~ có độ giống nhau bằng ~2~. Cho một xâu ~S~ có độ dài ~n~ và một xâu ~T~ có độ dài ~m (m \le n)~, độ giống nhau giữa xâu ~S~ và xâu ~T~ là tổng số độ giống nhau giữa xâu ~T~ và mọi xâu con gồm các kí tự liên tiếp của ~S~ có độ dài ~m~.

Yêu cầu: Cho hai xâu ~S~ và ~T~. Tính độ giống nhau giữa xâu ~S~ và xâu ~T~.

Input

• Dòng đầu ghi xâu ~T~.
• Dòng thứ ~2~ ghi xâu ~S~.
• Các kí tự trong hai xâu thuộc ~'a' .. 'z'~ và có độ dài không quá ~2.10^6~ kí tự.

Output

• Gồm một số nguyên duy nhất là độ giống nhau giữa xâu ~S~ và xâu ~T~.

Subtask

• Có ~25\%~ số test ứng với ~0 < n ≤ 10^2~
• Có ~25\%~ số test ứng với ~10^2 < n ≤ 10^4~
• Có ~50\%~ số test ứng với ~10^4 < n ≤ 2.10^6~

Sample Input 1

 abaab 
 aababacab

Sample Output 1

12

Cho một dãy ~a~ gồm ~N~ phần tử ~a_1, a_2,..a_N~ và ~Q~ truy vấn, mỗi truy vấn là một trong ~2~ loại sau:

• Loại ~1~ có dạng ~1~ ~u~ ~x~: Giá trị phần tử thứ u được thay đổi về ~x(1 \le u \le N)~;
• Loại ~2~ có dạng ~2~ ~l~ ~r~: Tính ước chung lớn nhất của các phần tử từ vị trí ~l~ đến vị trí ~r (1 \le l \le r \le N)~.

Yêu cầu: Hãy đưa ra câu trả lời cho mỗi truy vấn loại ~2~.

Input

• Dòng đầu tiên gồm ~2~ số nguyên ~N, Q (1 \le N, Q \le 10^5)~;
• Dòng thứ hai chứa ~N~ số nguyên ~a_1, a_2,..., a_N~ miêu tả giá trị ban đầu của dãy ~(1 \le a_i \le 10^9)~;
• ~Q~ dòng tiếp theo, mỗi dòng chứa ~3~ số nguyên miêu tả một trong ~2~ truy vấn đã được đề cập ở trên.

Output

• Ứng với mỗi truy vấn loại ~2~, in ra đáp án tìm được trên một dòng.

Example

Input

3 3
1 2 3
1 2 1
2 1 2
2 2 3

Output

1
1