Cho lưới hình chữ nhật có kích thước ~m \times n~, gồm các hình vuông đơn vị.

Yêu cầu

Hãy đếm số lượng hình vuông có kích thước lớn nhất được tạo bởi những hình vuông đơn vị trong hình chữ nhật đã cho.

Trong hình chữ nhật (AGNH) ở hình minh họa trên, có ~3~ hình vuông kích thước lớn nhất được tạo thành: (AELH); (BFMI); (CGNJ).

Dữ liệu đầu vào

Gồm một dòng chứa hai số nguyên dương ~m, n~ ~(1 \le m, n \le 10^{18})~.

Dữ liệu đầu ra

Gồm một số nguyên là số lượng hình vuông tìm được.

Ràng buộc dữ liệu

• Subtask 1: Có 50% điểm số với ~1 \le m, n \le 1000~.
• Subtask 2: Có 50% điểm số không có thêm ràng buộc gì.

Ví dụ

Ví dụ 1

INPUT

4 6

OUTPUT

3

Ví dụ 2

INPUT

1 5

OUTPUT

5

Lan có một chiếc vòng hạt nhiều màu, mỗi màu của hạt được mã hóa bằng một chữ cái Tiếng Anh in hoa. Trong một lần tham dự lễ hội, Lan vô tình làm đứt chiếc vòng của mình. Đây là quà tặng rất ý nghĩa nên Lan muốn nối lại chiếc vòng để sử dụng tiếp. Lan muốn vị trí điểm nối nằm giữa hai hạt cùng màu. Như vậy, có thể phải bỏ đi một số hạt ở hai đầu.

Yêu cầu

Bạn hãy giúp Lan, nối lại vòng với số lượng hạt còn lại nhiều nhất.

Dữ liệu đầu vào

Gồm xâu ký tự gồm các chữ cái in hoa, mỗi chữ cái tương ứng với một màu của hạt.

Dữ liệu đầu ra

Gồm một số nguyên duy nhất là số lượng hạt của vòng sau khi nối.

Ràng buộc dữ liệu

• Subtask 1: Có 50% điểm số với chuỗi hạt chỉ có hai màu.
• Subtask 2: Có 50% điểm số ứng với chuỗi có số lượng hạt không quá ~10^5~ và số màu của hạt không hạn chế.

Ví dụ

Ví dụ 1

INPUT

ABCQWERTYYA

OUTPUT

11

Giải thích: Không bỏ hạt nào vì hai hạt ở hai đầu chuỗi giống nhau.

Ví dụ 2

INPUT

ABCQWERTYYATY

OUTPUT

11

Giải thích: Bỏ đi ~2~ hạt cuối chuỗi, để hai đầu chuỗi có cùng màu A.

Ví dụ 3

INPUT

AABABABBB

OUTPUT

7

Giải thích: Bỏ đi ~2~ hạt ở đầu chuỗi.

Thời gian gần đây, phong trào chạy việt dã phát triển nở rộ ở khắp các tỉnh thành trên toàn quốc. Năm nay, các vận động viên tập trung về tỉnh Hòa Bình tham gia giải chạy Hòa Bình Marathon. Để đảm bảo hỗ trợ tốt nhất cho các vận động viên tham gia giải, chủ nhà Hòa Bình đã bố trí ~N~ tình nguyện viên tại ~N~ vị trí trên đường chạy. Để đảm bảo các tình nguyện viên được sắp xếp một cách hợp lí, Ban tổ chức đưa ra ~Q~ câu hỏi, mỗi câu hỏi yêu cầu cho biết số tình nguyện viên trên đoạn đường cho trước.

Yêu cầu

Em hãy viết chương trình để trả lời các câu hỏi của ban tổ chức.

Dữ liệu đầu vào

Gồm ~Q + 2~ dòng:

• Dòng đầu chứa hai số nguyên dương ~N, Q~ ~(1 \le N \le 10^5;\ 1 \le Q \le 10^5)~.
• Dòng thứ hai chứa ~N~ số nguyên phân biệt ~x_1, x_2, ..., x_N~ là vị trí các tình nguyện viên ~(0 \le x_i \le 10^9;\ 1 \le i \le N)~.
• ~Q~ dòng tiếp theo mỗi dòng chứa hai số nguyên ~A~ và ~B~, ứng với mỗi câu hỏi của Ban tổ chức ~(0 \le A, B \le 10^9)~.

Dữ liệu đầu ra

Gồm ~Q~ dòng, mỗi dòng tương ứng với câu trả lời cho câu hỏi của Ban tổ chức.

Ràng buộc dữ liệu

• Subtask 1: Có 50% điểm số ứng với ~N \le 100;\ Q \le 1000~.
• Subtask 2: Có 50% điểm số ứng với các trường hợp còn lại.

Ví dụ

Ví dụ 1

INPUT

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

OUTPUT

2
2
3
4
1
0

Trong bài toán này, người ta định nghĩa hai số nguyên tố được gọi là cặp số nguyên tố hấp dẫn nếu độ lệch tuyệt đối giữa chúng là ~6~.

Cho một mảng ~A~ gồm có ~N~ số tự nhiên.

Yêu cầu

Nhiệm vụ của bạn là đếm tất cả các cặp số nguyên tố hấp dẫn trong ~A~.

Ví dụ: ~A = \{6, 7, 5, 11, 13\}~, có ~2~ cặp số nguyên tố hấp dẫn là ~(5, 11)~ và ~(7, 13)~.

Dữ liệu đầu vào

Gồm hai dòng:

• Dòng đầu tiên chứa một số nguyên dương ~N~ ~(2 \le N \le 10^5)~.
• Dòng tiếp theo chứa ~N~ số nguyên ~A_1, A_2, ..., A_N~, mỗi số cách nhau một dấu cách ~(1 \le A_i \le 10^6;\ 1 \le i \le N)~.

Dữ liệu đầu ra

Gồm một số nguyên duy nhất là đáp số của bài toán.

Ràng buộc dữ liệu

• Subtask 1: Có 30% điểm số ứng với ~N \le 100~, dãy ~A~ gồm các số nguyên dương không quá ~1000~.
• Subtask 2: Có 70% điểm số ứng với các trường hợp còn lại.

Ví dụ

Ví dụ 1

INPUT

5
6 7 5 11 13

OUTPUT

2

Ví dụ 2

INPUT

4
2 4 6 11

OUTPUT

0

Giải thích: Dãy không có cặp số nguyên tố hấp dẫn nào.