시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 | 512 MB | 129 | 16 | 15 | 24.590% |
A pasture in the wild west can be represented as a rectangular grid embedded in the upper-right quadrant of a standard coordinate system. A herd of n buffalos is scattered throughout the grid, each occupying a unit square. Buffalos are numbered 1 through n; buffalo j is located in the unit square whose upper-right corner is the point with integer coordinates (xj, yj). The coordinate axes represent two rivers meeting at the origin, restricting buffalo movement downwards and leftwards.
A total of m settlers arrive, one by one, and each claims a piece of land using the following procedure:
For each settler, find the total number of buffalos he claimed when he arrived.
The first line contains an integer n (1 ≤ n ≤ 300 000) — the number of buffalos. The j-th of the following n lines contains two integers xj and yj (1 ≤ xj, yj ≤ 109) — the location of the j-th buffalo. No two buffalos will share the same location.
The following line contains an integer m (1 ≤ m ≤ 300 000) — the number of settlers. The j-th of the following m lines contains two integers x'j and y'j (1 ≤ x'j , y'j ≤ 109) — the coordinates of the fence post installed by the j-th settler. All x'j are different and all y'j are different.
Output m lines. The j-th line should contain the number of buffalos claimed by the j-th settler upon arrival.
7 1 1 4 2 6 2 5 3 2 5 4 7 7 5 4 4 4 8 2 9 6 6 5
2 1 3 2