CF1252G.Performance Review

Randall is a software engineer at a company with $N$ employees. Every year, the company re-evaluates its employees. At the end of every year, the company replaces its several worst-performing employees and replaces with the same number of new employees, so that the company keeps having $N$ employees. Each person has a constant performance and can be represented by an integer (higher integer means better performance), and no two people have the same performance.

The performance of the initial employees are represented by an array of integers $A = [A_1, A_2, \dots, A_N]$ where $A_i$ is the performance of the $i^{th}$ employee. Randall is employee $1$, so his performance is $A_1$. We will consider the first $M$ years. At the end of the $i^{th}$ year, the company replaces its $R_i$ worst-performing employees and replaces with $R_i$ new employees. The performance of these new employees are represented by an array of integers $B_i = [(B_i)_1, (B_i)_2, \dots, (B_i)_{R_i}]$ where $(B_i)_j$ is the performance of the $j^{th}$ new employee.

He will consider $Q$ scenarios. On the $i^{th}$ scenario, he will change the value of $(B_{X_i})_{Y_i}$ to $Z_i$. For each scenario, Randall is wondering whether he will still be in the company after $M$ years. Note that the changes in each scenario are kept for the subsequent scenarios.

兰德尔是一家拥有 $N$ 名员工的公司的软件工程师。每年，公司都会对员工进行绩效评估。每年年末，公司会淘汰若干名绩效最差的员工，并招聘相同数量的新员工，以确保公司始终维持 $N$ 名员工。每位员工的绩效为一个固定整数（数值越大表示绩效越好），且任意两名员工的绩效均不相同。

初始员工的绩效用一个整数数组 $A = [A_1, A_2, \dots, A_N]$ 表示，其中 $A_i$ 表示第 $i$ 位员工的绩效。兰德尔是第 $1$ 号员工，因此他的绩效为 $A_1$。我们考虑前 $M$ 年的情况。在第 $i$ 年年末，公司会淘汰 $R_i$ 名绩效最差的员工，并招聘 $R_i$ 名新员工。这些新员工的绩效用一个整数数组 $B_i = [(B_i)_1, (B_i)_2, \dots, (B_i)_{R_i}]$ 表示，其中 $(B_i)_j$ 表示第 $j$ 名新员工的绩效。

兰德尔将考虑 $Q$ 种情形。在第 $i$ 种情形中，他将把 $(B_{X_i})_{Y_i}$ 的值修改为 $Z_i$。对于每种情形，兰德尔想知道：在经历 $M$ 年后，他是否仍留在公司中。注意：每种情形所做的修改会持续保留至后续情形中。

Input begins with a line containing three integers: $N$ $M$ $Q$ ($2 \le N \le 100\,000$; $1 \le M, Q \le 100\,000$) representing the number of employees, the number of years to be considered, and the number of scenarios, respectively. The next line contains $N$ integers: $A_i$ ($0 \le A_i \le 10^9$) representing the performance of the initial employees. The next $M$ lines each contains several integers: $R_i$ $(B_i)_1$, $(B_i)_2$, $\cdots$, $(B_i)_{R_i}$ ($1 \le R_i \lt N$; $0 \le (B_i)_j \le 10^9$) representing the number of employees replaced and the performance of the new employees, respectively. It is guaranteed that the sum of $R_i$ does not exceed $10^6$. The next $Q$ lines each contains three integers: $X_i$ $Y_i$ $Z_i$ ($1 \le X_i \le M$; $1 \le Y_i \le R_{(X_i)}$; $0 \le Z_i \le 10^9$) representing a scenario. It is guaranteed that all integers in all $A_i$, $(B_i)_j$, and $Z_i$ (combined together) are distinct.

输入的第一行包含三个整数：$N$、$M$、$Q$（$2 \le N \le 100\,000$；$1 \le M, Q \le 100\,000$），分别表示员工人数、需考虑的年数以及场景数量。
第二行包含 $N$ 个整数：$A_i$（$0 \le A_i \le 10^9$），表示初始员工的绩效值。
接下来的 $M$ 行，每行包含若干整数：$R_i$、$(B_i)_1$、$(B_i)_2$、$\cdots$、$(B_i)_{R_i}$（$1 \le R_i \lt N$；$0 \le (B_i)_j \le 10^9$），分别表示第 $i$ 年被替换的员工人数，以及新员工的绩效值。保证所有 $R_i$ 的总和不超过 $10^6$。
接下来的 $Q$ 行，每行包含三个整数：$X_i$、$Y_i$、$Z_i$（$1 \le X_i \le M$；$1 \le Y_i \le R_{(X_i)}$；$0 \le Z_i \le 10^9$），表示一个场景。保证所有 $A_i$、$(B_i)_j$ 和 $Z_i$（合并在一起）中的整数互不相同。

For each scenario in the same order as input, output in a line an integer $0$ if Randall will not be in the company after $M$ years, or $1$ if Randall will still be in the company after $M$ years.

对于输入中每个场景（按相同顺序），在一行中输出一个整数：若 $M$ 年后 Randall 将不在该公司，则输出 $0$；若 $M$ 年后 Randall 仍将在该公司，则输出 $1$。

Explanation for the sample input/output #1

Randall performance is represented by $50$. For the first scenario, the value of $(B_1)_3$ is updated to $300$, causes the following:

• Initially, the performance of the employees is $[50, 40, 30, 20, 10]$.
• At the end of the first year, $4$ worst-performing employees are replaced by employees with performance $[300, 100, 2, 1]$. Therefore, the performance of the employees is $[300, 100, 50, 2, 1]$.
• At the end of the second year, the performance of the employees is $[300, 100, 50, 4, 2]$.
• At the end of the third year, the performance of the employees is $[300, 100, 50, 7, 6]$.

Therefore, Randall will still be in the company after $3$ years.

For the second scenario, the value of $(B_2)_1$ is updated to $400$, causes the following:

• Initially, the performance of the employees is $[50, 40, 30, 20, 10]$.
• At the end of the first year, the performance of the employees is $[300, 100, 50, 2, 1]$. Recall that the change in the first scenario is kept for this scenario as well.
• At the end of the second year, the performance of the employees is $[400, 300, 100, 50, 2]$.
• At the end of the third year, the performance of the employees is $[400, 300, 100, 7, 6]$.

Therefore, Randall will not be in the company after $3$ years.

样例输入/输出 #1 的说明

兰德尔的绩效值为 $50$。对于第一种情形，$(B_1)_3$ 的值被更新为 $300$，导致如下变化：

• 初始时，员工的绩效值为 $[50, 40, 30, 20, 10]$。
• 第一年末，绩效最低的 $4$ 名员工被绩效值为 $[300, 100, 2, 1]$ 的新员工替代。因此，员工的绩效值变为 $[300, 100, 50, 2, 1]$。
• 第二年末，员工的绩效值变为 $[300, 100, 50, 4, 2]$。
• 第三年末，员工的绩效值变为 $[300, 100, 50, 7, 6]$。

因此，兰德尔在 $3$ 年后仍将留在公司。

对于第二种情形，$(B_2)_1$ 的值被更新为 $400$，导致如下变化：

• 初始时，员工的绩效值为 $[50, 40, 30, 20, 10]$。
• 第一年末，员工的绩效值为 $[300, 100, 50, 2, 1]$。（注意：第一种情形中的修改在此情形中同样生效。）
• 第二年末，员工的绩效值变为 $[400, 300, 100, 50, 2]$。
• 第三年末，员工的绩效值变为 $[400, 300, 100, 7, 6]$。

因此，兰德尔在 $3$ 年后将不再留在公司。