Contest đặc biệt

Bạn được cho một lưới ô vuông kích thước \(N \times M\), với \(N\) hàng và \(M\) cột. Các hàng được đánh số từ \(1\) đến \(N\) từ trên xuống dưới, các cột được đánh số từ \(1\) đến \(M\) từ trái sang phải. Nhiệm vụ của bạn là tìm ra càng nhiều đường đi qua tất cả các ô trên lưới càng tốt, nhưng các đường đi phải thỏa mãn các điều kiện sau:

• Từ một ô, chỉ có thể đi sang một trong bốn ô chung cạnh với ô đang đứng, và không được đi ra khỏi bảng.
• Mỗi ô trên bảng chỉ được đi qua đúng một lần, kể cả ô xuất phát.
• Các đường đi không được phép trùng nhau, nghĩa là với hai đường đi bất kỳ, tồn tại một vị trí \(i\) sao cho ô thứ \(i\) được đi qua ở đường đi này khác với đường đi kia.

Bạn cần tìm ra số lượng đường đi nhiều hơn hoặc bằng chương trình của Ban tổ chức, hoặc \(3 \times 10^5\) đường đi để đạt điểm tối đa.

Cài đặt

Đầu tiên, chương trình của bạn cần khai báo thư viện gridpath.h bằng lệnh #include "gridpath.h" để tương tác với chương trình chấm.

Bạn cần cài đặt hàm sau:

void find_path (int N, int M)

Hàm này được gọi chính xác một lần trong mỗi test, với \(N\) và \(M\) là kích thước của lưới ô vuông.

Giới hạn: \(2 \le N, M \le 9, N \le M\).

Chương trình của bạn có thể gọi hàm sau trong chương trình chấm:

bool check_path (int r_start, int c_start, string path)

Hàm này cho biết bạn đã tìm được một đường đi bắt đầu từ ô ở hàng \(r_{start}\) và cột \(c_{start}\), và thực hiện các bước đi như trong xâu \(path\), trong đó:

• L biểu thị thao tác đi sang trái.
• R biểu thị thao tác đi sang phải.
• U biểu thị thao tác đi lên.
• D biểu thị thao tác đi xuống.

Hàm này sẽ trả về true nếu đường đi của bạn là một đường đi hợp lệ, và thêm đường đi đó vào tập hợp các câu trả lời của bạn. Ngược lại, hàm này sẽ trả về false. Bạn được phép gọi hàm này không giới hạn số lần (cho đến khi chương trình bị quá thời gian).

Bạn có thể khai báo thêm các hàm và biến toàn cục nếu cần thiết, nhưng không được khai báo hàm có tên là main.

Chấm điểm

Gọi \(J\) là số lượng đường đi mà chương trình của Ban tổ chức tìm được, \(P\) là số lượng đường đi mà chương trình của bạn tìm được. Biết rằng \(J \le 3 \times 10^5\). Chương trình của bạn sẽ được tính điểm theo công thức sau:

với \(S\) là số điểm của bạn cho test đó, nếu điểm tối đa cho mỗi test là \(1\).

Subtask

Bài tập này không có subtask. Thay vào đó, bộ test sẽ bao gồm \(36\) test với điểm số bằng nhau, mỗi test với một cặp số \(N, M\) thỏa mãn điều kiện nêu trên. Điểm của bạn cho bài tập này sẽ là tổng điểm của các test.

Ví dụ

Xét lần gọi hàm sau:

find_path (2, 2)

Bạn cần tìm càng nhiều đường đi càng tốt trên lưới \(2 \times 2\).

Chương trình của bạn đưa ra các lần gọi hàm sau:

check_path (1, 1, "RDL")

Với lần gọi hàm này, chương trình chấm trả về true vì đây là một đường đi hợp lệ.

check_path (2, 1, "RUL")

Chương trình chấm cũng sẽ trả về true, vì đây là một đường đi hợp lệ.

check_path (1, 1, "RDL")

Chương trình chấm sẽ trả về false, vì đường đi này đã xuất hiện trước đó.

check_path (1, 2, "DLU")
check_path (2, 2, "ULD")

Chương trình chấm sẽ trả về true cho cả hai lần gọi.

Sau khi thực hiện tất cả các lần gọi, chương trình của bạn quyết định dừng lại. Chương trình đã tìm được \(4\) trong tổng số \(8\) đường đi, và nhận được kết quả \(0.70\) điểm.

Trình chấm mẫu

Trình chấm mẫu sẽ nhập input từ bàn phím dưới dạng:

• Một dòng duy nhất gồm hai số nguyên dương \(N, M\).

Trình chấm mẫu sẽ in ra output trên màn hình dưới dạng:

• Một số nguyên dương duy nhất là số lượng đường đi hợp lệ mà chương trình của bạn tìm được.

Ví dụ, trong quá trình tương tác ở phần trên, trình chấm mẫu sẽ nhập input như sau:

2 2

và đưa ra output như sau:

4

The Royal Jeweler is crafting a magical necklace for the Queen. The necklace consists of \(N\) distinct jewels, numbered \(1\) to \(N\). The jewels must be arranged in a circle. To activate the magical properties, the absolute difference between the values of any two adjacent jewels in the circle must be a prime number.

Given \(N\), construct such an arrangement.

Input

• The first line contains an integer \(T\) (\(1 \le T \le 10\)) — the number of test cases.
• Each of the next \(T\) lines contains a single integer \(N\) (\(2 \le N \le 10000\)) — the number of jewels.

Output

For each test case, output exactly one line:

• If no valid arrangement exists, print -1.
• Otherwise, print \(N\) integers representing the circular arrangement of jewels.

Example

2
4
5

-1
1 3 5 2 4

Problem K: Kryptic Grid
Time Limit: 1.0 seconds
Memory Limit: 256 MB

You are designing a security panel with a grid of size \(N \cdot M\). You need to fill the grid with integers such that:

1. Each cell \((i, j)\) contains a non-negative integer \(A_{i,j}\) where \(0 \leq A_{i,j} < 2^{20}\).
2. All elements in the grid must be pairwise distinct.
3. For every \(2 \cdot 2\) subgrid, the bitwise XOR sum of the \(4\) elements is exactly \(V\) (where \(V\) is a given constant).

Formally, for all \(1 \leq i < N\) and \(1 \leq j < M\):

If there are multiple solutions, you can output any of them. If no such grid exists, output -1.

Input

• The single line contains three integers \(N, M, V\) (\(2 \leq N, M \leq 2^{10}\), \(0 \leq V < 2^{20}\)).

Output

• If a solution exists, print \(N\) lines, each containing \(M\) integers representing the grid.
• If no solution exists, print -1.

Example

2 2 0

0 1
2 3

Cho một số nguyên dương \(N\). Hãy tạo một hoán vị \(P_1, P_2, \dots, P_N\) thỏa mãn: với mọi \(1 \le i \le N - 2\), \(P_i, P_{i + 1}, P_{i + 2}\) không phải độ dài ba cạnh của một tam giác.

Input

• Dòng đầu tiên gồm một số nguyên dương \(T\) (\(1 \le T \le 100\)) - số lượng bộ dữ liệu bạn cần xử lý.
• \(T\) dòng tiếp theo, mỗi dòng gồm một số nguyên dương \(N\) (\(3 \le N \le 5000\)).

Output

• Với mỗi bộ dữ liệu:
  • Nếu không tìm được hoán vị thỏa mãn, in ra \(-1\).
  • Ngược lại, in ra một dòng gồm \(N\) số nguyên dương là một hoán vị bất kỳ thỏa mãn.

Scoring

• Subtask \(1\) (\(31\%\) số điểm): \(T = 1, N \le 10\).
• Subtask \(2\) (\(37\%\) số điểm): \(T = 1, N \le 20\).
• Subtask \(3\) (\(19\%\) số điểm): \(T = 1\).
• Subtask \(4\) (\(13\%\) số điểm): Không có ràng buộc gì thêm.

Example

2
3
4

3 1 2
4 3 1 2

Bạn được cho hai số nguyên \(N, D\). Bạn cần xây dựng một bảng \(N \times N\) thỏa mãn các điều kiện sau:

• Các số trên bảng có giá trị trong đoạn \([1, 10^6]\).
• Tổng các số trên cùng một hàng và một cột là một số nguyên tố.
• Nếu \(D = 1\), tổng các số trên hai đường chéo chính và phụ cũng là một số nguyên tố.

Input

• Một dòng duy nhất gồm hai số nguyên \(N, D\) (\(1 \le N \le 1000, 0 \le D \le 1\)).

Output

• Nếu không tồn tại bảng thỏa mãn, in ra \(-1\).
• Ngược lại, in ra bảng tìm được trên \(N\) dòng. Nếu có nhiều bảng thỏa mãn, in ra một bảng bất kỳ.

Scoring

• Subtask \(1\) (\(36\%\) số điểm): \(N\) là số nguyên tố.
• Subtask \(2\) (\(28\%\) số điểm): \(D = 0\).
• Subtask \(3\) (\(36\%\) số điểm): Không có giới hạn gì thêm.

Example

2 0

1 2
4 3

3 1

1 1 5
1 3 3
3 1 3