import java.util.*;
import java.util.zip.*;
import java.util.List;
import java.util.regex.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.*;
import java.util.concurrent.locks.*;
import javax.swing.*;
import javax.swing.event.*;
import javax.swing.text.*;
import javax.swing.table.*;
import java.io.*;
import java.net.*;
import java.lang.reflect.*;
import java.lang.ref.*;
import java.lang.management.*;
import java.security.*;
import java.security.spec.*;
import java.awt.*;
import java.awt.event.*;
import java.awt.image.*;
import javax.imageio.*;
import java.math.*;
class main {

static int[] cloneArray(int[] a) {
  if (a == null) return null;
  int[] b = new int[a.length];
  System.arraycopy(a, 0, b, 0, a.length);
  return b;
}

static boolean[] cloneArray(boolean[] a) {
  if (a == null) return null;
  boolean[] b = new boolean[a.length];
  System.arraycopy(a, 0, b, 0, a.length);
  return b;
}

static short[] cloneArray(short[] a) {
  if (a == null) return null;
  short[] b = new short[a.length];
  System.arraycopy(a, 0, b, 0, a.length);
  return b;
}

static <A> A[] cloneArray(A[] a) {
  if (a == null) return null;
  A[] b = arrayOfSameType(a, a.length);
  System.arraycopy(a, 0, b, 0, a.length);
  return b;
}
static <A> A[] arrayOfSameType(A[] a, int n) {
  return newObjectArrayOfSameType(a, n);
}




static <A> A[] newObjectArrayOfSameType(A[] a) { return newObjectArrayOfSameType(a, a.length); }
static <A> A[] newObjectArrayOfSameType(A[] a, int n) {
  return (A[]) Array.newInstance(a.getClass().getComponentType(), n);
}



}