Half Heart | Canada Day Contest 2021

Half Heart Solution

Deruikong is a highly skilled Minecraft player. Just as he had finished his great wool masterpiece, nn black holes suddenly appeared and started destroying everything! Acting fast, Deruikong started collecting his blocks so that he could rebuild elsewhere. However, some of the blocks were already too close for him to collect without the risk of getting sucked in.

See Also : Canada Day Contest 2021

The safeness of any location (X,Y,Z)(X,Y,Z) is the minimum of max(X−xj,Y−Yj,Z−zj)max(X−xj,Y−Yj,Z−zj) over all black holes jj such that X≥xj,Y≥yj,Z≥zjX≥xj,Y≥yj,Z≥zj, or −1−1 if no such hole exists. With only 1 hp left, Deruikong needs you to calculate the safeness of each block’s location before everything is lost!

No 2 black holes are in the same location.

Input Specification

The first line contains two space-separated integers, nn and qq.

The next nn lines contain three integers each, xixi, yiyi, and zizi, the location of the iith black hole.

The next qq lines contain three integers each, XiXi, YiYi, and ZiZi, the location of the iith block.

Output Specification

Provide the safeness of each block.

Constraints

1≤n+q≤2000001≤n+q≤200000

0≤xi,yi,zi,Xi,Yi,Zi≤600000000≤xi,yi,zi,Xi,Yi,Zi≤60000000

Sample Input 1

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

Sample Output 1

0
3
4

Sample Input 2

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

Sample Output 2

1
2
2

Sample Input 3

10 20
46902718 25907663 2878588
55735284 12603537 17470826
15981164 4340213 30136790
12018166 54408596 4435091
51715241 17349849 9656981
31709224 5992219 3823640
42153581 36646304 20195084
18012024 544896 8847160
53763337 3122454 57847793
3107443 19744160 1555718
8841107 20692456 40306182
2041879 33969394 20142890
36288293 48250270 20094855
42248889 34199313 57466914
21423927 40904396 30821857
39819710 7106627 5551137
41214546 36964634 24167718
17588623 9552541 52684010
15446397 42049027 9722824
19557164 43110839 11030939
30170944 55585276 31039047
49995090 36365705 35810198
43633569 56772072 2969715
36995652 35410194 45776812
43642245 53215913 58119326
1526616 52807672 52655983
28271301 32195317 31621432
51009822 32275518 46385152
23370956 47063794 16904853
53692856 35595834 4179859

Sample Output 3

38750464
-1
33180850
29859100
29266139
8110486
30972415
22547220
22304867
23366679
26603956
31986558
40526126
31069981
37924242
-1
27855104
35028658
27319634
9688171

Leave a Comment