고스트버스터즈

키보드는 $M$개의 행과 $N$개의 열로 배열된 버튼 판이다. 행마다 배선이 하나씩 있고 열에도 배선이 하나씩 있다. $i$행 $j$열의 버튼을 누르면 $i$행 배선과 $j$열 배선이 이어진다.

펌웨어는 샘플링으로 입력을 감지한다. 먼저 0번 행 배선에 전기 신호를 흘린다. 이 신호는 눌린 버튼으로 그 행과 이어진 열 배선으로 퍼지고, 이어서 눌린 버튼으로 그 열과 이어진 행 배선으로 퍼지며, 이 과정이 반복된다. 눌린 버튼을 따라 직접 또는 간접으로 처음 행과 연결된 배선은 모두 신호를 받는다. 펌웨어는 신호를 받은 열을 기록하고, 같은 과정을 모든 행에서 반복한다.

버튼을 하나만 누르면 접점이 (행, 열) 한 쌍뿐이라 위치를 바로 알아낸다. 키보드는 여러 버튼을 동시에 누르는 것도 허용하는데, 이때 서로 구분되지 않는 조합이 생긴다. 이 현상을 고스팅이라고 부른다. 예를 들어 $2 \times 2$ 키보드에서는 세 개나 네 개를 누른 어떤 조합이든 배선 네 개를 모두 연결하므로 기록되는 신호가 똑같다.

배선이 이어진 네 가지 예. 같은 색 굵은 선은 눌린 버튼(빨간 점)으로 이어진 배선이다. 오른쪽 두 조합은 연결하는 행과 열이 같아서 서로 구분되지 않는다.

버튼은 각각 눌릴 확률이 있고 서로 독립으로 눌린다. 눌린 버튼의 집합 $S$의 확률은 $S$에 속한 버튼의 $p_{ij}$를 모두 곱한 값에 $S$에 속하지 않은 버튼의 $1 - p_{ij}$를 모두 곱한 값이다. 기록된 신호가 주어질 때, 그 신호를 만들어 낼 수 있는 집합 중 확률이 가장 큰 집합을 구하라.

첫 줄에 행의 수 $M$과 열의 수 $N$이 주어진다. ($1 \le M, N \le 500$)

다음 $M$개의 줄에는 각각 실수 $N$개가 주어진다. $i$번째 줄의 $j$번째 수는 $i$행 $j$열 버튼이 눌릴 확률 $p_{ij}$이다. ($0 < p_{ij} < 0.5$) 행과 열의 번호는 0부터 시작하므로 $0 \le i \le M-1$, $0 \le j \le N-1$이다.

그다음 $M$개의 줄에는 각각 정수 $k$ ($0 \le k \le N$)와 정수 $k$개가 주어진다. 이 $k$개의 정수는 $i$행에 흘린 신호를 받은 열의 번호이다.

기록된 신호는 항상 실제로 어떤 버튼 집합을 눌러서 나오는 값이다.

확률이 가장 큰 버튼 집합을 출력한다. 눌린 버튼마다 한 줄에 행 번호 $r$과 열 번호 $c$를 공백으로 구분해 출력한다. 줄은 $r$이 작은 것부터 출력하고, $r$이 같으면 $c$가 작은 것부터 출력한다.

확률이 가장 큰 집합이 여럿이면 사전순으로 가장 앞서는 집합을 출력한다. 위 순서로 정렬한 (행, 열) 쌍의 수열을 비교해서 처음으로 달라지는 쌍이 더 작은 집합을 고르면 된다. 눌린 버튼이 없으면 아무것도 출력하지 않는다.