The K-League

Supporters of the professional football clubs in the K-League wonder whether the team $S$ they cheer for can still win the championship. In other words, is it possible to decide the winners of all the remaining games so that no team finishes the season with more wins than $S$? Two or more teams may share the title.

You are given, for every team $i$, its current number of wins $w_i$ and losses $d_i$, and for every pair of teams $i$ and $j$ the number $a_{i,j}$ of games still to be played between them (where $1 \le i, j \le n$ and $n$ is the number of teams). The teams are numbered $1, 2, \dots, n$. Find every team that still has a chance of winning the championship. There are no draws: every game has exactly one winner and one loser.

The input contains several test cases. The first line gives the number of test cases $T$.

Each test case consists of three lines:

• The first line has the number of teams $n$ ($1 \le n \le 25$).
• The second line has $2n$ integers $w_1\ d_1\ w_2\ d_2\ \dots\ w_n\ d_n$, where $w_i$ and $d_i$ are the current wins and losses of team $i$; each is a nonnegative integer at most $100$.
• The third line has $n^2$ integers $a_{1,1}\ a_{1,2}\ \dots\ a_{1,n}\ a_{2,1}\ \dots\ a_{n,n}$, where $a_{i,j}$ is the number of remaining games between teams $i$ and $j$; each is a nonnegative integer at most $10$. For all $i$ and $j$, $a_{i,j} = a_{j,i}$, and $a_{i,j} = 0$ when $i = j$.

Integers on the same line are separated by one or more spaces.

For each test case print exactly one line. The line lists the numbers of all teams that still have a chance of winning the championship, in increasing order, separated by single spaces.