Đề bài được tóm tắt theo trí nhớ.

Cho hai đường tròn đồng tâm ~O~ có bán kính lần lượt là ~R_1, R_2~ nguyên dương.

Yêu cầu: Đếm số điểm tọa độ nguyên thuộc hình tròn ~(O, R_2)~ nhưng không thuộc hình tròn ~(O, R_1)~ với ~R_1 < R_2~. Biết rằng, khoảng cách từ điểm ~M(x, y)~ đến gốc tọa độ ~O(0, 0)~ là ~\sqrt{x^2 + y^2}~.

INPUT

Nhập vào hai số nguyên dương ~R_1,~ ~R_2~ (~R_1 < R_2 \le 10^8~)

OUTPUT

In ra số nguyên duy nhất là kết quả tìm được.

SAMPLE INPUT

2 3

SAMPLE OUTPUT

16

SUBTASKS

Đề bài được tóm tắt theo trí nhớ.

Cho số nguyên ~n~ và xâu ~X~ chỉ gồm các ký tự A, U, G, C.

Yêu cầu: Hãy tìm dãy con ~[l, r]~ liên tiếp dài nhất thỏa mãn sao cho tồn tại một loại ký tự có số lượng đúng bằng ~[\frac{r - l + 1}{2}] + 1~.

INPUT

Dòng đầu tiên nhập vào số nguyên dương ~n~ (~1 \le n \le 2 \times 10^5~).

Dòng thứ hai nhập xâu ~X~ gồm ~n~ ký tự, mỗi ký tự thuộc một trong 4 chữ cái A, U, G, C.

OUTPUT

In ra số nguyên duy nhất là kết quả tìm được.

SAMPLE INPUT

8
ACUGUCGG

SAMPLE OUTPUT

5

SUBTASKS

Đề bài được tóm tắt theo trí nhớ.

Cho số nguyên dương ~n~ (~1 \le n \le 10^5~) và mảng ~a~ nguyên dương ~a_1, a_2, ..., a_n~ (~a_i \le 10^9~) phân biệt.

Cho ~q~ truy vấn, mỗi truy vấn gồm hai số ~i~ ~j~ (~1 \le i < j \le n~).

Yêu cầu: Tìm đoạn con dài nhất chứa hai chỉ số ~i~ và ~j~ sao cho:

• Nếu ~a_i < a_j~ thì tất cả các phần tử trong đoạn đó nhận ~a_i~ làm GTNN, ~a_j~ làm GTLN.
• Nếu ~a_j < a_i~ thì tất cả các phần tử trong đoạn đó nhận ~a_j~ làm GTNN, ~a_i~ làm GTLN.

INPUT

Dòng đầu tiên nhập vào hai số nguyên dương ~n~ và ~q~ (~n, q \le 10^5~)

Dòng thứ hai nhập vào ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ (~a_i \le 10^9~). Dữ liệu đảm bảo các số nguyên dương ~a_1, a_2, ..., a_n~ phân biệt.

~q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~i, j~ (~i < j~).

OUTPUT

In ra ~q~ dòng, mỗi dòng ghi hai số nguyên dương lần lượt là chỉ số đầu và chỉ số cuối của đoạn con thu được thỏa mãn yêu cầu đề bài. Nếu không có phương án thỏa mãn, in ra ~-1~.

SAMPLE INPUT

8 3
10 7 4 5 8 6 3 20
3 5
5 7
2 6

SAMPLE OUTPUT

2 6
2 7
-1

SUBTASKS

Đề bài được tóm tắt theo trí nhớ.

Cho mảng hai chiều kích thước ~m \times n~ là khu vực hoạt động của robot, mỗi ô có kích thước là ~1 \times 1~. Ô có vị trí tại hàng thứ ~i~, cột thứ ~j~ sẽ có giá trị là ~a_{i, j}~. Robot được lập trình để di chuyển theo quy định sau:

• Giả sử robot được đặt tại ô (~i, j~), khi này, robot chỉ có thể di chuyển sang ô kề phải (~i, j+1~) hoặc ô ngay dưới (~i+1, j~).
• Robot phải trả phí mỗi khi đến ô mới bất kỳ. Chi phí của ô (~i, j~) là tổng các ước nguyên dương của số ~a_{i, j}~ không kể chính nó.

Yêu cầu: Tính chi phí nhỏ nhất để robot di chuyển từ ô (~1, 1~) đến ô (~m, n~).

INPUT

Dòng đầu tiên nhập vào hai số nguyên dương ~m~ và ~n~ (~m, n \le 10^3~)

~m~ dòng tiếp theo, mỗi dòng gồm ~n~ số nguyên dương ~a_{i, j}~ (~a_{i, j} \le 10^9~).

OUTPUT

In ra một số nguyên duy nhất là đáp số đề bài.

SAMPLE INPUT

2 6
1 3 9 9 3 8
3 6 8 7 6 8

SAMPLE OUTPUT

23

SUBTASKS