Ướ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

Châu và Huy là đôi bạn thân. Vì yêu âm nhạc nên họ gửi cho nhau lyrics của các bài hát. Cụ thể đó là những xâu ~S~ độ dài ~N~ và chỉ gồm các kí tự từ ~a~ đến ~z~. Để làm cho những xâu này trở nên hay hơn, Huy đã đưa cho Châu một số nguyên dương ~K~ và nhờ thực hiện những thao tác sau. (Lưu ý mỗi thao tác bắt buộc phải làm một lần duy nhất):

• Tạo ra xâu ~T~ từ xâu ~S~ đã cho bằng cách viết ~K~ lần liên tiếp xâu ~S~ liên kề nhau. (Ví dụ ~K = 2~ và xâu ~S~ là ~hello~ thì khi viết sẽ cho xâu ~T~ là ~hellohello~).
• Chọn một chữ cái ở vị trí bất kì trong xâu ~T~, giả sử là vị trí ~i~. Biến đổi tất cả các chữ cái trong xâu ~T~ giống với chữ cái ở vị trí ~i~ thành chữ cái ở vị trí ~i-1~ hoặc chữ cái ở vị trí ~i+1~ (Tất nhiên nếu ở vị trí đầu tiên sẽ không có ~i-1~ và vị trí cuối cùng sẽ không có ~i+1~ để mà biến). Gọi ~X~ là số lần xuất hiện của chữ cái xuất hiện nhiều nhất trong xâu vừa tạo. Phải đảm bảo thao tác biến đổi vừa rồi tạo ra ~X~ lớn nhất.

Yêu cầu:

• Cho xâu ~S~ độ dài ~N~ và số ~K~. Tạo ra xâu ~T~ mới bằng viết liền xâu ~S~ cạnh nhau ~K~ lần. Sau đó thực hiện thao tác như đã miêu tả trong đề sao cho số lần xuất hiện của chữ cái xuất hiện nhiều nhất là lớn nhất và cho biết số lần xuất hiện là bao nhiêu.

Dữ liệu vào từ tệp văn bản: amnhac.inp

• Dòng đầu tiên là 2 số nguyên dương ~N~ và ~K~. ~(N \le 10^6, K \le 10^9)~
• Dòng thứ hai là xâu ~S~ chỉ gồm các kí tự từ ~a~ đến ~z~.

Kết quả ghi ra tệp văn bản: amnhac.out

• In ra một số nguyên duy nhất là số lần xuất hiện của chữ cái xuất hiện nhiều nhất sau các thao tác đã nêu trong đề.

Ràng buộc:

• Có ~20\%~ số điểm với ~N * K \le 10^3~
• Có ~30\%~ số điểm với ~K = 1~.
• ~50\%~ số điểm còn lại không có ràng buộc gì thêm.

Ví dụ

Input 1

10 1
bbabdcccaa

Output 1

6

Input 2

3 2
abc

Output 2

4

Giải thích

Ở ví dụ ~1~, ta được xâu ~T~ là ~bbabdcccaa~. Sau đó biến tất cả kí tự ~a~ thành ~c~ vì ở vị trí thứ ~8~ kí tự ~c~ liền kề với kí tự ~a~ ở vị trí ~9~ và được xâu mới là ~bbcbdccccc~. Ta được 6 kí tự ~c~ trong xâu mới này nên kết quả in ra là 6.

Ở ví dụ ~2~, ta được xâu ~T~ là ~abcabc~. Sau đó biến tất cả kí tự ~a~ thành ~c~ vì ở vị trí thứ ~3~ kí tự ~a~ liền kề với kí tự ~c~ ở vị trí ~4~ và được xâu mới là ~cbccbc~. Ta được 4 kí tự ~c~ trong xâu mới này nên kết quả in ra là 4.

Cho số nguyên dương ~n~, hãy tính tổng sau:

• ~S = \lfloor \frac{x}{1} \rfloor + \lfloor \frac{x}{2} \rfloor + ... + \lfloor \frac{x}{n} \rfloor ~

Ở đây, ~\lfloor x \rfloor~ kí hiệu số nguyên dương lớn nhất nhất không vượt quá ~x~.

Input

• Dòng đầu chứa số nguyên dương ~T~ ~(1 \le T \le 30)~ là số lượng bộ test.
• ~T~ dòng tiếp theo, mỗi dòng chứa một số nguyên dương ~n~ ~(1 \le n \le 10^{12})~

Output

• Gồm ~T~ dòng, mỗi dòng in ra đáp án tương ứng sau khi lấy modulo cho ~10^6~.

Scoring

• 50% số test có ~n \le 10^6~
• 50% số test còn lại không có ràng buộc gì thêm

Sample Input 1

2
1
5

Sample Output 1

1
10

Cho lưới ô vuông rộng vô tận, tâm của lưới ô vuông có tọa độ (0, 0). Có ~n~ ngôi nhà được xây dựng trên lưới ô vuông. Trong 1 đơn vị thời gian, người ~A~ có thể di chuyển đến các ô liền kề của lưới (8 ô liền kề). Khoảng cách giữa 2 ngôi nhà là thời gian ngắn nhất di chuyển từ nhà này đến nhà kia. Trong lúc nhàn rỗi, bạn Lương tính toán hết tất cả khoảng cách giữa 2 ngôi nhà và sắp xếp chúng thành dãy không giảm. Hãy tìm số thứ ~k~ trong dãy.

Input

• Dòng đầu tiên gồm 2 số nguyên dương ~n, k~ ~(2 \leq n \leq 10^5, k \leq \frac{n (n - 1)}{2})~.
• ~n~ dòng tiếp theo, dòng thứ ~i~ chứa 2 số nguyên ~x, y~ là tọa độ của nhà thứ ~i~ ~(|x|, |y| \leq 10^9)~.

Output

• In ra số nguyên là kết quả bài toán.

Scoring

• Subtask 1: ~\ n \leq 2000~
• Subtask 2: ~\ y_i = 0~ với mọi ~i~
• Subtask 3: ~\ k = 1~
• Subtask 4: không có dữ kiện gì thêm

Sample Input 1

4 3
3 1
1 -1
0 5
-2 1

Sample Output 1

4

Cảnh sát đang cần sự giúp đỡ của bạn trong việc tìm kiếm nơi trú ở của một tên tội phạm, kẻ đang ẩn náu ở đâu đó trong thành phố gồm n địa điểm khác nhau, được đánh số từ 1 đến ~n~, và có ~m~ đường hai chiều kết nối hai địa điểm khác nhau.

Thông tin từ các người dân trong thành phố, cảnh sát biết được tên tội phạm đã di chuyển từ một địa điểm ~x~ nào đó để đến nơi trú ẩn ~y~ nào đó. Và các nhân chứng có trông thấy hắn xuất hiện ở ~k~ địa điểm ~u_1,u_2,…,u_k~ trên đường đi từ ~x~ đến ~y~ theo thứ tự nào đó mà cảnh sát chưa xác định. Lưu ý rằng tên tội phạm có thể di chuyển từ ~x~ đến ~y~ thông qua các địa điểm khác không có trong ~k~ địa điểm mà các nhân chứng trông thấy. Tuy nhiên, cảnh sát đã phân tích đặc điểm của tên tội phạm này và biết rằng hắn sẽ luôn di chuyển theo đường đi ngắn nhất giữa hai địa điểm ~x~ và ~y~.

Nhiệm vụ của bạn là tìm các địa điểm có thể là ~y~ để giúp cảnh sát có thể nhanh chóng tìm được hắn. Tất nhiên, có thể lời khai của các nhân chứng không đồng nhất dẫn đến không tìm thấy một địa điểm ~y~ nào thỏa mãn.

Input

• Dòng đầu chứa số nguyên ~n,m,k~ (~1≤k≤n≤2⋅10^5,1≤m≤2⋅10^5~)
• Dòng thứ hai chứa ~k~ số nguyên ~u_i~ mô tả những địa điểm tên tội phạm đi qua (~1≤u_i≤n~)
• ~m~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~a,b,c~ mô tả có đường nối trực tiếp giữa hai địa điểm ~a~ và ~b~ có độ dài là ~c~ (~1≤a≠b≤n,1≤c≤10^9~)

Output

• Dòng đầu ghi ra số ~p~ là số địa điểm có thể là ~y~
• Dòng thứ hai ghi ra ~p~ số nguyên là những địa điểm có thể là ~y~ theo thứ tự tăng dần.

Scoring

• 15% số test có ~m=n-1~, và mỗi địa điểm được kết nối trực tiếp với tối đa 2 địa điểm khác.
• 15% số test có ~m=n-1~
• 15% số test có ~n,m≤100~
• 15% số test có ~n,m≤1000~
• 20% số test có ~k≤5~
• 20% số test còn lại không có ràng buộc gì thêm

Sample Input 1

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

Sample Output 1

4
1 2 4 5