Another Birthday Present! CodeChef SHUFFLE

Another Birthday Present! Problem Code: SHUFFLE

Chef got another sequence as a birthday present. He does not like this sequence very much because it is not sorted. Since you are a good programmer, Chef is asking for your help.

You are given a sequence A1,A2,…,AN$A_1,A_2,\dots ,A_N$ and an integer K$K$. You may perform any number of operations of the following type (in any order): choose a valid integer i$i$ and swap Ai$A_i$ with Ai+K$A_{i+K}$. Can you sort the sequence this way?

Input

• The first line of the input contains a single integer T$T$ denoting the number of test cases. The description of T$T$ test cases follows.
• The first line of each test case contains two space-separated integers N$N$ and K$K$.
• The second line contains N$N$ space-separated integers A1,A2,…,AN$A_1,A_2,\dots ,A_N$.

Output

For each test case, print a single line containing the string "yes" if the sequence can be sorted or "no" otherwise (without quotes).

Constraints

• 1≤T≤100$1\le T\le 100$
• 1≤K≤N≤105$1\le K\le N\le {10}^5$
• 1≤Ai≤109$1\le A_i\le {10}^9$ for each valid i$i$
• the sum of N$N$ over all test cases does not exceed 106${10}^6$

Subtasks

Subtask #1 (50 points): the sequence A$A$ is a permutation of the integers 1$1$ through N$N$

Subtask #2 (50 points): original constraints

Example Input

2
4 1
1 4 2 3
4 2
1 4 2 3

Example Output

yes
no

Explanation

Example case 1: We may freely swap adjacent elements, so the sequence can be sorted e.g. in the following way: (1,4,2,3)→(1,2,4,3)→(1,2,3,4)$(1,4,2,3)\to (1,2,4,3)\to (1,2,3,4)$.



CODE:



code<SHUFFLE>


import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
 public static void main (String[] args) throws java.lang.Exception
 {
  // your code goes here
  
  Scanner sc=new Scanner(System.in);
  int T=sc.nextInt();
  
  for(int z=0;z<T;z++)
  { int flag=1;
   int N=sc.nextInt();
   int K=sc.nextInt();
   int arr[]=new int[N];
   for(int i=0;i<N;i++)
    arr[i]=sc.nextInt();
  
   for(int i=0;i<N-K;i++)
   {   
    
   for(int j=i+K;j<N;j+=K)
   {   
     
          if(arr[i]>arr[j])
       { 
      
     int l=arr[i];
       arr[i]=arr[j];
     arr[j]=l;   
    }
         
   }   
     
   }
    
   //int flag=0;
   
   for(int i=0;i<N-1;i++)
   {
    if(arr[i]>arr[i+1])
     {flag=0;break;}
    
   }
   if(flag==1)
    System.out.println("yes");
   else
    System.out.println("no");
   /*for(int i=0;i<N;i++)
   System.out.print(arr[i]+" ");
   */
   }
}

}