시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 168 59 33 48.529%

문제

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)

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

출력

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

예제 입력 1

4 5
2 0 5 8
0 1 6 3
1 2 4 5
3 4 7 7
2 3 4 5
4 0 6 6
0 3 2 5
1 0 5 3
6 1 7 4

예제 출력 1

3
2
1
3
0

색종이가 놓여진 영역은 문제에서 예시를 들고 있는 그림과 같다.

첫 번째 쿼리의 경우 (3, 4, 4, 5)에는 세 장의 색종이가 겹쳐져 있으며 나머지 영역에는 두 장의 색종이가 겹쳐져 있다.

그러므로 (2, 3, 4, 5)에서 가장 많이 겹쳐 있는 영역에 놓여 있는 색종이의 장 수는 세 장이므로 3을 출력한다.