Problem D
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 |
