실베스터 구성법

시간 제한1초메모리 제한128 MB

요약

실베스터 이중화 규칙으로 만든 아다마르 행렬에서 왼쪽 위 좌표로 지정된 작은 부분 행렬을 출력한다.

난이도: 보통10점 중 7점
유형: 분할 정복, 재귀, 비트 연산, 수학
정답자: 아직 제출이 없습니다

문제

$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$ 개이다.

출력

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

예제3

예제 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

예제 2
입력
```
1
1 0 0 1 1
```
예상 출력
```
1
```

예제 3

입력

1
4 0 0 4 4

예상 출력