The classic N-Queens problem asks to place ~N~ queens on an ~N×N~ chessboard such that no two queens can attack each other. This extended version requires you to find as many fundamentally different valid solutions as possible within a time limit.

Important: Two solutions are considered identical if one can be obtained from the other through any combination of rotations ~(90°, 180°, 270°)~ and reflections (vertical, horizontal, diagonal). Only unique canonical solutions should be output.

Task

Given an N×N chessboard where rows and columns are numbered from ~1~ to ~N~, place ~N~ queens such that:

• No two queens are in the same row
• No two queens are in the same column
• No two queens are on the same diagonal

Your program should output as many fundamentally different valid solutions as possible within ~2~ seconds, up to a maximum of ~10,000~ solutions.

Input

• A single integer ~N~ ~(4 ≤ N ≤ 1000)~ representing the size of the chessboard.

Output

• At most ~10,000~ lines, each representing one unique canonical solution. Each line contains 2N integers where the numbers at positions ~(2i-1)~ and ~(2i)~ represent the row and column of the i-th queen respectively.
• Queens should be numbered from ~1~ to ~N~ in the output.

Note: Among all symmetric variants of a solution, output only the lexicographically smallest one when queens are listed row by row.

Example Input

8

Example Output

1 1 5 2 8 3 6 4 3 5 7 6 2 7 4 8
1 1 6 2 8 3 3 4 7 5 4 6 2 7 5 8
1 1 7 2 4 3 6 4 8 5 2 6 5 7 3 8
...
(up to 10,000 unique solutions)

Explanation:

• Each line represents one unique canonical solution
• First solution: Queen ~1~ at ~(1,1)~, Queen ~2~ at ~(5,2)~, Queen ~3~ at ~(8,3)~, etc.
• All solutions are fundamentally different (not symmetric variants of each other)

Symmetric Transformations (Considered Identical)

Two solutions are identical if one can be obtained from the other via:

1. Rotations: ~90°, 180°, 270°~ clockwise
2. Reflections:
   • Vertical (left-right mirror)
   • Horizontal (top-bottom mirror)
   • Main diagonal (transpose)
   • Anti-diagonal

Scoring System

Per Line Scoring:

• +1 point for each correct unique canonical solution
• -1 point for each incorrect line (invalid solution, duplicate, or malformed)

Per Test Case:

• Score = (Points Earned) / (Maximum Possible Points)
• Range: ~[0.0~, ~1.0]~ (can be negative if too many errors)
• Maximum Possible Points = min(~10,000~, Total Unique Solutions for ~N~)

Final Score:

• Final Score = (Sum of all test case scores) / (Number of test cases) × 100%
• This gives a percentage representing overall performance across all test cases

Constraints

• ~4 ≤ N ≤ 1000~
• Time limit: 2 seconds
• Memory limit: 256 MB
• Output limit: 10,000 lines maximum

Strategy Recommendations

For Small N (N ≤ 12):

• Try to output all unique solutions
• Focus on correctness over speed

For Medium N (N = 13-20):

• Output as many unique solutions as possible in 2 seconds
• Use efficient canonical form checking

For Large N (N > 20):

• Focus on finding the first few thousand unique solutions quickly
• May not be able to reach 10,000 solutions in 2 seconds

Expected Solution Counts

Implementation Tips

1. Canonical Form: Only output lexicographically smallest variant
2. Early Termination: Stop when reaching 10,000 solutions or time limit
3. Validation: Ensure all output solutions are valid and unique
4. Efficiency: Use bit manipulation for smaller N, array-based for larger N

Notes

• Solutions can be output in any order
• Each solution should be on a separate line
• Invalid solutions or duplicate symmetric variants will result in penalty
• Partial solutions (incomplete lines) will be ignored
• Program should terminate cleanly within time limit