Randall 是一家拥有 $$$N$$$ 员工的公司的软件工程师。每年,公司都会重新评估员工。每年年底,公司都会更换几名表现最差的员工,并更换同等数量的新员工,从而使公司继续拥有$$$N$$$员工。每个人都有一个恒定的表现,可以用一个整数来表示(整数越大表示表现越好),并且没有两个人的表现相同。
初始员工的绩效由整数数组 $$$A = [A_1, A_2, \dots, A_N]$$$ 表示,其中 $$$A_i$$$ 是 $$$i^{th}$$$ 员工的绩效。 Randall 是员工 $$$1$$$,因此他的绩效为 $$$A_1$$$。我们将考虑最初的 $$$M$$$ 年。在 $$$i^{th}$$$ 年结束时,公司将替换 $$$R_i$$$ 表现最差的员工,并用 $$$R_i$$$ 新员工替换。这些新员工的绩效由整数数组 $$$B_i = [(B_i)_1, (B_i)_2, \dots, (B_i)_{R_i}]$$$ 表示,其中 $$$(B_i)_j$$$ 是 $$$j^{th}$$$ 新员工的绩效。
他会考虑 $$$Q$$$ 场景。在$$$i^{th}$$$场景中,他会将$$$(B_{X_i})_{Y_i}$$$的值更改为$$$Z_i$$$。对于每种情况,兰德尔都在想,在 $$$M$$$ 年后他是否还会留在公司。请注意,每个场景中的更改都会保留用于后续场景。
输入
输入以包含三个整数的行开头: $$$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 < N$$$; $$$0 \le (B_i)_j \le 10^9$$$)分别代表被替换的员工数量和新员工的绩效。保证$$$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$$$(组合在一起)中的所有整数都是不同的。
输出
对于与输入相同顺序的每个场景,如果 Randall 在 $$$M$$$ 年后不再在公司,则在一行中输出一个整数 $$$0$$$;如果在 $$$M$$$ 年之后 Randall 仍将在公司,则输出 $$$1$$$。
示例
输入 #1
5 3 3 50 40 30 20 10 4 1 2 3 100 1 4 2 6 7 1 3 300 2 1 400 2 1 5
输出 #1
1 0 1
注意
示例输入/输出#1 的说明
Randall 的表现用 $$$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]$$$。
对于第二种情况,$$$(B_2)_1$$$ 的值更新为 $$$400$$$,导致以下结果:
- 最初,员工的绩效为 $$$[50, 40, 30, 20, 10]$$$。
- 第一年结束时,员工的绩效为 $$$[300, 100, 50, 2, 1]$$$。回想一下,第一个场景中的更改也适用于此场景。
- 第二年末,员工的绩效为 $$$[400, 300, 100, 50, 2]$$$。
- 第三年末,员工的绩效为$$$[400, 300, 100, 7, 6]$$$。