문제
정올국에는 0번부터 N-1번까지 N개의 마을이 있다.
정올국 과학부장관인 준혁이는 몇 개의 양방향 통신 케이블을 마을 간에 유치할 것이다. 현재, 정올국에는 케이블이 하나도 없다.
준혁이는 C일 간의 케이블 건설 계획이 있다. i번째 날(0 <= i <= C-1)의 계획은 세 정수 Ti, Xi, Yi로 나타난다.
- Ti = 0인 경우, 마을 Xi와 Yi를 잇는 케이블을 건설한다. (현재 이러한 케이블이 없음이 보장된다.)
- Ti = 1인 경우, 마을 Xi와 Yi를 잇는 케이블을 제거한다. (현재 이러한 케이블이 있음이 보장된다.)
정올국에는 절벽 붕괴가 자주 일어난다.
만약 마을 x와 마을 x+1 사이에서 붕괴가 일어난다면(0 <= x < N-1), x 이하의 마을과 x+1 이상의 마을을 잇는 모든 케이블이 붕괴된다.
절벽 붕괴를 대비하여, 준혁이는 몇 개의 마을에 긴급용 발전기를 놓기로 하였다.
긴급용 발전기는 모든 마을에서 케이블을 통해 긴급용 발전기에 도달할 수 있도록 설치되어야 한다.
준혁이는 건설 과정 중 절벽 붕괴가 일어날 것을 우려하여, 상황에 따라 몇 개의 발전기가 필요한지에 대하여 생각하고자 한다.
준혁이는 Q개의 질문이 있다.
j번째 질문(0 <= j < Q)은 두 정수 Wj, Pj로 나타내어진다.
이는 만약 Wj번째 날의 저녁에 마을 Pj와 Pj+1 사이에서 붕괴가 일어날 시, 몇 개의 발전기가 필요한가?라는 질문이다.
여러분이 준혁이를 도와, 준혁이의 질문을 해결해 주자.
입력
1번 줄 : N C Q
2 ~ 1 + C번 줄 : Ti, Xi, Yi
2 + C ~ 2 + C + Q 번 줄 : Wj, Pj
1번 부분문제 (5점) : 2 <= N <= 5000, 1 <= C, Q <= 5000
2번 부분문제 (30점) : 2 <= N <= 100000, 1 <= C, Q <= 100000, 모든 Pj는 동일하다.
3번 부분문제 (30점) : 2 <= N <= 100000, 1 <= C, Q <= 100000, 모든 Ti는 0이다.
4번 부분문제 (35점) : 2 <= N <= 100000, 1 <= C, Q <= 100000
출력
Q개의 줄에 걸쳐, i번째 질문에 대한 답을 각 줄에 출력하여라.
예제
5 8 2
0 0 1
0 1 3
0 2 4
0 4 0
1 1 3
0 0 3
0 1 2
0 4 3
3 1
7 3
3
2
로그인해야 코드를 작성할 수 있어요.