아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

달걀 받기

시간 제한5초메모리 제한256 MB

요약
각 날짜의 축에 평행한 직사각형 안에 들어가는 집의 수를 세어 테스트 케이스마다 합계를 출력합니다.
난이도

보통10점 중 6점

유형
누적 합, 정렬, 세그먼트 트리
정답자
아직 제출이 없습니다

문제

당신은 국민에게 큰 사랑을 받는 대통령이다. 퍼레이드에 나설 때마다 국민은 당신에게 달걀을 던진다. 당신이 달걀을 좋아하기 때문이고, 날아오는 달걀은 하나도 빠뜨리지 않고 받아낸다.

국민 한 명은 그날의 퍼레이드 구역이 자기 집을 덮을 때마다 달걀을 하나 던진다. 2차원 평면 위에 국민 nn명의 집 좌표가 주어진다. 한집에 여러 명이 살 수 있으므로 같은 좌표가 여러 번 나올 수 있다.

임기는 mm일 남았고, 날마다 퍼레이드 구역이 미리 정해져 있다. 헌법에 따라 퍼레이드 구역은 언제나 축에 평행한 직사각형 [ℓ,r]×[b,t][\ell, r] \times [b, t]이다. 집 좌표 (x,y)(x, y)가 ℓ≤x≤r\ell \le x \le r과 b≤y≤tb \le y \le t를 모두 만족하면, 그날 그 집에 사는 국민이 각각 달걀을 하나 던진다.

남은 임기 동안 받는 달걀의 총 개수를 구하라.

입력

첫 줄에 테스트 케이스의 개수 TT (1≤T≤201 \le T \le 20)가 주어진다.

각 테스트 케이스의 첫 줄에는 달걀을 던지는 국민 수 nn (0<n≤100000 < n \le 10000)과 남은 임기 일수 mm (0≤m≤500000 \le m \le 50000)이 공백으로 구분되어 주어진다.

다음 nn개 줄에는 집 한 채의 좌표 xx와 yy (0≤x,y≤1050 \le x, y \le 10^5)가 주어진다.

이어지는 mm개 줄에는 정수 ℓ\ell, rr, bb, tt (0≤ℓ≤r≤1050 \le \ell \le r \le 10^5, 0≤b≤t≤1050 \le b \le t \le 10^5)가 공백으로 구분되어 주어진다. 이 네 수는 그날의 퍼레이드 구역 [ℓ,r]×[b,t][\ell, r] \times [b, t]를 뜻한다.

출력

각 테스트 케이스마다 받는 달걀의 총 개수를 한 줄에 출력한다.

예제7

  1. 예제 1

    입력
    2
    3 1
    3 5
    2 3
    1 1
    1 2 1 3
    3 2
    5 3
    2 2
    1 1
    1 2 1 3
    2 5 2 3
    
    예상 출력
    2
    4
  2. 예제 2

    입력
    1
    1 0
    0 0
    
    예상 출력
    0
  3. 예제 3

    입력
    1
    5 3
    7 7
    7 7
    7 7
    0 0
    100000 100000
    0 100000 0 100000
    7 7 7 7
    8 9 8 9
    
    예상 출력
    8
  4. 예제 4

    입력
    1
    4 4
    0 0
    0 100000
    100000 0
    100000 100000
    0 100000 0 100000
    0 0 0 0
    100000 100000 100000 100000
    0 99999 0 99999
    
    예상 출력
    7
  5. 예제 5

    입력
    1
    6 5
    1 1
    1 1
    2 2
    3 3
    3 3
    3 3
    1 1 1 1
    2 2 2 2
    3 3 3 3
    1 3 1 3
    2 2 3 3
    
    예상 출력
    12
  6. 예제 6

    입력
    3
    1 1
    5 5
    5 5 5 5
    2 0
    0 0
    100000 100000
    4 3
    1 2
    2 1
    2 3
    3 2
    1 3 1 3
    2 2 1 3
    1 1 1 1
    
    예상 출력
    1
    0
    6
  7. 예제 7

    입력
    1
    3 3
    10 10
    20 20
    30 30
    0 9 0 9
    11 19 0 100000
    0 100000 31 100000
    
    예상 출력
    0