영업의 신

시간 제한1.5초메모리 제한1024 MB

요약
Q번의 매출 갱신이 일어날 때마다, 담당한 K개 매장 모두에서 1위인 직원 수를 센다.
난이도

보통10점 중 6점

유형
구현, 해시맵, 시뮬레이션
정답자
아직 제출이 없습니다

문제

ZerOne 주식회사의 사장인 정민이는 느슨해진 직원들에 긴장감을 주기 위해 영업왕을 뽑기로 한다. 각 직원은 총 MM개의 매장 중에서 KK개의 매장을 담당하고 있으며, 영업왕은 자신이 맡은 모든 매장에서 누적 매출 1위를 달성한 직원으로 한다. 단, 각 매장의 직원별 누적 매출액은 항상 서로 다르며 감소하지 않는다.

ZerOne 회사의 직원들이 올린 매출의 정보가 시간 순서대로 주어진다고 했을 때, 그때마다의 누적 매출액을 계산하여 영업왕의 수를 구하여라.

입력

첫 번째 줄에 직원의 수 NN과 총매장 수 MM, 각 직원이 맡은 매장의 수 KK가 공백으로 구분되어 주어진다. (1≤N≤300;(1 \leq N \leq 300; 1≤M≤10,000;1 \leq M \leq 10\\,000; 1≤K≤M)1 \leq K \leq M)

두 번째 줄부터 각 직원이 맡은 매장의 번호 jj와 초기 매출액 tt가 공백으로 구분되어 한 줄에 KK번 주어진다. 11번 직원부터 NN번 직원까지 순서대로 주어진다. (1≤j≤M;(1 \leq j \leq M; 1≤t≤10,000)1 \leq t \leq 10\\,000)

N+2N+2 번째 줄에 직원이 매출을 올린 횟수 QQ가 주어진다. (1≤Q≤1,000,000)(1 \leq Q \leq 1\\,000\\,000)

N+3N+3 번째 줄부터 QQ개의 줄에 걸쳐 매출을 올린 직원의 번호 ii와 매장 번호 jj, 누적 매출액 대비 증가한 매출액 vv가 공백으로 구분되어 시간 순서대로 주어진다. (1≤i≤N;(1 \leq i \leq N; 1≤j≤M;1 \leq j \leq M; 1≤v≤1,000)1 \leq v \leq 1\\,000)

입력에 주어지는 모든 수는 정수이다.

출력

현재 영업왕의 수를 QQ줄에 걸쳐 출력한다.

예제2

  1. 예제 1

    입력
    4 5 2
1 100 4 230
1 80 2 170
2 250 5 280
1 90 3 100
3
2 2 100
4 1 50
2 2 10
    예상 출력
    1
1
1

  2. 예제 2

    입력
    4 5 2
1 100 4 230
1 80 2 170
2 250 5 280
1 90 3 100
3
2 2 70
2 2 20
2 1 30
    예상 출력
    2
1
1