Problem Description

There are $n$ types of items and $m$ types of transformations. The $i$-th transformation can transform one item of type $a_i$ into $k_i$ pairwise distinct items, where the type of the $j$-th item is $b_{i,j}$. The same transformation can be used any number of times.

You have some items. You want to know, for each specific item type $d$, using the items you have, what is the maximum number of items of type $d$ that can be obtained through transformations.

Input Format

The first line contains two positive integers $n,m$.

The second line contains $n$ non-negative integers, where the $i$-th is $c_i$, meaning the number of items of type $i$ that you have.

The next $m$ lines describe the transformations.
The format of a transformation is: one line with $k_i+2$ positive integers. The first is $a_i$, the second is $k_i$, followed by $k_i$ pairwise distinct positive integers $b_{i,1},b_{i,2},\cdots,b_{i,k_i}$.

Constraints: $1\le n \le 100$, $1\le m \le 1000$.

It is guaranteed that $1\le a_i,k_i,b_{i,j} \le n$.

It is guaranteed that $0\le c_i \le 1000$.

Output Format

Output $n$ lines. The $d$-th line should contain the maximum possible number of items of type $d$. If it can be arbitrarily large, i.e., for any $N$ there exists a plan such that the number of items of type $d$ is greater than $N$, output infinity.

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

1
1
1
2

Hint

Without using any transformation, you can obtain one item $1$.

Using the first transformation once, you can turn item $1$ into item $2$ and item $4$. In this way, you can obtain one item $2$.

Using the second transformation once, you can turn item $1$ into item $3$. In this way, you can obtain one item $3$.

Using the first transformation once, you can turn item $1$ into item $2$ and item $4$. Then using the third transformation once, you can turn item $2$ into item $4$. In this way, you can obtain two items $4$.

It can be proven that these four plans are optimal when $d=1,2,3,4$, respectively.

Source and Acknowledgements

From the THUPC2024 Final (the 2024 Tsinghua University Student Programming Contest and Intercollegiate Invitational Contest). Thanks to THUSAA for providing this problem.

For the testdata, statement, reference solution, editorial, etc., please refer to the official THUPC repository: https://thusaac.com/public.

Translated by ChatGPT 5