MRECT1 - Point on the side of the rectangle

 

 

English Vietnamese

 

The government is planning to build a walkway for tourists in the middle of an oak forest. The forest can be represented as plane with N special lattice points representing oaks. The walkway is represented as a rectangle with sides parallel to the axes. If the sides of walkway rectangle intersect any oak lattice points, such oaks need to be axed down.

Oaks inside the rectangle do not represent problems and need not be cut down. Ljubo is the state secretary of Forestry and an passionate nature lover, so he ordered the secretary of Tourism to provide him with a list of P possible rectangle walkways that are attractive enough to draw in tourists.

Ljubo plans to select the walkway that needs the smallest amount of oak trees to be cut down.

Since we also like trees, would you be so kind and write a program that will determine the number of oaks that will be cut down for each walkway. Remember only the oaks intersecting the sides of the rectangle need to be cut.

Input

The first line of input contains one integer N (1 ≤ N ≤ 300 000), number of oaks.

The next N lines contain two integers each Xi Yi (1 ≤ X, Y ≤ 10^9) coordinates of oaks. There will be at most one oak on each lattice point.

The next line contains one integer P (1 ≤ P ≤ 100 000), number of walkways.

The next P lines contain four integers each X1, Y1, X2, Y2 (1 ≤ X1 < X2 ≤ 10^9, 1 ≤ Y1 < Y2 ≤ 10^9), the coordinates of the lower left (X1, Y1) and upper right (X2, Y2) corner of the rectangle.

Output

Output P integers, one per line, the number of oaks that need to be cut down for each walkway in the order they are presented in the input.

Sample

Input:
6
1 2
3 2
2 3
2 5
4 4
6 3
4
2 2 4 4
2 2 6 5
3 3 5 6
5 1 6 6

Output:
3
4
0
1


Được gửi lên bởi:psetter
Ngày:2010-05-24
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: GOSU NODEJS OBJC PERL6 PYPY RUST SED SQLITE VB.NET
Nguồn bài:COI 2010

hide comments
2018-07-12 17:05:16
1 đấm ac
2017-06-21 22:23:23
n.log(n) TLE -_-
2014-06-11 12:25:07 Chuyên Nhật CNN
9 cái tìm kiếm nhị phân trong 1 bài ;-; feeling so noob
2010-06-14 13:23:14 Hy Trường Sơn
@~!(*(@*!@^&: Em cam on anh ^^
2010-05-29 17:09:44 ~!(*(@*!@^&
@Son: Dung scanf, ko cin.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.