섬 연결하기

바이트랜드에서 오래 이어진 전쟁이 끝났다. 정부는 교통 수단부터 복구하기로 결정했다.

바이트랜드는 섬 두 개로 이루어져 있다. 전쟁 전에는 같은 섬에 있는 모든 도시가 양방향 선로 하나로 서로 직접 이어져 있었고, 전쟁 중에 선로 몇 개가 파괴되었다. 파괴된 선로는 15개를 넘지 않는다.

전쟁 전까지 두 섬 사이를 오갈 방법은 없었다. 이번 복구를 마친 뒤에는 두 섬을 왕복하는 페리 항로를 놓아 바이트랜드의 모든 도시를 선로나 항로로 직접 잇는다. 즉 서로 다른 섬에 있는 두 도시 사이에는 페리 항로가 있어야 하고, 같은 섬에 있는 두 도시 사이에는 선로가 있어야 한다.

바이트랜드에서는 모든 것을 이진수로 적는다. 기차 티켓과 페리 티켓의 가격도 0원 또는 1원이다.

정부는 파괴되지 않은 선로에 매겨져 있던 티켓 가격을 그대로 쓰기로 했다. 새로 복구하는 선로와 새로 놓는 페리 항로의 가격은 다음 규칙을 지켜야 한다. 서로 다른 세 도시 $X$, $Y$, $Z$에 대해 두 도시를 직접 잇는 선로 또는 항로의 티켓 가격을 $C$라고 하면

$C(X, Y) + C(Y, Z) \ge C(X, Z)$

직행 경로의 비용은 다른 도시를 거쳐 가는 경로의 비용보다 언제나 저렴하거나 같아야 한다는 뜻이다.

두 섬의 선로 정보가 주어진다. 규칙을 지키면서 선로를 복구하고 항로를 놓을 수 있는지 판정하고, 가능하면 최종 교통 계획까지 직접 구해 보자.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. ($1 \le T \le 100$)

각 테스트 케이스는 다음과 같이 구성된다.

• 첫 줄에 바이트랜드의 첫 번째 섬에 있는 도시 수 $C_1$이 주어진다. ($1 \le C_1 \le 100$)
• 이어지는 $C_1$개의 줄에 각각 문자 $C_1$개가 주어진다. 각 문자는 0, 1, x 중 하나다. $i$번째 줄의 $j$번째 문자가 0이면 그 섬의 $i$번 도시와 $j$번 도시를 잇는 선로의 티켓 가격이 0이고, 1이면 티켓 가격이 1이며, x이면 그 선로가 전쟁 중에 파괴되었다는 뜻이다.
• 다음 줄에 두 번째 섬에 있는 도시 수 $C_2$가 주어진다. ($1 \le C_2 \le 100$)
• 이어지는 $C_2$개의 줄에 각각 문자 $C_2$개가 첫 번째 섬과 같은 형식으로 주어진다.

주어지는 표는 항상 대각선에 대해 대칭이고, $i$번째 줄의 $i$번째 문자는 항상 0이다.

두 표에 나오는 x의 개수는 합해서 30개를 넘지 않는다. 표가 대칭이므로 파괴된 선로 하나마다 x가 두 개씩 나온다.

파괴되지 않은 선로만으로 이미 규칙이 깨져 있을 수도 있으니 주의하라.

각 테스트 케이스마다 규칙에 맞는 교통 계획을 세울 수 있으면 첫 줄에 YES를, 세울 수 없으면 NO를 출력한다.

YES를 출력한 경우 이어지는 $C_1 + C_2$개의 줄에 각각 문자 $C_1 + C_2$개로 최종 교통 계획을 출력한다. 섬 1의 도시는 1번부터 $C_1$번까지, 섬 2의 도시는 $C_1 + 1$번부터 $C_1 + C_2$번까지의 번호를 갖는다. $i$번째 줄의 $j$번째 문자는 $i$번 도시와 $j$번 도시를 잇는 선로 또는 항로의 티켓 가격 0 또는 1이어야 하고, 표는 대칭이어야 한다.

규칙을 만족하는 계획이 여러 가지인 경우에는 그중 하나만 출력한다. 표의 각 줄을 위에서 아래로 이어 붙여 길이 $(C_1 + C_2)^2$의 문자열을 만들었을 때, 사전순으로 가장 앞서는 계획을 출력한다.