Description

As senior high schools in City B are gradually diversifying their student recruitment method, the number of unified enrollment quotas decreases year after year. In this problem, you are asked to track the process based on the "Parallel Aspiration" rules, which will be explained below.

Little $\zeta$ found the admission statistics of some year to fill out high school applications better.

To be specific, there were $n$ students. The $i$-th of them filled out $l_i$ aspirations, i.e., chose $l_i$ schools. The $j$-th aspiration of the $i$-th student was $a_{i,j}$. Among the $m$ senior high schools participating in the admission process, the $i$-th school offered $t_i$ quotas.

Let $b_i$ be the number of students already determined to be admitted to school $i$. The following process was adopted to determine the admission statistics for each individual:

• All the remaining students with the highest score $\bm o$ in the entrance exam whose admission result hadn't been determined were selected.
• Let $S$ be the set of schools with available quotas. Formally, $S = \{1 \leq i \leq m \mid t_i > b_i\}$.
• For each selected student $x$, iterate $i$ over their list of aspirations $a_{x,1}, a_{x, 2}, \ldots, a_{x, l_x}$ in order:
  • if $i \in S$, then student $x$ was admitted by school $i$. Then, $b_i \gets b_i + 1$ and the process was terminated.
  • If none of the schools in $a_{x, 1}, a_{x, 2}, \ldots, a_{x, l_x}$ belonged to $S$, student $x$ was not admitted to any school.
• The changes of $b_i$ during the third step did not affect the set $S$. Therefore, it's possible for some schools to have $b_i > t_i$. Once the admission decision is made for a student, their status is final, whether they are admitted or not.
• Repeat this process until the status of all students are final.

Because the initial statistics have several errors, $q$ modifications are made. Each modification is described by two integers $x$ and $v$. It reduces $t_x$ by $v$. You need to determine the number of students whose admission result is changed from when the last modification was made. Note that the modifications are persistent, which means a previous modification keeps in effect.

Input Format

The first line of input contains three integers $n$, $m$, and $q$, denoting the number of students, schools, and modifications.

The second line of input contains $m$ integers $t_1, \ldots, t_m$.

Then $n$ lines follow. The $i$-th line describes the aspiration list of the $i$-th student: there is an integer $l_i$ followed by $l_i + 1$ integers $a_{i,1}, a_{i,2}, \ldots, a_{i, l_i}$, and $o_i$. $o_i$ denotes the score of student $i$ in the entrance exam.

Then $q$ lines follow. Each line consists of two integers $x, v$, representing a modification.

Output Format

Output $q$ lines. The $i$-th line contains an integer, as the number of students whose admission result is changed from when the last modification was made.

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

0
0
2
2
3

Hint

The admission results of each student after each modification are:

• $\{1, 2, 3, 3, 3\}$;
• $\{1, 2, 3, 3, 3\}$;
• $\{1, 2, 3, 3, 3\}$;
• $\{1, 2, 3, 2, 0\}$;
• $\{1, 0, 2, 2, 0\}$, and
• $\{0, 0, 1, 0, 0\}$, respectively, in which $0$ represents being not admitted.

Constraints

• $1 \leq n, m, q \leq 3 \cdot 10^5$
• $0 \leq t_i \leq 10^6$
• $0 \leq l_i \leq m$, $\sum l_i \leq m$
• $1 \leq a_{i,j} \leq m$ (For each $i$, It's not guaranteed that $a_{i,j}$ are distinct)
• $0 \leq o_i \leq 10^6$
• $1 \leq x \leq m$
• $1 \leq v \leq t_x$, where $t_x$ is the value of $t_x$ at the time exactly before the modification

Subtasks

Subtasks are used in this problem.

• Subtask 1 (15 pts): $\max(n, m, q) \leq 500$, $\sum l_i \leq 5000$
• Subtask 2 (20 pts): There are at most $2$ distinct values in $o$.
• Subtask 3 (35 pts): $o_i$ are distinct.
• Subtask 4 (30 pts): No additional constraints.