**Time limit:**1.00 s**Memory limit:**512 MB

Your task is to construct an n \times n grid where each square contains an integer between 1 \ldots n. There are two requirements:

- Each integer 1 \ldots n appears exactly n times in the grid.
- The rows and columns should form 2n distinct sums.

For example, one possible 5 \times 5 grid is as follows:

# Input

The only input line contains an integer n.

# Output

You should print any grid that fulfils the requirements. If there is no such grid, you should only print "QAQ".

# Example 1

Input:

5

Output:

2 3 1 1 1 1 5 5 3 3 2 3 5 2 4 5 4 5 4 1 2 3 4 4 2

# Example 2

Input:

2

Output:

QAQ

# Subtask 1 (35 points)

- 2 \le n \le 10

# Subtask 2 (21 points)

- 2 \le n \le 100

# Subtask 3 (44 points)

- 2 \le n \le 1000