{"trustable":true,"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\u003eTrên một dải đất dài $$$n$$$ có $$$k$$$ máy điều hòa: máy điều hòa thứ $$$i$$$ được đặt trong ô $$$a_i$$$ ($$$1 \\le a_i \\le n$$$). Hai hoặc nhiều máy điều hòa không thể được đặt trong cùng một ô (tức là tất cả các $$$a_i$$$ đều phải khác nhau).\u003c/p\u003e\u003cp\u003eMỗi máy điều hòa được đặc trưng bởi một tham số: nhiệt độ. Máy điều hòa thứ $$$i$$$ được đặt với nhiệt độ là $$$t_i$$$.\u003c/p\u003e\u003ccenter\u003e \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/950bc089b1b5c73deb78987d38b04bc0?v\u003d1708220576\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e \u003cspan class\u003d\"tex-font-size-small\"\u003eVí dụ về dải đất dài $$$n\u003d6$$$, với $$$k\u003d2$$$, $$$a\u003d[2,5]$$$ và $$$t\u003d[14,16]$$$.\u003c/span\u003e \u003c/center\u003e\u003cp\u003eĐối với mỗi ô $$$i$$$ ($$$1 \\le i \\le n$$$) hãy tìm nhiệt độ của nó, có thể tính bằng công thức $$$$$$\\min_{1 \\le j \\le k}(t_j + |a_j - i|),$$$$$$\u003c/p\u003e\u003cp\u003etrong đó $$$|a_j - i|$$$ biểu thị giá trị tuyệt đối của sự khác biệt $$$a_j - i$$$.\u003c/p\u003e\u003cp\u003eNói cách khác, nhiệt độ trong ô $$$i$$$ bằng với nhiệt độ tối thiểu giữa các máy điều hòa, cộng thêm khoảng cách từ đó đến ô $$$i$$$.\u003c/p\u003e\u003cp\u003eHãy xem một ví dụ. Giả sử rằng $$$n\u003d6, k\u003d2$$$, máy điều hòa đầu tiên được đặt trong ô $$$a_1\u003d2$$$ và được đặt với nhiệt độ là $$$t_1\u003d14$$$ và máy điều hòa thứ hai được đặt trong ô $$$a_2\u003d5$$$ và được đặt với nhiệt độ là $$$t_2\u003d16$$$. Trong trường hợp đó, nhiệt độ trong các ô là:\u003c/p\u003e\u003col\u003e \u003cli\u003e nhiệt độ trong ô $$$1$$$ là: $$$\\min(14 + |2 - 1|, 16 + |5 - 1|)\u003d\\min(14 + 1, 16 + 4)\u003d\\min(15, 20)\u003d15$$$; \u003c/li\u003e\u003cli\u003e nhiệt độ trong ô $$$2$$$ là: $$$\\min(14 + |2 - 2|, 16 + |5 - 2|)\u003d\\min(14 + 0, 16 + 3)\u003d\\min(14, 19)\u003d14$$$; \u003c/li\u003e\u003cli\u003e nhiệt độ trong ô $$$3$$$ là: $$$\\min(14 + |2 - 3|, 16 + |5 - 3|)\u003d\\min(14 + 1, 16 + 2)\u003d\\min(15, 18)\u003d15$$$; \u003c/li\u003e\u003cli\u003e nhiệt độ trong ô $$$4$$$ là: $$$\\min(14 + |2 - 4|, 16 + |5 - 4|)\u003d\\min(14 + 2, 16 + 1)\u003d\\min(16, 17)\u003d16$$$; \u003c/li\u003e\u003cli\u003e nhiệt độ trong ô $$$5$$$ là: $$$\\min(14 + |2 - 5|, 16 + |5 - 5|)\u003d\\min(14 + 3, 16 + 0)\u003d\\min(17, 16)\u003d16$$$; \u003c/li\u003e\u003cli\u003e nhiệt độ trong ô $$$6$$$ là: $$$\\min(14 + |2 - 6|, 16 + |5 - 6|)\u003d\\min(14 + 4, 16 + 1)\u003d\\min(18, 17)\u003d17$$$. \u003c/li\u003e\u003c/ol\u003e\u003cp\u003eĐối với mỗi ô từ $$$1$$$ đến $$$n$$$ hãy tìm nhiệt độ trong đó.\u003c/p\u003e"}},{"title":"Nhập","value":{"format":"HTML","content":"\u003cp\u003eDòng đầu tiên chứa một số nguyên $$$q$$$ ($$$1 \\le q \\le 10^4$$$)\u0026nbsp;— số lượng bài kiểm tra trong đầu vào. Sau đó là các bài kiểm tra. Trước mỗi bài kiểm tra, có một dòng trống.\u003c/p\u003e\u003cp\u003eMỗi bài kiểm tra chứa ba dòng. Dòng đầu tiên chứa hai số nguyên $$$n$$$ ($$$1 \\le n \\le 3 \\cdot 10^5$$$) và $$$k$$$ ($$$1 \\le k \\le n$$$)\u0026nbsp;— độ dài của dải đất và số lượng máy điều hòa tương ứng.\u003c/p\u003e\u003cp\u003eDòng thứ hai chứa $$$k$$$ số nguyên $$$a_1, a_2, \\ldots, a_k$$$ ($$$1 \\le a_i \\le n$$$)\u0026nbsp;— vị trí của các máy điều hòa trên dải đất.\u003c/p\u003e\u003cp\u003eDòng thứ ba chứa $$$k$$$ số nguyên $$$t_1, t_2, \\ldots, t_k$$$ ($$$1 \\le t_i \\le 10^9$$$)\u0026nbsp;— nhiệt độ của các máy điều hòa.\u003c/p\u003e\u003cp\u003eĐảm bảo rằng tổng của $$$n$$$ trên tất cả các bài kiểm tra không vượt quá $$$3 \\cdot 10^5$$$.\u003c/p\u003e"}},{"title":"Đầu ra","value":{"format":"HTML","content":"\u003cp\u003eĐối với mỗi bài kiểm tra, xuất $$$n$$$ số nguyên cách nhau bởi dấu cách: nhiệt độ của không khí trong các ô.\u003c/p\u003e"}},{"title":"Ví dụ 1","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5\n\n6 2\n2 5\n14 16\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\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e15 14 15 16 16 17 \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\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}