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 java.io.PrintWriter;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Random;
import java.util.StringTokenizer;

public class E {
    private static FastReader fr = new FastReader();
    private static PrintWriter out=new PrintWriter(System.out);
    private static Random random = new Random();

    public static void main(String[] args) throws IOException {
        StringBuilder sb = new StringBuilder();
        // code goes here
        int q = fr.nextInt();
        while (q-- > 0){
            int n = fr.nextInt();
            int k = fr.nextInt();
            long[] a = fr.nextLongArray(k);
            long[] t = fr.nextLongArray(k);
            Pair<Long, Long>[] pairs = new Pair[k];
            for(int i = 0; i < k; i++){
                pairs[i] = new Pair<>(a[i], t[i]);
            }
            Arrays.sort(pairs, new Comparator<Pair<Long, Long>>() {
                @Override
                public int compare(Pair<Long, Long> o1, Pair<Long, Long> o2) {
                    return (int) (o1.first - o2.first);
                }
            });
            long[] vals = new long[k];
            long[] val2 = new long[k];
            for(int i = 0; i < pairs.length; i++){
                vals[i] = pairs[i].second + pairs[i].first;
                val2[i] = pairs[i].second - pairs[i].first;
            }
            SegmentTree segmentTree = new SegmentTree(vals);
            SegmentTree s2 = new SegmentTree(val2);
            long[] ans = new long[n];
            for(int i = 0; i < n; i++){
                int lo = 0, hi = k - 1;
                int till = -1;
                while (lo <= hi){
                    int mid = lo + (hi - lo)/2;
                    if(pairs[mid].first > i){
                        hi = mid - 1;
                    } else {
                        till = mid;
                        lo = mid + 1;
                    }
                }
                // use segment tree and
                // add vals from 0 - till by -i
                // get min in that segment
                // add vals from till + 1 - n by i;
                // get min in that segment
                // pick min in all
                // revert changes made to vals array.
                long left = till >= 0 ? till + 1 : 0;
                long right = k - left;
                ans[i] = s2.queryMin(0, till) + ((i + 1));
                ans[i] = Math.min(ans[i], segmentTree.queryMin(till + 1, k - 1) - ((i + 1)));
            }

            for(int i = 0; i < n; i++){
                sb.append(ans[i]).append(" ");
            }
            sb.append("\n");
        }
        System.out.print(sb.toString());
    }

    static class SegmentTree {
        int size;
        private long[] max;
        private long[] min;
        private long[] sum;

        private long[] lazy;


        public SegmentTree(long[] array){
            size = array.length;
            max=new long[array.length*4];
            min=new long[array.length*4];
            sum=new long[array.length*4];
            lazy=new long[array.length*4];
            buildTree(array,1,0,size-1);
        }

        private void buildTree(long[] array, int position, int front, int end){
            //Basis case for returning the elements itself
            if(front==end){
                max[position]=array[front];
                min[position]=array[front];
                sum[position]=array[front];
                return;
            }
            //Building trees by dividing into two subtrees
            buildTree(array, position*2,front,(front+end)/2);
            buildTree(array, position*2+1,(front+end)/2+1,end);

            recalc(position,front,end);
        }

        private void recalc(int position, int front, int end) {
            max[position]=Math.max(getMax(position*2),getMax(position*2+1) );
            min[position]=Math.min(getMin(position*2), getMin(position*2+1));
            sum[position]=getSum(position*2,front,(front+end)/2)+getSum(position*2+1,(front+end)/2+1,end);
        }

        private long getMax(int position){
            return max[position]+lazy[position];
        }

        private long getMin(int position){
            return min[position]+lazy[position];
        }

        private long getSum(int position,int front,int end){
            return sum[position]+lazy[position]*(end-front+1);
        }

        public long queryMax(int queryFront, int queryEnd) {
            return queryMax(1,0,size-1,queryFront,queryEnd);
        }

        private long queryMax(int position,int front,int end, int queryFront, int queryEnd){
            //Case for entirely inclusive
            if(front>=queryFront&&queryEnd>=end){
                return getMax(position);
            }
            //Case for entirely exclusive
            if(end<queryFront||queryEnd<front){
                return Integer.MIN_VALUE;
            }
            propagate(position,front,end);
            long leftAns=queryMax(position*2,front,(front+end)/2,queryFront,queryEnd);
            long rightAns=queryMax(position*2+1,(front+end)/2+1,end,queryFront,queryEnd);
            return Math.max(leftAns, rightAns);
        }

        public long queryMin(int queryFront, int queryEnd) {
            return queryMin(1,0,size-1,queryFront,queryEnd);
        }

        private long queryMin(int position,int front,int end, int queryFront, int queryEnd){
            //Case for entirely inclusive
            if(front>=queryFront&&queryEnd>=end){
                return getMin(position);
            }
            //Case for entirely exclusive
            if(end<queryFront||queryEnd<front){
                return Integer.MAX_VALUE;
            }
            propagate(position,front,end);
            long leftAns=queryMin(position*2,front,(front+end)/2,queryFront,queryEnd);
            long rightAns=queryMin(position*2+1,(front+end)/2+1,end,queryFront,queryEnd);
            return Math.min(leftAns, rightAns);
        }
        public long querySum(int queryFront, int queryEnd) {
            return querySum(1,0,size-1,queryFront,queryEnd);
        }

        private long querySum(int position,int front,int end, int queryFront, int queryEnd){
            //Case for entirely inclusive
            if(front>=queryFront&&queryEnd>=end){
                return getSum(position,front,end);
            }
            //Case for entirely exclusive
            if(end<queryFront||queryEnd<front){
                return 0;
            }
            propagate(position,front,end);
            long leftAns=querySum(position*2,front,(front+end)/2,queryFront,queryEnd);
            long rightAns=querySum(position*2+1,(front+end)/2+1,end,queryFront,queryEnd);
            return leftAns+rightAns;
        }


        private void propagate(int position,int front, int end){
            lazy[position*2]+=lazy[position];
            lazy[position*2+1]+=lazy[position];
            max[position]=getMax(position);
            min[position]=getMin(position);
            sum[position]=getSum(position,front,end);
            lazy[position]=0;
            //Set the propagation to 0 so that it will not propagate the value again and again
        }

        public void update(int updateFront, int updateEnd, long value){
            update(1,0,size-1,updateFront,updateEnd,value);
        }

        private void update(int position, int front, int end, int updateFront,int updateEnd,long value){
            //Case for entirely inclusive
            if(front>=updateFront&&updateEnd>=end){
                lazy[position]+=value;
                return;
            }
            //Case for entirely exclusive
            if(end<updateFront||updateEnd<front){
                return;
            }
            propagate(position,front,end);
            update(position*2,front,(front+end)/2,updateFront,updateEnd,value);
            update(position*2+1,(front+end)/2+1,end,updateFront,updateEnd,value);
            recalc(position,front,end);
        }
    }

    static void ruffleSort(int[] a) {
        int n=a.length;//shuffle, then sort
        for (int i=0; i<n; i++) {
            int oi=random.nextInt(n), temp=a[oi];
            a[oi]=a[i]; a[i]=temp;
        }
        Arrays.sort(a);
    }

    static class FastReader{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer("");

        public String next() {
            while (!st.hasMoreTokens())
                try {
                    st=new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            return st.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public int[] nextIntArray(int n) {
            int[] a=new int[n];
            for (int i=0; i<n; i++) a[i]=nextInt();
            return a;
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public long[] nextLongArray(int n) {
            long[] a=new long[n];
            for (int i=0; i<n; i++) a[i]=nextLong();
            return a;
        }
    }

    static class Pair<A, B>{
        A first;
        B second;
        public Pair(A first, B second){
            this.first = first;
            this.second = second;
        }
    }

    static long mod(String num, long a)
    {
        // Initialize result
        long res = 0;

        // One by one process all digits of 'num'
        for (int i = 0; i < num.length(); i++)
            res = (res*10 +  num.charAt(i) - '0') %a;

        return res;
    }

    static long binomialCoeff(long n, long k, long MOD)
    {
        long res = 1;

        // Since C(n, k) = C(n, n-k)
        if (k > n - k)
            k = n - k;

        // Calculate value of
        // [n * (n-1) *---* (n-k+1)] / [k * (k-1) *----* 1]
        for (int i = 0; i < k; ++i) {
            res *= (n - i);
            res /= (i + 1);
            res %= MOD;
        }

        return res;
    }

    static long power(long x, long y, long p)
    {

        // Initialize result
        long res = 1;

        // Update x if it is more than or
        // equal to p
        x = x % p;

        while (y > 0) {

            // If y is odd, multiply x
            // with result
            if (y % 2 == 1)
                res = (res * x) % p;

            // y must be even now
            y = y >> 1; // y = y/2
            x = (x * x) % p;
        }

        return res;
    }

    // Returns n^(-1) mod p
    static long modInverse(long n, long p)
    {
        return power(n, p - 2, p);
    }

    // Returns nCr % p using Fermat's
    // little theorem.
    static long nCrModPFermat(int n, int r,
                              long p)
    {

        // Base case
        if (r == 0)
            return 1;

        // Fill factorial array so that we
        // can find all factorial of r, n
        // and n-r
        long[] fac = new long[n + 1];
        fac[0] = 1;

        for (int i = 1; i <= n; i++)
            fac[i] = fac[i - 1] * i % p;

        return (fac[n] * modInverse(fac[r], p)
                % p * modInverse(fac[n - r], p)
                % p)
                % p;
    }
}