실베스터 구성법

$n$차 아다마르 행렬(Hadamard matrix)은 원소가 $1$과 $-1$로만 이루어진 $n \times n$ 행렬 $H_n$으로, $H_n H_n^T = n I_n$을 만족한다. 여기서 $I_n$은 $n \times n$ 단위행렬이다. 아다마르 행렬의 주목할 만한 성질은, 모든 원소가 $[-1, 1]$ 범위에 있는 $n \times n$ 행렬 가운데 행렬식이 가질 수 있는 최댓값을 달성한다는 것이다. 아다마르 행렬은 오류 정정 부호와 계량 설계(weighing design) 등에 응용된다.

실베스터 구성법(Sylvester construction)은 $H_n$으로부터 크기가 $2n$인 아다마르 행렬을 만드는 방법이다. $H_{2n}$은 다음과 같이 구성한다.

$$H_{2n} = \begin{pmatrix} H_n & H_n \ H_n & -H_n \end{pmatrix}$$

예를 들어 다음과 같이 이어진다.

$$H_1 = \begin{pmatrix} 1 \end{pmatrix}, \qquad H_2 = \begin{pmatrix} 1 & 1 \ 1 & -1 \end{pmatrix}$$

이 문제에서는 위 방법으로 만든 아다마르 행렬의 일부분을 출력해야 한다.

입력의 첫 번째 수는 이어지는 테스트 케이스의 개수이다. 각 테스트 케이스는 다섯 개의 정수 $n$, $x$, $y$, $w$, $h$로 주어진다. $n$은 $2$의 거듭제곱이며 $1 \le n \le 2^{62}$이다. $(x, y)$는 출력할 부분 행렬의 왼쪽 위 모서리로, $x$는 열, $y$는 행을 나타낸다. $w$와 $h$는 각각 부분 행렬의 너비와 높이이다. 좌표는 $0$부터 시작하므로 $0 \le x, y < n$이다. 부분 행렬은 항상 전체 행렬 안에 완전히 들어가며, $0 < w, h \le 20$이다. 테스트 케이스는 최대 $1000$개이다.

각 테스트 케이스마다 요청된 부분 행렬을 출력한다. 한 행의 원소들은 공백 하나로 구분한다. 연속한 테스트 케이스의 출력 사이에는 빈 줄을 하나 넣는다.