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 (xi,yi,zi) (xi% red, yi% green, zi% blue using the RGB colour model). His build contains q pixels, the ith of which is of colour (Xi,Yi,Zi). Help Deruikong choose a good substitute for each pixel i by finding the wool j that minimizes |Xixj|+|Yiyj|+|Zizj|. 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, xi, yi, and zi for 1in.

The next q lines contain three space-separated integers, Xi, Yi, and Zi for 1iq.

Output Specification

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

Constraints

1n,q150000

0xi,yi,zi,Xi,Yi,Zi100

No two wool types have the same colour.

Sample Input 1

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

Sample Output 1

Copy
1
2
2

Sample Input 2

Copy
2 3
3 3 3
1 1 1
2 2 2
1 2 3
3 2 1

Sample Output 2

Copy
1
1
1

Comments

There are no comments at the moment.