이불과 페인트볼

어린 도널드가 어느 날 하얀 이불 $N$장을 모두 빨았다. 빨래를 끝낸 도널드는 뒷마당 바닥에 이불을 펼쳐 널었다. 어떤 두 이불도 꼭짓점이나 변이 맞닿지 않고 변끼리 교차하지도 않게 널었지만, 작은 이불이 큰 이불 위에 통째로 올라가거나 한 이불이 다른 이불을 완전히 덮는 것은 가능하다. 이불을 다 넌 도널드는 잠자리에 들었다.

도널드의 친구 킴은 도널드가 이불을 말린다는 소식을 듣고 장난을 치기로 했다. 킴은 다락에서 아버지의 페인트볼 총과 페인트볼 $M$개를 찾아냈다. 공은 색이 여러 가지이고, 같은 색이 여러 개 있을 수도 있다. 도널드가 잠들자마자 킴은 뒷마당으로 들어가 이불을 향해 총을 쐈다. 이불은 물감이 잘 배어서, 맨 위에 있는 이불이 총알을 맞으면 그 색이 아래에 깔린 이불로 전부 번진다. 킴은 공을 다 쓰고 신이 나서 돌아갔다.

아침에 이불을 걷으러 나온 도널드는 이불마다 못 보던 색이 잔뜩 생긴 것을 보고 충격에 빠졌다. 정확한 자료를 좋아하는 도널드는 지금 생각할 여력이 없으니, 이불마다 새로 생긴 색이 몇 가지인지 대신 세어 달라고 부탁했다.

뒷마당은 무한한 좌표평면, 이불은 좌표축에 평행한 직사각형, 킴이 쏜 자리는 그 평면 위의 점이라고 하자. 총알이 이불의 경계선 위에 떨어졌다면 그 이불을 맞힌 것으로 친다.

킴이 쏜 총알이 어떤 이불도 맞히지 못했을 수 있다. 각 총알이 떨어진 좌표는 모두 다르다.

첫째 줄에 이불의 수 $N$과 페인트볼의 수 $M$이 주어진다. ($1 \le N \le 80000$, $1 \le M \le 80000$)

다음 $N$개 줄 중 $i$번째 줄에는 $i$번 이불의 왼쪽 아래 꼭짓점 좌표 $A_i$, $B_i$와 오른쪽 위 꼭짓점 좌표 $C_i$, $D_i$가 주어진다. ($1 \le A_i < C_i \le 10^9$, $1 \le B_i < D_i \le 10^9$)

이어지는 $M$개 줄 중 $j$번째 줄에는 킴이 쏜 $j$번째 총알이 떨어진 좌표 $X_j$, $Y_j$와 그 공의 색 번호 $K_j$가 주어진다. ($1 \le X_j \le 10^9$, $1 \le Y_j \le 10^9$, $1 \le K_j \le 10^9$)

$N$개 줄을 출력한다. $i$번째 줄에는 $i$번 이불에 새로 생긴 색의 가짓수를 출력한다.

그림에서 점 옆에 적힌 번호는 그 총알의 색 번호다.

첫 번째 예제를 그린 그림이다.

두 번째 예제를 그린 그림이다.