동전

격자판의 크기는 $N \times N$이고, $N$은 짝수이다. 각 칸에 동전이 하나씩 놓여 있다. 은화와 동화가 정확히 절반씩 있다.

동화가 격자판의 왼쪽 위 영역에, 은화가 오른쪽 아래 영역에 모두 놓여 있으면 동전이 올바르게 배치된 것이다. 정확히 말하면, 한 칸의 변이 서로 다른 종류의 동전 사이의 경계일 때, 동화는 은화의 왼쪽이나 위쪽에 있어야 한다.

올바른 배치	잘못된 배치

그림 1: 오른쪽과 같은 배치가 없으면 동전이 올바르게 배치된 것이다. 검은 원은 동화, 흰 원은 은화를 나타낸다.

격자판에 잘못 배치된 동전들이 주어진다. 교환하는 쌍의 수를 가능한 한 적게 하여 올바른 배치가 되도록 동전을 옮겨라.

첫 줄에 정수 네 개 $T$, $N$, $K_1$, $K_2$가 주어진다.

• $T$는 테스트 번호이다.
• $N$은 격자판의 크기이다.
• $K_1$과 $K_2$는 채점 방식을 정하는 값이다 (채점 절 참고).

나머지 $N$개의 줄에는 각각 정수 $N$개가 주어진다. 초기 동전 배치를 나타내며, 각 정수는 0(동화) 또는 1(은화)이다.

입력과 같은 형식으로 $N \times N$ 격자판의 올바른 배치를 출력한다. 0은 정확히 절반, 나머지 절반은 1이어야 한다.