17960번 - 3차원 점과 쿼리

3차원 평면에 찍힌 N개의 점이 주어질 때 다음 쿼리를 처리하는 프로그램을 작성하시오

• l_x l_y l_z r_x r_y r_z : 점 (l_x, l_y, l_z)과 점 (r_x, r_y, r_z)을 꼭짓점으로 하는 직육면체 영역에 포함된 점의 갯수를 출력한다.

직육면체의 모든 모서리는 축에 평행하며 주어지는 (l_x, l_y, l_z)와 (r_x, r_y, r_z)를 연결한 선은 이 직육면체의 대각선이다

첫 번째 줄에 점의 수 N과 쿼리의 수 Q가 공백으로 구분하여 주어진다. (1 ≤ N, Q ≤ 10⁵)

다음 N개의 줄에 걸쳐 점의 좌표를 의미하는 세 정수 x, y, z가 공백으로 구분하여 주어진다. (0 ≤ x, y, z ≤ 10⁹)

다음 Q개의 줄에 걸쳐 6개의 정수 a_i, b_i, c_i, d_i, e_i, f_i가 주어진다. (0 ≤ a_i, b_i, c_i, d_i, e_i, f_i < 2⁶³)

i번째 쿼리의 l_x l_y l_z r_x r_y r_z는 다음과 같다.

• l_x = (a_i xor S_i-1) mod (10⁹ + 1)
• l_y = (b_i xor S_i-1) mod (10⁹ + 1)
• l_z = (c_i xor S_i-1) mod (10⁹ + 1)
• r_x = (d_i xor S_i-1) mod (10⁹ + 1)
• r_y = (e_i xor S_i-1) mod (10⁹ + 1)
• r_z = (f_i xor S_i-1) mod (10⁹ + 1)

S_i = S_i-1 + ans_i 이며 S₀는 0이다.

Q개의 줄에 각 쿼리의 정답을 순서대로 출력한다.