Bài tập

Cho \(n\) số nguyên dương \(A_1, A_2, \dots, A_n\) và một số nguyên dương \(K\). Hãy chọn ra một số phần tử (theo vị trí, không cần các giá trị khác nhau) sao cho tổng các phần tử được chọn chia hết cho \(K\) và số phần tử được chọn là nhiều nhất có thể. In ra số phần tử đó.

Tập rỗng có tổng bằng \(0\) (chia hết cho mọi \(K\)), nên nếu không thể chọn được tập khác rỗng nào thì đáp án là \(0\).

Input

• Dòng đầu gồm hai số nguyên dương \(n\) và \(K\).
• Dòng thứ hai gồm \(n\) số nguyên dương \(A_1, A_2, \dots, A_n\).

Output

In ra một số nguyên là số phần tử lớn nhất của một tập con có tổng chia hết cho \(K\).

Constraints

• \(1 \le n \le 22\), \(1 \le K \le 2 \cdot 10^{10}\)
• \(1 \le A_i \le 10^9\)

Sample Input

6 5
3 8 4 7 6 1

Sample Output

5

Explanation

Tổng cả sáu số là \(29\) không chia hết cho \(5\). Bỏ số \(4\) được tập gồm \(5\) số \(\{3, 8, 7, 6, 1\}\) có tổng \(25\) chia hết cho \(5\). Không thể chọn cả \(6\) số nên đáp án là \(5\).

Trên bàn cờ vua \(8 \times 8\), hai quân hậu tấn công nhau nếu chúng nằm cùng hàng, cùng cột hoặc cùng đường chéo. Bài toán tám quân hậu yêu cầu đặt \(8\) quân hậu lên bàn cờ sao cho không có hai quân nào tấn công nhau.

Cho trước vị trí một quân hậu đã đặt ở hàng \(x\), cột \(y\). Hãy đặt thêm \(7\) quân hậu nữa để cùng với quân đã cho tạo thành một nghiệm của bài toán tám quân hậu. (Với mọi ô \((x, y)\) luôn tồn tại nghiệm.)

Có thể có nhiều nghiệm; hãy in nghiệm mà dãy cột của các quân hậu theo thứ tự hàng từ \(1\) đến \(8\) nhỏ nhất theo thứ tự từ điển (nghĩa là so sánh cột của hàng \(1\), nếu bằng nhau thì so tiếp hàng \(2\), ...).

Input

Một dòng gồm hai số nguyên \(x, y\) (\(1 \le x, y \le 8\)): hàng và cột của quân hậu đã cho.

Output

In ra \(7\) dòng, mỗi dòng gồm hai số hàng cột là vị trí một quân hậu được đặt thêm, theo thứ tự hàng tăng dần (không in quân hậu đã cho).

Constraints

• \(1 \le x, y \le 8\)

Sample Input

5 2

Sample Output

1 1
2 7
3 5
4 8
6 4
7 6
8 3

Cho một số nguyên \(a\). Hãy biểu diễn \(a\) dưới dạng tổng của hai số nguyên dương \(u\) và \(v\), tức \(a = u + v\) với \(u, v \ge 1\).

Nếu tồn tại nhiều cách, hãy chọn cách sao cho \(u\) lớn nhất có thể mà vẫn thỏa \(u \le v\) (nói cách khác, chia \(a\) thật đều: \(u = \lfloor a/2 \rfloor\), \(v = a - u\)). Nếu không có cách nào, in ra 0 0.

Input

Một số nguyên \(a\).

Output

In ra hai số nguyên \(u\) và \(v\) cách nhau một dấu cách, hoặc 0 0 nếu không có cách tách.

Constraints

• \(|a| \le 10^9\)

Sample Input 1

9

Sample Output 1

4 5

Sample Input 2

-4

Sample Output 2

0 0

Explanation

Với \(a = 9\) có nhiều cách tách như \(1 + 8\), \(2 + 7\), ... nhưng theo quy tắc chọn ta lấy \(4 + 5\). Với \(a = -4\) không thể có hai số dương có tổng âm.

Bé Mì viết các số nguyên từ \(1\) đến \(N\), mỗi số đúng một lần, theo một thứ tự tùy ý và viết liền sát nhau, không có khoảng cách, thành một xâu chữ số rất dài. Chẳng hạn với \(N = 5\), Mì có thể viết 53214 (các số \(5, 3, 2, 1, 4\)).

Vì chỉ có xâu chữ số nên có khi ta tách ra được nhiều dãy số khác nhau. Hãy giúp Mì tìm tất cả các cách tách xâu đó thành các số, sao cho các số thu được là một hoán vị của \(1, 2, \dots, N\) (mỗi số từ \(1\) đến \(N\) xuất hiện đúng một lần, không có số nào bắt đầu bằng chữ số \(0\)).

Input

• Dòng đầu tiên gồm số nguyên \(N\).
• Dòng thứ hai là xâu chữ số mà Mì đã viết (có ít nhất một cách tách hợp lệ).

Output

Mỗi dòng in một cách tách: các số theo thứ tự từ trái sang phải, cách nhau một dấu cách. Các cách được in theo thứ tự từ điển tăng dần (so sánh các số theo giá trị số, từ trái sang phải).

Constraints

• \(1 \le N \le 40\)

Sample Input 1

12
311287112109465

Sample Output 1

3 1 12 8 7 11 2 10 9 4 6 5
3 11 2 8 7 1 12 10 9 4 6 5

Sample Input 2

10
11023456789

Sample Output 2

1 10 2 3 4 5 6 7 8 9

Explanation

Ở ví dụ 1, các dòng \(3\ 1\ 12\ 8\ldots\) và \(3\ 11\ 2\ 8\ldots\) cho cùng một xâu 311287112109465. Ở ví dụ 2, số \(0\) không thể đứng đầu một số nên chữ số 0 bắt buộc phải đi liền sau chữ số 1 để tạo thành \(10\).