cho.sh

색종이와 쿼리

축에 평행한 직사각형 N개와 질의 직사각형 M개가 주어질 때, 각 질의 영역 안에서 어떤 한 점을 덮는 색종이 수의 최댓값을 구한다.

어려움8세그먼트 트리누적 합정렬시뮬레이션아직 제출이 없습니다시간 제한1초메모리 제한512 MB

문제

2차원 좌표평면상에 각 변이 좌표축과 평행한 직사각형 모양의 색종이 N장이 있다.

(y1, x1, y2, x2)를 (y1, x1)은 직사각형의 왼쪽 아래 좌표, (y2, x2)은 직사각형의 오른쪽 위 좌표를 뜻하는 직사각형의 내부 영역이라 정의한다.

아래는 (2, 0, 5, 8), (0, 1, 6, 3), (1, 2, 4, 5), (3, 4, 7, 7)에 각각 한 장씩, 총 네 장의 색종이가 2차원 좌표평면에 놓여진 경우의 예시이다.


 

이때, 다음 쿼리를 수행하는 프로그램을 작성하시오.

  • y1 x1 y2 x2 : (y1, x1, y2, x2)에서 색종이가 가장 많이 겹쳐 있는 영역에 놓여 있는 색종이의 장 수를 출력한다.

입력

첫째 줄에 색종이의 장수 N과 쿼리의 개수 M이 주어진다. (1 ≤ N, M ≤ 100,000)

다음 N개의 줄에는 색종이가 놓여진 영역 (y1, x1, y2, x2)가 한 줄에 하나씩 주어진다. (0 ≤ y1 < y2 ≤ 1,500, 0 ≤ x1 < x2 ≤ 1,500)

다음 M개의 줄에는 쿼리 y1, x1, y2, x2가 한 줄에 하나씩 주어진다. (0 ≤ y1 < y2 ≤ 1,500, 0 ≤ x1 < x2 ≤ 1,500)

주어지는 좌표는 모두 정수이다.

출력

각각의 쿼리를 수행한 결과를 한 줄에 하나씩 출력한다.