Page Contents

*Fine Art Solution*

*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.

#### Constraints

1≤n,q≤1500001≤n,q≤150000

0≤xi,yi,zi,Xi,Yi,Zi≤1000≤xi,yi,zi,Xi,Yi,Zi≤100

No two wool types have the same color.

#### Input Specification

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.

#### Output Specification

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
```

**Hint**

There are only 1003=10000001003=1000000 possible colors.

**Hint**

Try converting the grid into a graph.

**Solution**

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.

Complexity: O(max(xi,yi,zi,Xi,Yi,Zi)3+q)