CF1547E.Air Conditioners

On a strip of land of length $n$ there are $k$ air conditioners: the $i$-th air conditioner is placed in cell $a_i$ ($1 \le a_i \le n$). Two or more air conditioners cannot be placed in the same cell (i.e. all $a_i$ are distinct).

Each air conditioner is characterized by one parameter: temperature. The $i$-th air conditioner is set to the temperature $t_i$.

Example of strip of length $n=6$, where $k=2$, $a=[2,5]$ and $t=[14,16]$.

For each cell $i$ ($1 \le i \le n$) find it's temperature, that can be calculated by the formula $$\min_{1 \le j \le k}(t_j + |a_j - i|),$$

where $|a_j - i|$ denotes absolute value of the difference $a_j - i$.

In other words, the temperature in cell $i$ is equal to the minimum among the temperatures of air conditioners, increased by the distance from it to the cell $i$.

Let's look at an example. Consider that $n=6, k=2$, the first air conditioner is placed in cell $a_1=2$ and is set to the temperature $t_1=14$ and the second air conditioner is placed in cell $a_2=5$ and is set to the temperature $t_2=16$. In that case temperatures in cells are:

1. temperature in cell $1$ is: $\min(14 + |2 - 1|, 16 + |5 - 1|)=\min(14 + 1, 16 + 4)=\min(15, 20)=15$;
2. temperature in cell $2$ is: $\min(14 + |2 - 2|, 16 + |5 - 2|)=\min(14 + 0, 16 + 3)=\min(14, 19)=14$;
3. temperature in cell $3$ is: $\min(14 + |2 - 3|, 16 + |5 - 3|)=\min(14 + 1, 16 + 2)=\min(15, 18)=15$;
4. temperature in cell $4$ is: $\min(14 + |2 - 4|, 16 + |5 - 4|)=\min(14 + 2, 16 + 1)=\min(16, 17)=16$;
5. temperature in cell $5$ is: $\min(14 + |2 - 5|, 16 + |5 - 5|)=\min(14 + 3, 16 + 0)=\min(17, 16)=16$;
6. temperature in cell $6$ is: $\min(14 + |2 - 6|, 16 + |5 - 6|)=\min(14 + 4, 16 + 1)=\min(18, 17)=17$.

For each cell from $1$ to $n$ find the temperature in it.

在一条长度为 $n$ 的土地上，有 $k$ 台空调：第 $i$ 台空调位于位置 $a_i$（$1 \le a_i \le n$）。两台或更多空调不能放置在同一位置（即所有 $a_i$ 互不相同）。

每台空调有一个参数：温度。第 $i$ 台空调设定的温度为 $t_i$。

长度为 $n=6$ 的土地示例，其中 $k=2$，$a=[2,5]$，$t=[14,16]$。

对每个位置 $i$（$1 \le i \le n$），其温度由如下公式计算：

$$\min_{1 \le j \le k}(t_j + |a_j - i|),$$

其中 $|a_j - i|$ 表示差值 $a_j - i$ 的绝对值。

换言之，位置 $i$ 的温度等于所有空调温度 $t_j$ 加上其到位置 $i$ 的距离 $|a_j - i|$ 后所得值中的最小值。

我们来看一个例子。设 $n=6$，$k=2$，第一台空调位于位置 $a_1=2$、温度 $t_1=14$，第二台空调位于位置 $a_2=5$、温度 $t_2=16$。此时各位置的温度为：

1. 位置 $1$ 的温度为：$\min(14 + |2 - 1|, 16 + |5 - 1|)=\min(14 + 1, 16 + 4)=\min(15, 20)=15$；
2. 位置 $2$ 的温度为：$\min(14 + |2 - 2|, 16 + |5 - 2|)=\min(14 + 0, 16 + 3)=\min(14, 19)=14$；
3. 位置 $3$ 的温度为：$\min(14 + |2 - 3|, 16 + |5 - 3|)=\min(14 + 1, 16 + 2)=\min(15, 18)=15$；
4. 位置 $4$ 的温度为：$\min(14 + |2 - 4|, 16 + |5 - 4|)=\min(14 + 2, 16 + 1)=\min(16, 17)=16$；
5. 位置 $5$ 的温度为：$\min(14 + |2 - 5|, 16 + |5 - 5|)=\min(14 + 3, 16 + 0)=\min(17, 16)=16$；
6. 位置 $6$ 的温度为：$\min(14 + |2 - 6|, 16 + |5 - 6|)=\min(14 + 4, 16 + 1)=\min(18, 17)=17$。

请对从 $1$ 到 $n$ 的每个位置，求出其对应的温度。

The first line contains one integer $q$ ($1 \le q \le 10^4$) — 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 $n$ ($1 \le n \le 3 \cdot 10^5$) and $k$ ($1 \le k \le n$) — the length of the strip of land and the number of air conditioners respectively.

The second line contains $k$ integers $a_1, a_2, \ldots, a_k$ ($1 \le a_i \le n$) — positions of air conditioners on the strip of land.

The third line contains $k$ integers $t_1, t_2, \ldots, t_k$ ($1 \le t_i \le 10^9$) — temperatures of air conditioners.

It is guaranteed that the sum of $n$ over all test cases does not exceed $3 \cdot 10^5$.

第一行包含一个整数 $q$（$1 \le q \le 10^4$）—— 输入中测试用例的数量。随后是各测试用例。每个测试用例之前有一空行。

每个测试用例包含三行。第一行包含两个整数 $n$（$1 \le n \le 3 \cdot 10^5$）和 $k$（$1 \le k \le n$）—— 分别表示土地条带的长度和空调的数量。

第二行包含 $k$ 个整数 $a_1, a_2, \ldots, a_k$（$1 \le a_i \le n$）—— 表示空调在土地条带上的位置。

第三行包含 $k$ 个整数 $t_1, t_2, \ldots, t_k$（$1 \le t_i \le 10^9$）—— 表示各空调的温度。

保证所有测试用例中 $n$ 的总和不超过 $3 \cdot 10^5$。

For each test case output $n$ integers separated by space: temperatures of air in cells.

对于每个测试用例，输出 $n$ 个由空格分隔的整数：各单元格中的空气温度。