{"trustable":false,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eOn a strip of a hotel corridor of length $$$n$$$ there are $$$k$$$ heaters: the $$$i$$$-th heater is placed in cell $$$a_i$$$ ($$$1 \\le a_i \\le n$$$). Two or more heaters cannot be placed in the same cell (i.e. all $$$a_i$$$ are distinct).\u003c/p\u003e\n\u003cp\u003eEach heater is characterized by one parameter: temperature. The $$$i$$$-th heater is set to the temperature $$$t_i$$$.\u003c/p\u003e\n\u003ccenter\u003e \n\n \nExample of strip of length $$$n\u003d6$$$, where $$$k\u003d2$$$, $$$a\u003d[2,5]$$$ and $$$t\u003d[16,14]$$$.\u003c/span\u003e \n\u003c/center\u003e\n\u003cp\u003eFor each cell $$$i$$$ ($$$1 \\le i \\le n$$$) find it\u0027s temperature, that can be calculated by the formula $$$$$$\\min_{1 \\le j \\le k}(t_j + |a_j - i|),$$$$$$\u003c/p\u003e\n\u003cp\u003ewhere $$$|a_j - i|$$$ denotes absolute value of the difference $$$a_j - i$$$.\u003c/p\u003e\n\u003cp\u003eIn other words, the temperature in cell $$$i$$$ is equal to the minimum among the temperatures of heaters, increased by the distance from it to the cell $$$i$$$.\u003c/p\u003e\n\u003cp\u003eLet\u0027s look at an example. Consider that $$$n\u003d6, k\u003d2$$$, the first heater is placed in cell $$$a_1\u003d2$$$ and is set to the temperature $$$t_1\u003d16$$$ and the second heater is placed in cell $$$a_2\u003d5$$$ and is set to the temperature $$$t_2\u003d14$$$. In that case temperatures in cells are:\u003c/p\u003e\n\u003col\u003e \n \u003cli\u003e temperature in cell $$$1$$$ is: $$$\\min(16 + |2 - 1|, 14 + |5 - 1|)\u003d\\min(16 + 1, 14 + 4)\u003d\\min(17, 18)\u003d17$$$; \u003c/li\u003e\n \u003cli\u003e temperature in cell $$$2$$$ is: $$$\\min(16 + |2 - 2|, 14 + |5 - 2|)\u003d\\min(16 + 0, 14 + 3)\u003d\\min(16, 17)\u003d16$$$; \u003c/li\u003e\n \u003cli\u003e temperature in cell $$$3$$$ is: $$$\\min(16 + |2 - 3|, 14 + |5 - 3|)\u003d\\min(16 + 1, 14 + 2)\u003d\\min(17, 16)\u003d16$$$; \u003c/li\u003e\n \u003cli\u003e temperature in cell $$$4$$$ is: $$$\\min(16 + |2 - 4|, 14 + |5 - 4|)\u003d\\min(16 + 2, 14 + 1)\u003d\\min(18, 15)\u003d15$$$; \u003c/li\u003e\n \u003cli\u003e temperature in cell $$$5$$$ is: $$$\\min(16 + |2 - 5|, 14 + |5 - 5|)\u003d\\min(16 + 3, 14 + 0)\u003d\\min(19, 14)\u003d14$$$; \u003c/li\u003e\n \u003cli\u003e temperature in cell $$$6$$$ is: $$$\\min(16 + |2 - 6|, 14 + |5 - 6|)\u003d\\min(16 + 4, 14 + 1)\u003d\\min(20, 15)\u003d15$$$. \u003c/li\u003e\n\u003c/ol\u003e\n\u003cp\u003eFor each cell from $$$1$$$ to $$$n$$$ find the temperature in it.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains one integer $$$q$$$ ($$$1 \\le q \\le 10^4$$$)\u0026nbsp;— the number of test cases in the input. Then test cases follow. Before each test case, there is an empty line.\u003c/p\u003e\n\u003cp\u003eEach 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$$$)\u0026nbsp;— the length of the strip of land and the number of heaters respectively.\u003c/p\u003e\n\u003cp\u003eThe second line contains $$$k$$$ integers $$$a_1, a_2, \\ldots, a_k$$$ ($$$1 \\le a_i \\le n$$$)\u0026nbsp;— positions of heaters on the strip of land.\u003c/p\u003e\n\u003cp\u003eThe third line contains $$$k$$$ integers $$$t_1, t_2, \\ldots, t_k$$$ ($$$1 \\le t_i \\le 10^9$$$)\u0026nbsp;— temperatures of heaters.\u003c/p\u003e\n\u003cp\u003eIt is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$3 \\cdot 10^5$$$.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eFor each test case output $$$n$$$ integers separated by space: temperatures of air in cells.\u003c/p\u003e"}},{"title":"Example","value":{"format":"HTML","content":"\u003cdiv class\u003d\"sample-test\"\u003e\n \u003cdiv class\u003d\"input\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Input\n \u003c/div\u003e\n \u003cpre\u003e5\n\n6 2\n2 5\n16 14\n\n10 1\n7\n30\n\n5 5\n3 1 4 2 5\n3 1 4 2 5\n\n7 1\n1\n1000000000\n\n6 3\n6 1 3\n5 5 5\n\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"output\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Output\n \u003c/div\u003e\n \u003cpre\u003e17 16 16 15 14 15 \n36 35 34 33 32 31 30 31 32 33 \n1 2 3 4 5 \n1000000000 1000000001 1000000002 1000000003 1000000004 1000000005 1000000006 \n5 6 5 6 6 5 \n\u003c/pre\u003e\n \u003c/div\u003e\n\u003c/div\u003e"}}]}