Contest ôn thi HSG 9-10 (số 6)

Năm nay, An được \(a\) tuổi và Bình được \(b\) tuổi. An và Bình có cùng ngày sinh nhật. Sinh nhật không rơi vào ngày \(29/2\) năm nhuận, nên mỗi năm trôi qua, mỗi người đều tăng thêm 1 tuổi. Hai người thắc mắc rằng, liệu có một thời điểm nào đó trong tương lai, số tuổi của một người sẽ nhiều gấp \(x\) lần số tuổi của người còn lại hay không?

Yêu cầu: Cho biết \(a\), \(b\), \(x\). Hãy tính số năm ít nhất để một người có số tuổi gấp \(x\) lần số tuổi người còn lại. Nếu không tồn tại thời điểm như vậy, thông báo bằng cách in ra \(-1\).

Input

• Dòng duy nhất chứa ba số nguyên \(a\), \(b\), \(x\) cách nhau bởi dấu cách.
• Dữ liệu vào đảm bảo \(1 \leq a, b \leq 100\), \(0 \leq x \leq 100\).

Output

• Dòng duy nhất chứa kết quả bài toán.

Example

3 9 2

3

30 15 2

0

Số đẹp là số được tạo thành từ việc viết liền dãy các số tự nhiên liên tiếp. Ví dụ: \(1011121314\) là một số đẹp tạo thành từ dãy \(10, 11, 12, 13, 14\).

Yêu cầu: Cho trước số đẹp \(S\), tìm số đầu tiên và cuối cùng trong dãy số đã tạo ra \(S\). Nếu tìm thấy nhiều bộ thỏa mãn, ưu tiên chọn theo số đầu nhỏ nhất.

Input

• Dòng duy nhất chứa số đẹp \(S\) (\(1 \le S \le 10^{10^6}\))
• Dữ liệu đảm bảo số đẹp \(S\) được tạo từ dãy số tự nhiên có giá trị không quá \(10^6\)

Output

• Một dòng duy nhất chứa số đầu tiên và số cuối cùng của dãy, cách nhau bởi dấu cách

Example

9101112

9 12

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(S \le 10^9\)
• Subtask \(2\) (\(50\%\) số điểm): Không có ràng buộc thêm

Sau khi tốt nghiệp Thạc sĩ Công nghệ thông tin tại MIT, công chúa QQ được nhà vua ban thưởng. Tuy nhiên, không dễ gì mà lấy được quà từ nhà vua! Ông ta đưa ra một chuỗi vòng gồm \(n\) hạt ngọc. Các hạt ngọc được đánh số thứ tự từ \(1\) đến \(n\), trong đó, hạt ngọc thứ \(n\) và hạt ngọc thứ \(1\) nằm liên tiếp nhau. Hạt ngọc thứ \(i\) có độ lấp lánh là \(a_i\) (\(a_i\) có thể âm). Nhà vua cho phép công chúa cắt ra một đoạn liên tiếp trên chuỗi vòng đó, sao cho độ dài đoạn phải nằm trong \([L, R]\). Công chúa muốn chọn ra đoạn đẹp nhất – tức đoạn có tổng độ lấp lánh của các hạt ngọc chứa trong nó là lớn nhất. Hãy giúp công chúa nhé!

Yêu cầu: Cho biết \(n\) và \(a_1, a_2, \dots, a_n\). Hãy tìm đoạn thỏa mãn đẹp nhất.

Input

• Dòng đầu tiên chứa các số nguyên \(n, L, R\) (\(1 \leq L \leq R < n \leq 2\cdot 10^6\)).
• Dòng tiếp theo chứa \(n\) số nguyên \(a_1, a_2, a_3, \dots, a_n\) (\(|a_i| \leq 10^9\)).

Output

• Dòng duy nhất chứa giá trị cần tìm.

Example

5 2 3
3 4 -1 4 1

8

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(n \leq 300\).
• Subtask \(2\) (\(25\%\) số điểm): \(n \leq 5000\).
• Subtask \(3\) (\(20\%\) số điểm): \(n \leq 10^5\).
• Subtask \(4\) (\(15\%\) số điểm): \(L = R\).
• Subtask \(5\) (\(15\%\) số điểm): không có ràng buộc gì thêm.