Nhân kỷ niệm 50 năm Thành phố mang tên Bác, Sở Văn hóa và Thể thao Thành phố Hồ Chí Minh triển khai dự án lập bản đồ di tích số toàn thành phố. Bản đồ được mô hình hóa bằng một lưới tọa độ nguyên, trong đó mỗi ô ~(x, y)~ đại diện cho một địa điểm trên thành phố.

Một ô tọa độ ~(x, y)~ được gọi là Điểm di tích nếu thỏa mãn điều kiện: Tổng các chữ số của ~|x|~ cộng với tổng các chữ số của ~|y|~ là một số chia hết cho ~3~ hoặc chia hết cho ~5~.

Ví dụ:

• Ô ~(1, 2)~: tổng chữ số ~= 1 + 2 = 3~, chia hết cho ~3~ ~\rightarrow~ là Điểm di tích.
• Ô ~(1, 1)~: tổng chữ số ~= 1 + 1 = 2~, khchia hết cho ~3~ hay ~5~ ~\rightarrow~ không phải là Điểm di tích.
• Ô ~(0, 5)~: tổng chữ số ~= 0 + 5= 5~, chia hết cho ~5~ ~\rightarrow~ là Điểm di tích.

Ban tổ chức muốn thống kê số lượng Điểm di tích nằm trong vùng quy hoạch hình chữ nhật có hai góc đối diện là ~(0, 0)~ và ~(X, Y)~ — bao gồm cả các ô trên biên.

Input

Gồm một dòng duy nhất chứa hai số nguyên ~X~ và ~Y \ (-1000 \leq X, Y \leq 1000)~.

Output

Gồm một số nguyên duy nhất là số lượng Điểm di tích nằm trong vùng quy hoạch.

Sample Input 1

0 0

Sample Output 1

1

Giải thích. Ô thỏa: ~(0, 0)~ - tổng chữ số ~= 0~, chia hết cho cả ~3~ và ~5~.

Sample Input 2

2 2

Sample Output 2

3

Giải thích. Ô thỏa: ~(0, 0), (1, 2), (2, 1)~.

Sample Input 3

-2 3

Sample Output 3

5

Giải thích. Vùng quy hoạch bao gồm ~x \in [-2, 0]~ và ~y \in [0, 3]~. Các ô thỏa mãn: ~(0, 0), (0, 3), (-1, 2), (-2, 1), (-2, 3)~.

Ghi chú.

• Khi ~X < 0~ hoặc ~Y < 0~, vùng quy hoạch là hình chữ nhật có các tọa độ ~x~ chạy từ ~\min(0, X)~ đến ~\max(0, X)~, và ~y~ chạy từ ~\min(0, Y)~ đến ~\max(0, Y)~.
• Điều kiện luôn sử dụng ~|x|~ và ~|y|~ (giá trị tuyệt đối).

Để chuẩn bị cho đại lễ diễu hành kỷ niệm 50 năm ngày Thành phố chính thức mang tên Bác Hồ tại Đường đi bộ Nguyễn Huệ, Ban tổ chức huy động ~N~ nhóm học sinh tham gia đồng diễn, xếp thành một hàng theo thứ tự cho trước; nhóm thứ ~i~ có ~A_i~ học sinh.

Để đội hình trông đẹp mắt và cân đối, Ban tổ chức muốn chia ~N~ nhóm này thành các khối đồng diễn thỏa mãn đồng thời:

• Mỗi khối gồm một số nhóm đứng liền kề nhau trong danh sách ban đầu. Mỗi nhóm thuộc về đúng một khối, và các khối phủ kín toàn bộ dãy (không bỏ sót nhóm nào). Số khối là tùy ý, từ ~1~ đến ~N~.
• Tổng số học sinh của mỗi khối không vượt quá một hằng số ~M~ (để bảo đảm khoảng cách giãn cách an toàn trên đường phố).
• Độ chênh lệch giữa khối có tổng số học sinh lớn nhất và khối có tổng số học sinh nhỏ nhất là nhỏ nhất có thể.

Hãy đưa ra giá trị độ chênh lệch nhỏ nhất đó.

Lưu ý. Dữ liệu luôn bảo đảm ~A_i \leq M~ với mọi ~i~, do đó luôn tồn tại ít nhất một cách chia hợp lệ (chẳng hạn, mỗi nhóm là một khối riêng). Thí sinh không cần xử lý trường hợp vô nghiệm.

Input

• Dòng đầu chứa hai số nguyên ~N~ và ~M \ (1 \leq N \leq 10^3; 1 \leq M \leq 10^5)~.
• Dòng thứ hai chứa ~N~ số nguyên ~A_1, A_2, \ldots, A_N~ - số lượng học sinh của từng nhóm, các số phân tách nhau bằng dấu cách ~(1 \leq A_i \leq 10^4; \max(A_i) \leq M)~.

Output

Một số nguyên duy nhất: độ chênh lệch nhỏ nhất giữa tổng số học sinh của khối lớn nhất và khối nhỏ nhất trong cách chia tìm được.

Sample Input 1

5 10
2 3 4 2 5

Sample Output 1

1

Sample Input 2

4 50
10 10 10 10

Sample Output 2

0

Subtasks

• Subtask 1 (15% số điểm). ~N \leq 18~.
• Subtask 2 (25% số điểm). ~N \leq 100~.
• Subtask 3 (25% số điểm). ~N \leq 1000; M \leq 2000~.
• Subtask 4 (35% số điểm). Không có ràng buộc gì thêm.

Nằm trong chuỗi sự kiện Kỷ niệm 50 năm Thành phố mang tên Bác, một giải chạy việt dã kết hợp giải đố được tổ chức dọc theo tuyến Metro số 1. Tuyến đường có ~n~ trạm kiểm soát xếp thành một hàng ngang, đánh số từ ~1~ đến ~n~. Mỗi trạm ~i~ mang lại một số điểm thưởng hoặc điểm phạt ~a_i~.

Vận động viên Minh bắt đầu chạy từ một trạm bất kỳ và di chuyển theo hướng tăng dần đến một trạm bất kỳ phía sau. Minh có thể dừng cuộc thi bất cứ lúc nào kể cả việc dừng ngay tại trạm xuất phát. Trong quá trình chạy, anh ấy bắt buộc phải nhận lượng điểm thưởng (hoặc chịu điểm phạt) tại mỗi trạm mà anh ấy đặt chân đến. Tuy nhiên, Minh được phép sử dụng thẻ đặc quyền để bỏ qua một số trạm liên tiếp (ví dụ đi tàu điện ngầm qua nhanh) để tránh bị phạt điểm theo luật chơi được quy định như sau:

• Minh chỉ được phép bỏ qua tối đa ~k~ trạm liên tiếp trong mỗi lần sử dụng đặc quyền.
• Với mỗi trạm Minh bỏ qua, anh ấy bị trừ một khoản phí bỏ qua là ~C~ điểm cho trạm đó.
• Ví dụ: Minh đang ở trạm ~1~, bỏ qua trạm ~2~ và trạm ~3~ để tiến thẳng sang trạm ~4~. Khi đó, Minh sẽ nhận số điểm (thưởng hoặc phạt) tại trạm ~1~ và trạm ~4~. Đồng thời Minh sẽ bị trừ ~2 \times C~ điểm phí do bỏ qua ~2~ trạm ~2~ và ~3~. Lưu ý, điểm phí ~C~ có thể bằng ~0~, khi đó Minh sẽ không bị thu phí.

Yêu cầu. Hãy giúp Minh tìm phương án tối ưu để đạt được tổng số điểm lớn nhất. Chỉ cần cho biết tổng số điểm lớn nhất có thể đạt được.

Chú ý. Minh phải ghé thăm ít nhất 1 trạm kiểm soát trong toàn bộ quá trình di chuyển.

Input

• Dòng ~1~: Ba số nguyên ~n, k~ và ~C \ (1 \leq n \leq 10^5, 0 \leq k \leq n - 1; 0 \leq C \leq 10^4)~.
• Dòng ~2~: ~n~ số nguyên ~a_1, a_2, \ldots, a_n \ (-10^9 \leq a_i \leq 10^9)~.

Output

In ra một số nguyên duy nhất - tổng số điểm lớn nhất Minh có thể đạt được.

Sample Input 1

5 2 2
5 -10 4 -10 5

Sample Output 1

10

Giải thích. ~k = 2~ (được bỏ qua tối đa ~2~ trạm), phí cho mỗi trạm bị bỏ qua là ~C = 2~. Hành trình tối ưu: Chọn trạm ~1 (5)~ ~\rightarrow~ bỏ qua trạm ~2~ ~\rightarrow~ chọn trạm ~3 (4)~ ~\rightarrow~ bỏ qua trạm ~4~ ~\rightarrow~ chọn trạm ~5 (5)~. Phí bỏ qua trạm ~2~ và trạm ~4~: trừ ~2 + 2~. Tổng điểm ~= 5 + 4 + 5 - 2 - 2 = 10~.

Sample Input 2

4 1 5
10 -2 10 -2

Sample Output 2

18

Giải thích. Phí bỏ qua trạm quá cao ~(C = 5)~. Thay vì bỏ qua trạm ~2~ (phạt ~5~), Minh nên chọn luôn trạm ~2~ (chỉ phạt ~2~). Hành trình tối ưu: Chọn trạm ~1~, trạm ~2~, trạm ~3~. Tổng điểm ~= 10 + (-2) + 10 = 18~.

Subtasks

• Subtask 1 (30% số điểm). ~n \leq 1000, k = 0~.
• Subtask 2 (30% số điểm). ~n \leq 10^5, k \leq 20~.
• Subtask 3 (20% số điểm). ~n, k \leq 10^5, C = 0~.
• Subtask 4 (20% số điểm). Không có ràng buộc gì thêm.

Để chào mừng Kỷ niệm 50 năm Thành phố mang tên Bác, Ban tổ chức sự kiện muốn chọn ra ~k~ khối đại biểu thanh niên tiêu biểu để trao cờ luân lưu danh dự trong lễ đài chính.

Đội hình đang có tất cả ~n~ khối đại biểu được xếp thành một hàng dọc chờ tiến vào khán đài, được đánh số lần lượt từ vị trí thứ ~1~ đến ~n~. Để đảm bảo đội hình trao cờ trông đẹp mắt, trải đều và không bị dồn ứ trên sân, Ban tổ chức đề ra các quy tắc như sau:

• Trong ~n~ khối thì chỉ trao đúng ~k~ lá cờ cho ~k~ khối (mỗi khối chỉ nhận tối đa một lá cờ);
• Khối thứ ~i~ đã được chọn nhận cờ thì hai khối kế bên (trước và sau) là khối thứ ~i - 1~ và khối thứ ~i + 1~ sẽ không được nhận cờ nữa ~(i = 2, 3, …, n - 1)~.
• Khối thứ ~1~ đã nhận cờ thì khối thứ ~2~ không được nhận. Tương tự, nếu khối thứ ~n~ được nhận cờ thì khối thứ ~n - 1~ chắc chắn sẽ không được nhận cờ.

Với các quy tắc như trên, Ban tổ chức muốn biết có bao nhiêu cách để chọn các khối trao cờ? Hãy viết chương trình giúp Ban tổ chức trả lời bài toán này.

Yêu cầu. Cho hai số nguyên dương ~n~ và ~k \ (k < n \leq 10^5)~. Hãy xác định số cách chọn trao cờ, chia lấy phần dư cho ~m \ (2 \leq m \leq 10^9)~

Input

Gồm một dòng chứa ~3~ số nguyên dương ~n,k,m~.

Output

Gồm một số nguyên là kết quả tìm được.

Sample Input

6 3 12345

Sample Output

4

Subtasks

• Subtask 1 (20% số điểm). ~n \leq 20~.
• Subtask 2 (80% số điểm). Không có ràng buộc gì thêm.

Để chuẩn bị trình chiếu các tư liệu lịch sử tại bảo tàng số nhân Kỷ niệm 50 năm Thành phố mang tên Bác, Ban tổ chức phải lưu trữ một lượng dữ liệu văn bản khổng lồ. Do hệ thống có hạn, các chuỗi dữ liệu (xâu) được lưu dưới một định dạng mã hóa gọi là định dạng xâu nén. Một xâu nén hợp lệ được định nghĩa đệ quy như sau:

• Một chữ cái thường (a-z) là xâu nén hợp lệ, đại diện cho chính nó.
• Nếu S là xâu nén hợp lệ và ~k~ là số nguyên dương ~(2 \leq k \leq 9)~, thì k[S] là xâu nén hợp lệ, đại diện cho xâu S được lặp lại ~k~ lần.
• Phép nối: nếu A và B đều hợp lệ thì AB cũng hợp lệ.

Ví dụ giải nén.

Cho một xâu nén hợp lệ T và ~q~ truy vấn. Mỗi truy vấn cho hai số nguyên ~l, r~. Hãy trả lời: trong đoạn ký tự từ vị trí ~l~ đến ~r~ của xâu sau khi giải nén, ký tự nào xuất hiện nhiều nhất, và số lần xuất hiện của nó là bao nhiêu?

Nếu có nhiều ký tự cùng số lần xuất hiện tối đa, in ký tự nhỏ nhất theo thứ tự bảng chữ cái.

Input

• Dòng 1: Xâu nén T ~(1 \leq |T| \leq 10^5)~.
• Dòng 2: Số nguyên dương ~q \ (1 \leq q \leq 10^5)~.
• ~q~ dòng tiếp theo: Hai số nguyên dương ~l, r~ (mỗi truy vấn một dòng). Các ký tự của xâu sau giải nén được đánh số thứ tự bắt đầu từ ~1~.

Dữ liệu đảm bảo độ dài xâu sau giải nén ~\leq 10^6~ và ~1 \leq l \leq r \leq~ độ dài giải nén.

Output

Với mỗi truy vấn, in ra một dòng gồm một ký tự và một số nguyên (số lần xuất hiện), cách nhau bởi dấu cách.

Sample Input

2[3[ab]c]
3
1 6
3 12
1 14

Sample Output

a 3
a 5
a 6

Subtasks

• Subtask 1 (30% số điểm). Không lồng nhau; xâu giải nén dài ~\leq 10^5; q \leq 100~.
• Subtask 2 (30% số điểm). Có lồng nhau; xâu giải nén dài ~\leq 10^5; q \leq 100~.
• Subtask 3 (20% số điểm). Có lồng nhau; xâu giải nén dài ~\leq 10^5; q \leq 10^5~.
• Subtask 4 (20% số điểm). Có lồng nhau; xâu giải nén dài ~\leq 10^6; q \leq 100~.