Points In Cuboid

Time Limit: 10000/5000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

Problem Description

There are n points in a three-dimensional space.

Your mission is to find out how many points in a given cuboid.

You should notice that the given cuboid is always parallel to xoy, xoz and yoz.

As a result, the cuboid "ABCDEFGH" will be denoted by it's diagonal "AG".

Input

There are multiple cases.

For each case:

The first line contains an integer n, denoting the number of points.

Each of the next n lines contains 3 integers x, y, z, denoting the coordinates of point.

The a line contains an integer m, denoting the number of queries.

Each of the next m lines contains 6 integers x1, y1, z1, x2, y2, z2, denoting a cuboid.

1 ≤ n, m ≤ 50000

-5000 ≤ x, y, z ≤ 5000

-10000 ≤ x1, y1, z1, x2, y2, z2 ≤ 10000

-1000 ≤ x2-x1, y2-y1, z2-z1 ≤ 1000

You can assume that the number of points in a cuboid is always less that 1000.

Output

For each test case, we need to output one line containing "Case #x:", and then output all results in the next m lines.

Sample Input

9
0 3 -2
2 3 2
-1 -2 -1
2 1 2
-2 0 3
0 0 2
-2 -2 2
-1 1 0
3 0 0
2
-1 -2 -2 -15 -8 8
0 -1 0 -14 -7 -10

Sample Output

Case #1:
2
1

Source

KIDx

Manager

Information
Solved Number45
Submit Number147
Problem Tags
data structures
divide and conquer
No tag edit access
温馨提示:AC后可以编辑标签哦. ^-^
Login
LoginCancel