Học sinh giỏi 9 Khánh Hòa 2025-2026

Nấm là cô bé đáng yêu và tốt bụng. Cô bé đặc biệt thích truyện cổ tích. Vì thế, đêm qua, Nấm nằm mơ về nàng Lọ Lem. Trong giấc mơ, Lọ Lem không bị mụ dì ghẻ bắt phân loại các loại đậu nữa mà bắt nhặt gạo. Có rất nhiều gạo trong kho, các hạt gạo đã được đánh số thứ tự là số nguyên liên tiếp từ \(a\) tới \(b\). Mụ bắt nàng phải nhặt ra các hạt gạo có số thứ tự là bội của một số \(k\) cho trước. Đồng thời sau khi nhặt xong phải trả lời cho mụ biết số lượng hạt gạo nhặt được. Việc nhặt gạo thì quá đơn giản, chỉ trong tích tắc bầy chim đã giúp nàng nhặt xong. Bây giờ nhiệm vụ của Nấm là đếm số lượng hạt gạo đã nhặt được. Thật không may, chưa đếm xong thì Nấm đã tỉnh dậy. Nấm rất muốn có câu trả lời cho Lọ Lem.

Yêu cầu: Hãy trả lời giúp Nấm, nếu hoàn thành phần việc của mình, Nấm sẽ đếm được bao nhiêu hạt gạo?

Input

• Dữ liệu vào từ tệp văn bản DEMGAO.INP gồm ba số nguyên dương \(a\), \(b\) và \(k\) ghi trên cùng 1 dòng (\(1 \leq a \leq b \leq 10^{18}\); \(1 \leq k \leq 10^{18}\)).

Output

• Ghi ra tệp văn bản DEMGAO.OUT một số nguyên duy nhất là kết quả cần tìm.

Example

3 10 5

2

6 9 5

0

Scoring

• \(70\%\) số test tương ứng với \(70\%\) số điểm có \(1 \leq a \leq b \leq 10^6\).
• \(30\%\) số test còn lại tương ứng \(30\%\) số điểm không có ràng buộc gì thêm.

Một từ được định nghĩa là một hoặc một dãy các kí tự liên tiếp nhau và không chứa dấu cách (kí tự trắng). Độ dài của một từ là số kí tự có trong từ đó.

Cho xâu gồm các kí tự A..Z, a..z, 0..9, kí tự trắng (dấu cách).

Yêu cầu: Tìm độ dài của từ có nhiều kí tự nhất và từ tương ứng với độ dài đó.

Lưu ý: nếu có nhiều từ có cùng độ dài lớn nhất thì ghi từ có độ dài lớn nhất sau cùng trong xâu.

Input

• Dữ liệu vào từ tệp văn bản TUDAI.INP gồm 1 dòng duy nhất chứa xâu (độ dài xâu không quá \(255\) kí tự và trong xâu chứa ít nhất một từ).

Output

• Ghi ra tệp văn bản TUDAI.OUT gồm 2 dòng:
  • Dòng 1: Ghi độ dài của từ có nhiều kí tự nhất (độ dài lớn nhất).
  • Dòng 2: Ghi từ có độ dài lớn nhất.

Example

Khanh Hoa que huong toi

5
huong

Tí đang chơi trò ghép nhà từ những que tính. Phần căn nhà đã được ghép xong, chỉ còn thiếu một cửa sổ hình chữ nhật. Hiện tại, Tí còn dư \(n\) que tính, các que tính được đánh số thứ tự từ \(1\) tới \(n\), que thứ \(i\) có độ dài \(a_i\) (đơn vị đo chiều dài). Tí muốn ghép được cửa sổ càng to càng tốt. Một cửa sổ sẽ được ghép từ 4 que tính.

Yêu cầu: Hãy cho biết chu vi của cửa sổ lớn nhất mà Tí có thể ghép được.

Lưu ý: Không bẻ gãy hay chắp nối để thay đổi chiều dài que tính và hình vuông cũng được xem là hình chữ nhật.

Input

• Dòng đầu chứa số nguyên dương \(n\) \((1 \leq n \leq 10^6)\).
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_i\) \((1 \leq a_i \leq 10^6;\ 1 \leq i \leq n)\).

Output

• Ghi ra số nguyên duy nhất là chu vi lớn nhất của cửa sổ có thể ghép được. Nếu không thể ghép được thì ghi \(-1\).

Example

7
3 8 4 3 8 1 1

22

5
4 9 1 9 3

-1

Scoring

• \(30\%\) số test tương ứng với \(30\%\) số điểm có \(n \leq 50\).
• \(40\%\) số test tương ứng với \(40\%\) số điểm có \(50 < n \leq 1000\).
• \(30\%\) số test còn lại tương ứng với \(30\%\) số điểm không có ràng buộc gì thêm.

Hôm nay, An được học về số nguyên tố. Số nguyên tố là số có đúng hai ước nguyên dương là 1 và chính nó. Ví dụ số 17 là số nguyên tố nhưng số 16 thì không.

Vốn là người có nhiều ý tưởng sáng tạo, An đưa ra một khái niệm mới gọi là "số nguyên tố toàn diện". Một số nguyên dương \(x\) gọi là số nguyên tố toàn diện nếu thỏa mãn đồng thời 3 điều kiện sau:

• \(x\) là số nguyên tố.
• Lần lượt bỏ đi các chữ số bên phải của \(x\) thì phần còn lại của nó vẫn là số nguyên tố.
• Thêm vào bên phải của \(x\) một trong các chữ số từ 0 tới 9, số thu được cũng là số nguyên tố.

Ví dụ số 313 là số nguyên tố toàn diện vì:

• 313 là số nguyên tố.
• Bỏ đi số 3 bên phải ta còn số 31 là số nguyên tố, bỏ tiếp số 1 ta còn số 3 cũng là số nguyên tố.
• Thêm số 7 vào sau 313 ta được số 3137 là số nguyên tố.

Yêu cầu: Cho dãy \(A\) gồm \(n\) số nguyên dương \(a_1, a_2, \ldots, a_n\) và \(m\) câu hỏi. Mỗi câu hỏi có dạng \((u, v)\) với ý nghĩa: Đếm số lượng số nguyên tố toàn diện trong dãy \(A\) từ vị trí \(u\) tới \(v\).

Input

• Dòng đầu chứa số nguyên \(n\) \((1 \le n \le 10^5)\).
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2, \ldots, a_n\) \((1 \le a_i \le 10^6;\ 1 \le i \le n)\).
• Dòng thứ ba chứa số nguyên \(m\) là số lượng câu hỏi \((1 \le m \le 10^5)\).
• \(m\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(u, v\) \((1 \le u \le v \le n)\).

Output

• Ghi ra \(m\) dòng, mỗi dòng là đáp án của một câu hỏi theo thứ tự của các câu hỏi được đưa ra trong tệp dữ liệu vào.

Example

6
59 12 57 53 23 313
3
1 3
2 5
3 6

1
1
2

Scoring

• 70% số test tương ứng với 70% số điểm có \(1 \le n \le 10^3\); \(1 \le a_i \le 10^3\); \(1 \le m \le 10^3\).
• 30% số test còn lại tương ứng với 30% số điểm không có ràng buộc gì thêm.