Description

The fans of the professional football clubs in the K-League are organized and well-trained cheerleaders, like the Red Devils cheer squad (the supporters of Korea’s national team at the 2002 Korea–Japan FIFA World Cup).

This season, after many matches, the fans want to know whether the team they support still has a chance to win the league title in the end. In other words, can the team, through some possible set of match outcomes, finish with the highest number of points (i.e., the most wins)? Ties for first place are allowed.

There are $n$ teams. For each team $i$, the numbers of wins and losses already recorded are $w_i$ and $d_i$. There are still some matches to be played: between team $i$ and team $j$, there are $a_{ij}$ remaining matches.

You need to find all teams that can still possibly become champions.

All teams will play the same total number of matches, and to simplify the problem, you may assume there are no draws; every match has only two outcomes: win or loss.

Input Format

• The first line contains a positive integer $n$, the number of teams.
• The second line contains $2n$ non-negative integers, representing $w_1, d_1, w_2, d_2, \cdots, w_n, d_n$.
• The third line contains $n^2$ non-negative integers, representing $a_{11}, a_{12}, \cdots, a_{1n}, a_{21}, \cdots, a_{2n}, \cdots, a_{n1}, \cdots, a_{nn}$ (row-major order).

Output Format

Output a single line containing all teams that can possibly become champions, in ascending order of their indices, separated by spaces.

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

1 2 3

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

1 2

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

2 4

Hint

For $100\%$ of the testdata, $n \le 25$, $w_i, d_i \le 100$, $a_{ij} \le 10$, $a_{ij} = a_{ji}$, $a_{ii} = 0$.

Translated by ChatGPT 5