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

You possess a certain quantity of items. For each item type $d$, you want to determine the maximum number of items of that type you can obtain using the items you currently have.

Input

The input is read from standard input.

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

The second line contains $n$ non-negative integers, where the $i$-th integer $c_i$ represents the number of items of type $i$ you possess.

The next $m$ lines describe the conversion rules. The $i$-th line represents the $i$-th conversion rule.

The format of a conversion rule is: a line containing $k_i+2$ positive integers, where the first is $a_i$, the second is $k_i$, followed by $k_i$ distinct positive integers $b_{i,1}, b_{i,2}, \dots, b_{i,k_i}$.

It is guaranteed that $1 \le n \le 100$ and $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

Output to standard output.

Output $n$ lines, where the $d$-th line represents the maximum number of items of type $d$ that can be obtained. If it is possible to obtain an arbitrarily large number of items (i.e., for any $N$, there exists a strategy to obtain more than $N$ items of type $d$), output infinity.

Examples

Input 1

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

Output 1

1
1
1
2

Note 1

Without using any conversion rules, you can obtain one item of type $1$.

Using the first conversion rule once, you can transform one item of type $1$ into one item of type $2$ and one item of type $4$. Thus, you can obtain one item of type $2$.

Using the second conversion rule once, you can transform one item of type $1$ into one item of type $3$. Thus, you can obtain one item of type $3$.

Using the first conversion rule once, you can transform one item of type $1$ into one item of type $2$ and one item of type $4$. Then, using the third conversion rule once, you can transform the item of type $2$ into one item of type $4$. Thus, you can obtain two items of type $4$.

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