Problem: On a strip of land of length n there are k air conditioners: the i-th air conditioner is placed in cell a_i (1 ≤ a_i ≤ n). Two or more air conditioners cannot be placed in the same cell (i.e. all a_i are distinct).

Each air conditioner is characterized by one parameter: temperature. The i-th air conditioner is set to the temperature t_i.

<image> Example of strip of length n=6, where k=2, a=[2,5] and t=[14,16].

For each cell i (1 ≤ i ≤ n) find it's temperature, that can be calculated by the formula $$$min_{1 ≤ j ≤ k}(t_j + |a_j - i|),$$$

where |a_j - i| denotes absolute value of the difference a_j - i.

In other words, the temperature in cell i is equal to the minimum among the temperatures of air conditioners, increased by the distance from it to the cell i.

Let's look at an example. Consider that n=6, k=2, the first air conditioner is placed in cell a_1=2 and is set to the temperature t_1=14 and the second air conditioner is placed in cell a_2=5 and is set to the temperature t_2=16. In that case temperatures in cells are:

  1. temperature in cell 1 is: min(14 + |2 - 1|, 16 + |5 - 1|)=min(14 + 1, 16 + 4)=min(15, 20)=15; 
  2. temperature in cell 2 is: min(14 + |2 - 2|, 16 + |5 - 2|)=min(14 + 0, 16 + 3)=min(14, 19)=14; 
  3. temperature in cell 3 is: min(14 + |2 - 3|, 16 + |5 - 3|)=min(14 + 1, 16 + 2)=min(15, 18)=15; 
  4. temperature in cell 4 is: min(14 + |2 - 4|, 16 + |5 - 4|)=min(14 + 2, 16 + 1)=min(16, 17)=16; 
  5. temperature in cell 5 is: min(14 + |2 - 5|, 16 + |5 - 5|)=min(14 + 3, 16 + 0)=min(17, 16)=16; 
  6. temperature in cell 6 is: min(14 + |2 - 6|, 16 + |5 - 6|)=min(14 + 4, 16 + 1)=min(18, 17)=17. 



For each cell from 1 to n find the temperature in it.

Input

The first line contains one integer q (1 ≤ q ≤ 10^4) — the number of test cases in the input. Then test cases follow. Before each test case, there is an empty line.

Each test case contains three lines. The first line contains two integers n (1 ≤ n ≤ 3 ⋅ 10^5) and k (1 ≤ k ≤ n) — the length of the strip of land and the number of air conditioners respectively.

The second line contains k integers a_1, a_2, …, a_k (1 ≤ a_i ≤ n) — positions of air conditioners on the strip of land.

The third line contains k integers t_1, t_2, …, t_k (1 ≤ t_i ≤ 10^9) — temperatures of air conditioners.

It is guaranteed that the sum of n over all test cases does not exceed 3 ⋅ 10^5.

Output

For each test case output n integers separated by space: temperatures of air in cells.

Example

Input


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


Output


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 

Solution (in PYTHON3):

Solution:
from __future__ import division, print_function

import os,sys
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip

from bisect import bisect_left as lower_bound, bisect_right as upper_bound 
def so():  return int(input())
def st():  return input()
def mj():  return map(int,input().strip().split(" "))
def msj(): return map(str,input().strip().split(" "))
def le():  return list(map(int,input().split()))
def lebe():return list(map(int, input()))

def dmain():
    sys.setrecursionlimit(1000000)
    threading.stack_size(1024000)
    thread = threading.Thread(target=main)
    thread.start()
def joro(L):
    return(''.join(map(str, L)))
def cheems(c,d):
    a=1
    while(d!=0):
        if(d%2==1):
            a*=c
        c=c*c
        d=d//2
    return a

        

def decimalToBinary(n): return bin(n).replace("0b","")


def isprime(n):
    for i in range(2,int(n**0.5)+1):
        if n%i==0:
            return False
    return True
def npr(n, r):
    return factorial(n) // factorial(n - r) if n >= r else 0
 
 
def ncr(n, r):
    return factorial(n) // (factorial(r) * factorial(n - r)) if n >= r else 0
 
 
def lower_bound(li, num):
    answer = -1
    start = 0
    end = len(li) - 1
 
    while (start <= end):
        middle = (end + start) // 2
        if li[middle] >= num:
            answer = middle
            end = middle - 1
        else:
            start = middle + 1
    return answer  # min index where x is not less than num
 
 
def upper_bound(li, num):
    answer = -1
    start = 0
    end = len(li) - 1
 
    while (start <= end):
        middle = (end + start) // 2
 
        if li[middle] <= num:
            answer = middle
            start = middle + 1
 
        else:
            end = middle - 1
    return answer  # max index where x is not greater than num
def tir(a,b,c):
    if(0==c):
        return 1
    if(len(a)<=b):
        return 0
    
    if(c!=-1):
        return (tir(a,1+b,c+a[b]) or tir(a,b+1,c-a[b]) or tir(a,1+b,c)) 
        
        
    else:
        return (tir(a,1+b,a[b]) or tir(a,b+1,-a[b]) or tir(a,1+b,-1))
        
 
def abs(x):
    return x if x >= 0 else -x
 
 
def binary_search(li, val, lb, ub):
    # print(lb, ub, li)
    ans = -1
    while (lb <= ub):
        mid = (lb + ub) // 2
        # print('mid is',mid, li[mid])
        if li[mid] > val:
            ub = mid - 1
        elif val > li[mid]:
            lb = mid + 1
        else:
            ans = mid  # return index
            break
    return ans
 
 
def kadane(x):  # maximum sum contiguous subarray
    sum_so_far = 0
    current_sum = 0
    for i in x:
        current_sum += i
        if current_sum < 0:
            current_sum = 0
        else:
            sum_so_far = max(sum_so_far, current_sum)
    return sum_so_far
def wubu(m):
    import math as my
    d=0
    while(not m%2):
        m=m//2
        d=1+d
    for i in range(3,int(my.sqrt(m))+1,2):
        while(not m%i):
            m=m//i
            d=1+d
    return int(m>1)+d
 
def pref(li):
    pref_sum = [0]
    for i in li:
        pref_sum.append(pref_sum[-1] + i)
    return pref_sum
 
 
def SieveOfEratosthenes(n):
    prime = [True for i in range(n + 1)]
    p = 2
    li = []
    while (p * p <= n):
        if (prime[p] == True):
            for i in range(p * p, n + 1, p):
                prime[i] = False
        p += 1
 
    for p in range(2, len(prime)):
        if prime[p]:
            li.append(p)
    return li
 
 
def primefactors(n):
    factors = []
    while (n % 2 == 0):
        factors.append(2)
        n //= 2
    for i in range(3, int(sqrt(n)) + 1, 2):  # only odd factors left
        while n % i == 0:
            factors.append(i)
            n //= i
    if n > 2:  # incase of prime
        factors.append(n)
    return factors
         
    
def read():
    sys.stdin  = open('input.txt', 'r')  
    sys.stdout = open('output.txt', 'w') 
def tr(n):
    return n*(n+1)//2

def bro(q,r,c):
    bec,pot,h=0,0,0
    ds=[]
    bs=[]
    es=[]
    for i in range(c):
        while(h<len(r) and r[h]<=q[i][0]):
            pot=0
            ds.clear()
            bs.clear()
            h=1+h
    for i in range(c):
        ds.append(q[i][1])
        es.append(q[i][1])
    ds=list(set(ds))
    
    for i in ds:
        bs.append(es.count(i))
    
    print(bs)
    for i in range(c):
        if(q[i][0]>r[h-1]):
            bec=bec+pot-bs[i]
            pot=1+pot
            
            
    return bec
        
            
            
            
        
    
def iu():
    import sys
    input = sys.stdin.readline
    import math as my
    import bisect as op
    c=0
    t=st()
    m,q=mj()
    L=le()
    M=le()
    bec=[sys.maxsize]*m
    for i in range(q):
        bec[L[i]-1]=M[i]
    r=1
    while(r<m):
        bec[r]=min(bec[r],1+bec[r-1])
        r=1+r
    op=m-2
    while(op>=0):
        bec[op]=min(bec[op],1+bec[1+op])
        op=op-1
    print(*bec)
        
    
    
        
    
    
    
    
        
        
        
            
        
            
def main():
    for i in range(so()):
        iu()
    
    
                
        
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
            
    
    
        
    

        
    
    

        
    
    
    
    
    
    
    
    
    
    

    

    
        
        
            
    
    
                
            
                
                
                
                
            
    
            
            
    
    
    
    
        
            
    
           
            
            
        
    
        
    
    
        
        
        

            
                    
                
                    
                    
                    
                    
                    
                    
        
                
        
        
       
    
           
          
          
                
            
        
                
    
        
        
        
       
            
                
        




# region fastio
# template taken from https://github.com/cheran-senthil/PyRival/blob/master/templates/template.py

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion


if __name__ == "__main__":
    #read()
    main()
    #dmain()

# Comment Read()