Toán cơ bản

Một hoán vị của các số nguyên \(1, 2, 3, \ldots, n\) được gọi là đẹp nếu không có hai phần tử liền kề nào chênh lệch đúng \(1\) đơn vị.

Cho số nguyên dương \(n\), hãy tìm một hoán vị đẹp nếu tồn tại một dãy như thế.

Input

• Chỉ một dòng duy nhất chứa số nguyên dương \(n\).

Output

• In ra một hoán vị đẹp của các số tự nhiên \(1, 2, 3, \ldots, n\). Nếu có nhiều kết quả, hãy in ra một hoán vị bất kì. Nếu không có hoán vị thoả mãn, hãy in ra NO SOLUTION.

Constraints

• \(1 \le n \le 10^6\)

Example

5

4 2 5 3 1

3

NO SOLUTION

Một xoắn ốc số là một lưới vô hạn có ô vuông trái trên chứa số \(1\). Dưới đây là năm lớp đầu tiên của xoắn ốc:

Nhiệm vụ của bạn là tìm ra số trong hàng \(y\) và cột \(x\).

Input

• Dòng đầu chứa một số nguyên \(t\): số lượng test
• Tiếp theo là \(t\) dòng, mỗi dòng chứa hai số nguyên \(y\) và \(x\)
• Ràng buộc:
  • \(1 \leq t \leq 10^5\)
  • \(1 \leq y,x \leq 10^9\)

Output

• Với mỗi test, in ra số ở hàng \(y\) và cột \(x\)

Example

3
2 3
1 1
4 2

8
1
15

Cho số \(N\) là số trang sách của quyển sách. Hãy đếm số lượng chữ số cần dùng để đánh số thứ tự cho các trang sách này.

Ví dụ: \(N=11\) thì đưa ra kết quả là \(13\). Vì đánh số trang \(1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11\) thì dùng hết \(13\) chữ số.

Dữ liệu

• Dòng duy nhất chứa số nguyên \(N\)

Ràng buộc: \(N \le 7\times 10^7\)

Kết quả

• Số lượng chữ số để đánh số thứ tự các trang sách

Ví dụ

Dữ liệu

24

Kết quả

39

Nguồn: Đề thi thử tỉnh Nghệ An 2021

Cho dãy số: \(1, 1\cdot 2, 1\cdot 2\cdot 3, 1\cdot 2\cdot 3\cdot 4, \dots\) (số thứ \(N\) là tích của các số từ \(1\) đến \(N\)). Hỏi chữ số cuối cùng khác \(0\) của số thứ \(N\) trong dãy là chữ số nào?

Input

• Nhập vào số tự nhiên \(N\) (\(N \le 10^4\)).

Output

• Đưa ra chữ số cuối cùng khác \(0\) của số thứ \(N\) trong dãy.

Scoring

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

Example

3

6

6

2

Mã Gray là danh sách gồm tất cả \(2^n\) xâu nhị phân độ dài \(n\), trong đó bất kỳ hai xâu liên tiếp nào khác nhau tại chính xác một vị trí (tức là khoảng cách Hamming của chúng là một).

Nhiệm vụ của bạn là tạo mã Gray cho một độ dài \(n\) được cho.

Input

• Dòng đầu vào duy nhất có một số nguyên \(n\).

Output

• In \(2^n\) dòng mô tả mã Gray. Bạn có thể in bất kì lời giải hợp lệ nào.

Constraints

• \(1 \leq n \leq 16\)

Example

2

00
01
11
10

Hãy xét một trò chơi trong đó có \(n\) đửa trẻ (được đánh số \(1, 2, \ldots,n\)) trong một vòng tròn. Trong quá trình chơi, điều sau được lặp lại cho đến khi không còn đứa trẻ nào: một đứa trẻ tiếp theo bị bỏ qua và một đứa trẻ tiếp theo bị loại khỏi vòng tròn. Những đứa trẻ sẽ bị loại theo thứ tự nào?

Input

• Dòng đầu vào duy nhất có một số nguyên \(n\) (\(1 \le n \le 2\cdot 10^5\)).

Output

• In \(n\) số nguyên: thứ tự bị loại.

Example

7

2 4 6 1 5 3 7

Hai số dương \(a, a+2\) được gọi là cặp số nguyên tố sinh đôi nếu cả \(a\) và \(a+2\) đều là số nguyên tố.
Hỏi có bao nhiêu cặp như vậy trong các số nguyên từ \(L\) tới \(R\)?

Input

• Gồm 1 dòng duy nhất chứa 2 số \(L, R\).

Output

• Gồm 1 dòng duy nhất chứa kết quả.

Example

1 10

2

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(1 \le L \le R \le 10^3\).
• Subtask \(2\) (\(70\%\) số điểm): \(1 \le L \le R \le 10^6\).

Cho một số nguyên, nhiệm vụ của bạn là tìm số lượng, tổng và tích của các ước số của nó. Ví dụ, chúng ta hãy xem xét số \(12\):

• số lượng ước số là \(6\) (chúng là \(1, 2, 3, 4, 6, 12\))
• tổng của các ước số là \(1 + 2 + 3 + 4 + 6 + 12 = 28\)
• tích của các ước số là \(1 \cdot 2 \cdot 3 \cdot 4 \cdot 6 \cdot 12 = 1728\)

Vì số đầu vào có thể rất lớn, nó sẽ được cho dưới dạng phân tích thừa số nguyên tố.

Input

• Dòng đầu tiên có một số nguyên \(n\): số phần trong dạng phân tích thừa số nguyên tố
• Sau đó, gồm \(n\) dòng mô tả dạng phân tích. Mỗi dòng có hai số \(x\) và \(k\), trong đó \(x\) là số nguyên tố và \(k\) là lũy thừa của nó

Constraints

• \(1 \leq n \leq 10^5\)
• \(2 \leq x \leq 10^6\)
• Mỗi \(x\) là một số nguyên tố riêng biệt
• \(1 \leq k \leq 10^9\)

Output

• In ba số nguyên chia lấy dư cho \(10^9 + 7\): số lượng, tổng và tích của các ước số

Example

2
2 2
3 1

6 28 1728