Contest giao lưu Tin học trẻ 2024 - Lần thứ Hai (Bảng A)

Bạn được cho hai số tự nhiên \(a, b\). Tìm hai số tự nhiên \(x, y\) sao cho \(a \le x < y \le b\) và \(x \times y\) là số lẻ và lớn nhất.

Input

• Hai số tự nhiên \(a, b\) trên hai dòng \(0 \le a < b \le 10^9\).

Output

• Hai số tự nhiên \(x, y\) sao cho \(x \times y\) lẻ lớn nhất. Nếu không tồn tại kết quả in ra -1. Nếu có nhiều kết quả in ra kết quả có \(y\) lớn nhất.

Example

1
4

1 3

Subtask

• Subtask 1 (\(60\%\) số điểm): \(0 \le a \le b \le 500\).
• Subtask 2 (\(40\%\) số điểm): Không có giới hạn gì thêm.

Cho một xâu gồm toàn các ký tự số (từ 0 đến 9), có thể có số 0 ở đầu. Bạn cần loại bỏ đi chính xác một ký tự của xâu sao cho số thu được khi loại bỏ các chữ số 0 vô nghĩa ở xâu còn lại là lớn nhất.

Input

• Một xâu có ít nhất 2 và nhiều nhất \(10^6\) ký tự biểu diễn số (xâu này có thể có các chữ số 0 ở đầu).

Output

• Một số duy nhất là số lớn nhất thu được sau khi bỏ hết các chữ số 0 vô nghĩa.

Example

123

23

100

10

Scoring

• Subtask \(1\) (\(30\%\) số điểm): có không quá 3 chữ số.
• Subtask \(2\) (\(30\%\) số điểm): có không quá \(1000\) chữ số.
• Subtask \(3\) (\(40\%\) số điểm): Không có giới hạn gì thêm.

Cho \(n\), tính tổng số lượng các ước số chính phương của tất cả các số nguyên từ \(1\) đến \(n\). Cụ thể, xét các số \(1, 2, 3, \ldots, n\), hãy đếm tổng số lượng các ước số là số chính phương của tất cả các số này.

Input

• Một dòng duy nhất gồm một số nguyên dương \(n \le 10^{12}\).

Output

• Một dòng duy nhất gồm kết quả bài toán.

Example

5

6

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(1 \le n \le 10^3\).
• Subtask \(2\) (\(30\%\) số điểm): \(1 \le n \le 10^6\).
• Subtask \(3\) (\(30\%\) số điểm): Không có giới hạn gì thêm.

Một dãy chia hết là một dãy các số đôi một phân biệt \(a_1, a_2, \dots, a_k\) sao cho với mọi \(i\):

• \(L \le a_i \le R\).
• \(a_{i+1}\) chia hết cho \(a_i\) nếu \(i < k\).

Bạn được cho hai số nguyên dương \(L, R\), yêu cầu:

• Xác định độ dài của dãy chia hết dài nhất (tìm \(k\) lớn nhất có thể).
• Trả lời xem có bao nhiêu dãy có độ dài như vậy.

Input

• Hai số nguyên dương \(L, R\) trên hai dòng (\(1 \le L \le R \le 10^{18}\)).

Output

• Hai số nguyên dương cách nhau một dấu cách: số lớn nhất có thể và số dãy có độ dài \(k\). Vì kết quả có thể rất lớn nên chỉ cần in ra \(9\) chữ số cuối của kết quả.

Example

3
16

3 2

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(R < 3 \times L\).
• Subtask \(2\) (\(30\%\) số điểm): \(R < 5 \times L\).
• Subtask \(3\) (\(20\%\) số điểm): \(R \le 1000\).
• Subtask \(4\) (\(20\%\) số điểm): Không có giới hạn gì thêm.

Nhân đang tập đếm các số \(1, 2, 3, 4, 5, \dots\) Nhận thấy việc này quá dễ, cộng với việc vừa mới học được phép nhân, Nhân quyết định đếm các số chính phương (là những số bằng một số nguyên nhân với chính nó) và viết chúng ra giấy và thu được một dãy dài có các số đầu tiên là \(149162536\dots\) Nhân muốn biết chữ số thứ \(n\) của dãy là bao nhiêu. Các bạn hãy tính giúp Nhân nhé.

Input

• Một số nguyên dương duy nhất \(n\) (\(1 \le n \le 10^{18}\)).

Output

• Chữ số thứ \(n\) của dãy.

Example

10

4

Subtask

• Subtask 1 (\(30\%\) số điểm): \(n \le 1000\).
• Subtask 2 (\(30\%\) số điểm): \(n \le 10^{12}\).
• Subtask 3 (\(40\%\) số điểm): Không có giới hạn gì thêm.