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: