import java.util.*; import java.io.*; public class Solution { private static boolean[][] visited; private static int[][] level; static int[][] par; static int[] fx = {-2,-2,0,2,2,0}; static int[] fy = {-1,1,2,1,-1,-2}; public static boolean checkBoundary(int i,int j, int n) { return i>=0 && i=0 && jkey) { hi = mid-1; } else { lo = mid+1; } } return -1; } public static int upperBound(int[] A, int key, int lo, int hi) { while(lo<=hi) { int mid = (lo+hi)/2; if(A[mid]>key && (mid==1 || A[mid-1]<=key)) { return mid; } else if(A[mid]>key) { hi = mid-1; } else { lo = mid+1; } } return -1; } public static int lowerBound(int[] A, int key, int lo, int hi) { while(lo<=hi) { int mid = (lo+hi)/2; if(A[mid]>=key && (mid==1 || A[mid-1]=key) { hi = mid-1; } else { lo = mid+1; } } return -1; } public static int power(int x, int n) { if(n==0) { return 1; } if(n==1) { return x; } int ret = power(x,n/2); int val = ret*ret; if(n%2==1) { val*=x; } return val; } public static void initialize(int[] A, int[] segmentTree, int start, int end, int index) { if(start==end) { segmentTree[index] = start; return; } int mid = (start+end)/2; initialize(A,segmentTree, start, mid, index*2+1); initialize(A,segmentTree, mid+1, end, index*2+2); if(A[segmentTree[index*2+1]]<=A[segmentTree[index*2+2]]) { segmentTree[index] = segmentTree[index*2+1]; } else { segmentTree[index] = segmentTree[index*2+2]; } } public static void update(int[] A, int[] segmentTree, int start, int end, int index, int pos, int val) { if(start==end) { A[segmentTree[index]] = val; return; } int mid = (start+end)/2; if(pos<=mid) { update(A,segmentTree,start,mid,index*2+1,pos,val); } else { update(A,segmentTree,mid+1,end,index*2+2,pos,val); } if(A[segmentTree[index*2+1]]<=A[segmentTree[index*2+2]]) { segmentTree[index] = segmentTree[index*2+1]; } else { segmentTree[index] = segmentTree[index*2+2]; } } public static int query(int[] A, int[] segmentTree, int start, int end, int index, int rangeStart, int rangeEnd) { if(rangeStart>end || rangeEnd=end) { return segmentTree[index]; } int mid = (start+end)/2; int val1 = query(A,segmentTree, start, mid, index*2+1, rangeStart, rangeEnd); int val2 = query(A,segmentTree, mid+1, end, index*2+2, rangeStart, rangeEnd); if(val1==-1) { return val2; } if(val2==-1) { return val1; } if(A[val1]<=A[val2]) { return val1; } return val2; } public static void constructSegmentTree(int[] A, int n) { int x = (int)Math.ceil(Math.log(n)/Math.log(2)); int size = (int)Math.pow(2,x+1)-1; int[] segmentTree = new int[size+1]; initialize(A,segmentTree,0,n-1,0); //update update(A,segmentTree,0,n-1,0,4,10); //query int ret = query(A,segmentTree,0,n-1,0,9,9); } //Z Algorithm public static int[] createLCPArray(String str) { int len = str.length(); int[] lcp = new int[len]; int L=0,R=0; lcp[0] = 0; for(int i=1;iR) { L=R=i; while(R=0;i--) { if((T&(1<