성과 평가

Randall은 직원이 N명인 회사의 소프트웨어 엔지니어다. 회사는 매년 직원을 재평가한다. 매년 연말에 회사는 성과가 가장 나쁜 직원 몇 명을 내보내고 같은 수의 신입 사원으로 대체하여 항상 N명의 직원을 유지한다. 각 사람의 성과는 일정하고 정수로 나타낼 수 있으며(정수가 클수록 성과가 좋다), 두 사람의 성과가 같지 않다.

처음 직원의 성과는 정수 배열 A = [A1, A2, . . . , AN]로 나타내며, Ai는 i번째 직원의 성과다. Randall은 1번 직원이므로 그의 성과는 A1이다. 처음 M년을 고려하자. i번째 해 연말에 회사는 성과가 가장 나쁜 Ri명의 직원을 내보내고 Ri명의 신입 사원으로 대체한다. 이 신입 사원의 성과는 정수 배열 Bi = [(Bi)1,(Bi)2, . . . ,(Bi)Ri]로 나타내며, (Bi)j는 j번째 신입 사원의 성과다.

그는 Q개의 시나리오를 고려한다. i번째 시나리오에서 그는 (BXi)Yi의 값을 Zi로 바꾼다. 각 시나리오에 대해 Randall은 M년 후에도 회사에 남아 있을지 궁금해한다. 각 시나리오의 변경은 이후 시나리오에도 유지된다.

입력은 세 정수 N M Q (2 ≤ N ≤ 100 000; 1 ≤ M, Q ≤ 100 000)를 포함한 한 줄로 시작한다. 이는 각각 직원 수, 고려할 연수, 시나리오 수다. 다음 줄은 N개의 정수 Ai (0 ≤ Ai ≤ 109)를 포함하며, 처음 직원의 성과를 나타낸다. 다음 M개 줄은 각각 여러 정수를 포함한다. Ri (Bi)1, (Bi)2, · · · , (Bi)Ri (1 ≤ Ri < N; 0 ≤ (Bi)j ≤ 109)는 각각 대체되는 직원 수와 신입 사원의 성과를 나타낸다. Ri의 합은 106을 초과하지 않음이 보장된다. 다음 Q개 줄은 각각 세 정수 Xi Yi Zi (1 ≤ Xi ≤ M; 1 ≤ Yi ≤ R(Xi) ; 0 ≤ Zi ≤ 109)를 포함하며, 시나리오를 나타낸다. 모든 Ai, (Bi)j, Zi(전부 합쳐서)에 있는 모든 정수는 서로 다름이 보장된다.

각 시나리오에 대해 입력 순서대로, Randall이 M년 후 회사에 없을 경우 0을, Randall이 M년 후에도 회사에 남아 있을 경우 1을 한 줄에 출력한다.

Randall의 성과는 50으로 나타난다. 첫 번째 시나리오에서 (B1)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년 후에도 회사에 남아 있다.

두 번째 시나리오에서 (B2)1의 값이 400으로 갱신되면 다음과 같다.

• 처음 직원의 성과는 [50, 40, 30, 20, 10]이다.
• 첫해 연말에 직원의 성과는 [300, 100, 50, 2, 1]이다. 첫 번째 시나리오의 변경이 이 시나리오에도 유지됨을 기억하자.
• 둘째 해 연말에 직원의 성과는 [400, 300, 100, 50, 2]이다.
• 셋째 해 연말에 직원의 성과는 [400, 300, 100, 7, 6]이다.

따라서 Randall은 3년 후에 회사에 없다.