Background

The small square’s adventure journey has not been smooth.

Along the way, the small square saw magnificent and beautiful islands being polluted, saw grand volcanoes, and encountered many enemies.

Now, the small square is dealing with a huge triangle.

Problem Description

The big triangle tells the small square about its past: it used to be a treasure miner, but later it was corrupted by the Lord of Darkness and ended up like this.

It also hopes that the small square can defeat the Lord of Darkness, but because the Lord of Darkness has spies everywhere, it must set obstacles for the small square to fool those “spies”.

The problem it gives to the small square is: it has $n$ small triangles, and each small triangle has a certain weight. It performed $n + 1$ weighings on these triangles; however, due to an issue with the pan balance (?), one weighing result is wrong.

Now, the big triangle wants to know the index of the heaviest small triangle.

An input is considered valid if and only if it satisfies the following condition:

There do not exist two indices $i$, $j$ such that, when we assume the $i$-th weighing data is wrong, we can find a valid solution, and when we assume the $j$-th weighing data is wrong, we can also find a valid solution.

A valid solution is defined as follows:

1. There is exactly one heaviest triangle.

2. There is no triangle whose weight is undetermined.

3. The weights of all triangles are positive integers.

Input Format

The first line contains a positive integer $n$, representing the number of small triangles.

The next $n + 1$ lines are given in the following format:

First, an integer $m$, representing how many small triangles are grabbed in this weighing.

Then $m$ integers, representing the indices of the small triangles being weighed.

The last integer $weight$ represents the result of this weighing.

Output Format

If it is valid, output the index of the heaviest small triangle; otherwise output "illegal" (without quotes).

2
1 1 2
2 1 2 5
2 1 2 1

2

2
1 1 2
2 1 2 4
2 1 2 5

2

2
1 1 2
2 1 2 6
2 1 2 5

illegal

Hint

Sample 1:

If the result of the first weighing is wrong, then a correct solution cannot be obtained.

If the result of the second weighing is wrong, then the weight of the second small triangle is negative, which is obviously not correct.

If the result of the third weighing is wrong, we obtain that triangle $1$ has weight $2$, triangle $2$ has weight $3$, and triangle $2$ is the heaviest.

This problem uses bundled testdata and has three $subtask$s, described as follows:

$subtask 0 - 30Pts$: It is guaranteed that the weights of small triangles are <= 20 and $n <= 5$. In this $subtask$, you can get $10$ points for each test you pass.

$subtask 1 - 30Pts$: It is guaranteed that the weights of small triangles are <= 100 and $n <= 100$. The testdata are randomly generated.

$subtask 2 - 40Pts$: It is guaranteed that the weights of small triangles are <= 100 and $n <= 100$.

In the last two $subtask$s, you must pass all testdata to get any score.

For $100\%$ of the testdata, $1 <= m <= n$

Translated by ChatGPT 5