Problem: The Human-Cow Confederation (HC2), led by Heidi, has built a base where people and cows can hide, guarded from zombie attacks. The entrance to the base is protected by an automated gate which performs a kind of a Turing test: it shows the entering creature a photograph and asks them whether the top and bottom halves of this photograph have been swapped or not. A person (or even a cow) will have no problem answering such questions; on the other hand, a zombie would just randomly smash one of the two buttons.

The creature is asked a series of such questions. If at least 75% of them are answered correctly, the gate is unlocked; otherwise, a side door opens, beneath which a huge fan is spinning...

Heidi is now building a robot army to fight the zombies, and she wants the robots to also be able to enter the base. You are tasked with programming them to distinguish the images.

<image>

The first two images from the test set. The first picture has been rearranged, but not the second.

Input

The first line of the input contains the number q of questions (1 ≤ q ≤ 220). After that, q questions follow, each of which in the format described below.

The first line of every question contains two space-separated integers h and w (1 ≤ h, w ≤ 600) – the height (number of rows) and width (number of columns) of the photograph. (Most photographs are roughly 200 × 300.) After this, h lines follow, each describing a single row of the picture. The picture is monochrome (in shades of grey). Its i-th row is described by w space-separated integers aij (j = 1, ..., w), where aij is the brightness of the corresponding pixel (0 ≤ aij < 256, where 0 is black and 255 is white).

Each picture will be either a real-life photograph, or a real-life photograph which has been broken up into two pieces and rearranged. More precisely, in the latter case, the topmost <image> rows have been moved to the bottom of the picture. It is guaranteed that h is even.

There is only a single input file to be processed, called all.in, and it is downloadable from the online judge. You are also a given another input file, called sample.in, which contains the first 20 pictures from all.in; you are provided the correct answers for sample.in in sample.out. You are also given a directory easy_bmp, which contains the first 50 input photographs in the form of .bmp image files, as well as a directory easy_sample_original_bmp, which contains the first 20 images before rearrangement. Check the notes for the download links.

Output

Your program should print q lines. The i-th line should contain your answer for the i-th question: YES if the photograph has been rearranged and NO otherwise. Your answers will be accepted if they all conform to this format and if at least 75% of them are correct.

Because the input is rather huge, feel free to process it locally and submit just your precomputed answers (i.e., a program which just prints your output for the input file all.in).

Note

The link to download all necessary files is http://assets.codeforces.com/files/690/easy_contestant_package.zip

Solution (in JAVA):

Solution:
import java.io.*;
import java.math.*;
import java.util.*;
import java.util.stream.*;

@SuppressWarnings("unchecked")
public class P690E1 {

  int h, w;
  double [][] p;

  double diff(double [] a, double [] b) {
    double d = 0;
    for (int i = 0; i < w; i++) {
      d += Math.abs(a[i] - b[i]);
    }
    return (d / w);
  }

  double sko(int r) {
    double x = 0;
    for (int i = 0; i < w; i++) {
      x += p[r][i];
    }
    x /= w;

    double sko = 0;
    for (int i = 0; i < w; i++) {
      sko = (p[r][i] - x) * (p[r][i] - x);
    }

    return Math.sqrt(sko / w);
  }

  public void run() throws Exception {
    for (int q = nextInt(); q > 0; q--) {
      h = nextInt();
      w = nextInt();
      
      p = new double [h][w];
      for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
          p[i][j] = nextDouble() / 1;//256;
        }
      }

//Arrays.stream(p).forEach(this::println);        
//      for (int i = 1; i < h; i++) println(i + "\t" + diff(p[i - 1], p[i]));
//      println(diff(p[h / 2 - 2], p[h / 2 - 1]) + "\t" + diff(p[h / 2 - 1], p[h / 2]) + "\t" + diff(p[h / 2], p[h / 2 + 1]) + "\t" + diff(p[h / 2 + 1], p[h / 2 + 2]));
//      println(((diff(p[0], p[h / 2 + 1]) / diff(p[h / 2], p[h / 2 + 1])) > 10) ? "YES" : "NO");
//println(sko(0) + "\t" + sko(h / 2) + "\t" + sko(h / 2 + 1) + "\t" + sko(h - 1));
      double d1 = diff(p[h / 2 - 1], p[h / 2]), d2 = diff(p[h / 2], p[h / 2 + 1]);
//      println(d1 + "\t" + d2 + "\t" + Math.max(d1, d2) / Math.min(d1, d2));
      println(((Math.max(d1, d2) / Math.min(d1, d2)) > 4) ? "YES" : "NO");
//break;
    }
  }
  
  public static void main(String... args) throws Exception {
    br = new BufferedReader(new InputStreamReader(System.in));
    pw = new PrintWriter(new BufferedOutputStream(System.out));
    new P690E1().run();
    br.close();
    pw.close();
    System.err.println("\n[Time : " + (System.currentTimeMillis() - startTime) + " ms]");
  }
  
  static long startTime = System.currentTimeMillis();
  static BufferedReader br;
  static PrintWriter pw;
  StringTokenizer stok;

  String nextToken() throws IOException {
    while (stok == null || !stok.hasMoreTokens()) {
      String s = br.readLine();
      if (s == null) { return null; }
      stok = new StringTokenizer(s);
    }
    return stok.nextToken();
  }

  void print(byte b) { print("" + b); }
  void print(int i) { print("" + i); }
  void print(long l) { print("" + l); }
  void print(double d) { print("" + d); }
  void print(char c) { print("" + c); }
  void print(Object o) {
    if (o instanceof int[]) { print(Arrays.toString((int [])o));
    } else if (o instanceof long[]) { print(Arrays.toString((long [])o));
    } else if (o instanceof char[]) { print(Arrays.toString((char [])o));
    } else if (o instanceof byte[]) { print(Arrays.toString((byte [])o));
    } else if (o instanceof short[]) { print(Arrays.toString((short [])o));
    } else if (o instanceof boolean[]) { print(Arrays.toString((boolean [])o));
    } else if (o instanceof float[]) { print(Arrays.toString((float [])o));
    } else if (o instanceof double[]) { print(Arrays.toString((double [])o));
    } else if (o instanceof Object[]) { print(Arrays.toString((Object [])o));
    } else { print("" + o); }
  }
  void print(String s) { pw.print(s); }
  void println() { println(""); }
  void println(byte b) { println("" + b); }
  void println(int i) { println("" + i); }
  void println(long l) { println("" + l); }
  void println(double d) { println("" + d); }
  void println(char c) { println("" + c); }
  void println(Object o) { print(o); println(); }
  void println(String s) { pw.println(s); }
  int nextInt() throws IOException { return Integer.parseInt(nextToken()); }
  long nextLong() throws IOException { return Long.parseLong(nextToken()); }
  double nextDouble() throws IOException { return Double.parseDouble(nextToken()); }
  char nextChar() throws IOException { return (char) (br.read()); }
  String next() throws IOException { return nextToken(); }
  String nextLine() throws IOException { return br.readLine(); }
  int [] readInt(int size) throws IOException {
    int [] array = new int [size];
    for (int i = 0; i < size; i++) { array[i] = nextInt(); }
    return array;
  }
  long [] readLong(int size) throws IOException {
    long [] array = new long [size];
    for (int i = 0; i < size; i++) { array[i] = nextLong(); }
    return array;
  }
  double [] readDouble(int size) throws IOException {
    double [] array = new double [size];
    for (int i = 0; i < size; i++) { array[i] = nextDouble(); }
    return array;
  }
  String [] readLines(int size) throws IOException {
    String [] array = new String [size];
    for (int i = 0; i < size; i++) { array[i] = nextLine(); }
    return array;
  }

  int gcd(int a, int b) {
    return ((b > 0) ? gcd(b, a % b) : a);
  }
}