3D Points and Queries

Time limit7sMemory limit1024 MB

Summary

Count points inside axis-aligned 3D boxes, where each query's box coordinates are decoded by XOR with the running sum of previous answers.

Problem

You are given N points in three-dimensional space. Write a program that processes the following queries.

lx ly lz rx ry rz: Print the number of points contained in the rectangular box whose vertices include the points (lx, ly, lz) and (rx, ry, rz).

Every edge of the rectangular box is parallel to an axis, and the segment connecting (lx, ly, lz) and (rx, ry, rz) is a diagonal of the box.

The first line gives the number of points N and the number of queries Q, separated by a space. (1 ≤ N, Q ≤ 105)

The next N lines give the coordinates of each point as three integers x, y, z, separated by spaces. (0 ≤ x, y, z ≤ 109)

The next Q lines give six integers ai, bi, ci, di, ei, fi. (0 ≤ ai, bi, ci, di, ei, fi < 263)

For the i-th query, lx ly lz rx ry rz are determined as follows.

lx = (ai xor Si-1) mod (109 + 1)
ly = (bi xor Si-1) mod (109 + 1)
lz = (ci xor Si-1) mod (109 + 1)
rx = (di xor Si-1) mod (109 + 1)
ry = (ei xor Si-1) mod (109 + 1)
rz = (fi xor Si-1) mod (109 + 1)

Si = Si-1 + ansi, and S0 is 0.

Print the answer to each query on its own line, in order.

Example 1

Input

5 8
1 0 5
1 1 10
5 1 10
0 10 5
2 10 0
0 0 3 5 5 8
0 0 2 6 5 6
1 1 0 2 4 11
2 2 6 7 9 4
2 3 1 0 9 4
5 4 0 14 5 14
6 6 2 1 2 14
6 7 3 15 5 0

Expected output