Bài tập

Số đối xứng là số mà viết các chữ số của nó theo chiều từ trái sang phải hay từ phải sang trái đều là số đó.

Số đối xứng dạng nón là số đối xứng và các chữ số tăng dần từ trái đến giữa và từ phải đến giữa.

\begincenter

\endcenter

Ví dụ: các số \(11, 13631, 245542, 1357531, 24688642, \ldots\) là số đối xứng dạng nón; còn các số \(23332, 245642\) không phải là số đối xứng dạng nón.

Yêu cầu: Đưa ra số lượng số đối xứng dạng nón từ \(1\) đến \(N\).

Input

• Nhập vào duy nhất một số tự nhiên \(N\) (\(N \leq 10^{10}\)).

Output

• Đưa ra kết quả của bài toán

Example

123

19

Scoring

• Nếu chương trình chạy đúng những trường hợp \(N \le 10^4\), thí sinh sẽ được \(40\) điểm;

• Nếu chương trình chạy đúng những trường hợp \(N \le 10^{10}\) thí sinh sẽ được \(100\) điểm

Alice có một bảng màu kích thước \(m \times n\), các hàng được đánh số từ \(1\) đến \(m\) theo chiều từ trên xuống, các hàng được đánh số từ \(1\) đến \(n\) theo chiều từ trái qua phải. Ô nằm giao giữa hàng \(i\) (\(1 \le i \le m\)) và cột \(j\) (\(1 \le j \le n\)) gọi là ô \((i,j)\). Ban đầu, toàn bộ bảng là màu trắng (màu \(0\)), Alice thực hiện \(k\) thao tác tô màu như sau:

• Chọn một hình chữ nhật nằm trong bảng chiếm nguyên các ô và một màu \(c\) (\(1 \le c \le 100\)).
• Tô đè tất cả các ô trong hình chữ nhật vừa chọn thành màu \(c\).

Yêu cầu: Cho \(m,n\) là kích thước bảng và dãy gồm \(k\) thao tác tô màu, hãy xác định bảng màu mà Alice nhận được.

Input

• Dòng đầu tiên gồm ba số nguyên \(m,n,k\) (\(m,n,k \le 100\)).

• Dòng thứ \(s\) (\(1 \le s \le k\)) chứa năm số nguyên \(x_s,y_s,u_s,v_s,c_s\) trong đó (\(x_s,y_s\)) và (\(u_s,v_s\)) tương ứng là ô góc trái trên và ô góc phải dưới của hình chữ nhật được chọn ở thao tác tô màu thứ \(s\), \(c_s\) là màu sẽ tô cho hình chữ nhật đó.

Output

• Dòng thứ \(i\) (\(1 \le i \le m\)) trong \(m\) dòng sau chứa \(n\) số nguyên \(a_{i,1},a_{i,2},...,a_{i,n}\) mô tả màu trên hàng \(i\) của bảng màu Alice.

Example

3 3 2
1 1 2 2 2
2 2 3 3 1

2 2 0
2 1 1
0 1 1

Dino có \(A\) cái kẹo, chị Cam có \(B\) cái kẹo. Mỗi ngày một bạn được ăn \(3\) cái kẹo. Ai ăn hết kẹo của mình rồi sẽ không ăn nữa. Nếu số kẹo nhỏ hơn \(3\) thì các bạn cũng chỉ được ăn hết số kẹo mình có.

Yêu cầu: Đưa ra chênh lệch số kẹo của hai chị em sau ngày thứ \(N\).

Input

• Nhập vào ba số tự nhiên \(A,B,N\) (\(1 \le A,B,N \le 10^9\)). Mỗi số trên một dòng.

Output

• Ghi ra một số tự nhiên duy nhất là kết quả bài toán.

Example

10
6
2

4

    Sau ngày $1$ thì Dino còn $7$ cái kẹo, chị Cam còn $1$ cái kẹo.

    Sau ngày $2$ thì Dino còn $4$ cái kẹo, chị Cam còn $0$ cái kẹo.

    Sau ngày $3$ thì Dino còn $1$ cái kẹo, chị Cam còn $0$ cái kẹo.

    Nên kết quả là $1$.

10
4
3

1

Ở một chiếc đồng hồ điện tử bất kì nào thì cũng sẽ dùng một ô có hai số biểu diễn số phút từ \(00\) đến \(59\).

Khi bắt đầu thì ở ô phút đang thể hiện số \(A\).

Yêu cầu: Sau \(T\) phút, chữ số \(K\) được dùng bao nhiêu lần (Chỉ tính các lần sử dụng tạo ô phút và tính cả thời điểm bắt đầu bao gồm số \(A\)).

Input

• Nhập vào ba số tự nhiên lần lượt theo thứ tự là \(A,T\) và \(K\). Mỗi số viết trên một dòng (\(0 \le A \le 59, 1 \le T \le 10^9, 0 \le K \le 9\)).

• Nếu số \(A\) nhập vào chỉ có một chữ số thì thí sinh tự thêm chữ số \(0\) vào phía trước để đảm bảo có \(2\) chữ số tại ô phút.

Output

• Đưa ra một số duy nhất là đáp án của bài toán trên.

Example

25
10
3

7

58
7
0

7

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(1 \le T \le 10^3\).

• Subtask \(2\) (\(60\%\) số điểm): \(1 \le T \le 10^9\).