Randall 是一名拥有 $N$ 名员工的公司里的软件工程师。每年，公司都会重新评估其员工。在每年年底，公司会替换掉几名表现最差的员工，并招募相同数量的新员工，以确保公司始终保持 $N$ 名员工。每个人的表现都是恒定的，可以用一个整数表示（整数越大表示表现越好），且没有两个人的表现相同。

初始员工的表现由一个整数数组 $A = [A_1, A_2, \dots, A_N]$ 表示，其中 $A_i$ 是第 $i$ 名员工的表现。Randall 是第 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$。对于每个场景，Randall 想知道在 $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, \dots, (B_i)_{R_i}$ ($1 \le R_i < N$; $0 \le (B_i)_j \le 10^9$)，分别表示每年替换的员工人数和新员工的表现。保证 $\sum 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$；如果 Randall 在 $M$ 年后仍会留在公司，则输出 $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]$。

因此，Randall 在 $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]$。

因此，Randall 在 $3$ 年后将不会留在公司。