На клетчатой полоске длины \(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\)-й клетке равна: \(\min(14 + |2 - 1|, 16 + |5 - 1|)=\min(14 + 1, 16 + 4)=\min(15, 20)=15\);
- температура во \(2\)-й клетке равна: \(\min(14 + |2 - 2|, 16 + |5 - 2|)=\min(14 + 0, 16 + 3)=\min(14, 19)=14\);
- температура в \(3\)-й клетке равна: \(\min(14 + |2 - 3|, 16 + |5 - 3|)=\min(14 + 1, 16 + 2)=\min(15, 18)=15\);
- температура в \(4\)-й клетке равна: \(\min(14 + |2 - 4|, 16 + |5 - 4|)=\min(14 + 2, 16 + 1)=\min(16, 17)=16\);
- температура в \(5\)-й клетке равна: \(\min(14 + |2 - 5|, 16 + |5 - 5|)=\min(14 + 3, 16 + 0)=\min(17, 16)=16\);
- температура в \(6\)-й клетке равна: \(\min(14 + |2 - 6|, 16 + |5 - 6|)=\min(14 + 4, 16 + 1)=\min(18, 17)=17\).
Для каждой клетки от \(1\) до \(n\) найдите температуру воздуха в ней.