퍼즐스탄

$N$가지 종류의 물품과 $M$명의 손님이 있다. 각 손님은 종류마다 정확히 하나씩의 물품을 가진다(예를 들어 손님마다 외투 하나, 모자 하나 등을 맡긴다). 따라서 물품은 모두 $N \times M$개이며, 각 물품에는 서로 다른 한 글자짜리 이름이 붙어 있다(대문자와 소문자를 구별한다).

종류 $i$($1 \le i \le N$)에 속한 $M$개의 물품을 길이 $M$인 문자열로 나타내고, 이를 $i$번째 그룹이라 부른다. 이 문자열의 $j$번째 글자가 그룹 $i$의 $j$번째 물품이다.

어떤 두 물품이 같은 손님의 것인지, 서로 다른 손님의 것인지를 알려 주는 여러 개의 진술이 주어진다. 각 진술은 다음 중 하나다.

• 두 물품이 같은 손님의 것이다.
• 두 물품이 서로 다른 손님의 것이다.

이 진술들을 이용하여 각 물품이 어떤 손님의 것인지 알아내라. 주어진 진술은 항상 배정을 유일하게 결정한다.

첫 줄에 테스트 케이스의 개수(최대 $20$)가 주어진다.

각 테스트 케이스의 첫 줄에는 두 양의 정수 $N$과 $M$이 주어진다. $N$($1 \le N \le 7$)은 물품 종류의 수, $M$($1 \le M \le 7$)은 손님의 수다. 이어지는 $N$개의 줄에는 각각 길이 $M$인 문자열이 하나씩 주어지며, 이는 한 그룹(같은 종류에 속한 서로 다른 물품들)을 나타낸다.

그 다음에는 여러 줄의 진술이 주어진다. 각 진술은 i j X k r 꼴이며, 그룹 $i$의 $j$번째 물품과 그룹 $k$의 $r$번째 물품이 $X$가 R이면 같은 손님의 것이고, $X$가 N이면 서로 다른 손님의 것임을 뜻한다. 각 테스트 케이스의 마지막 줄은 더미 진술 0 0 R 0 0이다.

각 테스트 케이스마다 $M$개의 줄을 출력한다. $g$번째 줄($1 \le g \le M$)은 첫 번째 그룹의 $g$번째 물품으로 식별되는 손님에 대한 것으로, 그 손님이 가진 첫 번째 그룹의 물품, 두 번째 그룹의 물품, ..., $N$번째 그룹의 물품을 순서대로 이어 붙인 글자들을 출력한다. 따라서 각 줄의 첫 번째 글자는 첫 번째 그룹의 순서와 같다.

연속한 두 테스트 케이스의 출력 사이는 정확히 한 개의 빈 줄로 구분한다.