Kiểm tra

Cho hai dãy số:

• Dãy số \(A\) gồm các số nguyên dương lẻ \((1,3,5,7,9,\ldots)\)
• Dãy số \(B\) gồm toàn các số nguyên dương chẵn \((2,4,6,8,10,\ldots)\)

Dãy số \(S\) được tạo thành bằng cách sau:

• Lấy \(1\) số đầu tiên từ dãy \(A\) (tức \(1\))
• Lấy \(2\) số đầu tiên từ dãy \(B\) xếp theo thứ tự ngược lại (tức \(4,2\))
• Lấy \(3\) số tiếp theo từ dãy \(A\) (tức \(3,5,7\))
• Lấy \(4\) số tiếp theo từ dãy \(B\) xếp theo thứ tự ngược lại (tức \(12,10,8,6\))
• \(\ldots\)

Một số số đầu tiên của dãy \(S\) như sau:

\(1,4,2,3,5,7,12,10,8,6,9,11,13,15,17,24,22,20,18,16,14,19,\ldots\)

Yêu cầu: Cho số tự nhiên \(N\). Hãy tính tổng các số trong dãy \(S\) từ số đầu tiên đến số \(N\) (bao gồm cả số \(N\)).

Input

• Gồm một dòng duy nhất chứa số tự nhiên \(N\) \((1 \le N \le 10^{15})\).

Output

• Một dòng chứa một số nguyên duy nhất là phần dư khi chia tổng cần tìm cho \(2025\).

Example

2

7

5

15

Scoring

• \(60\%\) số test tương ứng với \(60\%\) số điểm có \(N \le 10^6\)
• \(40\%\) số test còn lại tương ứng với \(40\%\) số điểm có \(10^6 \le N \le 10^{15}\)

Các số nguyên dương được xếp vào hình vuông vô hạn theo quy luật như hình minh họa trên.

VÍ DỤ:

• Số 1 ở hàng 1, cột 1.
• Số 2 ở hàng 1, cột 2.
• Số 3 ở hàng 2, cột 1.
• Số 4 ở hàng 3, cột 1.
• Số 5 ở hàng 2, cột 2.
• Số 6 ở hàng 1, cột 3.

Yêu cầu: Viết chương trình nhập vào số nguyên dương \(n\ (1 ≤ n ≤ 10^6)\). Hãy xác định vị trí của số \(n\) trong bảng: hàng mấy, cột mấy?

Dữ liệu

• Một số nguyên dương \(n\ (1 ≤ n ≤ 10^6)\).

Kết quả

• Hai số nguyên là hàng và cột chứa số \(n\).

Ràng buộc

Ví dụ

25

4 4

100

9 6

Trong một trò chơi rèn luyện tư duy số học có tên là chữ số cuối cùng, người chơi bắt đầu với số tự nhiên \(X\). Họ sẽ liên tục thay thế \(X\) bằng tổng các chữ số của nó cho đến khi kết quả cuối là một số có một chữ số.

Ví dụ: số \(X = 395\) sẽ thay được bởi số \(X = 3 + 9 + 5 = 17\), sau đó lại thay số \(X=17\) bởi \(X = 1 + 7 = 8\) thì kết thúc.

Yêu cầu: Trong phần tiếp theo của trò chơi, người chơi nhận được một số tự nhiên \(N\). Đếm có bao nhiêu cách cắt số \(N\) thành hai phần liên tiếp: phần đầu và phần cuối (không để trống phần nào) sao cho chữ số cuối cùng của phần cuối lớn hơn phần đầu.

Dữ liệu

• Một số nguyên dương \(n\ (10 ≤ n ≤ 10^9)\).

Kết quả

• Số cách cắt \(N\) thỏa mãn yêu cầu đề bài. Nếu không có cách nào thỏa mãn, in số 0.

Ràng buộc

Ví dụ

234

1

33

0

Biến đổi

Cho dãy số nguyên không âm \(a_1, a_2, \dots, a_n\) (\(4 \le n \le 8\); \(a_i \le 10^9\)). Cần biến đổi dãy để tất cả các phần tử đều bằng \(0\). Mỗi bước được phép chọn \(4\) phần tử liên tiếp \(a, b, c, d\) biến đổi thành \(|a - b|, |b - c|, |c - d|, |d - a|\).

Ví dụ:
0 1 3 5 9
0 2 2 4 8 (1)
0 0 2 4 6 (2)
0 2 2 2 6 (3)
0 0 0 4 4 (4)
0 0 4 0 4 (5)
0 4 4 4 4 (6)
0 0 0 0 0 (7)

Yêu cầu: Hãy tính số phép biến đổi ít nhất cần thực hiện để tất cả các phần tử đều bằng \(0\).

Input

• Gồm một số dòng, mỗi dòng chứa một số nguyên là các phần tử của dãy \(a_1, a_2, \dots, a_n\).

Output

• Ghi số phép biến đổi ít nhất cần thực hiện để tất cả các phần tử đều bằng \(0\).

Example

0
1
3
5
9

7

Ràng buộc

• Có \(30\%\) số điểm tương ứng với \(n = 4\).
• Có \(30\%\) số điểm khác tương ứng với \(n \le 6\).
• \(40\%\) số điểm còn lại không có ràng buộc nào thêm.