Cho hai số nguyên \(N\) và \(K\).

Yêu cầu: Tìm số nguyên \(M\) nhỏ nhất sao cho \(N \times M \vdots 10^{K}\).

Input

• Gồm một dòng chứa hai số nguyên \(N, K\) \((|N| \leq 10^{9}, 0 \leq k \leq 18)\).

Output

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

Scoring

• Subtask \(1\) (\(70\%\) số điểm): \(K \leq 6\).
• Subtask \(2\) (\(30\%\) số điểm): không có ràng buộc gì thêm.

8 2

25

Cho dãy số nguyên \(A\) gồm \(N\) phần tử \(A_{1}, A_{2}, \ldots, A_{N}\) và một số nguyên \(K\).

Yêu cầu: Đếm số cặp số \(L, R\) \((1 \leq L \leq R \leq N)\) sao cho dãy con liên tiếp \(A_{L}, A_{L + 1}, \ldots, A_{R}\) có hiệu giữa số lớn nhất và số nhỏ nhất không vượt quá \(K\).

Input

• Dòng đầu tiên gồm hai số nguyên dương \(N, K\) \((N \leq 10^{5}, K \leq 10^{18})\)
• Dòng thứ hai gồm \(N\) số nguyên dương \(A_{1}, A_{2}, \ldots, A_{N}\) \((|A_{i}| \leq 10^{9})\).

Outputs

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

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(N \leq 100\).
• Subtask \(2\) (\(20\%\) số điểm): \(N \leq 5000\).
• Subtask \(3\) (\(30\%\) số điểm): không có ràng buộc gì thêm.

5 2
2 -1 3 1 3

8

Số \(T\) được gọi là số tuần hoàn chu kì \(I\) nếu tồn tại một số \(B\) có \(I\) chữ số và có thể xếp các số \(B\) cạnh nhau để thu được số \(T\). Ví dụ:

• \(10101010\) là số tuần hoàn chu kì \(2\) và cũng là số tuần hoàn chu kì \(4, 8\).
• \(2023\) là số tuần hoàn chu kì \(4\).
• \(154154\) là số tuần hoàn chu kì \(3\) và cũng là số tuần hoàn chu kì \(6\).

Yêu cầu: Tìm một số tuần hoàn chu kì \(N\) bất kì lớn hơn \(L\) và nhỏ hơn \(R\).

Input

• Gồm một dòng chứa ba số nguyên dương \(N, L, R\) \((1 \leq N \leq 10^{5}, 1 \leq L \leq R \leq 10^{10^{7}})\).

Output

• In ra một số nguyên là số tuần hoàn thỏa mãn. Nếu không có kết quả thỏa mãn, in ra \(-1\).

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(R \leq 10^{5}\).
• Subtask \(2\) (\(20\%\) số điểm): \(R - L \leq 10^{5}\).
• Subtask \(3\) (\(20\%\) số điểm): \(R = 10^{10^{7}}\).
• Subtask \(4\) (\(20\%\) số điểm): không có ràng buộc gì thêm.

Example

2 1234 9876

2222

2 1234 2000

1515

2 1234 1300

-1

Dãy số \(B\) gồm \(N\) phần tử \(B_{1}, B_{2}, \ldots, B_{M - 1}, B_{M}\) được gọi là dãy số đối xứng độ dài \(M\) khi viết dãy số theo thứ tự ngược lại vẫn thu được dãy số \(B\). Ví dụ hai dãy số \((3, 2, 3), (4, -1, -1, 4)\) là dãy số đối xứng độ dài \(3\) và \(4\).

Cho dãy số \(A\) gồm \(N\) phần tử \(A_{1}, A_{2}, \ldots, A_{N - 1}, A_{N}\) và một số nguyên dương \(K\).

Yêu cầu: Tìm cách bỏ đi ít phần tử nhất của dãy số \(A\) để thu được dãy số đối xứng có độ dài không vượt quá \(K\).

Input

• Dòng đầu tiên gồm hai số nguyên dương \(N, K\) \((1 \leq N \leq 10^{5}, 1 \leq k \leq 100)\)
• Dòng thứ hai gồm \(N\) số nguyên dương \(A_{1}, A_{2}, \ldots, A_{N - 1}, A_{N}\) \((1 \leq A_{i} \leq 10^{5})\).

Output

• In ra một số nguyên là độ dài của dãy số đối xứng thoả mãn đề bài.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(N \leq 20\).
• Subtask \(2\) (\(20\%\) số điểm): \(N \leq 10^{3}\).
• Subtask \(3\) (\(20\%\) số điểm): \(A_{i} \leq 10\).
• Subtask \(4\) (\(30\%\) số điểm): không có ràng buộc gì thêm.

Example

5 4
1 1 2 1 1

4