题目描述

参与 $K$ 联赛（前身为韩国职业足球联赛）的职业足球俱乐部的球迷们，会像 $2002$ 年韩日世界杯期间韩国国家足球队的官方球迷组织“红魔”一样，进行有序且有组织的助威活动。在本赛季许多比赛结束后，球迷们可能会想知道他们所支持的球队 $S$ 是否仍有可能赢得联赛冠军。换句话说，能否为剩余的比赛安排获胜者，使得没有球队的胜场数超过球队 $S$ 呢？（两支或多支球队可以共同获得冠军。）

已知每支球队 $i$（$1 \leq i \leq n$）目前的胜场数 $w_i$ 和负场数 $d_i$，以及每两队 $i$ 和 $j$（$1 \leq i, j \leq n$）之间剩余的比赛场数 $a_{i,j}$，其中 $n$ 是球队的数量。球队编号为 $1, 2, \cdots, n$。你需要找出所有有可能赢得联赛冠军的球队。每个赛季中，每支球队必须参加相同数量的比赛。为了简化问题，我们假设比赛没有平局，即每场比赛都有胜负之分。

输入

输入包含 $T$ 个测试用例。测试用例的数量 $T$ 在输入文件的第一行给出。每个测试用例由三行组成：

1. 第一行包含一个整数 $n$（$1 \leq n \leq 25$），表示该测试用例中的球队数量。
2. 第二行包含 $2n$ 个非负整数 $w_1, d_1, w_2, d_2, \cdots$，每个数最大为 100，其中 $w_i$ 和 $d_i$ 分别是球队 $i$ 目前的胜场数和负场数。
3. 第三行包含 $n^2$ 个非负整数 $a_{1,1}, a_{1,2}, \cdots$，每个数最大为 10，其中 $a_{i,j}$ 是球队 $i$ 和球队 $j$ 之间剩余的比赛场数。对于所有的 $i$ 和 $j$，有 $a_{i,j} = a_{j,i}$。如果 $i = j$，则 $a_{i,j} = 0$。一行中给出的整数由一个或多个空格分隔。

输出

每个测试用例精确地输出一行。该行应按球队编号升序包含所有有可能赢得联赛冠军的球队。

输入样例

3
3
2 0 1 1 0 2
0 2 2 
2 0 2 
2 2 0
3
4 0 2 2 0 4
0 1 1 
1 0 1 
1 1 0
4
0 3 3 1 1 3 3 0
0 0 0 2 
0 0 1 0 
0 1 0 0 
2 0 0 0

输出样例

1 2 3
1 2
2 4

题目来源

Taejon 2002