Truyền thuyết tết Trung Thu ở Nhật Bản kể rằng, loài thỏ vì không kiếm được thức ăn cho một gã ăn xin nên đã nguyện dâng hiến bản thân. Cảm động vì hành động của loài thỏ, gã ăn xin đã biến thành Nguyệt Ông, đưa loài thỏ lên cũng trăng sống với mình. Người Nhật tin rằng, mặt trăng có hình dạng lồi lõm vì loài thỏ ngọc hằng ngày vẫn giã nếp làm mochi ở đấy.

Sau khi nghe về sự tích tết Trung Thu ở Nhật Bản, Heo cảm thấy rất hứng thú với những con thỏ ngọc được kể trong truyện. Heo liền thử nhìn lên mặt trăng. Bất ngờ thay, Heo lại nhìn thấy ~n~ vị trí, được đánh số từ ~1~ đến ~n~. Có ~k~ con thỏ đang giã mochi, con thỏ thứ ~i~ đang giã ở vị trí ~p_{i}~ tại độ cao ~t_{i}~. Heo nhận thấy rằng, độ cao tổng thể tại vị trí ~i~ bất kì sẽ bằng ~\min(t_{j} + |p_{j} - i|)~ với mọi ~j~ từ ~1~ đến ~k~. Nhằm thỏa mãn sự hiếu kì của bản thân, Heo muốn biết độ cao tổng thể tại tất cả vị trí tử ~1~ đến ~n~. Đương nhiên, bạn sẽ là người làm công việc ấy (Vi con Heo nay no luoi vcl).

Input

Vào từ file văn bản BAI2.inp:

• Dòng đầu tiên gồm số nguyên dương ~T~ ~(T\leq2)~ ~-~ Số bộ test.
• Dòng đầu tiên của mỗi test gồm 2 số ~n,k~ ~(1\leq k \leq n \leq 10^{6},~ Tổng ~n~ của các test không vượt quá ~15\times10^{5})~ ~-~ Số vị trí và số con thỏ đang giã mochi.
• Dòng thứ 2 của mỗi test gồm ~k~ số ~p_{1},p_{2},...,p_{k}~ ~(1\leq p_{i}\leq n, p_{i} \neq p_{j}~ với mọi ~i\neq j)~ ~-~ Vị trí của con thỏ thứ ~i~.
• Dòng thứ 3 của mỗi test gồm ~k~ số ~t_{1},t_{2},...,t_{k}~ ~(1\leq t_{i}\leq 10^{9})~ ~-~ Độ cao của con thỏ thứ ~i~.

Output

Ghi ra file văn bản BAI2.out:

• Với mỗi bộ test, in ra ~1~ dòng chứa ~n~ số ~-~ Độ cao tổng thể tại vị trí ~1,2,...,n~.

Scoring

Example

Sample Input

2
5 1
3 
18 
10 4
9 5 10 6 
13 19 8 16 

Sample Output

20 19 18 19 20 
17 16 15 14 13 12 11 10 9 8 

Note

• Cấp số cộng là dãy số thỏa mãn sai khác giữa hai phần tử liên tiếp bất kì là hằng số. Ví dụ như dãy ~(2; 4; 6)~ hay ~(6; 9; 12; 15)~ là cấp số cộng, còn ~(1; 7; 7; 0; 1; 3)~ hay ~(4; 0; 7; 1; 7; 7)~ thì không.
• Cấp số nhân là dãy số thỏa mãn điều điện kể từ phần tử thứ 2 trở đi (nếu có), mỗi số hạng đều là tích của số hạng trước đó với một hằng số. Ví dụ dãy ~(2; 4; 8; 16)~ hay ~(7; 35; 175; 875)~ là cấp số nhân, còn ~(3; 8; 9; 1; 9; 5)~ hay ~(4; 1; 7; 5; 5; 2)~ thì không.