Cho một dãy gồm n số nguyên dương \(𝑎_1,𝑎_2,...,𝑎_𝑛\) và một số nguyên dương \(𝑚\). Hãy lập trình xác định một số nguyên dương \(d\) lớn nhất sao cho:

• \(𝑑\) có giá trị không vượt quá \(𝑚\).

• \(𝑎_1\) mod \(𝑑\) = \(𝑎_2\) mod \(𝑑\) = ... = \(𝑎_𝑛\) mod \(𝑑\) trong đó mod là phép chia lấy phần dư, ví dụ \(15\) mod \(6\) = \(3\) (Phép toán \(%\) trong C++ và Python)

Input

Dòng đầu khi số nguyên \(𝑛\) và \(𝑚\).

Dòng thứ hai ghi \(𝑛\) số nguyên \(𝑎_1,𝑎_2,...,𝑎_𝑛\), mỗi số có giá trị không vượt quá \(𝑚\).

Output

Một số nguyên là kết quả tìm được.

Scoring

• \(50\%\) số điểm tương ứng với các test có \(𝑛,𝑚≤10^3\).
• \(30\%\) số điểm tương ứng với các test có \(𝑛≤10^3, 𝑚≤10^{18}\).
• \(20\%\) số điểm tương ứng với các test có \(𝑛≤10^5, 𝑚≤10^{18}\).

5 34
23 17 26 14 23

3

2 10
2 10

8

Trong một thành phố thông minh, hệ thống cảm biến giao thông gửi dữ liệu liên tục về trung tâm xử lí, mỗi tín hiệu cảm biến là một số nguyên dương. Tuy nhiên, do lỗi kĩ thuật, có những chuỗi tín hiệu bị trùng lặp ba lần liên tiếp gây nhiễu loạn quá trình phân tích. Đội kĩ thuật cần làm sạch tín hiệu theo quy tắc đặc biệt để đảm bảo dữ liệu đầu vào là tối ưu nhất.

Chuỗi tín hiệu ban đầu là một dãy số nguyên có \(𝑛\) số. Hệ thống sẽ lọc nhiễu tín hiệu trên chuỗi đó theo quy trình như sau:

• Bước \(1\). Từ trái sang phải, nếu phát hiện \(3\) tín hiệu liên tiếp giống nhau, hệ thống xóa bộ ba này khỏi dãy và đánh lại chỉ số từ đầu, rồi chuyển sang bước \(2\).

• Bước \(2\). Từ phải sang trái, nếu phát hiện \(3\) tín hiệu liên tiếp giống nhau, hệ thống xóa bộ ba này khỏi dãy và đánh lại chỉ số từ đầu, rồi chuyển về bước \(1\).

Quy trình này lặp lại cho đến khi không còn bộ ba nào giống nhau liên tiếp.

Yêu cầu

Viết chương trình mô phỏng quy trình lọc nhiễu tín hiệu và ghi ra kết quả.

Input

Dòng thứ nhất chứa số nguyên dương \(𝑛\) \((3≤𝑛≤3.10^5)\);
Dòng thứ hai chứa 𝑛 số nguyên dương \(𝐴_𝑖 (1≤𝐴_𝑖≤10^4)\).

Output

Dãy số nguyên dương \(A\) sau khi xóa.

14
1 1 3 3 3 1 1 2 1 1 2 2 2 1

1 2

Cho dãy số gồm \(𝑛\) số nguyên không âm \(𝑎_1,𝑎_2,…,𝑎_𝑛\). Hãy tìm số chính phương nhỏ nhất không xuất hiện trong dãy số đã cho.

Biết rằng: Số chính phương là số tự nhiên mà có thể viết dưới dạng bình phương của một số tự nhiên khác.

Ví dụ: \(0, 1, 4, 9, 16, 25, ...\) là các số chính phương, còn các số: \(2, 3, 5, ...\) không là số chính phương.

Input

Dòng đầu tiên chứa số nguyên \(𝑛 (1≤𝑛≤10^6)\).

Dòng thứ hai chứa \(𝑛\) số nguyên \(𝑎_1,𝑎_2,…,𝑎_𝑛 (0≤𝑎_𝑖≤10^{12})\), các số cách nhau một dấu cách.

Output

Một số nguyên duy nhất là kết quả của bài toán.

Scoring

Subtask \(1\): \(50\%\) số test đầu tiên có \(𝑛≤10,0≤𝑎_𝑖≤10^4\).
Subtask \(2\): \(30\%\) số test tiếp theo có \(10^3<𝑛≤10^6,0≤𝑎_𝑖≤10^6\).
Subtask \(3\): \(20\%\) số test cuối cùng có \(0≤𝑎_𝑖≤10^{12}\).

8
0 3 4 2 1 4 16 25

9

Chữ số tận cùng của một số là chữ số cuối cùng của số đó.

Ví dụ: Số \(268\) có chữ số tận cùng là \(8\); số \(7\) có chữ số tận cùng là \(7\).

Yêu cầu

Cho hai số nguyên dương \(𝑎,𝑏\). Hãy tìm chữ số tận cùng của \(𝑎^𝑏 (1 \leq a,b \leq 10^9)\)

Input

Một dòng duy nhất ghi hai số nguyên dương lần lượt là \(𝑎,𝑏\). Hai số cách nhau một dấu cách.

Output

Một số nguyên duy nhất là chữ số tận cùng tìm được.

3 4

1