Cho dãy số nguyên dương ~A~ gồm ~N~ phần tử ~a_1,a_2,…,a_N~. Với phần tử ~a_i~ của dãy số, số chính phương kết hợp của ~a_i~ là số chính phương ~s~ lớn nhất thoả mãn: khi thay ~a_i~ thành ~a_i \times s~ thì bội chung nhỏ nhất của dãy số ~A~ không đổi. Yêu cầu: Cho dãy số ~A~ và vị trí ~i~, tìm số chính phương kết hợp của phần tử ~a_i~.

Dữ liệu:

• Vào từ thiết bị vào chuẩn có khuôn dạng:
  • Dòng đầu tiên chứa hai số nguyên dương ~N~ và ~i~ ~(i≤N≤10^6)~;
  • Dòng thứ hai gồm N số nguyên dương mô tả dãy số A, các số có giá trị không quá ~10^7~.

Kết quả:

• Ghi ra thiết bị ra chuẩn một dòng gồm một số nguyên duy nhất là phần dư của kết quả tìm được khi chia cho ~10^9+7~.

Ràng buộc:

• Có 50% số test ứng với 50% số điểm của bài thỏa mãn: ~N≤20; a_i≤20~;
• 30% số test khác ứng với 30% số điểm của bài thỏa mãn: ~N≤10^3; a_i≤10^7~;
• 20% số test còn lại ứng với 20% số điểm của bài không có ràng buộc gì thêm.

Sample Test

Input

5 2
8 4 6 18 5

Output:

9

Giải thích:

• Bội chung nhỏ nhất của dãy số A là 360. Thay số 4 thành 4×9=36 thì dãy số là 8,36,6,18,5 vẫn có bội chung nhỏ nhất là 360. Vậy kết quả là 9.

Cho bảng ~𝐴~ kích thước ~𝑚 × 𝑛~ các hàng của bảng được đánh số từ 1 tới ~𝑚~ và các cột của bảng được đánh số từ 1 tới ~𝑛~. Ô nằm trên hàng ~𝑖~ và cột ~𝑗~ được điền một số nguyên có giá trị bằng ~𝑖^2 + 𝑗^2~ . Hỏi nếu đem các số trên bảng xếp theo thứ tự không giảm (tăng dần) và đánh số từ 1 tới ~𝑚 × 𝑛~ thì số thứ ~𝑘~ mang giá trị bao nhiêu.

Dữ liệu:

• Gồm một dòng chứa ba số nguyên dương ~m, n, k (k ≤ m \times n ≤ 10^9 )~.

Kết quả:

• Ghi ra một dòng chứa kết quả tìm được.

Sample Test

Input:

3 5 10

Output:

18

Cho dãy số nguyên ~A~ gồm ~N~ phần tử ~a_1,a_2,…,a_N~. Giá trị của dãy số ~A~ được tính như sau:

~v(A) = \sum_{i = 1}^{n} |a_i - i|~

Ví dụ dãy số ~A: 6,2,1,3~. Ta có ~v(A)=|6-1|+|2-2|+|1-3|+|3-4|=8.~

Cho thao tác quay vòng mảng A được thực hiện như sau: chuyển số ở vị trí cuối cùng lên vị trí đầu tiên:

~a_1,a_2,…,a_{N-1},a_N→a_N,a_1,a_2,…,a_{N-1}~

Sau một thao tác quay vòng thì dãy số sẽ như sau: ~3,6,2,1~.

Yêu cầu: cho dãy số ~A~, hãy sử dụng thao tác quay vòng một số lần để giá trị của dãy số lớn nhất.

Dữ liệu:

• Vào từ thiết bị vào chuẩn có khuôn dạng:
  • Dòng đầu tiên gồm một số nguyên dương ~N (N≤10^5)~.
  • Dòng thứ hai gồm ~N~ số nguyên ~a_1,a_2,…,a_{N-1},a_N (|a_i |≤10^9;1≤i≤N). ~

Kết quả:

• Ghi ra thiết bị ra chuẩn gồm một số nguyên là giá trị của dãy số lớn nhất tìm được.

Ràng buộc:

• Có 40% số test ứng với 40% số điểm của bài có ~N≤10^3~;
• 30% số test khác ứng với 30% số điểm của bài có ~N≤10^5; a_i≤a_{i+1}~ với ~1≤i<N~;</li>
• 30% số test còn lại ứng với 30% số điểm của bài không có ràng buộc gì thêm.

Sample Test

Input:

4
6 2 1 3 10

Output:

10

Giải thích

• Ban đầu, dãy số 6,2,1,3 có giá trị là 8;
• Quay vòng dãy số trên ta có dãy số: 3,6,2,1 có giá trị là 10;
• Quay vòng dãy số trên ta có dãy số: 1,3,6,2 có giá trị là 6;
• Quay vòng dãy số trên ta có dãy số: 2,1,3,6 có giá trị là 4;
• Vậy giá trị lớn nhất tìm được là 10.

Cho ba số nguyên dương ~s,d,m (s≤10^6;d≤9;m≤9)~. Hãy tìm số nguyên dương ~N~ nhỏ nhất thỏa mãn các điều kiện:

• Tổng các chữ số của ~N~ bằng ~s~.
• Các chữ số của ~N~ đều xuất hiện chẵn lần và là tập con của tập các chữ số từ 0 đến ~d~ (~N~ không được bắt đầu bằng chữ số 0);
• Số ~N~ chia hết cho ~m~.

Dữ liệu:

• Vào từ thiết bị vào chuẩn gồm một dòng chứa ba số nguyên dương s,d,m.

Kết quả:

• Ghi ra thiết bị ra chuẩn một dòng chứa số nguyên dương N tìm được hoặc ghi số -1 nếu không tồn tại số N thỏa mãn.

Ràng buộc:

• Có 20% số test ứng với 20% số điểm có ~m=1;s≤100;~
• Có 30% số test khác ứng với 30% số điểm có ~s≤100;~
• Có 30% số test khác ứng với 30% số điểm có ~s≤1000;~
• Có 20% số test còn lại ứng với 20% số điểm không có ràng buộc gì thêm.

Sample Test:

Input:

6 5 4

Output:

1212