Cho ba số nguyên dương ~a, b, m~ (~1 ≤ a < b ≤ 10^4~, ~1 < m ≤ 10^9~).

Yêu cầu: Tìm số dư của phép chia tích các số nguyên trong đoạn ~[a; b]~ cho số ~m~.

INPUT

Một dòng duy nhất chứa ba số ~a, b, m~. Mỗi số cách nhau một dấu cách.

OUTPUT

Một dòng duy nhất ghi kết quả của bài toán.

SAMPLE INPUT

1 5 10

SAMPLE OUTPUT

0

Giải thích: ~1*2*3*4*5~ ~mod~ ~10~ ~=~ ~0~.

Cho xâu ~S~ chỉ bao gồm các kí tự chữ cái, chữ số và kí tự trắng. Một từ thuộc xâu ~S~ là một hoặc một dãy các kí tự liên tiếp nhau và không chứa kí tự trắng. Độ dài của một từ là số kí tự trong từ đó.

Yêu cầu: Cho biết độ dài của mỗi từ trong xâu ~S~.

INPUT

Một dòng duy nhất chứa xâu ~S~ (khác rỗng) có độ dài tối đa ~10^6~ kí tự.

OUTPUT

Một dòng duy nhất ghi các số nguyên là độ dài các từ trong xâu ~S~, thứ tự các số tương ứng với thứ tự các từ trong xâu ~S~. Mỗi số cách nhau một dấu cách.

SAMPLE INPUT

Ky thi tuyen sinh vao lop 10

SAMPLE OUTPUT

2 3 5 4 3 3 2

Trường em có màn hình LED lớn ở sân trường để chiếu các video tuyên truyền, quảng bá hình ảnh, vinh danh học sinh vào những lúc giải lao hay sinh hoạt ngoại khóa. Thư viện video của trường có ~N~ video clip (đoạn phim ngắn), mỗi video clip có thời lượng chiếu là ~a_i~ giây. Để tự động hóa khâu chiếu video, nhà trường cần chọn một số video clip liên tiếp có tống thời lượng tối thiếu là ~S~ giây, nhằm đảm bảo chiếu đủ thời gian đã lên lịch. Ngoài ra, việc xử lí video khá phức tạp nên để tối ưu cho việc xử lí sau này thì số lượng video clip được chọn phải là ít nhất.

Yêu cầu: Là thành viên trong câu lạc bộ truyền thông em hãy viết chương trình giúp nhà trường tìm ra số lượng video clip liên tiếp ít nhất sao cho tổng thời lượng các video clip được chọn lớn hơn hoặc bằng ~S~. Thư viện video luôn đảm bảo để tìm được kết quả.

INPUT

• Dòng ~1~: Gồm hai số nguyên dương ~N, S~ cách nhau một dấu cách (~N \le 10^6~, ~S \le 2 \times 10^9~).
• Dòng ~2~: Gồm ~N~ số nguyên dương ~a_1, a_2, ..., a_n~ thể hiện thời lượng của mỗi video clip. Mỗi số cách nhau một dấu cách (~1 \le a_i \le 10^9~).

OUTPUT

Một dòng duy nhất ghi một số nguyên là kết quả bài toán.

SAMPLE INPUT

10 10
1 5 3 2 3 1 4 4 1 2

SAMPLE OUTPUT

3

~5, 3, 2~ là thời lượng các video clip liên tiếp có số lượng ít nhất thỏa mãn yêu cầu bài toán.

SUBTASKS

• ~40 \%~ số test ứng với ~40 \%~ số điểm có ~N \le 100~.
• ~30 \%~ số test ứng với ~30 \%~ số điểm có ~100 < N \le 1000~.
• ~30 \%~ số test ứng với ~30 \%~ số điểm có ~1000 < N \le 10^6~.

Em cùng nhóm bạn đang tham gia cuộc thi lập trình cho Robot. Nhiệm vụ lần này của robot là nhanh chóng mở được ~N~ cánh cửa bí mật để tiến vào phòng chứa kho báu. Trên mỗi cánh cửa có in một số nguyên dương ~x~ và một nút nhấn có màn hình đang hiển thị một số nguyên dương ~y~; mỗi lần nhấn nút thì số ~y~ hiển thị trên màn hình sẽ tăng lên ~1~. Cánh cửa sẽ mở khóa nếu ước chung của ~x~ và ~y~ lớn hơn ~1~.

Yêu cầu: Em hãy lập trình cho robot tìm ra số lần nhấn nút ít nhất để mở từng cánh cửa, nhanh chóng tiến vào phòng chứa kho báu.

INPUT

• Dòng ~1~: Gồm số nguyên dương ~N~ là số lượng cánh cửa (~1 \le N \le 100~).
• Dòng thứ ~i~ trong ~N~ dòng tiếp theo: Mỗi dòng chứa hai số nguyên ~x~ và ~y~ cách nhau một dấu cách (~2 \le x, y \le 10^9~).

OUTPUT

Với mỗi cặp số ~x~ và ~y~ trong dữ liệu vào, ghi ra một số nguyên là số lần nhấn nút ít nhất tương ứng. Mỗi số ghi trên một dòng riêng biệt.

SAMPLE INPUT

3
10 8
13 11
10 3

SAMPLE OUTPUT

0
2
1

SUBTASKS

• ~30 \%~ số test ứng với ~30 \%~ số điểm có ~N = 1~, ~2 \le x, y \le 10^5~.
• ~30 \%~ số test ứng với ~30 \%~ số điểm có ~N \le 100~, ~2 \le x, y \le 10^5~.
• ~40 \%~ số test ứng với ~40 \%~ số điểm có ~N \le 100~, ~2 \le x, y \le 10^9~.