Description

The Olympic Games are in full swing, and many teams on the medal table need to be ranked. You need to choose three integers $P_g, P_s$ and $P_b$, representing the score awarded for each gold, silver, and bronze medal, respectively, and they must satisfy $1000 \ge P_g \ge P_s \ge P_b \ge 1$. Teams will be sorted by their scores in descending order. Now, to make your own team rank as high as possible, you will choose $P_g, P_s, P_b$.

Input Format

The first line contains an integer $n$ ($1 \le n \le 15$), indicating that there are $n$ teams to be ranked.

Each of the following $n$ lines contains three integers $G, S, B$ ($0 \le G, S, B \le 10^5$), representing the numbers of gold, silver, and bronze medals obtained by each team.

• The first team is your team.
• If the scores are equal, your team ranks first.

Output Format

Output three numbers $P_g, P_s, P_b$ in one line, separated by spaces.

If there are multiple solutions, output the one with the smallest $P_g$. If there are still multiple solutions, output the one with the smallest $P_s$. If there are still multiple solutions, output the one with the smallest $P_b$.

3
1 1 1
0 1 2
2 1 0

1 1 1

Hint

Constraints

• For $10\%$ of the testdata, it is guaranteed that the optimal solution has $P_g \le 10$.
• For $30\%$ of the testdata, it is guaranteed that the optimal solution has $P_g \le 100$.

Translated by ChatGPT 5