Fine Art Solution
Deruikong is a highly skilled artist. He wants to build a scuplture out of wool in Minecraft. He has nn types of wool, the iith of which is of color (xi,yi,zi) xi,yi,zi) (xi%xi% red, yi%yi% green, zi%zi% blue using the RGB color model).
See Also : Canada Day Contest 2021
His build contains qq pixels, the iith of which is of color (Xi,Yi,Zi)(Xi,Yi,Zi). Help Deruikong choose a good substitute for each pixel ii by finding the wool jj that minimizes |Xi−xj|+|Yi−yj|+|Zi−zj||Xi−xj|+|Yi−yj|+|Zi−zj|. If there are multiple solutions, output the smallest value of jj.
No two wool types have the same color.
The first line will contain two space-separated integers, nn and qq.
The next nn lines contain three space-separated integers, xixi, yiyi, and zizi for 1≤i≤n1≤i≤n.
The next qq lines contain three space-separated integers, XiXi, YiYi, and ZiZi for 1≤i≤q1≤i≤q.
For each pixel, output the lowest index of the closest substitute.
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
There are only 1003=10000001003=1000000 possible colors.
Try converting the grid into a graph.
Perform a multisource breadth first search from each of the paints to find the closest paint for every possible color. Now the answer to each query has been calculated.