/*
 * USACOTOOLS-Official version
 * This is the official version.
 * 
 */
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;
import java.util.*;
import java.util.regex.*;
public abstract class utools {
	public static final String ANSI_RESET = "\u001B[0m";
	public static final String ANSI_BLACK = "\u001B[30m";
	public static final String ANSI_RED = "\u001B[31m";
	public static final String ANSI_GREEN = "\u001B[32m";
	public static final String ANSI_YELLOW = "\u001B[33m";
	public static final String ANSI_BLUE = "\u001B[34m";
	public static final String ANSI_PURPLE = "\u001B[35m";
	public static final String ANSI_CYAN = "\u001B[36m";
	public static final String ANSI_WHITE = "\u001B[37m";
	public static int ERRORS=0;
	public static ArrayList console=new ArrayList();
	public static String error="Error";
	public static int debugcode=-1;
	public static boolean DEBUG=false;
	public static boolean lock;
	public static boolean IO=true;
	public static void blockio() {
		IO=false;
	}
	public static boolean isrect(int[][] map,int x,int y) {
		int cachedsize=-1;
		int cachey=-1;
		for(int i=x;icachedsize) {
				return false;
			}
			for(int j=y;jcachey) {
					return false;
				}
			}
		}
		return true;
	}
	public static Set sclones(Set k) {
    	return (new HashSet(k));
    }
	public static Set sclone(Set k) {
    
		return (new HashSet(k));
    }
	public static Set sclonel(Set k) {
    	return (new HashSet(k));
    }
	public static boolean smartequals(int[] a,int[] b) {
    	if(a.length!=b.length) {
    		return false;
    	}
    	for(int i=0;i x)
               return binarySearch(arr, l, mid-1, x);
 
            return binarySearch(arr, mid+1, r, x);
        }
 
       
        return -1;
    }
	public static int[][] copy2D(int[][] a){
		
		int[][] b=new int[a.length][];
		for(int i=0;i