Cho một dãy số nguyên ~A~ gồm ~N~ phần tử ~A_1,A_2,…,A_N~. In ra độ dài của dãy con liên tiếp đan dấu dài nhất. (Đan dấu là không có hai phần tử nào cạnh nhau mà có cùng dấu)

Input:

• Dòng đầu tiên gồm một số nguyên dương ~N~ ~(N≤10^5)~ là số lượng phần tử của dãy ~A~.
• Dòng thứ hai gồm ~N~ số nguyên ~A_1,A_2,…,A_N~ mô tả dãy ~A~ ~(0<|A_i|≤10^9)~.

Output:

Ghi ra một số nguyên duy nhất là độ dài của dãy con liên tiếp đan dấu dài nhất.

Ràng buộc

• Có ~60\%~ số test ứng với ~60\%~ số điểm có ~N≤10^3~;
• ~40\%~ số test còn lại ứng với ~40\%~ số điểm không có ràng buộc gì thêm.

Sample Test 1

Input:

9
1 3 -1 3 -2 4 -5 -6 7

Output

6

Giải thích

Dãy đan dấu: 3 -1 3 -2 4 -5

Sample Test 2

Input:

9
1 3 -1 3 -2 4 -5 6 7

Output

7

Giải thích

Dãy đan dấu 3 -1 3 -2 4 -5 6

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

Tewi đã ốm liệt giường nên Yagokoro Eirin phải chữa bệnh cho cô. Đoạn ADN của Tewi có độ dài ~n~ gồm cách kí tự ~a, b, c~ (vì sao thì chưa rõ). Eirin có thể sửa đổi một vị trí bất kì trên ADN với chi phí là 1.

Cô đang nghi ngờ ~q~ đoạn con ~[l_i, r_i]~ có thể là nguyên nhân gây bệnh. Với mỗi đoạn ADN con này, Eirin muốn sửa lại đoạn này sao cho không tồn tại đoạn con nào có độ dài lớn hơn 1 là xâu đối xứng. Ví dụ ~aab~ là không thỏa mãn vì có ~aa~ là xâu đối xứng. Hãy giúp cô tính trước chi phí để chữa bệnh nhé!

Input:

• Dòng đầu tiên gồm 2 số ~n, q~.
• Dòng tiếp theo là một xâu gồm ~n~ kí tự chỉ gồm ~a, b, c~.
• ~q~ dòng tiếp theo mỗi dòng gồm 2 số ~l_i, r_i~.

Output:

• ~q~ dòng là chi phí chữa bệnh.

Sample Test

Input:

5 4
baacb
1 3
1 5
4 5
2 3

Output:

1
2
0
1

Giới hạn:

• Trong mọi test ~n, q \le 10^5~
• 10% số điểm: ~n, q \le 5~.
• 30% số điểm: ~n, q \le 2000~.
• 30% số điểm: ADN chỉ gồm 2 kí tự ~a, b~.
• 30% số điểm: Không có giới hạn gì thêm.

Bob đang bị dương tính với COVID-19, và ở nhà cậu ấy chẳng có gì để làm nên Bob muốn chơi một trò chơi gì đấy để cho cậu ấy đỡ chán. Bob nhớ ra là cậu ấy có 1 chiếc hộp thần kỳ bao gồm vô số các số từ ~1~ đến ~10^9~. Bob lấy ~N~ số trong chiếc hộp đấy ra và đặt lên trên một chiếc bàn. Nhận ra rằng chơi một mình thì chẳng có gì vui nên Bob rủ Alice chơi cùng. Trong khi Bob không biết rằng mình sẽ phải làm gì với ~N~ số trên bàn, Alice có một ý tưởng: Vì Alice không thể chơi cùng Bob trực tiếp vì tình hình dịch bệnh phức tạp, Alice sẽ có ~Q~ câu hỏi cho Bob trả lời.

Với mỗi câu hỏi, Bob sẽ phải lấy ra các số ở vị trí từ ~L~ đến ~R~, sau đó tìm ước chung lớn nhất của các số còn lại trên bàn. Sau mỗi câu hỏi, Bob sẽ đặt lại các số vừa lấy về vị trí ban đầu.

Yêu cầu: Hãy giúp Bob trả lời ~Q~ câu hỏi mà Alice đã cho.

Dữ liệu

• Dòng đầu tiên chứa hai số nguyên dương ~N~ và ~Q~ là số lượng số trên bàn và số câu hỏi Alice dành cho Bob (~N,Q \le 10^5~).
• Dòng tiếp theo chứa ~N~ số nguyên dương ~A_i~ là các số ở trên bàn (~A_i \le 10^9, \ 1 \le i \le N~).
• ~Q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~L_i~ và ~R_i~ (~1 \le L_i \le R_i \le N, \ 1 \le i \le Q~).

Kết quả

In ra ~Q~ dòng, mỗi dòng là đáp án của câu hỏi thứ ~i~ mà Alice dành cho Bob (~1 \le i \le Q~).

Ví dụ

Input

3 3
2 6 9
1 1
2 2
2 3

Output

3
1
2

Giải thích

• Ở câu hỏi đầu tiên, Bob lấy số ~2~ ra khỏi bàn, còn lại số ~6~ và ~9~ có ước chung lớn nhất là ~3~.
• Ở câu hỏi tiếp theo, Bob lấy số ~6~ ra khỏi bàn, còn lại số ~2~ và ~9~ có ước chung lớn nhất là ~1~.
• Ở câu hỏi cuối cùng, Bob lấy số ~6~ và ~9~ ra khỏi bàn, còn lại số ~2~ có ước chung lớn nhất là ~2~.

Subtasks

• ~50\%~ số test có ~N, Q \le 1000~.
• ~50\%~ số test còn lại không có ràng buộc gì thêm.

Cho một dãy ~a~ gồm ~n~ phần tử. Ta định nghĩa ~g(l,r) = min (a[i]) \forall (l \le i \le r)~.

Tiếp đó, ta có ~f(k) = max (g(l,r)) \forall (r - l + 1= k)~, hay ~f(k)~ là giá trị lớn nhất của các ~g(l,r)~ với mọi đoạn ~(l,r)~ có độ dài ~k~.

Hãy lập trình tính các ~f(k)~ từ ~1 -> n~.

Input

• Dòng đầu tiên gồm số nguyên dương ~n~. ~(1 \le n \le 10^5).~
• Dòng sau gồm n số nguyên dương miêu tả dãy ~a~. ~(1 \le a[i] \le 10^6~ ~\forall (1 \le i \le n))~.

Output

• In ra một dòng gồm ~n~ số miêu tả kết quả của ~f(k)~ từ ~1 -> n~.

Sample Test

Input:

10
1 2 3 4 5 4 3 2 1 6

Output:

6 4 4 3 3 2 2 1 1 1 

Cho 2 dãy số nguyên dương ~a~ có ~n~ phần tử và ~b~ có ~m~ phần tử. Với ~j~ từ 1 đến ~m~ hãy tìm ~gcd(a_1 + b_j, a_2 + b_j,...,a_n + b_j)~.

Input

• Dòng đầu tiên gồm 2 số nguyên dương ~1 \le n, m \le 2 \times 10^5~.
• Dòng thứ 2 gồm ~n~ số nguyên dương ~1 \le a_i \le 10^9~.
• Dong thứ 3 gồm ~n~ số nguyên dương ~1 \le b_j \le 10^9~.

Output

• In ra ~m~ số nguyên tương ứng với đáp án.

Sample Test

Input:

4 4
1 25 121 169
1 2 7 23

Output:

2 3 8 24