Ông Pascal xây dựng một kệ tài liệu theo dạng hình tam giác có chiều cao ~h~. Có tầng được đánh số từ ~1, 2, \ldots, h~. Tầng ~i~ có ngăn đánh số từ ~1, 2, \ldots, i~. Minh hoạ như hình bên dưới:

• Tầng ~1~: ~1~
• Tầng ~2~: ~1~ ~2~
• Tầng ~3~: ~1~ ~2~ ~3~
• ...

Có ~N~ tài liệu được đánh số từ ~1, 2, \ldots, N~ được cất vào các ngăn trên kệ theo thứ tự từ trái sang phải và từ trên xuống dưới.

Do kệ quá cao nên ông thiết kế một hệ thống robot tự động có thể di chuyển đến ngăn cất tài liệu thứ ~P~ mà ông cần.

Yêu cầu

Hãy viết chương trình xác định tầng và ngăn cất tài liệu thứ ~P~.

Dữ liệu đầu vào

Gồm một dòng chứa một số nguyên ~P~ ~(1 \le P \le 10^{18})~.

Dữ liệu đầu ra

Gồm hai số nguyên lần lượt là số tầng và số ngăn cất tài liệu, hai số cách nhau một khoảng trắng.

Ràng buộc dữ liệu

• Subtask 1: 50% số điểm: ~1 \le P \le 10^3~.
• Subtask 2: 30% số điểm: ~1 \le P \le 10^{12}~.
• Subtask 3: 20% số điểm: ~1 \le P \le 10^{18}~.

Ví dụ

Ví dụ 1

INPUT

13

OUTPUT

5 3

Giải thích: Các tài liệu được cất trên kệ lần lượt là:

• Tầng ~1~: ~1~
• Tầng ~2~: ~2~ ~3~
• Tầng ~3~: ~4~ ~5~ ~6~
• Tầng ~4~: ~7~ ~8~ ~9~ ~10~
• Tầng ~5~: ~11~ ~12~ ~\underline{13}~ ~14~ ~15~
• ...

Trong hội trại cuối năm, nhà trường tổ chức trò chơi xổ số mat mắn. Thể lệ trò chơi như sau:

• Người chơi sẽ chọn cặp số may mắn, cặp số may mắn là cặp số mà tích của chúng có chữ số ở hàng đơn vị bằng với số ~P~ do ban tổ chức công bố.
• Tuy nhiên, người chơi sẽ có rất nhiều cách chọn cặp số khác nhau, vì thế ban tổ chức giới hạn phạm vi giá trị người chơi có thể chọn bằng hai số ~L~ và ~R~ ~(L \le R)~, số được chọn có giá trị không nhỏ hơn ~L~ và không lớn hơn ~R~.

Nhằm chuẩn bị tốt cho trò chơi, ban tổ chức cần biết được có bao nhiêu cặp số may mắn theo thể lệ trên.

Ví dụ: với ~L = 1, R = 7~ và ~P = 1~, sẽ có ~3~ cặp số may mắn là ~(1, 1), (3, 7)~ và ~(7, 3)~ vì tích của chúng đều có chữ số ở hàng đơn vị bằng ~1~.

Yêu cầu

Hãy viết chương trình giúp ban tổ chức biết được số lượng cặp số may mắn khi dự kiến công bố giá trị ~L, R~ và ~P~.

Dữ liệu đầu vào

Gồm ba dòng:

• Dòng đầu tiên là số nguyên ~L~.
• Dòng thứ hai là số nguyên ~R~ ~(1 \le L \le R \le 10^9)~.
• Dòng thứ ba là số nguyên ~P~ ~(0 \le P \le 9)~.

Dữ liệu đầu ra

Gồm một số nguyên duy nhất là số lượng cặp số may mắn theo yêu cầu.

Ràng buộc dữ liệu

• 35% số điểm: ~R \le 1000~.
• 15% số điểm: ~R \le 10^6, P = 5~.
• 15% số điểm: ~P = 5~.
• 35% số điểm: không có ràng buộc gì thêm.

Ví dụ

Ví dụ 1

INPUT

1
4
4

OUTPUT

3

Giải thích: Có ~3~ cặp số may mắn là ~(1, 4), (2, 2)~ và ~(4, 1)~ vì tích của chúng có chữ số hàng đơn vị là ~4~.

Công ty VinasatX cho thuê máy chủ, hiện đang có ~N~ khách hàng. Khách hàng thứ ~i~ có nhu cầu sẽ đăng ký các thông tin gồm: ngày bắt đầu thuê ~(x_i)~, số ngày sử dụng ~(d_i)~ và dung lượng cần dùng ~(k_i)~.

Nhằm chuẩn bị cho việc đầu tư cơ sở hạ tầng, công ty cần đánh giá quá trình biến động về dung lượng cho thuê trong suốt quá trình hoạt động. Ngày công ty bắt đầu chạy máy chủ được xem là ngày ~1~, các ngày tiếp theo được ghi nhận lần lượt là ngày ~2~, ngày ~3~, ...

Để đánh giá biến động về dung lượng máy chủ cần cung cấp, công ty sẽ tính tổng dung lượng của tất cả khách thuê theo từng ngày. Những ngày không có khách thuê thì dung lượng cần dùng được xem là ~0~.

Công ty cần lập bảng theo dõi quá trình biến động này từ ngày bắt đầu cho thuê (~x_i~ nhỏ nhất) cho đến ngày cuối cùng máy chủ được khách hàng sử dụng.

Yêu cầu

Viết chương trình thông báo biến động dung lượng trong quá trình hoạt động.

Dữ liệu đầu vào

Gồm ~N + 1~ dòng:

• Dòng đầu tiên chứa số nguyên dương ~N~ ~(1 \le N \le 8 \times 10^5)~.
• ~N~ dòng tiếp theo, mỗi dòng chứa ba số nguyên dương ~x_i, d_i, k_i~ ~(x_i + d_i \le 10^5, 1 \le k_i \le 10^9)~, mỗi số cách nhau một khoảng trắng.

Dữ liệu đầu ra

Gồm một dòng duy nhất là dãy số cho biết quá trình biến động về dung lượng theo yêu cầu trên, mỗi số cách nhau một khoảng trắng.

Ràng buộc dữ liệu

• 40% số điểm: ~1 \le N \le 10^2, 1 \le x_i + d_i \le 10^2~.
• 30% số điểm: ~1 \le N \le 2 \times 10^4~.
• 30% số điểm: ~1 \le N \le 8 \times 10^5~.

Ví dụ

Ví dụ 1

INPUT

3
6 2 15
3 6 9
4 5 7

OUTPUT

9 16 31 16

Giải thích:

Ví dụ 2

INPUT

3
1 2 5
5 3 7
1 3 9

OUTPUT

14 9 0 7