2184: Air Conditioners (1547E)
Description
On a strip of land of length nn there are kk air conditioners: the ii-th air conditioner is placed in cell aiai (1≤ai≤n1≤ai≤n). Two or more air conditioners cannot be placed in the same cell (i.e. all aiai are distinct).
Each air conditioner is characterized by one parameter: temperature. The ii-th air conditioner is set to the temperature titi.
Example of strip of length n=6n=6, where k=2k=2, a=[2,5]a=[2,5] and t=[14,16]t=[14,16].
For each cell ii (1≤i≤n1≤i≤n) find it's temperature, that can be calculated by the formula
where |aj−i||aj−i| denotes absolute value of the difference aj−iaj−i.
In other words, the temperature in cell ii is equal to the minimum among the temperatures of air conditioners, increased by the distance from it to the cell ii.
Let's look at an example. Consider that n=6,k=2n=6,k=2, the first air conditioner is placed in cell a1=2a1=2 and is set to the temperature t1=14t1=14 and the second air conditioner is placed in cell a2=5a2=5 and is set to the temperature t2=16t2=16. In that case temperatures in cells are:
- temperature in cell 11 is: min(14+|2−1|,16+|5−1|)=min(14+1,16+4)=min(15,20)=15min(14+|2−1|,16+|5−1|)=min(14+1,16+4)=min(15,20)=15;
- temperature in cell 22 is: min(14+|2−2|,16+|5−2|)=min(14+0,16+3)=min(14,19)=14min(14+|2−2|,16+|5−2|)=min(14+0,16+3)=min(14,19)=14;
- temperature in cell 33 is: min(14+|2−3|,16+|5−3|)=min(14+1,16+2)=min(15,18)=15min(14+|2−3|,16+|5−3|)=min(14+1,16+2)=min(15,18)=15;
- temperature in cell 44 is: min(14+|2−4|,16+|5−4|)=min(14+2,16+1)=min(16,17)=16min(14+|2−4|,16+|5−4|)=min(14+2,16+1)=min(16,17)=16;
- temperature in cell 55 is: min(14+|2−5|,16+|5−5|)=min(14+3,16+0)=min(17,16)=16min(14+|2−5|,16+|5−5|)=min(14+3,16+0)=min(17,16)=16;
- temperature in cell 66 is: min(14+|2−6|,16+|5−6|)=min(14+4,16+1)=min(18,17)=17min(14+|2−6|,16+|5−6|)=min(14+4,16+1)=min(18,17)=17.
For each cell from 11 to nn find the temperature in it.
The first line contains one integer qq (1≤q≤1041≤q≤104) — the number of test cases in the input. Then test cases follow. Before each test case, there is an empty line.
Each test case contains three lines. The first line contains two integers nn (1≤n≤3⋅1051≤n≤3⋅105) and kk (1≤k≤n1≤k≤n) — the length of the strip of land and the number of air conditioners respectively.
The second line contains kk integers a1,a2,…,aka1,a2,…,ak (1≤ai≤n1≤ai≤n) — positions of air conditioners on the strip of land.
The third line contains kk integers t1,t2,…,tkt1,t2,…,tk (1≤ti≤1091≤ti≤109) — temperatures of air conditioners.
It is guaranteed that the sum of nn over all test cases does not exceed 3⋅1053⋅105.
For each test case output nn integers separated by space: temperatures of air in cells.
Sample Input Copy
5
6 2
2 5
14 16
10 1
7
30
5 5
3 1 4 2 5
3 1 4 2 5
7 1
1
1000000000
6 3
6 1 3
5 5 5
Sample Output Copy
15 14 15 16 16 17
36 35 34 33 32 31 30 31 32 33
1 2 3 4 5
1000000000 1000000001 1000000002 1000000003 1000000004 1000000005 1000000006
5 6 5 6 6 5