K리그

K리그(옛 한국 프로 축구 리그)에 참가하는 프로 축구단의 서포터들은 자신이 응원하는 팀 $S$가 아직 우승할 가능성이 있는지 궁금해한다. 다시 말해, 남은 모든 경기의 승패를 적절히 정했을 때 팀 $S$보다 더 많이 이긴 팀이 하나도 없도록 만들 수 있는가? 두 팀 이상이 공동 우승할 수도 있다.

각 팀 $i$의 현재 승수 $w_i$와 패수 $d_i$가 주어지고, 모든 팀 쌍 $i$, $j$에 대해 앞으로 치러야 할 경기 수 $a_{i,j}$가 주어진다 (여기서 $1 \le i, j \le n$이고 $n$은 팀의 수). 팀은 $1, 2, \dots, n$으로 번호가 매겨져 있다. 우승할 가능성이 있는 모든 팀을 찾아라. 무승부는 없으며 모든 경기에는 승자와 패자가 정확히 한 팀씩 있다.

입력은 여러 개의 테스트 케이스로 이루어진다. 첫 줄에 테스트 케이스의 수 $T$가 주어진다.

각 테스트 케이스는 세 줄로 구성된다.

• 첫째 줄: 팀의 수 $n$ ($1 \le n \le 25$).
• 둘째 줄: $2n$개의 정수 $w_1\ d_1\ w_2\ d_2\ \dots\ w_n\ d_n$. 여기서 $w_i$와 $d_i$는 각각 팀 $i$의 현재 승수와 패수이며, 모두 $100$ 이하의 음이 아닌 정수이다.
• 셋째 줄: $n^2$개의 정수 $a_{1,1}\ a_{1,2}\ \dots\ a_{1,n}\ a_{2,1}\ \dots\ a_{n,n}$. $a_{i,j}$는 팀 $i$와 $j$가 앞으로 치를 경기 수이며 $10$ 이하의 음이 아닌 정수이다. 모든 $i$, $j$에 대해 $a_{i,j} = a_{j,i}$이고, $i = j$이면 $a_{i,j} = 0$이다.

한 줄 안의 정수들은 하나 이상의 공백으로 구분된다.

각 테스트 케이스마다 정확히 한 줄을 출력한다. 그 줄에는 우승할 가능성이 있는 모든 팀의 번호를 증가하는 순서로, 한 칸의 공백으로 구분하여 출력한다.