Cho hai số nguyên dương ~𝑁~ và ~𝑀~ (~1 ≤ 𝑁~, ~𝑀 ≤ 10^{14}~).

Yêu cầu: Tính tổng ước chung lớn nhất và ước chung lớn nhì của hai số đã cho.

Dữ liệu vào:

• Ghi hai số ~𝑁~, ~𝑀~ ghi cách nhau một dấu cách.

Kết quả:

• Ghi một số duy nhất là tổng tìm được, nếu không có ước chung lớn nhì thì ghi -1.

Ràng buộc:

• Có 80% số điểm ~1 ≤ 𝑁~, ~𝑀 ≤ 10^6~;

• Có 20% số điểm không có ràng buộc gì thêm.

Ví dụ:

Input1

10 20

Output1

15

Input2

23 24

Output2

-1

Mật thư là một xâu kí tự gồm các chữ cái tiếng Anh in hoa. Để mã hóa mật thư, Ban tổ chức xếp các chữ cái theo vòng tròn: đứng sau ~𝐴~ là ~𝐵~, đứng sau ~𝐵~ là ~𝐶~,…, đứng sau ~𝑍~ là ~𝐴~. Xâu mã hoá của mật thư được tạo ra bằng cách thay thế lần lượt các kí tự trong mật thư bằng xâu mã hoá tương ứng. Các kí tự trong mật thư được mã hoá như sau: Mỗi kí tự ~𝑥~ được mã hoá là xâu ~𝑦𝑘~ trong đó ~𝑘~ là một số tự nhiên được Ban tổ chức lựa chọn và ~𝑦~ là kí tự đứng sau ~𝑥~ ~𝑘~ vị trí.

Ví dụ: ~𝐴7𝐾2𝑃2~ là xâu mã hoá của xâu ~𝑇𝐼𝑁~; ~𝐴7~ là xâu mã hóa của ~𝑇~ (đứng sau ~𝑇~ 7 vị trí là ~𝐴~), ~𝐾2~ là xâu mã hóa của ~𝐼~ (đứng sau ~𝐼~ 2 vị trí là ~𝐾~), ~𝑃2~ là xâu mã hóa của ~𝑁~ (đứng sau ~𝑁~ 2 vị trí là ~𝑃~).**

Yêu cầu: Cho ~𝑆~ là xâu mã hoá của mật thư, hãy tìm mật thư tương ứng với ~𝑆~.

Dữ liệu vào:

• Ghi xâu ~𝑆~ có không quá 300000 kí tự.

Kết quả:

• Ghi xâu mật thư tìm được.

Ràng buộc:

• Có 80% số điểm ~0 ≤ 𝑘 ≤ 9~; • Có 20% số điểm ~0 ≤ 𝑘 ≤ 10000~.

Ví dụ:

Input

U1K2Q3L4P1F3

Output

TINHOC

Có 𝑁 gói kẹo được đánh số từ 1 đến ~𝑁~, gói thứ ~𝑖~ có số kẹo là số nguyên dương ~𝑎_𝑖~ (~1 ≤ 𝑖 ≤ 𝑁~). Vương quốc Alpha có ~𝐾~ cháu được nhận kẹo, Quốc Vương muốn chọn các gói kẹo liên tiếp nhau sao cho tổng số kẹo trong các gói có thể chia đều cho các cháu và số kẹo mỗi cháu được nhận là lớn nhất.

Yêu cầu: Xác định số kẹo nhiều nhất mà mỗi cháu có thể nhận được.

Dữ liệu vào:

• Dòng đầu ghi hai số nguyên dương ~𝑁~, ~𝐾~ (~1 ≤ 𝐾 ≤ 10000~);

• Dòng thứ hai ghi 𝑁 số lần lượt ~𝑎_1, 𝑎_2, … , 𝑎_𝑁~ có giá trị không quá 10000; Các số trong tệp ghi cách nhau ít nhất một dấu cách.

Kết quả:

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

Ràng buộc:

• Có 50% số điểm ~10 ≤ 𝑁 ≤ 200~;

• Có 30% số điểm ~200 < 𝑁 ≤ 10000~;

• Có 20% số điểm ~10000 < 𝑁 ≤ 1000000~.

Ví dụ:

Input

6 3
1 3 3 4 5 4

Output

5

Giải thích:

• Chọn các gói {3,3,4,5} có tổng số kẹo là 15. Do đó số kẹo mỗi cháu nhận được là 5.

Cho một bảng số gồm 𝑀 dòng và 𝑁 cột, các dòng được đánh số từ 1 đến ~𝑀~, các cột được đánh chỉ số từ 1 đến ~𝑁~, ô ở dòng 𝑖 cột 𝑗 có giá trị bằng ~𝑖^2 + 𝑗^2~. Các số trong bảng được sắp xếp tăng dần tạo thành dãy ~𝐴~ có các phần tử được đánh chỉ số từ 1 đến ~𝑀 × 𝑁~.

Yêu cầu: Cho biết 𝑇 số nguyên ~𝑥_1, 𝑥_2, … , 𝑥_𝑇~, hãy tìm giá trị thứ ~𝑥_𝑖~ của dãy ~𝐴~.

Dữ liệu vào:

• Dòng đầu ghi ba số nguyên dương ~𝑀~, ~𝑁~, ~𝑇~ (~1 ≤ 𝑇 ≤ 10~);

• Dòng thứ hai ghi ~𝑇~ số lần lượt ~𝑥_1, 𝑥_2, … , 𝑥_𝑇~ (~1 ≤ 𝑥_𝑖 ≤ 𝑀 × 𝑁~); Các số trong tệp ghi cách nhau ít nhất một dấu cách.

Kết quả:

• Gồm ~𝑇~ dòng, mỗi dòng ghi một giá trị tương ứng tìm được.

Ràng buộc:

• Có 50% số điểm ~1 ≤ 𝑀~, ~𝑁 ≤ 500~;

• Có 30% số điểm ~1 ≤ 𝑀 × 𝑁 ≤ 1000000~;

• Có 20% số điểm ~10000 < 𝑀, 𝑁 ≤ 100000~.

Ví dụ:

Input

3   4   2
3   8   

Output

5
13

Giải thích: