페인트볼 2초 512MB
문제
준혁이는 직사각형 모양의 이불 N개를 세탁한 후, 건조시키기 위하여 앞마당에 널어놓았다. 이 때 어떠한 두 이불들도 꼭짓점이나 변에서 겹치지 않게 하였고, 큰 이불 위에 작은 이불을 올려 놓아 한 이불이 다른 이불에 완전히 포함되도록 하기도 하였다. 준혁이가 잠깐 자리를 비운 사이, 친구 재민이는 준혁이를 골탕먹이기 위하여 색이 있는 페인트볼 M개를 사용하여 특정 위치에 페인트볼을 던졌다. 이 때, 한 페인트볼이 위에 있는 이불에 묻는다면 그 아래의 이불들 모두에도 묻는다. 모든 페인트볼의 위치는 서로 다름이 보장된다.
엉망이 된 이불을 보고 충격에 빠진 준혁이는, 세탁비 청구를 위하여 각 이불에 있는 서로 다른 색의 개수를 구하고자 한다. 준혁이를 도와주자!
입력
첫 번째 줄에 이불의 개수 N (1 ≤ N ≤ 80 000), 페인트볼의 개수 M (1 ≤ N ≤ 80 000)이 주어진다.
이후 주어지는 N개의 줄에는 직사각형의 왼쪽 아래 좌표 Ai, Bi (1 ≤ Ai, Bi ≤ 10^9), 오른쪽 위 좌표 Ci, Di, (1 ≤ Ci, Di ≤ 10^9 )가 주어진다.
이후 주어지는 M개의 줄에는 j번째 페인트볼의 좌표 Xj, Yj (1 ≤ Xj, Yj ≤ 10^9 )와 색 Kj (1 ≤ Kj ≤ 10^9)가 주어진다.
출력
i번째 줄에 i번 이불에 묻은 서로 다른 페인트볼의 색의 개수를 출력한다.
예제 #1
2 2
1 1 3 3
5 6 10 10
3 3 1
5 1 2
1
0
예제 #2
3 3
1 1 7 7
2 2 6 6
3 3 5 5
4 4 1
2 6 2
4 7 3
3
2
1
예제 #3
1 3
1 1 7 7
2 6 2
4 7 3
4 4 1
3
로그인해야 코드를 작성할 수 있어요.