Kattis

# Sylvester Construction

A Hadamard matrix of order $n$ is an $n \times n$ matrix containing only $1$s and $-1$s, called $H_{n}$, such that $H_{n} \cdot H_{n}^{\top } = n \cdot I_{n}$ where $I_{n}$ is the $n \times n$ identity matrix. An interesting property of Hadamard matrices is that they have the maximum possible determinant of any $n \times n$ matrix with elements in the range $[-1, 1]$. Hadamard matrices have applications in error correcting codes and weighing design problems.

The Sylvester construction is a way to create a Hadamard matrix of size $2n$ given $H_{n}$. $H_{2n}$ can be constructed as:

\begin{align*} H_{2n} & = \left( \begin{array}{ll} H_ n & H_ n \\ H_ n & -H_ n \\ \end{array}\right) \end{align*}

For example:

\begin{align*} H_{1} & = \left( \begin{array}{l} 1 \\ \end{array}\right) \\ H_{2} & = \left( \begin{array}{ll} 1 & 1 \\ 1 & -1 \\ \end{array}\right), \end{align*}

and so on. In this problem you are required to print a part of a Hadamard matrix constructed in the way described above.

## Input

The first number in the input is the number of test cases to follow. For each test case there are five integers: $n$, $x$, $y$, $w$ and $h$. $n$ will be between $1$ and $2^{62}$ (inclusive) and will be a power of $2$. $x$ is the column and $y$ is the row of the upper left corner of the sub matrix to be printed, and $w$ and $h$ specify the width and height respectively. Coordinates are zero based, so $0 \le x,y < n$. You can assume that the sub matrix will fit entirely inside the whole matrix and that $0 < w,h \le 20$. There will be no more than $1000$ test cases.

## Output

For each test case print the sub matrix followed by an empty line.

Sample Input 1 Sample Output 1
3
2 0 0 2 2
4 1 1 3 3
268435456 12345 67890 11 12

1 1
1 -1

-1 1 -1
1 -1 -1
-1 -1 1

1 -1 -1 1 1 -1 -1 1 1 -1 -1
-1 -1 1 1 -1 -1 1 1 -1 -1 1
1 1 1 -1 -1 -1 -1 1 1 1 1
-1 1 -1 -1 1 -1 1 1 -1 1 -1
1 -1 -1 -1 -1 1 1 1 1 -1 -1
-1 -1 1 -1 1 1 -1 1 -1 -1 1
-1 -1 -1 -1 -1 -1 -1 1 1 1 1
1 -1 1 -1 1 -1 1 1 -1 1 -1
-1 1 1 -1 -1 1 1 1 1 -1 -1
1 1 -1 -1 1 1 -1 1 -1 -1 1
-1 -1 -1 1 1 1 1 1 1 1 1
1 -1 1 1 -1 1 -1 1 -1 1 -1