18246번 - 색종이와 쿼리

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차원 좌표평면에 놓여진 경우의 예시이다.

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

• y₁ x₁ y₂ x₂ : (y₁, x_1, y₂, x₂)에서 색종이가 가장 많이 겹쳐 있는 영역에 놓여 있는 색종이의 장 수를 출력한다.

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

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

다음 M개의 줄에는 쿼리 y₁, x₁, y₂, x₂가 한 줄에 하나씩 주어진다. (0 ≤ y₁ < y₂ ≤ 1,500, 0 ≤ x₁ < x₂ ≤ 1,500)

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

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