E. Triangle Pick
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

There are $$$n$$$ triangle slices in the 3-dimensional space. Determine which triangle will a given ray intersect with first. The ray begins at $$$(0,0,0)$$$ and its direction is given by each query.

Input

The first line contains two integers $$$n, m$$$ $$$(1 \leq n \leq 1000, 1 \leq m \leq 10000)$$$, describing the number of triangle slices, and the number of queries.

Each of the next $$$n$$$ lines contains nine integers $$$x_1,y_1,z_1,x_2,y_2,z_2,x_3,y_3,z_3$$$, indicating the vertex coordinates of the triangle slice, which are $$$(x_1,y_1,z_1)$$$, $$$(x_2,y_2,z_2)$$$, $$$(x_3,y_3,z_3)$$$ respectively. It is guaranteed that all coordinates will not exceed $$$\pm 10000$$$.

Each of the next $$$m$$$ lines contains three integers $$$x,y,z$$$, indicating the direction vector of the ray. It is guaranteed that $$$x,y,z$$$ will not exceed $$$\pm 10000$$$.

Output

For each query, print the serial number of the first intersected slice (numbered in the order in the input, starting from $$$1$$$). If the ray did not intersect with any of the slices, print $$$0$$$.

Examples
Input
1 3
1 1 0 -1 1 0 0 0 2
0 1 1
0 -1 1
1 0 0
Output
1
0
0
Input
2 3
1 1 0 1 -1 0 0 0 1
3 0 0 0 3 0 0 0 3
2 -1 2
-1 -1 -1
1 3 1
Output
1
0
2
Note

The slices are solid, and will not intersect with each other. The ray will not go through anywhere near the border of a slice, causing precision issues.