Canada Day Contest 2021 - Fine Art

View as PDF

Submit solution


Points: 7
Time limit: 2.0s
Python 3.0s
Memory limit: 768M

Author:
Problem type

Deruikong is a highly skilled artist. He wants to build a sculpture out of wool in Minecraft. He has n types of wool, the ith of which is of colour (x_i,y_i,z_i) (x_i\% red, y_i\% green, z_i\% blue using the RGB colour model). His build contains q pixels, the ith of which is of colour (X_i,Y_i,Z_i). Help Deruikong choose a good substitute for each pixel i by finding the wool j that minimizes |X_i-x_j|+|Y_i-y_j|+|Z_i-z_j|. If there are multiple solutions, output the smallest value of j.

Input Specification

The first line will contain two space-separated integers, n and q.

The next n lines contain three space-separated integers, x_i, y_i, and z_i for 1 \le i \le n.

The next q lines contain three space-separated integers, X_i, Y_i, and Z_i for 1 \le i \le q.

Output Specification

For each pixel, output the lowest index of the closest substitute.

Constraints

1 \le n, q \le 150\,000

0 \le x_i, y_i, z_i, X_i, Y_i, Z_i \le 100

No two wool types have the same colour.

Sample Input 1

2 3
0 0 0
0 0 5
0 0 0
0 0 3
0 0 4

Sample Output 1

1
2
2

Sample Input 2

2 3
3 3 3
1 1 1
2 2 2
1 2 3
3 2 1

Sample Output 2

1
1
1

Comments

There are no comments at the moment.