/*
* 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 javatools {
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 Random getrandom() {
return new Random();
}
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 touching(int[][] map,int x,int y){
ArrayList out=new ArrayList();
try {
out.add(map[x-1][y]);
}catch(Exception e) {
}
try {
out.add(map[x+1][y]);
}catch(Exception e) {
}
try {
out.add(map[x][y-1]);
}catch(Exception e) {
}
try {
out.add(map[x][y+1]);
}catch(Exception e) {
}
return out;
}
public static String repeat(int count, String with) {
return new String(new char[count]).replace("\0", with);
}
public static String changen(int position, char ch, String str){
char[] charArray = str.toCharArray();
charArray[position] = ch;
return new String(charArray);
}
public static BufferedReader mreader(String filen) throws IOException {
//Make a reader
return new BufferedReader(new FileReader(filen));
}
public static PrintWriter mwriter(String filen) throws IOException {
return new PrintWriter(new BufferedWriter(new FileWriter(filen)));
}
public static Scanner getsysscan() {
return new Scanner(System.in);
}
public static int binarySearch(int arr[], int l, int r, int x)
{
/*
* Binary Search
*
*/
if (r>=l)
{
int mid = l + (r - l)/2;
if (arr[mid] == x)
return mid;
if (arr[mid] > 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 arr) {
int[] stuff=new int[arr.size()];
for(int i=0;i arr) {
String[] stuff=new String[arr.size()];
for(int i=0;i fibmem=new ArrayList();
public static long ffib(long n){
/*
* Fibonnaci implemented with DP
*/
if(n<=1) {
return n;
}
if(fibmem.size()>n) {
return fibmem.get((int) n-1)+fibmem.get((int) n-2);
}else {
fibmem.add(ffib(n-1)+ffib(n-2));
return fibmem.get((int) n);
}
}
public static void print() {
System.out.println();
}
public static void setupfib() {
fibmem.add((long) 0);fibmem.add((long)1);fibmem.add((long)1);fibmem.add((long)2);
}
public static void show2Darr(int[][] a) {
//Print out a 2D array for you
for(int[] b:a) {
for(int c:b) {
print(c+" ","");
}
print();
}
}
public static void showarr(int[] a) {
//Print out a array for you
for(int x:a) {print(x+" ");}
}
public static int[][] dpcache;
public static int ks(int W,int[] wt,int[] val,int n) {
int result;
if(dpcache[n][W]!=0) {return dpcache[n][W];}
if(n==0||W==0) {
result=0;
}else if(wt[n-1]>W) {
result=ks(W,wt,val,n-1);
}else {
result=Math.max(val[n-1]+ks(W-wt[n-1],wt,val,n-1),ks(W,wt,val,n-1));
}
dpcache[n][W]=result;
return result;
}
public static void kssetup(int n,int W) {
dpcache=new int[n+1][W+1];
}
public static int count(int[] arr) {
/*
* Number of groups of 1s
* Modify for other purposes if needed
* Example
* 1111000111
* Returns 2
*
*/
boolean b=false;int c=0;int temp;
for(int i=0;i speedqueue=new LinkedList();
public static long prevtime=0;
public static void $1() {
long time=System.currentTimeMillis();
if(prevtime==0) {
prevtime=time;
}else {
speedqueue.add((long) abs(time-prevtime));
prevtime=0;
}
}
public static long $r() {
return speedqueue.poll().longValue();
}
public static boolean $r$smatch(String a,String b) {
return Pattern.matches(a, b);
}
public static boolean $r$match(String a,String b) throws Exception{
//WIP
throw new Exception("Not implemented");
}
}