시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 114 20 19 20.000%

문제

N개의 블럭들이 쌓여 요새를 만든다. 각각의 블럭은 서로 겹치지 않게 H층에서 L칸에서 R칸까지의 구간을 차지한다. 1층의 블럭을 제외한 다른 블럭들은 항상 아래층에 어떤 블럭이 존재한다. 이때 위에 쌓여 있는 블럭은 아래에 있는 블럭의 구간 안에 전부 포함된다. 즉, 임의의 i 번 블럭의 위에 쌓이는 모든 j번 블럭에 대해서 Li ≤ Lj ≤ Rj ≤ Ri가 성립한다. 

이러한 요새를 파괴하기 위해 미사일 폭격이 K번 이루어졌다. 각 폭격은 위치 X에 위력 P인 미사일이 발사되었고, 요새의 X 위치에 있는 블럭 중 위에서부터 최대 P개의 블럭을 파괴한다. 이때 블럭이 제거되는 과정에서 아래에 깔려 있던 블럭이 제거되는 경우 위에 있는 블럭은 피해 없이 그대로 아래로 내려온다.

다음 그림은 위치 X=5에 위력 P=1인 미사일이 발사되는 모습이다.


 

폭격된 순서대로 각 폭격에 대하여 파괴된 블럭의 개수를 구하시오.

입력

첫 줄에 블럭의 개수 N이 주어진다. (1 ≤ N ≤ 100,000)

다음 N줄에 걸쳐 요새를 이루고 있는 블럭의 정보 HL, R가 주어진다. (1 ≤ H ≤ N, 1 ≤ L ≤ R ≤ 1,000,000,000)

다음 줄에 폭격의 횟수 Q가 주어진다. (1 ≤ Q ≤ 100,000)

다음 Q줄에 걸쳐 폭격의 위치 X와 위력 P가 주어진다. (1 ≤ X ≤ 1,000,000,000, 1 ≤ P ≤ N)

출력

폭격된 순서대로 각 폭격에 대하여 파괴된 블럭의 개수를 출력한다.

예제 입력 1

7
4 10 11
3 9 11
3 7 8
2 7 11
1 1 12
3 3 4
2 2 5
4
5 1
11 2
10 3
9 4

예제 출력 1

1 2 2 0

출처

University > 경인지역 6개대학 연합 프로그래밍 경시대회 > shake! 2020 G번