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 JAVA):

Solution:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

import static java.lang.Math.*;
import static java.lang.System.out;
import static java.lang.System.setProperty;

import java.util.*;
import java.io.*;
import java.math.*;
public class A {

    static int checkr(int[] a,int k){
        int n = a.length;
        int l=1,r=n;
        int ans=Integer.MAX_VALUE;
        while (l <= r) {
            int mid = (l+r)/2;
            if(mid>=n)break;
            if(a[mid]>k){
                ans = Math.min(ans,a[mid]);
                r=mid-1;
            }
            else l=mid+1;
        }
      if(ans==Integer.MAX_VALUE)return -1;
      return ans;
    }
    static int checkl(int[] a,int k) {
        int n = a.length;
        int l=1,r=n;
        int ans=-1;
        while (l <= r) {
            int mid = (l+r)/2;
            if(mid>=n)break;
            if(a[mid]<k){
                ans = Math.max(ans,a[mid]);
                l=mid+1;
            }
            else  r=mid-1;;
        }
        if(ans==-1)return -1;
        return ans;
    }
    public static void main(String hi[]) throws Exception
    {
        FastScanner s = new FastScanner();
        int T = s.nextInt();
//        int T=1;
        while(T-->0)
        {
            int n = s.nextInt();
            int k =s.nextInt();
            int[] a = new int[k+1];
            long[] t = new long[n+1];
            Arrays.fill(t,Integer.MAX_VALUE);
            for(int i=1;i<=k;i++){
                a[i] = s.nextInt();
            }
            for(int i=1;i<=k;i++){
                t[a[i]] = s.nextLong();
            }
            sort(a);
            long[] pre=t.clone();
            long[] suf = t.clone();
            for(int i=2;i<=n;i++) {
                pre[i] = min(pre[i],pre[i-1]+1);
            }
            for(int i=n-1;i>=1;i--) {
                suf[i] = min(suf[i],suf[i+1]+1);
            }
            StringBuilder se = new StringBuilder("");
            for(int i=1;i<=n;i++){
                se.append(min(pre[i],suf[i])+" ");
            }
            out.println(se);
        }
        //BufferedReader infile = new BufferedReader(new FileReader("input.txt"));
        //System.setOut(new PrintStream(new File("output.txt")));
    }

    //input shenanigans
      /*
         Random stuff to try when stuck:
            -in case for TLE in optimised solution use stringBuilder
            -for combo/probability problems, expand the given form we're interested in
            -make everything the same then build an answer (constructive, make everything 0 then do something)
            -something appears in parts of 2 --> model as graph
            -assume a greedy then try to show why it works
            -find way to simplify into one variable if multiple exist
            -treat it like fmc (note any passing thoughts/algo that could be used so you can revisit them)
            -find lower and upper bounds on answer
            -figure out what ur trying to find and isolate it
            -see what observations you have and come up with more continuations
            -work backwards (in constructive, go from the goal to the start)
            -turn into prefix/suffix sum argument (often works if problem revolves around adjacent array elements)
            -instead of solving for answer, try solving for complement (ex, find n-(min) instead of max)
            -draw something
            -simulate a process
            -dont implement something unless if ur fairly confident its correct
            -after 3 bad submissions move on to next problem if applicable
            -do something instead of nothing and stay organized
            -write stuff down
         Random stuff to check when wa:
            -if code is way too long/cancer then reassess
            -switched N/M
            -int overflow
            -switched variables
            -wrong MOD
            -hardcoded edge case incorrectly
         Random stuff to check when tle:
            -continue instead of break
            -condition in for/while loop bad
         Random stuff to check when rte:
            -switched N/M
            -long to int/int overflow
            -division by 0
            -edge case for empty list/data structure/N=1
      */
    public static int[] readArr(int N, BufferedReader infile, StringTokenizer st) throws Exception
    {
        int[] arr = new int[N];
        st = new StringTokenizer(infile.readLine());
        for(int i=0; i < N; i++)
            arr[i] = Integer.parseInt(st.nextToken());
        return arr;
    }
    public static long[] readArr2(int N, BufferedReader infile, StringTokenizer st) throws Exception
    {
        long[] arr = new long[N];
        st = new StringTokenizer(infile.readLine());
        for(int i=0; i < N; i++)
            arr[i] = Long.parseLong(st.nextToken());
        return arr;
    }
    public static void print(int[] arr)
    {
        //for debugging only
        for(int x: arr)
            out.print(x+" ");
        out.println();
    }
    static long gcd(long a, long b)throws IOException{return (b==0)?a:gcd(b,a%b);}
    static int gcd(int a, int b)throws IOException{return (b==0)?a:gcd(b,a%b);}
    public static boolean isPrime(long n)
    {
        if(n < 2) return false;
        if(n == 2 || n == 3) return true;
        if(n%2 == 0 || n%3 == 0) return false;
        long sqrtN = (long)Math.sqrt(n)+1;
        for(long i = 6L; i <= sqrtN; i += 6) {
            if(n%(i-1) == 0 || n%(i+1) == 0) return false;
        }
        return true;
    }
    static void sortr(int[] a) {
        ArrayList<Integer> l=new ArrayList<>();
        for (int i:a) l.add(i);
        Collections.sort(l,Collections.reverseOrder());
        for (int i=0; i<a.length; i++) a[i]=l.get(i);
    }
    static void sort(int[] a) {
        ArrayList<Integer> l=new ArrayList<>();
        for (int i:a) l.add(i);
        Collections.sort(l);
        for (int i=0; i<a.length; i++) a[i]=l.get(i);
    }
    static void sort(long[] a) {
        ArrayList<Long> l=new ArrayList<>();
        for (long i:a) l.add(i);
        Collections.sort(l);
        for (int i=0; i<a.length; i++) a[i]=l.get(i);
    }
    public static long power(long x, long y, long p)
    {
        //0^0 = 1
        long res = 1L;
        x = x%p;
        while(y > 0)
        {
            if((y&1)==1)
                res = (res*x)%p;
            y >>= 1;
            x = (x*x)%p;
        }
        return res;
    }
    static class FastScanner
    {
        //I don't understand how this works lmao
        private int BS = 1 << 16;
        private char NC = (char) 0;
        private byte[] buf = new byte[BS];
        private int bId = 0, size = 0;
        private char c = NC;
        private double cnt = 1;
        private BufferedInputStream in;

        public FastScanner() {
            in = new BufferedInputStream(System.in, BS);
        }

        public FastScanner(String s) {
            try {
                in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
            } catch (Exception e) {
                in = new BufferedInputStream(System.in, BS);
            }
        }

        private char getChar() {
            while (bId == size) {
                try {
                    size = in.read(buf);
                } catch (Exception e) {
                    return NC;
                }
                if (size == -1) return NC;
                bId = 0;
            }
            return (char) buf[bId++];
        }

        public int nextInt() {
            return (int) nextLong();
        }

        public int[] nextInts(int N) {
            int[] res = new int[N];
            for (int i = 0; i < N; i++) {
                res[i] = (int) nextLong();
            }
            return res;
        }

        public long[] nextLongs(int N) {
            long[] res = new long[N];
            for (int i = 0; i < N; i++) {
                res[i] = nextLong();
            }
            return res;
        }

        public long nextLong() {
            cnt = 1;
            boolean neg = false;
            if (c == NC) c = getChar();
            for (; (c < '0' || c > '9'); c = getChar()) {
                if (c == '-') neg = true;
            }
            long res = 0;
            for (; c >= '0' && c <= '9'; c = getChar()) {
                res = (res << 3) + (res << 1) + c - '0';
                cnt *= 10;
            }
            return neg ? -res : res;
        }

        public double nextDouble() {
            double cur = nextLong();
            return c != '.' ? cur : cur + nextLong() / cnt;
        }

        public double[] nextDoubles(int N) {
            double[] res = new double[N];
            for (int i = 0; i < N; i++) {
                res[i] = nextDouble();
            }
            return res;
        }

        public String next() {
            StringBuilder res = new StringBuilder();
            while (c <= 32) c = getChar();
            while (c > 32) {
                res.append(c);
                c = getChar();
            }
            return res.toString();
        }

        public String nextLine() {
            StringBuilder res = new StringBuilder();
            while (c <= 32) c = getChar();
            while (c != '\n') {
                res.append(c);
                c = getChar();
            }
            return res.toString();
        }

        public boolean hasNext() {
            if (c > 32) return true;
            while (true) {
                c = getChar();
                if (c == NC) return false;
                else if (c > 32) return true;
            }
        }
    }
}