E. Кондиционеры
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На клетчатой полоске длины $$$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$$$ равна минимуму среди температур кондиционеров, увеличенных на расстояние от кондиционера до клетки $$$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$$$ найдите температуру воздуха в ней.

Входные данные

В первой строке задано целое число $$$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$$$.

Выходные данные

Для каждого набора входных данных выведите через пробел $$$n$$$ целых чисел — температуры воздуха в клетках.

Пример
Входные данные
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
Выходные данные
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