시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 7 4 4 80.000%

문제

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 = [A1, A2, . . . , AN] where Ai is the performance of the ith employee. Randall is employee 1, so his performance is A1. We will consider the first M years. At the end of the ith year, the company replaces its Ri worst-performing employees and replaces with Ri new employees. The performance of these new employees are represented by an array of integers Bi = [(Bi)1,(Bi)2, . . . ,(Bi)Ri] where (Bi)j is the performance of the jth new employee.

He will consider Q scenarios. On the ith scenario, he will change the value of (BXi)Yi to Zi. 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.

입력

Input begins with a line containing three integers: N M Q (2 ≤ N ≤ 100 000; 1 ≤ M, Q ≤ 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: Ai (0 ≤ Ai ≤ 109) representing the performance of the initial employees. The next M lines each contains several integers: Ri (Bi)1, (Bi)2, · · · , (Bi)Ri (1 ≤ Ri < N; 0 ≤ (Bi)j ≤ 109) representing the number of employees replaced and the performance of the new employees, respectively. It is guaranteed that the sum of Ri does not exceed 106. The next Q lines each contains three integers: Xi Yi Zi (1 ≤ Xi ≤ M; 1 ≤ Yi ≤ R(Xi) ; 0 ≤ Zi ≤ 109) representing a scenario. It is guaranteed that all integers in all Ai, (Bi)j, and Zi (combined together) are distinct.

출력

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.

예제 입력 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

힌트

Randall performance is represented by 50. For the first scenario, the value of (B1)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 (B2)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