Trong tiết học môn Toán về chủ đề tìm ước chung lớn nhất (UCLN), bội chung nhỏ nhất (BCNN) của hai số nguyên dương \(A, B\), Bình dễ dàng tìm được \(UCLN(A, B)\) là \(m\), \(BCNN(A, B)\) là \(n\). Hôm nay, cô giáo đưa ra bài toán sau:

Cho trước hai số nguyên dương \(m\) và \(n\). Nếu tìm được một hoặc nhiều cặp số \((A, B)\) thỏa mãn \(UCLN(A, B) = m, BCNN(A, B) = n\) thì đưa ra giá trị nhỏ nhất của tổng \(A + B\), ngược lại đưa ra \(-1\).

Bình đang loay hoay tìm cách giải. Bạn hãy giúp Bình giải bài toán trên.

Yêu cầu: Tìm giá trị nhỏ nhất của tổng \(A + B\), nếu không tìm được cặp số \((A, B)\) nào thì đưa ra \(-1\)./

Input

• Một dòng duy nhất chứa hai số nguyên dương \(m\) và \(n\) \((1 \leq m \leq n \leq 10^{12})\).

Output

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

Scoring

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

Example

2 10

12

2 20

14

3 5

-1

Thật là thú vị, khi Tuấn nhập \(n = 5\). ChatGPT đưa ra kết quả là: Có 4 số, cụ thể là các số: \(1, 2, 3, 4\). Tuấn muốn các bạn lập trình giải bài toán này để cùng kiểm tra kết quả của ChatGPT nhé.

Input: Dữ liệu cho trong tệp văn bản NTCN.INP gồm một số nguyên dương \(n\ (2 ≤ n ≤ 2 \times 10)\).
Output: Kết quả ghi ra tệp văn bản NTCN.OUT gồm một số nguyên duy nhất là số lượng các số nguyên dương \(x\), nhỏ hơn \(n\) và nguyên tố cùng nhau với \(n\).

Scoring

• Có 50% số test ứng với 50% số điểm thỏa mãn: \(2 ≤ n ≤ 2000\).
• Có 40% số test ứng với 40% số điểm thỏa mãn: \(2000<n≤2×10^6\)
• Có 10% số test ứng với 10% số điểm thỏa mãn: \(2 × 10^6 <n≤2 \times 10^9\)

Example

5

4

10

4

Công ty X chuyên sản xuất các mặt hàng tiêu dùng. Sau mỗi lần tạo ra một sản phẩm, trên bao bì được in một mã sản phẩm, đồng thời hệ thống máy tính tự động lưu mã sản phẩm vào tệp văn bản trên máy tính. Các kí tự trong mỗi mã sản phẩm được viết liền nhau gồm hai phần:

• Phần đầu là các kí tự chữ cái;
• Phần sau là các kí tự chữ số (phần chữ số).

Tất cả các mã sản phẩm được cập nhật liên tục và liền kề nhau. Để thuận tiện cho việc tổng hợp sau này, lãnh đạo công ty yêu cầu tách phần chữ số trong các mã sản phẩm và sắp xếp theo thứ tự không giảm của giá trị số.

Bạn hãy viết chương trình giúp công ty X thực hiện công việc trên.

Yêu cầu: Đưa ra phần chữ số các mã sản phẩm theo thứ tự không giảm của giá trị số, nếu giá trị của các phần chữ số bằng nhau thì đưa ra theo thứ tự từ trái qua phải.

Input

• Một dòng duy nhất chứa một xâu kí tự \(S\) \((1 \leq |S| \leq 10^{6})\) là các mã sản phẩm ban đầu.

Output

• Ghi ra dãy các phần chữ số thỏa mãn yêu cầu bài toán. Giữa các phần chữ số cách nhau bởi một dấu cách trống.

Scoring

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

Example

abcd65mnpq25

25 65

aBc003mMpq001xyz25hthhtpq3

001 003 3 25

Anh An là nhân viên kỹ thuật trong nhà máy X trên địa bàn tỉnh. Nhà máy được trang bị dây chuyền sản xuất hiện đại, tất cả các sản phẩm khi đi qua băng chuyền được máy tính đánh mã loại và lưu lại. Sản phẩm thứ \(i\) đi qua băng chuyền được gán bởi một số nguyên dương \(a_{i}\) là mã loại tương ứng (các sản phẩm giống nhau thì có cùng một mã loại). Trong một công đoạn sản xuất, có \(n\) sản phẩm đi qua băng chuyền được máy tính đánh mã loại và lưu lại thành một dãy \(A\) gồm các số nguyên dương \(a_{1}, a_{2}, \ldots, a_{n}\). Kết thúc công đoạn, lãnh đạo công ty yêu cầu anh An báo cáo số lượng tất cả các dãy con của dãy \(A\) thỏa mãn có ít nhất \(k\) sản phẩm cùng mã loại, với dãy con là dãy được tạo từ các phần tử liên
tiếp của dãy \(A\).

Bạn hãy viết chương trình giúp anh An giải quyết bài toán trên.

Yêu cầu: Đưa ra số lượng tất cả các dãy con của dãy A có ít nhất k sản phẩm cùng mã loại

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n\) và \(k\) \((1 \leq k \leq n \leq 4 \times 10^{5})\).
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_{1}, a_{2}, \ldots, a_{n}\) \((1 \leq a_{i} \leq 10^{6})\).

Output

• Ghi ra một dòng chứa một số nguyên dương thỏa mãn yêu cầu bài toán.

Scoring

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

Example

5 2
1 2 1 2 1

6

Dọc theo tuyến đường giao thông liên xã của xã \(A\) và xã \(B\) có \(n\) ngôi nhà được chiếu sáng bởi \(m\) cột đèn điện công cộng. Tuyến đường giao thông liên xã được xem là một đường thẳng, gốc tọa độ được đặt tại trường trung học cơ sở của xã \(A\) nằm trên tuyến đường đó. Mỗi đèn điện có cường độ, phạm vi chiếu sáng nhất định. Ngôi nhà thứ \(i\) nằm trên tọa độ \(a_{i}\), cột đèn điện thứ \(j\) nằm trên tọa độ \(b_{i}\). Mỗi ngôi nhà sẽ được chiếu sáng nếu khoảng cách từ cột đèn điện đến ngôi nhà không quá giá trị \(d\) \((|a_{i} − b_{i}| \leq d)\); nếu cột đèn điện đặt tại cổng ngôi nhà nào đó thì xem như \(d = 0\). Để đảm bảo an toàn giao thông, mỗi ngôi nhà cần ít nhất được một đèn điện chiếu sáng.

Yêu cầu: Hãy tìm giá trị \(d\)# tối thiểu sao cho mỗi ngôi nhà được ít nhất một đèn điện chiếu sáng.

Input

• Dòng đầu tiên gồm hai số nguyên dương \(n\) và \(m\) \((1 \leq n, m \leq 10^{5})\).
• Dòng thứ hai gồm \(n\) số nguyên \(a_{1}, a_{2}, \ldots, a_{n}\) \((-10^{9} \leq a_{i} \leq 10^{9})\).
• Dòng thứ ba gồm \(m\) số nguyên \(b_{1}, b_{2}, \ldots, b_{n}\) \((-10^{9} \leq b_{i} \leq 10^{9})\).

Output

• Ghi ra một dòng chứa một số nguyên là giá trị \(d\) cần tìm.

Scoring

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

Example

3 2
-2 2 4
-3 0

4

5 3
1 5 10 14 17
4 11 15

3