Stage Lighting

$n$ projectors are installed along a stage, numbered from 1 to $n$ from left to right. Projector $i$ has power $p_i$. The stage counts as lit if the total power of the switched-on projectors is at least $Z$.

Each working projector must be connected to a set of connectors. There are $k$ different connectors in total. Projector $i$ has $k_i$ outputs and must be connected to connectors $a_{i,1}, a_{i,2}, \dots, a_{i,k_i}$. At any moment, at most one projector can be connected to a given connector.

For each $i$ from 1 to $n$, find the minimum $r_i$ such that, among projectors numbered from $i$ to $r_i$ inclusive, you can choose a subset of projectors to run at the same time so that the stage is lit.

The first line contains three integers $n$, $k$, and $Z$ ($1 \le n \le 10^5$, $1 \le k \le 8$, $1 \le Z \le 10^9$). The second line contains $n$ integers $p_1, \dots, p_n$ ($1 \le p_i \le 10^9$). The next $n$ lines describe the connectors. Line $i$ contains $k_i$ ($1 \le k_i \le k$) followed by $k_i$ distinct integers $a_{i,1}, \dots, a_{i,k_i}$ ($1 \le a_{i,j} \le k$).

Print $n$ lines. On line $i$, print $r_i$ if it exists, and $-1$ otherwise.