Submission #13637503


Source Code Expand

Copy
import java.io.IOException;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.NoSuchElementException;
import java.util.Objects;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Random;
import java.util.Scanner;
import java.util.Set;
import java.util.Stack;
import java.util.TreeMap;
import java.util.TreeSet;
import java.util.function.BiFunction;

public class Main{
	static Scanner scn = new Scanner(System.in);
	static FastScanner sc = new FastScanner();
	static Mathplus mp = new Mathplus();
	static PrintWriter ot = new PrintWriter(System.out);
	static Random rand = new Random();
	static StringManager sm = new StringManager(" ");
	static int mod = 1000000007;
	static long modmod = (long)mod * mod;
	static long inf = (long)1e17;
	static int[] dx = {0,1,0,-1};
	static int[] dy = {1,0,-1,0};
	static int[] dx8 = {-1,-1,-1,0,0,1,1,1};
	static int[] dy8 = {-1,0,1,-1,1,-1,0,1};
	static char[] dc = {'R','D','L','U'};
	static BiFunction<Integer,Integer,Integer> fmax = (a,b)-> {return Math.max(a,b);};
	static BiFunction<Integer,Integer,Integer> fmin = (a,b)-> {return Math.min(a,b);};
	static BiFunction<Integer,Integer,Integer> fsum = (a,b)-> {return a+b;};
	static BiFunction<Long,Long,Long> fmaxl = (a,b)-> {return Math.max(a,b);};
	static BiFunction<Long,Long,Long> fminl = (a,b)-> {return Math.min(a,b);};
	static BiFunction<Long,Long,Long> fsuml = (a,b)-> {return a+b;};
	static BiFunction<Integer,Integer,Integer> fadd = fsum;
	static BiFunction<Integer,Integer,Integer> fupd = (a,b)-> {return b;};
	static BiFunction<Long,Long,Long> faddl = fsuml;
	static BiFunction<Long,Long,Long> fupdl = (a,b)-> {return b;};
	static String sp = " ";
	static int[] l;
	public static void main(String[] args) {
		
		int q = sc.nextInt();
		char[] c = new char[q];
		int[] i = new int[q];
		int[] j = new int[q];
		Tree T = new Tree(200001);
		for(int x=0;x<q;x++) {
			c[x] = sc.nextChar();
			i[x] = sc.nextInt()-1;
			j[x] = sc.nextInt()-1;
			if(c[x]=='A')T.addEdge(i[x],j[x]);
		}
		T.buildlca(0);
		for(int x=0;x<q;x++) {
			if(c[x]=='B') {
				int p = T.lca(i[x],j[x]);
				ot.println(T.depth[i[x]]+T.depth[j[x]]-T.depth[p]-1);
			}
		}
		ot.flush();
		
	}
	

	
	

}


class Point{
	double x;
	double y;
	Point(double X,double Y){
		x = X;
		y = Y;
	}

	double atan(){
		return Math.atan2(y,x);
	}
	double length() {
		return Math.sqrt(x*x+y*y);
	}
	Point add(Point Q) {
		return new Point(x+Q.x,y+Q.y);
	}
	Point sub(Point Q) {
		return new Point(x-Q.x,y-Q.y);
	}
	Point mul(double d) {
		return new Point(x*d,y*d);
	}
	Point div(double d) {
		return new Point(x/d,y/d);
	}

}


class Triangle{
	double eps = 1e-7;
	Point A;
	Point B;
	Point C;
	double edgeA;
	double edgeB;
	double edgeC;
	double argA;
	double argB;
	double argC;
	Triangle(Point a,Point b,Point c){
		A = a;
		B = b;
		C = c;
		edgeA = b.sub(c).length();
		edgeB = c.sub(a).length();
		edgeC = a.sub(b).length();
		argA = Math.acos(getcos(edgeA,edgeB,edgeC));
		argB = Math.acos(getcos(edgeB,edgeC,edgeA));
		argC = Math.acos(getcos(edgeC,edgeA,edgeB));
	}
	double getcos(double a,double b,double c){
		return (b*b+c*c-a*a)/(2*b*c);
	}
	Point outheart() {
		return A.mul(Math.sin(2*argA)).add(B.mul(Math.sin(2*argB))).add(C.mul(Math.sin(2*argC))).div(Math.sin(2*argA)+Math.sin(2*argB)+Math.sin(2*argC));
	}
}

class Slidemax{
	int[] dat;

	ArrayDeque<LongIntPair> q = new ArrayDeque<LongIntPair>();

	long get() {
		if(q.isEmpty()) return (long) -1e17;
		return q.peek().a;
	}

	void remove() {
		q.getFirst().b--;
		if(q.getFirst().b==0)q.pollFirst();
	}

	void add(long x) {
		int num = 1;
		while(!q.isEmpty()&&q.peekLast().a<=x) {
			num += q.peekLast().b;
			q.pollLast();
		}
		q.addLast(new LongIntPair(x,num));
	}
}
class Slidemin{
	int[] dat;
	int l = 0;
	int r = -1;
	ArrayDeque<LongIntPair> q = new ArrayDeque<LongIntPair>();

	long get() {
		if(q.isEmpty()) return (long)1e17;
		return q.peek().a;
	}

	void remove() {
		q.getFirst().b--;
		if(q.getFirst().b==0)q.pollFirst();
	}

	void add(long x) {
		int num = 1;
		while(!q.isEmpty()&&q.peekLast().a>=x) {
			num += q.peekLast().b;
			q.pollLast();
		}
		q.addLast(new LongIntPair(x,num));
	}
}


class Counter{

	int[] cnt;
	Counter(int M){
		cnt = new int[M+1];
	}
	Counter(int M,int[] A){
		cnt = new int[M+1];
		for(int i=0;i<A.length;i++)add(A[i]);
	}
	void add(int e) {
		cnt[e]++;
	}
	void remove(int e) {
		cnt[e]--;
	}
	int count(int e) {
		return cnt[e];
	}
}

class MultiHashSet{
	HashMap<Integer,Integer> set;
	int size;
	long sum;
	MultiHashSet(){
		set = new HashMap<Integer,Integer>();
		size = 0;
		sum = 0;
	}
	void add(int e){
		if(set.containsKey(e))set.put(e,set.get(e)+1);
		else set.put(e,1);
		size++;
		sum += e;
	}
	void remove(int e) {
		set.put(e,set.get(e)-1);
		if(set.get(e)==0)set.remove(e);
		size--;
		sum -= e;
	}

	boolean contains(int e) {
		return set.containsKey(e);
	}
	boolean isEmpty() {
		return set.isEmpty();
	}
	int count(int e) {
		if(contains(e))return set.get(e);
		else return 0;
	}

	Set<Integer> keyset(){
		return set.keySet();
	}

}


class MultiSet{
	TreeMap<Integer,Integer> set;
	long size;
	long sum;
	MultiSet(){
		set = new TreeMap<Integer,Integer>();
		size = 0;
		sum = 0;
	}
	void add(int e){
		if(set.containsKey(e))set.put(e,set.get(e)+1);
		else set.put(e,1);
		size++;
		sum += e;
	}
	void addn(int e,int n){
		if(set.containsKey(e))set.put(e,set.get(e)+n);
		else set.put(e,n);
		size += n;
		sum += e*(long)n;
	}
	void remove(int e) {
		set.put(e,set.get(e)-1);
		if(set.get(e)==0)set.remove(e);
		size--;
		sum -= e;
	}
	int first() {return set.firstKey();}
	int last() {return set.lastKey();}
	int lower(int e) {return set.lowerKey(e);}
	int higher(int e) {return set.higherKey(e);}
	int floor(int e) {return set.floorKey(e);}
	int ceil(int e) {return set.ceilingKey(e);}
	boolean contains(int e) {return set.containsKey(e);}
	boolean isEmpty() {return set.isEmpty();}
	int count(int e) {
		if(contains(e))return set.get(e);
		else return 0;
	}
	MultiSet marge(MultiSet T) {
		if(size>T.size) {
			while(!T.isEmpty()) {
				add(T.first());
				T.remove(T.first());
			}
			return this;
		}else {
			while(!isEmpty()) {
				T.add(first());
				remove(first());
			}
			return T;
		}
	}
	Set<Integer> keyset(){
		return set.keySet();
	}

}

class MultiSetL{
	TreeMap<Long,Integer> set;
	int size;
	long sum;
	MultiSetL(){
		set = new TreeMap<Long,Integer>();
		size = 0;
		sum = 0;
	}
	void add(long e){
		if(set.containsKey(e))set.put(e,set.get(e)+1);
		else set.put(e,1);
		size++;
		sum += e;
	}
	void remove(long e) {
		set.put(e,set.get(e)-1);
		if(set.get(e)==0)set.remove(e);
		size--;
		sum -= e;
	}
	long first() {return set.firstKey();}
	long last() {return set.lastKey();}
	long lower(long e) {return set.lowerKey(e);}
	long higher(long e) {return set.higherKey(e);}
	long floor(long e) {return set.floorKey(e);}
	long ceil(long e) {return set.ceilingKey(e);}
	boolean contains(long e) {return set.containsKey(e);}
	boolean isEmpty() {return set.isEmpty();}
	int count(long e) {
		if(contains(e))return set.get(e);
		else return 0;
	}
	MultiSetL marge(MultiSetL T) {
		if(size>T.size) {
			while(!T.isEmpty()) {
				add(T.first());
				T.remove(T.first());
			}
			return this;
		}else {
			while(!isEmpty()) {
				T.add(first());
				remove(first());
			}
			return T;
		}
	}
	Set<Long> keyset(){
		return set.keySet();
	}
}




class GridGraph extends Graph{

	int N;
	int M;
	String[] S;
	HashMap<Character,Integer> map;
	GridGraph(int n,int m,String[] s){
		super(n*m);
		N = n;
		M = m;
		S = s;
		for(int i=0;i<n-1;i++) {
			for(int j=0;j<m;j++) {
				if(S[i].charAt(j)=='.'&&S[i+1].charAt(j)=='.') {
					addWeightedEdge(toint(i,j),toint(i+1,j),1);
					addWeightedEdge(toint(i+1,j),toint(i,j),1);
				}
			}
		}
		for(int i=0;i<n;i++) {
			for(int j=0;j<m-1;j++) {
				if(S[i].charAt(j)=='.'&&S[i].charAt(j+1)=='.') {
					addWeightedEdge(toint(i,j),toint(i,j+1),1);
					addWeightedEdge(toint(i,j+1),toint(i,j),1);
				}

			}
		}

	}
	GridGraph(int n,int m,String[] s,char[] c){
		super(n*m);
		N = n;
		M = m;
		S = s;
		map = new HashMap<Character,Integer>();
		for(int i=0;i<n-1;i++) {
			for(int j=0;j<m;j++) {
				if(S[i].charAt(j)!=S[i+1].charAt(j)) {
					addWeightedEdge(toint(i,j),toint(i+1,j),1);
					addWeightedEdge(toint(i+1,j),toint(i,j),1);
				}else {
					addWeightedEdge(toint(i,j),toint(i+1,j),0);
					addWeightedEdge(toint(i+1,j),toint(i,j),0);
				}
			}
		}
		for(int i=0;i<n;i++) {
			for(int j=0;j<m-1;j++) {
				if(S[i].charAt(j)!=S[i].charAt(j+1)) {
					addWeightedEdge(toint(i,j),toint(i,j+1),1);
					addWeightedEdge(toint(i,j+1),toint(i,j),1);
				}else{
					addWeightedEdge(toint(i,j),toint(i,j+1),0);
					addWeightedEdge(toint(i,j+1),toint(i,j),0);
				}

			}
		}
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				for(int k=0;k<c.length;k++) {
					if(S[i].charAt(j)==c[k])map.put(c[k],toint(i,j));
				}
			}
		}
	}

	int toint(int i,int j) {
		return i*M+j;
	}

}

class StringManager{
	ArrayList<Character> S;
	static Mathplus mp;
	static boolean calced;
	static int base;
	static long baserev;
	ArrayList<Long> l;
	StringManager(String s){
		S = new ArrayList<Character>();
		for(int i=0;i<s.length();i++) {
			S.add(s.charAt(i));
		}
		if(!calced) {
			calced = true;
			mp = new Mathplus();
			base = 1000003;
			baserev = mp.rev(base);
			mp.buildpow(base,2000050);
			mp.buildrevpow(base, 2000050);

		}
		l = new ArrayList<Long>();

		l.add((long)S.get(0));

		for(int i=1;i<S.size();i++) {
			char c = S.get(i);
			l.add((l.get(i-1) + mp.pow[i] * c)%mp.mod);

		}
	}
	StringManager(String s,int b){
		S = new ArrayList<Character>();
		for(int i=0;i<s.length();i++) {
			S.add(s.charAt(i));
		}
		base = b;
		if(!calced) {
			calced = true;
			mp = new Mathplus();
			base = b;
			baserev = mp.rev(base);
			mp.buildpow(base,2000050);
			mp.buildrevpow(base, 2000050);

		}
		l = new ArrayList<Long>();

		l.add((long)S.get(0));

		for(int i=1;i<S.size();i++) {
			char c = S.get(i);
			l.add((l.get(i-1) + mp.pow[i] * c)%mp.mod);

		}
	}
	void add(char C){
		int i = S.size();
		S.add(C);
		l.add((l.get(i-1) + mp.pow[i] * C)%mp.mod);
	}
	long gethash(int le,int ri) {
		long res = l.get(ri);
		if(le!=0) {
			res -= l.get(le-1);
			res += mp.mod;
			res %= mp.mod;
			res *= mp.revpow[le];
			res %= mp.mod;
		}
		return res;
	}

	ArrayList<CIPair> runlength(String s){
		ArrayList<CIPair> ret = new ArrayList<CIPair>();
		s += ' ';
		char bef = ' ';
		int len = 0;
		for(int i=0;i<s.length();i++) {
			if(s.charAt(i)!=bef) {
				if(bef != ' ')ret.add(new CIPair(bef,len));
				len = 1;
			}else {
				len++;
			}
			bef = s.charAt(i);
		}
		return ret;
	}
	ArrayList<CIPair> runlength(ArrayList<Character> s){
		ArrayList<CIPair> ret = new ArrayList<CIPair>();
		s.add(' ');
		char bef = ' ';
		int len = 0;
		for(int i=0;i<s.size();i++) {
			if(s.get(i)!=bef) {
				if(bef != ' ')ret.add(new CIPair(bef,len));
				len = 1;
			}else {
				len++;
			}
			bef = s.get(i);
		}
		return ret;
	}
	boolean isPalindrome(String S) {
		boolean b = true;
		for(int i=0;i<S.length();i++) {
			if(S.charAt(i)!=S.charAt(S.length()-1-i))b = false;
		}
		return b;
	}


}




class BetterGridGraph{
	int N;
	int M;
	char[][] S;
	HashMap<Character,ArrayList<Integer>> map;
	int[] dx = {0,1,0,-1};
	int[] dy = {1,0,-1,0};
	int[] dx6 = {0,1,0,-1,-1,1};
	int[] dy6 = {1,0,-1,0,1,1};
	char w;
	char b = '#';
	BetterGridGraph(int n,int m,String[] s,char[] c){

		N = n;
		M = m;
		for(int i=0;i<s.length;i++) {
			S[i] = s[i].toCharArray();
		}
		map = new HashMap<Character,ArrayList<Integer>>();
		for(int i=0;i<c.length;i++) {
			map.put(c[i],new ArrayList<Integer>());
		}
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				for(int k=0;k<c.length;k++) {
					if(S[i][j]==c[k])map.get(c[k]).add(toint(i,j));
				}
			}
		}
	}
	BetterGridGraph(int n,int m,char[][] s,char[] c){

		N = n;
		M = m;
		S = s;
		map = new HashMap<Character,ArrayList<Integer>>();
		for(int i=0;i<c.length;i++) {
			map.put(c[i],new ArrayList<Integer>());
		}
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				for(int k=0;k<c.length;k++) {
					if(S[i][j]==c[k])map.get(c[k]).add(toint(i,j));
				}
			}
		}
	}

	BetterGridGraph(int n,int m,String[] s,char[] c,char W,char B){

		N = n;
		M = m;
		for(int i=0;i<s.length;i++) {
			S[i] = s[i].toCharArray();
		}
		w = W;
		b = B;
		map = new HashMap<Character,ArrayList<Integer>>();
		for(int i=0;i<c.length;i++) {
			map.put(c[i],new ArrayList<Integer>());
		}
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				for(int k=0;k<c.length;k++) {
					if(S[i][j]==c[k])map.get(c[k]).add(toint(i,j));
				}
			}
		}
	}
	BetterGridGraph(int n,int m,char[][] s,char[] c,char W,char B){

		N = n;
		M = m;
		S = s;
		w = W;
		b = B;
		map = new HashMap<Character,ArrayList<Integer>>();
		for(int i=0;i<c.length;i++) {
			map.put(c[i],new ArrayList<Integer>());
		}
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				for(int k=0;k<c.length;k++) {
					if(S[i][j]==c[k])map.get(c[k]).add(toint(i,j));
				}
			}
		}
	}

	int toint(int i,int j) {
		return i*M+j;
	}

	ArrayList<Integer> getposlist(char c) {
		return map.get(c);
	}

	int getpos(char c) {
		return map.get(c).get(0);
	}

	int[] bfs(char C) {
		int[] L = new int[N*M];
		ArrayDeque<Integer> Q = new ArrayDeque<Integer>();
		for(int i=0;i<N*M;i++){
			L[i] = -1;
		}
		for(int s:map.get(C)) {
			L[s] = 0;
			Q.add(s);
		}
		Range X = new Range(0,N-1);
		Range Y = new Range(0,M-1);
		while(!Q.isEmpty()){
			int v = Q.poll();
			for(int i=0;i<4;i++){
				int x = v/M;
				int y = v%M;
				int nx = x+dx[i];
				int ny = y+dy[i];
				if(X.isIn(nx)&&Y.isIn(ny)&&S[nx][ny]!=b) {
					int w = toint(nx,ny);
					if(L[w]==-1){
						L[w] = L[v] + 1;
						Q.add(w);
					}
				}
			}
		}
		return L;
	}
	int[] bfs6(char C) {
		int[] L = new int[N*M];
		ArrayDeque<Integer> Q = new ArrayDeque<Integer>();
		for(int i=0;i<N*M;i++){
			L[i] = -1;
		}
		for(int s:map.get(C)) {
			L[s] = 0;
			Q.add(s);
		}
		Range X = new Range(0,N-1);
		Range Y = new Range(0,M-1);
		while(!Q.isEmpty()){
			int v = Q.poll();
			for(int i=0;i<6;i++){
				int x = v/M;
				int y = v%M;
				int nx = x+dx6[i];
				int ny = y+dy6[i];
				if(X.isIn(nx)&&Y.isIn(ny)&&S[nx][ny]!=b) {
					int w = toint(nx,ny);
					if(L[w]==-1){
						L[w] = L[v] + 1;
						Q.add(w);
					}
				}
			}
		}
		return L;
	}

	int[] bfsb(int s) {
		int[] L = new int[N*M];
		ArrayDeque<Integer> Q = new ArrayDeque<Integer>();
		for(int i=0;i<N*M;i++){
			L[i] = -1;
		}
		Q.add(s);
		L[s] = 0;
		Range X = new Range(0,N-1);
		Range Y = new Range(0,M-1);
		while(!Q.isEmpty()){
			int v = Q.poll();
			for(int i=0;i<4;i++){
				int x = v/M;
				int y = v%M;
				int nx = x+dx[i];
				int ny = y+dy[i];
				if(X.isIn(nx)&&Y.isIn(ny)) {
					int w = toint(nx,ny);
					if(L[w]==-1){
						if(S[x][y]==S[nx][ny]) {
							L[w] = L[v];
							Q.addFirst(w);
						}else {
							L[w] = L[v] + 1;
							Q.addLast(w);
						}
					}
				}
			}
		}
		return L;
	}

	int[][] bfs2(char C,int K){
		int[][] L = new int[N*M][K+1];
		ArrayDeque<IntIntPair> Q = new ArrayDeque<IntIntPair>();
		for(int i=0;i<N*M;i++){
			for(int j=0;j<=K;j++) {
				L[i][j] = 1000000007;
			}
		}
		for(int s:map.get(C)) {
			L[s][0] = 0;
			Q.add(new IntIntPair(0,s));
		}
		Range X = new Range(0,N-1);
		Range Y = new Range(0,M-1);
		while(!Q.isEmpty()){
			IntIntPair v = Q.poll();
			for(int i=0;i<4;i++){
				int x = v.b/M;
				int y = v.b%M;
				int h = v.a;
				int nx = x+dx[i];
				int ny = y+dy[i];
				if(X.isIn(nx)&&Y.isIn(ny)&&S[nx][ny]!=b) {
					int ni = toint(nx,ny);
					int nh = S[nx][ny]==w?h+1:h;
					if(nh>K) continue;
					if(L[ni][nh]==1000000007){
						L[ni][nh] = L[v.b][h]+1;
						Q.add(new IntIntPair(nh,ni));
					}
				}
			}
		}
		for(int i=0;i<N*M;i++) {
			for(int j=1;j<=K;j++) {
				L[i][j] = Math.min(L[i][j],L[i][j-1]);
			}
		}
		return L;
	}

	int[] dijkstra(char C) {
		int[] L = new int[N*M];
		PriorityQueue<IntIntPair> Q = new PriorityQueue<IntIntPair>(new IntIntComparator());
		for(int i=0;i<N*M;i++){
			L[i] = -1;
		}
		for(int s:map.get(C)) {
			L[s] = 0;
			Q.add(new IntIntPair(0,s));
		}
		Range X = new Range(0,N-1);
		Range Y = new Range(0,M-1);
		while(!Q.isEmpty()){
			IntIntPair P = Q.poll();
			int v = P.b;
			int x = v/M;
			int y = v%M;
			for(int i=0;i<4;i++){
				int nx = x+dx[i];
				int ny = y+dy[i];
				if(X.isIn(nx)&&Y.isIn(ny)&&S[nx][ny]!=b) {
					int w = toint(nx,ny);
					if(L[w]==-1||L[w]>L[v] + (S[nx][ny]!='t'?S[nx][ny]-'0':0)){
						L[w] = L[v] + (S[nx][ny]!='t'?S[nx][ny]-'0':0);
						Q.add(new IntIntPair(L[w],w));
					}
				}
			}
			if(x%2==0) {
				int nx = x+1;
				int ny = y-1;
				if(X.isIn(nx)&&Y.isIn(ny)&&S[nx][ny]!=b) {
					int w = toint(nx,ny);
					if(L[w]==-1){
						L[w] = L[v] + (S[nx][ny]!='t'?S[nx][ny]-'0':0);
						Q.add(new IntIntPair(L[w],w));
					}
				}
				nx = x-1;
				ny = y-1;
				if(X.isIn(nx)&&Y.isIn(ny)&&S[nx][ny]!=b) {
					int w = toint(nx,ny);
					if(L[w]==-1){
						L[w] = L[v] + (S[nx][ny]!='t'?S[nx][ny]-'0':0);
						Q.add(new IntIntPair(L[w],w));
					}
				}
			}else {
				int nx = x+1;
				int ny = y+1;
				if(X.isIn(nx)&&Y.isIn(ny)&&S[nx][ny]!=b) {
					int w = toint(nx,ny);
					if(L[w]==-1){
						L[w] = L[v] + (S[nx][ny]!='t'?S[nx][ny]-'0':0);
						Q.add(new IntIntPair(L[w],w));
					}
				}
				nx = x-1;
				ny = y+1;
				if(X.isIn(nx)&&Y.isIn(ny)&&S[nx][ny]!=b) {
					int w = toint(nx,ny);
					if(L[w]==-1){
						L[w] = L[v] + (S[nx][ny]!='t'?S[nx][ny]-'0':0);
						Q.add(new IntIntPair(L[w],w));
					}
				}
			}

		}
		return L;
	}
}
class IntGridGraph{
	int N;
	int M;
	int[][] B;
	int[] dx = {0,1,0,-1};
	int[] dy = {1,0,-1,0};
	BiFunction<Integer,Integer,Boolean> F;

	IntGridGraph(int n,int m,int[][] b){

		N = n;
		M = m;
		B = b;
	}
	IntGridGraph(int n,int m,int[][] b,BiFunction<Integer,Integer,Boolean> f){

		N = n;
		M = m;
		B = b;
		F = f;
	}


	int toint(int i,int j) {
		return i*M+j;
	}


	int[] bfs(int s) {
		int[] L = new int[N*M];
		for(int i=0;i<N*M;i++){
			L[i] = -1;
		}
		L[s] = 0;
		ArrayDeque<Integer> Q = new ArrayDeque<Integer>();
		Q.add(s);
		Range X = new Range(0,N-1);
		Range Y = new Range(0,M-1);
		while(!Q.isEmpty()){
			int v = Q.poll();
			for(int i=0;i<4;i++){
				int x = v/M;
				int y = v%M;
				int nx = x+dx[i];
				int ny = y+dy[i];
				if(X.isIn(nx)&&Y.isIn(ny)&&F.apply(B[x][y],B[nx][ny])) {
				int w = toint(nx,ny);
					if(L[w]==-1){
						L[w] = L[v] + 1;
						Q.add(w);
					}
				}
			}
		}
		return L;
	}

	void bfs(int s,int[] L) {

		if(L[s]!=-1) return;
		L[s] = 0;
		ArrayDeque<Integer> Q = new ArrayDeque<Integer>();
		Q.add(s);
		Range X = new Range(0,N-1);
		Range Y = new Range(0,M-1);
		while(!Q.isEmpty()){
			int v = Q.poll();
			for(int i=0;i<4;i++){
				int x = v/M;
				int y = v%M;
				int nx = x+dx[i];
				int ny = y+dy[i];
				if(X.isIn(nx)&&Y.isIn(ny)&&F.apply(B[x][y],B[nx][ny])) {
				int w = toint(nx,ny);
					if(L[w]==-1){
						L[w] = L[v] + 1;
						Q.add(w);
					}
				}
			}
		}
		return;
	}

	int[][] bfs2(int s,int K){
		int[][] L = new int[N*M][K+1];
		for(int i=0;i<N*M;i++){
			for(int j=0;j<=K;j++)
			L[i][j] = 1000000007;
		}
		L[s][0] = 0;
		PriorityQueue<IntIntPair> Q = new PriorityQueue<IntIntPair>(new IntIntComparator());
		Q.add(new IntIntPair(0,s));
		Range X = new Range(0,N-1);
		Range Y = new Range(0,M-1);
		while(!Q.isEmpty()){
			IntIntPair v = Q.poll();
			for(int i=0;i<4;i++){
				int x = v.b/M;
				int y = v.b%M;
				int h = v.a;
				int nx = x+dx[i];
				int ny = y+dy[i];
				if(X.isIn(nx)&&Y.isIn(ny)&&F.apply(B[x][y],B[nx][ny])) {
					int ni = toint(nx,ny);
					int nh = h + B[nx][ny];
					if(nh>K) continue;
					if(L[ni][nh]==1000000007){
						L[ni][nh] = L[v.b][h] + 1;
						Q.add(new IntIntPair(nh,ni));
					}
				}
			}
		}
		for(int i=0;i<N*M;i++) {
			for(int j=1;j<=K;j++) {
				L[i][j] = Math.min(L[i][j],L[i][j-1]);
			}
		}
		return L;
	}
}
class Trie{
	int nodenumber = 1;
	ArrayList<TrieNode> l;
	Trie(){
		l = new ArrayList<TrieNode>();
		l.add(new TrieNode());
	}

	void add(String S,int W){
		int now = 0;
		for(int i=0;i<S.length();i++) {
			TrieNode n = l.get(now);
			char c = S.charAt(i);
			if(n.Exist[c-'a']!=-1) {
				now = n.Exist[c-'a'];
			}else {
				l.add(new TrieNode());
				n.Exist[c-'a'] = nodenumber;
				now = nodenumber;
				nodenumber++;
			}
		}
		l.get(now).weight = W;
	}

	void find(String S,int i,int[] dp) {
		int now = 0;
		dp[i+1] = Math.max(dp[i],dp[i+1]);
		for(int j=0;;j++) {
			TrieNode n = l.get(now);
			dp[i+j] = Math.max(dp[i+j],dp[i]+n.weight);
			int slook = i+j;
			if(slook>=S.length())return;
			char c = S.charAt(slook);
			if(n.Exist[c-'a']==-1)return;
			now = n.Exist[c-'a'];
		}
	}
}

class TrieNode{

	int[] Exist = new int[26];
	int weight = 0;
	TrieNode(){
		for(int i=0;i<26;i++) {
			Exist[i] = -1;
		}
	}
}

class SizeComparator implements Comparator<Edge>{
	int[] size;
	SizeComparator(int[] s) {
		size = s;
	}

	public int compare(Edge o1, Edge o2) {
		return size[o1.to]-size[o2.to];

	}

}

class ConvexHullTrick {
	long[] A, B;
	int len;

	public ConvexHullTrick(int n) {
		A = new long[n];
		B = new long[n];
	}

	private boolean check(long a, long b) {
		return (B[len - 2] - B[len - 1]) * (a - A[len - 1]) >= (B[len - 1] - b) * (A[len - 1] - A[len - 2]);
	}

	public void add(long a, long b) {
		while (len >= 2 && check(a, b)) {
			len--;
		}
		A[len] = a;
		B[len] = b;
		len++;
	}

	public long query(long x) {
		int l = -1, r = len - 1;
		while (r - l > 1) {
			int mid = (r + l) / 2;
			if (get(mid,x)>=get(mid+1,x)) {
				l = mid;
			} else {
				r = mid;
			}
		}
		return get(r,x);
	}

	private long get(int k, long x) {
		return A[k] * x + B[k];
	}
}

class Range{
	long l;
	long r;
	long length;
	Range(int L,int R){
		l = L;
		r = R;
		length = R-L+1;
	}

	public Range(long L, long R) {
		l = L;
		r = R;
		length = R-L+1;
	}

	boolean isIn(int x) {
		return (l<=x&&x<=r);

	}
	long kasanari(Range S) {
		if(this.r<S.l||S.r<this.l) return 0;
		else return Math.min(this.r,S.r) - Math.max(this.l,S.l)+1;
	}
}
class LeftComparator implements Comparator<Range>{
	public int compare(Range P, Range Q) {
		return (int) Math.signum(P.l-Q.l);
	}
}
class RightComparator implements Comparator<Range>{
	public int compare(Range P, Range Q) {
		return (int) Math.signum(P.r-Q.r);

	}
}
class LengthComparator implements Comparator<Range>{
	public int compare(Range P, Range Q) {
		return (int) Math.signum(P.length-Q.length);
	}
}
class SegmentTree<T,E>{
	int N;
	BiFunction<T,T,T> f;
	BiFunction<T,E,T> g;
	T d1;
	ArrayList<T> dat;
	SegmentTree(BiFunction<T,T,T> F,BiFunction<T,E,T> G,T D1,T[] v){
		int n = v.length;
		f = F;
		g = G;
		d1 = D1;
		init(n);
		build(v);
	}


	void init(int n) {
		N = 1;
		while(N<n)N*=2;
		dat = new ArrayList<T>();
	}

	void build(T[] v) {
		for(int i=0;i<2*N;i++) {
			dat.add(d1);
		}
		for(int i=0;i<v.length;i++) {
			dat.set(N+i-1,v[i]);
		}
		for(int i=N-2;i>=0;i--) {
			dat.set(i,f.apply(dat.get(i*2+1),dat.get(i*2+2)));
		}
	}

	void update(int k,E a) {
		k += N-1;
		dat.set(k,g.apply(dat.get(k),a));
		while(k>0){
			k = (k-1)/2;
			dat.set(k,f.apply(dat.get(k*2+1),dat.get(k*2+2)));
		}
	}

	T query(int a,int b, int k, int l ,int r) {
		if(r<=a||b<=l) return d1;
		if(a<=l&&r<=b) return dat.get(k);
		T vl = query(a,b,k*2+1,l,(l+r)/2);
		T vr = query(a,b,k*2+2,(l+r)/2,r);
		return f.apply(vl,vr);
	}
	T query(int a,int b){
		return query(a,b,0,0,N);
	}

}

class LazySegmentTree<T,E> extends SegmentTree<T,E>{
	BiFunction<E,E,E> h;
	BiFunction<E,Integer,E> p = (E a,Integer b) ->{return a;};
	E d0;
	ArrayList<E> laz;
	LazySegmentTree(BiFunction<T,T,T> F,BiFunction<T,E,T> G,BiFunction<E,E,E> H,T D1,E D0,T[] v){
		super(F,G,D1,v);
		int n = v.length;
		h = H;
		d0 = D0;
		Init(n);
	}
	void build() {

	}
	void Init(int n){
		laz = new ArrayList<E>();
		for(int i=0;i<2*N;i++) {
			laz.add(d0);
		}
	}

	void eval(int len,int k) {
		if(laz.get(k).equals(d0)) return;
		if(k*2+1<N*2-1) {
			laz.set(k*2+1,h.apply(laz.get(k*2+1),laz.get(k)));
			laz.set(k*2+2,h.apply(laz.get(k*2+2),laz.get(k)));
		}
		dat.set(k,g.apply(dat.get(k), p.apply(laz.get(k), len)));
		laz.set(k,d0);
	}

	T update(int a,int b,E x,int k,int l,int r) {
		eval(r-l,k);
		if(r<=a||b<=l) {
			return dat.get(k);
		}
		if(a<=l&&r<=b) {
			laz.set(k,h.apply(laz.get(k),x));
			return g.apply(dat.get(k),p.apply(laz.get(k),r-l));
		}
		T vl = update(a,b,x,k*2+1,l,(l+r)/2);
		T vr = update(a,b,x,k*2+2,(l+r)/2,r);
		dat.set(k,f.apply(vl,vr));
		return dat.get(k);

	}

	T update(int a,int b,E x) {
		return update(a,b,x,0,0,N);
	}

	T query(int a,int b,int k,int l,int r) {

		eval(r-l,k);
		if(r<=a||b<=l) return d1;
		if(a<=l&&r<=b) return dat.get(k);
		T vl = query(a,b,k*2+1,l,(l+r)/2);
		T vr = query(a,b,k*2+2,(l+r)/2,r);
		return f.apply(vl, vr);
	}

	T query(int a,int b){
		return query(a,b,0,0,N);
	}

}

class AddSumSegmentTree{
	int N;
	int d1;
	ArrayList<Integer> dat;
	AddSumSegmentTree(int[] v){
		int n = v.length;
		init(n);
		build(v);
	}

	void init(int n) {
		N = 1;
		while(N<n)N*=2;
		dat = new ArrayList<Integer>();
	}

	void build(int[] v) {
		for(int i=0;i<2*N;i++) {
			dat.add(d1);
		}
		for(int i=0;i<v.length;i++) {
			dat.set(N+i-1,v[i]);
		}
		for(int i=N-2;i>=0;i--) {
			dat.set(i,dat.get(i*2+1)+dat.get(i*2+2));
		}
	}

	void update(int k,int a) {
		k += N-1;
		dat.set(k,dat.get(k)+a);
		while(k>0){
			k = (k-1)/2;
			dat.set(k,dat.get(k*2+1)+dat.get(k*2+2));
		}
	}

	int query(int a,int b, int k, int l ,int r) {
		if(r<=a||b<=l) return d1;
		if(a<=l&&r<=b) return dat.get(k);
		int vl = query(a,b,k*2+1,l,(l+r)/2);
		int vr = query(a,b,k*2+2,(l+r)/2,r);
		return vl+vr;
	}
	int query(int a,int b){
		return query(a,b,0,0,N);
	}
}
class AddSumLazySegmentTree {
	int N;
	long[] dat;
	long[] laz;
	AddSumLazySegmentTree(long[] v){
		init(v.length);

		for(int i=0;i<v.length;i++) {
			dat[N+i-1]=v[i];
		}
		for(int i=N-2;i>=0;i--) {
			dat[i]=dat[i*2+1]+dat[i*2+2];
		}
	}

	void init(int n) {
		N = 1;
		while(N<n)N*=2;
		dat = new long[2*N];
		laz = new long[2*N];
	}


	void eval(int len,int k) {
		if(laz[k]==0) return;
		if(k*2+1<N*2-1) {
			laz[k*2+1] += laz[k];
			laz[k*2+2] += laz[k];
		}
		dat[k] += laz[k] * len;
		laz[k] = 0;
	}

	long update(int a,int b,long x,int k,int l,int r) {
		eval(r-l,k);
		if(r<=a||b<=l) {
			return dat[k];
		}
		if(a<=l&&r<=b) {
			laz[k] += x;
			return dat[k]+laz[k]*(r-l);
		}
		long vl = update(a,b,x,k*2+1,l,(l+r)/2);
		long vr = update(a,b,x,k*2+2,(l+r)/2,r);
		return dat[k] = vl+vr;


	}

	long update(int a,int b,long x) {
		return update(a,b,x,0,0,N);
	}

	long query(int a,int b,int k,int l,int r) {
		eval(r-l,k);
		if(r<=a||b<=l) return 0;
		if(a<=l&&r<=b) return dat[k];

		long vl = query(a,b,k*2+1,l,(l+r)/2);
		long vr = query(a,b,k*2+2,(l+r)/2,r);
		return vl+vr;
	}

	long query(int a,int b){
		return query(a,b,0,0,N);
	}

}

class BinaryIndexedTree{
	int[] val;
	BinaryIndexedTree(int N){
		val = new int[N+1];
	}
	long sum(int i) {
		if(i==0)return 0;
		long s = 0;
		while(i>0) {
			s += val[i];
			i -= i & (-i);
		}
		return s;
	}
	void add(int i,int x) {
		if(i==0)return;
		while(i<val.length){
			val[i] += x;
			i += i & (-i);
		}
	}
}


class UnionFindTree {
	int[] root;
	int[] rank;
	long[] size;
	int[] edge;
	int num;
	UnionFindTree(int N){
		root = new int[N];
		rank = new int[N];
		size = new long[N];
		edge = new int[N];
		num = N;
		for(int i=0;i<N;i++){
			root[i] = i;
			size[i] = 1;
		}
	}
	
	public long size(int x) {
		return size[find(x)];
	}
	public boolean isRoot(int x) {
		return x==find(x);
	}
	public long extraEdge(int x) {
		int r = find(x);
		return edge[r] - size[r] + 1;
	}
	public int find(int x){
		if(root[x]==x){
			return x;
		}else{
			return find(root[x]);
		}
	}

	public boolean unite(int x,int y){
		x = find(x);
		y = find(y);
		if(x==y){
			edge[x]++;
			return false;
		}else{
			num--;
			if(rank[x]<rank[y]){
				root[x] = y;
				size[y] += size[x];
				edge[y] += edge[x]+1;
			}else{
				root[y] = x;
				size[x] += size[y];
				edge[x] += edge[y]+1;
				if(rank[x]==rank[y]){
					rank[x]++;
				}
			}
			return true;
		}
	}

	public boolean same(int x,int y){
		return find(x)==find(y);
	}

}
class LightUnionFindTree {
	int[] par;
	int num;
	LightUnionFindTree(int N){
		par = new int[N];
		num = N;
		for(int i=0;i<N;i++){
			par[i] = -1;
		}
	}
	public boolean isRoot(int x) {
		return x==find(x);
	}

	public int find(int x){
		if(par[x]<0){
			return x;
		}else{
			return find(par[x]);
		}
	}

	public void unite(int x,int y){
		x = find(x);
		y = find(y);
		if(x==y){
			return;
		}else{
			num--;
			if(par[x]<par[y]){
				par[x] += par[y];
				par[y] = x;
			}else{
				par[y] += par[x];
				par[x] = y;
			}
		}
	}

	public boolean same(int x,int y){
		return find(x)==find(y);
	}

}

class JustCompressUnionFind{
	int[] par;
	int num;
	JustCompressUnionFind(int N){
		par = new int[N];
		num = N;
		for(int i=0;i<N;i++){
			par[i] = -1;
		}
	}
	public boolean isRoot(int x) {
		return x==find(x);
	}

	public int find(int x){
		if(par[x]<0){
			return x;
		}else{
			return par[x] = find(par[x]);
		}
	}

	public boolean unite(int x,int y){
		x = find(x);
		y = find(y);
		if(x==y){
			return false;
		}else{
			num--;
			par[y] = x;
			return true;
		}
	}

	public boolean same(int x,int y){
		return find(x)==find(y);
	}
}

class ParticalEternalLastingUnionFindTree extends UnionFindTree{
	int[] time;
	int now;
	ParticalEternalLastingUnionFindTree(int N){
		super(N);
		time = new int[N];
		for(int i=0;i<N;i++) {
			time[i] = 1000000007;
		}
	}

	public int find(int t,int i) {
		if(time[i]>t) {
			return i;
		}else {
			return find(t,root[i]);
		}
	}

	public void unite(int x,int y,int t) {
		now = t;
		x = find(t,x);
		y = find(t,y);
		if(x==y)return;
		if(rank[x]<rank[y]){
			root[x] = y;
			size[y] += size[x];
			time[x] = t;
		}else{
			root[y] = x;
			size[x] += size[y];
			if(rank[x]==rank[y]){
				rank[x]++;
			}
			time[y] = t;
		}
	}

	public int sametime(int x,int y) {
		if(find(now,x)!=find(now,y)) return -1;
		int ok = now;
		int ng = 0;
		while(ok-ng>1) {
			int mid = (ok+ng)/2;
			if(find(mid,x)==find(mid,y)) {
				ok = mid;
			}else {
				ng = mid;
			}
		}
		return ok;
	}


}
class FlowEdge{
	int to;
	long cap;
	int rev = 0;
	FlowEdge(int To,long Cap,int Rev){
		to = To;
		cap = Cap;
		rev = Rev;
	}
}
class FlowGraph{
	ArrayList<FlowEdge>[] list;
	int[] level;
	int[] iter;
	ArrayDeque<Integer> q;
	FlowGraph(int N){
		list = new ArrayList[N];
		for(int i=0;i<N;i++) {
			list[i] = new ArrayList<FlowEdge>();
		}
		level = new int[N];
		iter = new int[N];
		q = new ArrayDeque<Integer>();
	}

	void addEdge(int i, int to, long cap) {
		list[i].add(new FlowEdge(to,cap,list[to].size()));
		list[to].add(new FlowEdge(i,0,list[i].size()-1));
	}

	void bfs(int s) {
		Arrays.fill(level,-1);
		level[s] = 0;
		q.add(s);
		while(!q.isEmpty()) {
			int v = q.poll();
			for(FlowEdge e:list[v]) {
				if(e.cap>0&&level[e.to]<0) {
					level[e.to] = level[v] + 1;
					q.add(e.to);
				}
			}
		}
	}

	long dfs(int v,int t,long f) {
		if(v==t) return f;
		for(int i = iter[v];i<list[v].size();i++) {
			FlowEdge e = list[v].get(i);
			if(e.cap>0&&level[v]<level[e.to]) {
				long d = dfs(e.to,t,Math.min(f,e.cap));
				if(d>0) {
					e.cap -= d;
					list[e.to].get(e.rev).cap += d;
					return d;
				}
			}
			iter[v]++;
		}
		return 0;
	}

	long flow(int s,int t,long lim) {
		long flow = 0;
		while(true) {
			bfs(s);
			if(level[t]<0||lim==0) return flow;
			Arrays.fill(iter,0);
			while(true) {
				long f = dfs(s,t,lim);
				if(f>0) {
					flow += f;
					lim -= f;
				}

				else break;
			}
		}

	}
	long flow(int s,int t) {
		return flow(s,t,1000000007);
	}
}
class Graph {
	ArrayList<Edge>[] list;
	int size;
	TreeSet<LinkEdge> Edges = new TreeSet<LinkEdge>(new LinkEdgeComparator());

	@SuppressWarnings("unchecked")
	Graph(int N){
		size = N;
		list = new ArrayList[N];
		for(int i=0;i<N;i++){
			list[i] = new ArrayList<Edge>();
		}
	}

	public long[] dicount(int s) {
		long[] L = new long[size];
		long[] c = new long[size];
		int mod = 1000000007;
		for(int i=0;i<size;i++){
			L[i] = -1;
		}
		int[] v = new int[size];
		L[s] = 0;
		c[s] = 1;
		PriorityQueue<LongIntPair> Q = new PriorityQueue<LongIntPair>(new LongIntComparator());
		Q.add(new LongIntPair(0,s));

		while(!Q.isEmpty()){

			LongIntPair C = Q.poll();

			if(v[C.b]==0){
				L[C.b] = C.a;
				v[C.b] = 1;
				for(Edge D:list[C.b]) {
					//System.out.println(C.b +" "+ D.to);
					if(L[D.to]==-1||L[D.to]>L[C.b]+D.cost) {
						L[D.to]=L[C.b]+D.cost;
						c[D.to] = c[C.b];
						Q.add(new LongIntPair(L[C.b]+D.cost,D.to));
					}else if(L[D.to]==L[C.b]+D.cost) {
						c[D.to] += c[C.b];
					}
					c[D.to] %= mod;

				}
			}
		}
		return c;
	}

	public long[] roots(int s) {
		int[] in = new int[size];
		ArrayDeque<Integer> q = new ArrayDeque<Integer>();
		long[] N = new long[size];
		long mod = 1000000007;
		for(int i=0;i<size;i++) {
			for(Edge e:list[i])in[e.to]++;
		}
		for(int i=0;i<size;i++) {
			if(in[i]==0)q.add(i);
		}
		N[s] = 1;
		while(!q.isEmpty()) {
			int v = q.poll();
			for(Edge e:list[v]) {
				N[e.to] += N[v];
				if(N[e.to]>=mod)N[e.to]-= mod;
				in[e.to]--;
				if(in[e.to]==0)q.add(e.to);
			}
		}
		return N;

	}

	void addEdge(int a,int b){
		list[a].add(new Edge(b,1));
	}

	void addWeightedEdge(int a,int b,long c){
		list[a].add(new Edge(b,c));
	}

	void addEgdes(int[] a,int[] b){
		for(int i=0;i<a.length;i++){
			list[a[i]].add(new Edge(b[i],1));
		}
	}

	void addWeightedEdges(int[] a ,int[] b ,int[] c){
		for(int i=0;i<a.length;i++){
			list[a[i]].add(new Edge(b[i],c[i]));
		}
	}
	long[] bfs(int s){
		long[] L = new long[size];
		for(int i=0;i<size;i++){
			L[i] = -1;
		}
		L[s] = 0;
		ArrayDeque<Integer> Q = new ArrayDeque<Integer>();
		Q.add(s);

		while(!Q.isEmpty()){
			int v = Q.poll();
			for(Edge e:list[v]){
				int w = e.to;
				long c = e.cost;
				if(L[w]==-1){
					L[w] = L[v] + c;
					Q.add(w);
				}
			}
		}
		return L;
	}


	long[][] bfswithrev(int s){
		long[][] L = new long[2][size];
		for(int i=0;i<size;i++){
			L[0][i] = -1;
			L[1][i] = -1;
		}
		L[0][s] = 0;
		ArrayDeque<Integer> Q = new ArrayDeque<Integer>();
		Q.add(s);

		while(!Q.isEmpty()){
			int v = Q.poll();
			for(Edge e:list[v]){
				int w = e.to;
				long c = e.cost;
				if(L[0][w]==-1){
					L[0][w] = L[0][v] + c;
					L[1][w] = v;
					Q.add(w);
				}
			}
		}
		return L;
	}
	long[] bfs2(int[] d,int s){
		long[] L = new long[size];
		for(int i=0;i<size;i++){
			L[i] = -1;
		}
		int p = 0;
		L[s] = 0;
		d[s] = p;
		p++;
		ArrayDeque<Integer> Q = new ArrayDeque<Integer>();
		Q.add(s);

		while(!Q.isEmpty()){
			int v = Q.poll();
			for(Edge e:list[v]){
				int w = e.to;
				long c = e.cost;
				if(L[w]==-1){
					d[w] = p;
					p++;
					L[w] = L[v] + c;
					Q.add(w);
				}
			}
		}
		return L;
	}
	boolean bfs3(int s,long[] L, int[] vi){

		if(vi[s]==1) return true;

		vi[s] = 1;
		ArrayDeque<Integer> Q = new ArrayDeque<Integer>();
		Q.add(s);

		while(!Q.isEmpty()){
			int v = Q.poll();
			for(Edge e:list[v]){
				int w = e.to;
				long c = e.cost;
				if(vi[e.to]==0) {
					L[e.to] = (int)c - L[v];
					Q.add(w);
					vi[e.to] = 1;
				}else {
					if(L[e.to]!=(int)c - L[v]) {
						return false;
					}
				}
			}
		}
		return true;
	}
	int[] isTwoColor(){
		int[] L = new int[size];
		for(int i=0;i<size;i++){
			L[i] = -1;
		}
		L[0] = 0;
		ArrayDeque<Integer> Q = new ArrayDeque<Integer>();
		Q.add(0);

		while(!Q.isEmpty()){
			int v = Q.poll();
			for(Edge e:list[v]){
				int w = e.to;
				if(L[w]==-1){
					L[w] = 1-L[v];
					Q.add(w);
				}else{
					if(L[v]+L[w]!=1){
						L[0] = -2;
					}
				}
			}
		}
		return L;
	}
	void isTwoColor2(int i,int[] L){


		L[i] = 0;
		ArrayDeque<Integer> Q = new ArrayDeque<Integer>();
		Q.add(i);

		while(!Q.isEmpty()){
			int v = Q.poll();
			for(Edge e:list[v]){
				int w = e.to;
				if(L[w]==-1){
					L[w] = 1-L[v];
					Q.add(w);
				}else{
					if(L[v]+L[w]!=1){
						L[0] = -2;
					}
				}
			}
		}
	}

	long[] dijkstra(int s){
		long[] L = new long[size];
		for(int i=0;i<size;i++){
			L[i] = -1;
		}
		int[] v = new int[size];
		L[s] = 0;
		PriorityQueue<LongIntPair> Q = new PriorityQueue<LongIntPair>(new LongIntComparator());
		Q.add(new LongIntPair(0,s));

		while(!Q.isEmpty()){

			LongIntPair C = Q.poll();

			if(v[C.b]==0){
				L[C.b] = C.a;
				v[C.b] = 1;
				for(Edge D:list[C.b]) {
					if(L[D.to]==-1||L[D.to]>L[C.b]+D.cost) {
						L[D.to]=L[C.b]+D.cost;
						Q.add(new LongIntPair(L[C.b]+D.cost,D.to));
					}

				}
			}
		}
		return L;
	}








	ArrayList<Graph> makeapart(){
		ArrayList<Graph> ans = new ArrayList<Graph>();
		boolean[] b = new boolean[size];
		int[] num = new int[size];
		for(int i=0;i<size;i++){
			if(b[i])continue;
			int sz = 0;
			ArrayList<Integer> l = new ArrayList<Integer>();
			ArrayDeque<Integer> Q = new ArrayDeque<Integer>();
			Q.add(i);
			b[i] = true;
			while(!Q.isEmpty()){
				int v = Q.poll();
				num[v] = sz;
				sz++;
				l.add(v);
				for(Edge e:list[v]){
					if(!b[e.to]){
						Q.add(e.to);
						b[e.to] = true;
					}
				}
			}
			Graph H = new Graph(sz);
			for(int e:l){
				for(Edge E:list[e]){
					H.addWeightedEdge(num[e],num[E.to],E.cost);
				}
			}
			ans.add(H);

		}
		return ans;
	}

	long[] bellmanFord(int s) {
		long inf = 1000000000;
		inf *= inf;
		long[] d = new long[size];
		boolean[] n = new boolean[size];
		d[s] = 0;
		for(int i=1;i<size;i++){
			d[i] = inf;
			d[i] *= d[i];
		}
		for(int i=0;i<size-1;i++){
			for(int j=0;j<size;j++){
				for(Edge E:list[j]){
					if(d[j]!=inf&&d[E.to]>d[j]+E.cost){
						d[E.to]=d[j]+E.cost;
					}
				}
			}
		}
		for(int i=0;i<size;i++){
			for(int j=0;j<size;j++){
				for(Edge e:list[j]){
					if(d[j]==inf) continue;
					if(d[e.to]>d[j]+e.cost) {
						d[e.to]=d[j]+e.cost;
						n[e.to] = true;
					}
					if(n[j])n[e.to] = true;
				}
			}
		}
		for(int i=0;i<size;i++) {
			if(n[i])d[i] = inf;
		}
		return d;
	}

	long[][] WarshallFloyd(long[][] a){
		int n = a.length;
		long[][] ans = new long[n][n];
		for(int i=0;i<n;i++) {
			for(int j=0;j<n;j++) {
				ans[i][j] = a[i][j]==0?(long)1e16:a[i][j];
				if(i==j)ans[i][j]=0;
			}
		}
		for(int k=0;k<n;k++) {
			for(int i=0;i<n;i++) {
				for(int j=0;j<n;j++) {
					ans[i][j] = Math.min(ans[i][j],ans[i][k]+ans[k][j]);
				}
			}
		}
		return ans;
	}
	long[] maxtra(int s,long l){
		long[] L = new long[size];
		for(int i=0;i<size;i++){
			L[i] = -1;
		}
		int[] v = new int[size];
		L[s] = -1;

		PriorityQueue<Pair> Q = new PriorityQueue<Pair>(new SampleComparator());
		Q.add(new Pair(l,s));

		while(!Q.isEmpty()){

			Pair C = Q.poll();
			if(v[(int)C.b]==0){
				L[(int)C.b] = C.a;
				v[(int) C.b] = 1;
				for(Edge D:list[(int) C.b])Q.add(new Pair(Math.max(L[(int)C.b],D.cost),D.to));
			}
		}

		return L;
	}
	long[] mintra(int s){
		long[] L = new long[size];
		for(int i=0;i<size;i++){
			L[i] = -1;
		}
		int[] v = new int[size];
		L[s] = s;

		PriorityQueue<Pair> Q = new PriorityQueue<Pair>(new SampleComparator().reversed());
		Q.add(new Pair(s,s));

		while(!Q.isEmpty()){

			Pair C = Q.poll();
			if(v[(int)C.b]==0){
				L[(int)C.b] = C.a;
				v[(int) C.b] = 1;
				for(Edge D:list[(int) C.b])Q.add(new Pair(Math.min(L[(int)C.b],D.cost),D.to));
			}
		}

		return L;
	}
	long Kruskal(){
		long r = 0;
		for(int i=0;i<size;i++) {
			for(Edge e:list[i]) {
				Edges.add(new LinkEdge(e.cost,i,e.to));
			}
		}
		UnionFindTree UF = new UnionFindTree(size);
		for(LinkEdge e:Edges){
			if(e.a>=0&&e.b>=0) {
				if(!UF.same(e.a,e.b)){
					r += e.L;
					UF.unite(e.a,e.b);
				}
			}
		}
		return r;
	}

	ArrayList<Integer> Kahntsort(){

		ArrayList<Integer> ans = new ArrayList<Integer>();
		PriorityQueue<Integer> q = new PriorityQueue<Integer>();
		int[] in = new int[size];
		for(int i=0;i<size;i++) {
			for(Edge e:list[i])in[e.to]++;
		}
		for(int i=0;i<size;i++) {
			if(in[i]==0)q.add(i);
		}
		while(!q.isEmpty()) {
			int v = q.poll();
			ans.add(v);
			for(Edge e:list[v]) {
				in[e.to]--;
				if(in[e.to]==0)q.add(e.to);
			}
		}
		for(int i=0;i<size;i++) {
			if(in[i]>0)return new ArrayList<Integer>();
		}
		return ans;
	}
	public Stack<Integer> findCycle() {
		Stack<Integer> ans = new Stack<Integer>();
		boolean[] v = new boolean[size];
		boolean[] f = new boolean[size];
		for(int i=0;i<size;i++) {
			if(findCycle(i,ans,v,f))break;
		}
		return ans;
	}
	private boolean findCycle(int i, Stack<Integer>ans, boolean[] v,boolean[] f) {
		v[i] = true;
		ans.push(i);
		for(Edge e:list[i]) {
			if(f[e.to]) continue;
			if(v[e.to]&&!f[e.to]) {
				return true;
			}
			if(findCycle(e.to,ans,v,f))return true;
		}
		ans.pop();
		f[i] = true;
		return false;

	}
	RootedTree dfsTree(int i) {
		int[] u = new int[size];
		RootedTree r = new RootedTree(size);
		dfsTree(i,u,r);
		return r;

	}

	private void dfsTree(int i, int[] u, RootedTree r) {
		u[i] = 1;
		r.trans[r.node] = i;
		r.rev[i] = r.node;
		r.node++;
		for(Edge e:list[i]) {
			if(u[e.to]==0) {
				r.list[i].add(e);
				u[e.to] = 1;
				dfsTree(e.to,u,r);
			}
		}


	}
}

class LightGraph {
	ArrayList<Integer>[] list;
	int size;
	TreeSet<LinkEdge> Edges = new TreeSet<LinkEdge>(new LinkEdgeComparator());

	@SuppressWarnings("unchecked")
	LightGraph(int N){
		size = N;
		list = new ArrayList[N];
		for(int i=0;i<N;i++){
			list[i] = new ArrayList<Integer>();
		}
	}






	void addEdge(int a,int b){
		list[a].add(b);
	}


	public Stack<Integer> findCycle() {
		Stack<Integer> ans = new Stack<Integer>();
		boolean[] v = new boolean[size];
		boolean[] f = new boolean[size];
		for(int i=0;i<size;i++) {
			if(findCycle(i,ans,v,f))break;
		}
		return ans;
	}
	private boolean findCycle(int i, Stack<Integer>ans, boolean[] v,boolean[] f) {
		v[i] = true;
		ans.push(i);
		for(int e:list[i]) {
			if(f[e]) continue;
			if(v[e]&&!f[e]) {
				return true;
			}
			if(findCycle(e,ans,v,f))return true;
		}
		ans.pop();
		f[i] = true;
		return false;

	}

}

class FunGraph {
	int[] list;
	int size;
	TreeSet<LinkEdge> Edges = new TreeSet<LinkEdge>(new LinkEdgeComparator());

	@SuppressWarnings("unchecked")
	FunGraph(int N){
		size = N;
		list = new int[N];
		Arrays.fill(list,-1);
	}






	void addEdge(int a,int b){
		list[a] = b;
	}


	public Stack<Integer> findCycle() {
		Stack<Integer> ans = new Stack<Integer>();
		boolean[] v = new boolean[size];
		boolean[] f = new boolean[size];
		for(int i=0;i<size;i++) {
			if(findCycle(i,ans,v,f))break;
		}
		return ans;
	}
	private boolean findCycle(int i, Stack<Integer>ans, boolean[] v,boolean[] f) {
		v[i] = true;
		ans.push(i);
		int e = list[i];
		if(e!=-1&&!f[e]) {
			if(v[e]&&!f[e]) {
				return true;
			}
			if(findCycle(e,ans,v,f))return true;
		}
		
		ans.pop();
		f[i] = true;
		return false;

	}

}


class Tree extends Graph{

	static int[][] lcat;
	static int[] depth;
	public Tree(int N) {
		super(N);
	}


	long[] tyokkei(){
		long[] a = bfs(0);


		int md = -1;
		long m = 0;
		for(int i=0;i<size;i++){
			if(m<a[i]){
				m = a[i];
				md = i;
			}
		}

		long[] b = bfs(md);
		int md2 = -1;
		long m2 = 0;
		for(int i=0;i<size;i++){
			if(m2<b[i]){
				m2 = b[i];
				md2 = i;
			}
		}
		long[] r = {m2,md,md2};
		return r;
	}
	
	int[] size(int r) {
		int[] ret = new int[size];
		dfssize(r,-1,ret);
		return ret;
	}


	private int dfssize(int i, int rev, int[] ret) {
		int sz = 1;
		for(Edge e:list[i]) {
			if(e.to!=rev) sz += dfssize(e.to,i,ret);
		}
		return ret[i] = sz;
		
	}
	void lcadfs(int i,int rev,int d) {
		lcat[0][i] = rev;
		depth[i] = d;
		for(Edge e:list[i]) {
			if(e.to!=rev)lcadfs(e.to,i,d+1);
		}
	}
	
	void buildlca(int r){
		lcat = new int[21][size];
		depth = new int[size];
		lcadfs(r,-1,0);
		for(int i=1;i<20;i++) {
			for(int j=0;j<size;j++) {
				lcat[i+1][j] = lcat[i][lcat[i][j]];
			}
		}
	}
	
	int lca(int a,int b) {
		if(depth[a]>depth[b]) {
			int tmp = a;
			a = b;
			b = tmp;
		}
		int d = depth[b]-depth[a];
		for(int i=0;i<=20;i++) {
			if(((d>>i)&1)==1)b = lcat[i][b];
		}
		if(a==b) return a;
		for(int i=20;i>=0;i--) {
			if(lcat[i][a]!=lcat[i][b]) {
				a = lcat[i][a];
				b = lcat[i][b];
			}
		}
		return lcat[0][a];
	}
	
	



}

class RootedTree extends Graph{
	int[] trans;
	int[] rev;
	int node = 0;
	RootedTree(int N){
		super(N);
		trans = new int[N];
		rev = new int[N];
	}
	public int[] parents() {
		int[] ret = new int[size];
		for(int i=0;i<size;i++) {
			for(Edge e:list[i]) {
				ret[rev[e.to]] = rev[i];
			}
		}
		ret[0] = -1;
		return ret;
	}
}
class LinkEdge{
	long L;
	int a ;
	int b;
	int id;
	LinkEdge(long l,int A,int B){
		L = l;
		a = A;
		b = B;
	}
	LinkEdge(long l,int A,int B,int i){
		L = l;
		a = A;
		b = B;
		id = i;
	}
	public boolean equals(Object o){
		LinkEdge O = (LinkEdge) o;
		return O.a==this.a&&O.b==this.b&&O.L==this.L;
	}

	public int hashCode(){
		return Objects.hash(L,a,b);
	}
}

class DoubleLinkEdge{
	double D;
	int a;
	int b;
	DoubleLinkEdge(double d,int A,int B){
		D = d;
		a = A;
		b = B;
	}
	public boolean equals(Object o){
		DoubleLinkEdge O = (DoubleLinkEdge) o;
		return O.a==this.a&&O.b==this.b&&O.D==this.D;
	}

	public int hashCode(){
		return Objects.hash(D,a,b);
	}
}


class Edge{
	int to;
	long cost;
	Edge(int a,long b){
		to = a;
		cost = b;
	}
}

class indexedEdge extends Edge{
	int id;
	indexedEdge(int a, long b, int c) {
		super(a,b);
		id = c;
	}

}

class DoubleLinkEdgeComparator implements Comparator<DoubleLinkEdge>{
	public int compare(DoubleLinkEdge P, DoubleLinkEdge Q) {
		return Double.compare(P.D,Q.D);
	}
}

class LinkEdgeComparator implements Comparator<LinkEdge>{
	public int compare(LinkEdge P, LinkEdge Q) {
		return Long.compare(P.L,Q.L);
	}
}


class Pair{
	long a;
	long b;

	Pair(long p,long q){
		this.a = p;
		this.b = q;
	}

	public boolean equals(Object o){
		Pair O = (Pair) o;
		return O.a==this.a&&O.b==this.b;
	}

	public int hashCode(){
		return Objects.hash(a,b);
	}
}

class SampleComparator implements Comparator<Pair>{
	public int compare(Pair P, Pair Q) {
		long t = P.a-Q.a;
		if(t==0){
			if(P.b==Q.b)return 0;
			return P.b>Q.b?1:-1;

		}
		return t>=0?1:-1;
	}
}


class LongIntPair{
	long a;
	int b;

	LongIntPair(long p,int q){
		this.a = p;
		this.b = q;
	}

	public boolean equals(Object o){
		LongIntPair O = (LongIntPair) o;
		return O.a==this.a&&O.b==this.b;

	}

	public int hashCode(){
		return Objects.hash(a,b);
	}
}

class LongIntComparator implements Comparator<LongIntPair>{
	public int compare(LongIntPair P, LongIntPair Q) {
		long t = P.a-Q.a;
		if(t==0){
			if(P.b>Q.b){
				return 1;
			}else{
				return -1;
			}
		}
		return t>=0?1:-1;
	}
}


class IntIntPair{
	int a;
	int b;

	IntIntPair(int p,int q){
		this.a = p;
		this.b = q;
	}
	IntIntPair(int p,int q,String s){
		if(s.equals("sort")) {
			this.a = Math.min(p,q);
			this.b = Math.max(p,q);
		}
	}


	public boolean equals(Object o){
		IntIntPair O = (IntIntPair) o;
		return O.a==this.a&&O.b==this.b;

	}

	public int hashCode(){
		return Objects.hash(a,b);
	}
}



class IntIntComparator implements Comparator<IntIntPair>{
	public int compare(IntIntPair P, IntIntPair Q) {
		int t = P.a-Q.a;
		if(t==0){
			return P.b-Q.b;
		}
		return t;
	}
}

class IntIntsecondComparator implements Comparator<IntIntPair>{
	public int compare(IntIntPair P, IntIntPair Q) {
		int t = P.b-Q.b;
		if(t==0){
			return P.a-Q.a;
		}
		return t;
	}
}




class CIPair{
	char c;
	int i;
	CIPair(char C,int I){
		c = C;
		i = I;
	}
	public boolean equals(Object o){
		CIPair O = (CIPair) o;
		return O.c==this.c&&O.i==this.i;
	}
	public int hashCode(){
		return Objects.hash(c,i);
	}
}




class DoublePair{
	double a;
	double b;

	DoublePair(double p,double q){
		this.a = p;
		this.b = q;
	}

	public boolean equals(Object o){
		DoublePair O = (DoublePair) o;
		return O.a==this.a&&O.b==this.b;

	}

	public int hashCode(){
		return Objects.hash(a,b);
	}
}
class Triplet{
	long a;
	long b;
	long c;
	Triplet(long p,long q,long r){
		a = p;
		b = q;
		c = r;
	}
	public boolean equals(Object o){
		Triplet O = (Triplet) o;
		return O.a==this.a&&O.b==this.b&&O.c==this.c?true:false;

	}

	public int hashCode(){
		return Objects.hash(a,b,c);
	}
}

class TripletComparator implements Comparator<Triplet>{
	public int compare(Triplet P, Triplet Q) {
		long t = P.a-Q.a;
		if(t==0){
			long tt = P.b-Q.b;
			if(tt==0) {
				if(P.c>Q.c) {
					return 1;
				}else if(P.c<Q.c){
					return -1;
				}else {
					return 0;
				}
			}
			return tt>0?1:-1;
		}
		return t>=0?1:-1;
	}
}
class DDComparator implements Comparator<DoublePair>{
	public int compare(DoublePair P, DoublePair Q) {
		return P.a-Q.a>=0?1:-1;
	}
}

class DoubleTriplet{
	double a;
	double b;
	double c;

	DoubleTriplet(double p,double q,double r){
		this.a = p;
		this.b = q;
		this.c = r;
	}

	public boolean equals(Object o){
		DoubleTriplet O = (DoubleTriplet) o;
		return O.a==this.a&&O.b==this.b&&O.c==this.c;

	}

	public int hashCode(){
		return Objects.hash(a,b,c);
	}
}

class DoubleTripletComparator implements Comparator<DoubleTriplet>{
	public int compare(DoubleTriplet P, DoubleTriplet Q) {
		if(P.a==Q.a) return 0;
		return P.a-Q.a>0?1:-1;
	}
}


class FastScanner {
    private final java.io.InputStream in = System.in;
    private final byte[] b = new byte[1024];
    private int p = 0;
    private int bl = 0;
    private boolean hNB() {
        if (p<bl) {
            return true;
        }else{
            p = 0;
            try {
                bl = in.read(b);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (bl<=0) {
                return false;
            }
        }
        return true;
    }

	private int rB() { if (hNB()) return b[p++]; else return -1;}
    private static boolean iPC(int c) { return 33 <= c && c <= 126;}
    private void sU() { while(hNB() && !iPC(b[p])) p++;}
    public boolean hN() { sU(); return hNB();}
    public String next() {
        if (!hN()) throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = rB();
        while(iPC(b)) {
            sb.appendCodePoint(b);
            b = rB();
        }
        return sb.toString();
    }
    public char nextChar() {
    	return next().charAt(0);
    }
    public long nextLong() {
        if (!hN()) throw new NoSuchElementException();
        long n = 0;
        boolean m = false;
        int b = rB();
        if (b=='-') {
            m=true;
            b=rB();
        }
        if (b<'0'||'9'<b) {
            throw new NumberFormatException();
        }
        while(true){
            if ('0'<=b&&b<='9') {
                n *= 10;
                n += b - '0';
            }else if(b == -1||!iPC(b)){
                return (m?-n:n);
            }else{
                throw new NumberFormatException();
            }
            b = rB();
        }
    }
    public int nextInt() {
        if (!hN()) throw new NoSuchElementException();
        long n = 0;
        boolean m = false;
        int b = rB();
        if (b == '-') {
            m = true;
            b = rB();
        }
        if (b<'0'||'9'<b) {
            throw new NumberFormatException();
        }
        while(true){
            if ('0'<=b&&b<='9') {
                n *= 10;
                n += b-'0';
            }else if(b==-1||!iPC(b)){
                return (int) (m?-n:n);
            }else{
                throw new NumberFormatException();
            }
            b = rB();
        }
    }
    public int[] nextInts(int n) {
    	int[] a = new int[n];
    	for(int i=0;i<n;i++) {
    		a[i] = nextInt();
    	}
    	return a;
    }
    public int[] nextInts(int n,int s) {
    	int[] a = new int[n+s];
    	for(int i=s;i<n+s;i++) {
    		a[i] = nextInt();
    	}
    	return a;
    }
    public long[] nextLongs(int n, int s) {
    	long[] a = new long[n+s];
    	for(int i=s;i<n+s;i++) {
    		a[i] = nextLong();
    	}
    	return a;
	}
    public long[] nextLongs(int n) {
    	long[] a = new long[n];
    	for(int i=0;i<n;i++) {
    		a[i] = nextLong();
    	}
    	return a;
    }
    public int[][] nextIntses(int n,int m){
    	int[][] a = new int[n][m];
    	for(int i=0;i<n;i++) {
    		for(int j=0;j<m;j++) {
    			a[i][j] = nextInt();
    		}
    	}
    	return a;
    }

    public String[] nexts(int n) {
    	String[] a = new String[n];
    	for(int i=0;i<n;i++) {
    		a[i] = next();
    	}
    	return a;
    }
    void nextIntses(int n,int[] ...m) {
    	int l = m[0].length;
    	for(int i=0;i<l;i++) {
    		for(int j=0;j<m.length;j++) {
    			m[j][i] = nextInt();
    		}
    	}
    }
    void nextLongses(int n,long[] ...m) {
    	int l = m[0].length;
    	for(int i=0;i<l;i++) {
    		for(int j=0;j<m.length;j++) {
    			m[j][i] = nextLong();
    		}
    	}
    }

    Graph nextyukoGraph(int n,int m) {
    	Graph G = new Graph(n);
    	for(int i=0;i<m;i++) {
    		int a = nextInt()-1;
    		int b = nextInt()-1;
    		G.addEdge(a,b);
    	}
    	return G;
    }

    Graph nextGraph(int n,int m) {
    	Graph G = new Graph(n);
    	for(int i=0;i<m;i++) {
    		int a = nextInt()-1;
    		int b = nextInt()-1;
    		G.addEdge(a,b);
    		G.addEdge(b,a);
    	}
    	return G;
    }

    Graph nextWeightedGraph(int n,int m) {
    	Graph G = new Graph(n);
    	for(int i=0;i<m;i++) {
    		int a = nextInt()-1;
    		int b = nextInt()-1;
    		long c = nextLong();
    		G.addWeightedEdge(a,b,c);
    		G.addWeightedEdge(b,a,c);
    	}
    	return G;
    }

    Tree nextTree(int n) {
    	Tree T = new Tree(n);
    	for(int i=0;i<n-1;i++) {
    		int a = nextInt()-1;
    		int b = nextInt()-1;
    		T.addEdge(a,b);
    		T.addEdge(b,a);
    	}
    	return T;
    }
}


class Mathplus{
	long mod = 1000000007;
	long[] fac;
	long[] revfac;
	long[][] comb;
	long[] pow;
	long[] revpow;
	boolean isBuild = false;
	boolean isBuildc = false;
	boolean isBuildp = false;
	int mindex = -1;
	int maxdex = -1;
	int graydiff = 0;
	int graymark = 0;

	int LIS(int N, int[] a) {
		int[] dp = new int[N+1];
		Arrays.fill(dp,(int)mod);
		for(int i=0;i<N;i++) {
			int ok = 0;
			int ng = N;
			while(ng-ok>1) {
				int mid = (ok+ng)/2;
				if(dp[mid]<a[i])ok = mid;
				else ng = mid;
			}
			dp[ok+1] = a[i];
		}
		int ok = 0;
		for(int i=1;i<=N;i++) {
			if(dp[i]<mod)ok=i;
		}
		return ok;
	}

	public Integer[] Ints(int n, int i) {
		Integer[] ret = new Integer[n];
		Arrays.fill(ret,i);
		return ret;
	}
	public Long[] Longs(int n, long i) {
		Long[] ret = new Long[n];
		Arrays.fill(ret,i);
		return ret;
	}

	public boolean nexperm(int[] p) {
		int n = p.length;
		for(int i=n-1;i>0;i--) {
			if(p[i-1]<p[i]) {
				int sw = n;
				for(int j=n-1;j>=i;j--) {
					if(p[i-1]<p[j]) {
						sw = j;
						break;
					}
				}

				int tmp = p[i-1];
				p[i-1] = p[sw];
				p[sw] = tmp;
				int[] r = new int[n];
				for(int j=i;j<n;j++) {
					r[j] = p[n-1-j+i];
				}
				for(int j=i;j<n;j++) {
					p[j] = r[j];
				}
				return true;
			}
		}
		return false;
	}

	public int[] makeperm(int n) {
		int[] a = new int[n];
		for(int i=0;i<n;i++) {
			a[i] = i;
		}
		return a;
	}

	int color(int[][] diff,int N) {

		int[] val = new int[1<<N];
		val[0] = 1;
		for(int i=0;i<(1<<N);i++) {
			for(int j=0;j<N;j++) {
				if(contains(i,j)) {
					if(val[bitremove(i,j)]==1) {
						boolean b = true;
						for(int k=0;k<N;k++) {
							if(contains(i,k)&&diff[j][k]==1) {
								b = false;
							}
						}
						if(b)val[i] = 1;
					}
					break;
				}
			}
		}
		int[] dp = new int[1<<N];
		Arrays.fill(dp,N+1);;
		dp[0] = 0;
		for(int i=0;i<(1<<N);i++) {
			for(int j=i;j>0;j=(j-1)&i) {
				if(val[j]==1)dp[i]=Math.min(dp[i],dp[i^j]+1);
			}
		}
		return dp[(1<<N)-1];
	}



	public void timeout() throws InterruptedException {
		Thread.sleep(10000);
	}

	public int gray(int i) {
		for(int j=0;j<20;j++) {
			if(contains(i,j)) {
				graydiff = j;
				if(contains(i,j+1))graymark=-1;
				else graymark = 1;
				break;
			}
		}
		return i ^ (i>>1);


	}

	public void hakidashi(long[] A) {
		Arrays.sort(A);
		int N = A.length;
		int[] index = new int[61];
		for(int i=0;i<=60;i++){
			index[i] = -1;
		}
		int searching = 60;
		int [] used = new int[N];
		while(searching>=0){
			boolean b = true;
			for(int i=N-1;i>=0;i--){
				for(int j=60;j>searching;j--){
					if((A[i]>>j&1)==1){
						if(i!=index[j]&&index[j]!=-1){
							A[i] ^= A[index[j]];
							//System.out.println(i+" changed by " + index[j]);
							//System.out.println(A[i]);
						}
					}
				}
				if((A[i]>>searching&1)==1&&used[i]==0){
					//System.out.println("find " + searching+" is "+i);
					index[searching] = i;
					searching--;
					used[i] = 1;
					b = false;
					if(searching==-1){
						searching = 0;
					}
				}
			}
			if(b){
				searching--;
			}

		}

		for(int i=N-1;i>=0;i--){
			for(int j=60;j>=searching;j--){
				if((A[i]>>j&1)==1){
					if(i!=index[j]&&index[j]!=-1){
						A[i] ^= A[index[j]];
					}
				}
			}
		}

		Arrays.sort(A);

	}

	public void printjudge(boolean b, String y, String n) {
		System.out.println(b?y:n);
	}
	public void printYN(boolean b) {
		printjudge(b,"Yes","No");
	}
	public void printyn(boolean b) {
		printjudge(b,"yes","no");
	}

	public void reverse(int[] x) {
		int[] r = new int[x.length];
		for(int i=0;i<x.length;i++)r[i] = x[x.length-1-i];
		for(int i=0;i<x.length;i++)x[i] = r[i];
	}
	public void reverse(long[] x) {
		long[] r = new long[x.length];
		for(int i=0;i<x.length;i++)r[i] = x[x.length-1-i];
		for(int i=0;i<x.length;i++)x[i] = r[i];
	}

	public DoubleTriplet Line(double x1,double y1,double x2,double y2) {
		double a = y1-y2;
		double b = x2-x1;
		double c = x1*y2-x2*y1;
		return new DoubleTriplet(a,b,c);
	}
	public double putx(DoubleTriplet T,double x) {
		return -(T.a*x+T.c)/T.b;
	}
	public double puty(DoubleTriplet T,double y) {
		return -(T.b*y+T.c)/T.a;
	}
	public double Distance(DoublePair P,DoublePair Q) {
		return Math.sqrt((P.a-Q.a) * (P.a-Q.a) + (P.b-Q.b) * (P.b-Q.b));
	}
	public double DistanceofPointandLine(DoublePair P,Triplet T) {
		return Math.abs(P.a*T.a+P.b*T.b+T.c) / Math.sqrt(T.a*T.a+T.b*T.b);
	}
	public boolean cross(long ax, long ay, long bx, long by, long cx, long cy, long dx, long dy) {
		if((ax-bx)*(cy-dy)==(ay-by)*(cx-dx)) {
			if(ax-bx!=0) {
				Range A = new Range(ax,bx);
				Range B = new Range(cx,dx);
				return A.kasanari(B)>0;
			}else {
				Range A = new Range(ay,by);
				Range B = new Range(cy,dy);
				return A.kasanari(B)>0;
			}
		}
		long ta = (cx - dx) * (ay - cy) + (cy - dy) * (cx - ax);
		long tb = (cx - dx) * (by - cy) + (cy - dy) * (cx - bx);
		long tc = (ax - bx) * (cy - ay) + (ay - by) * (ax - cx);
		long td = (ax - bx) * (dy - ay) + (ay - by) * (ax - dx);
		return((tc>=0&&td<=0)||(tc<=0&&td>=0))&&((ta>=0&&tb<=0)||(ta<=0&&tb>=0));
	}
	public boolean dcross(double ax, double ay, double bx, double by, double cx, double cy, double dx, double dy) {
		double ta = (cx - dx) * (ay - cy) + (cy - dy) * (cx - ax);
		double tb = (cx - dx) * (by - cy) + (cy - dy) * (cx - bx);
		double tc = (ax - bx) * (cy - ay) + (ay - by) * (ax - cx);
		double td = (ax - bx) * (dy - ay) + (ay - by) * (ax - dx);
		return((tc>=0&&td<=0)||(tc<=0&&td>=0))&&((ta>=0&&tb<=0)||(ta<=0&&tb>=0));
	}

	void buildFac(){
		fac = new long[10000003];
		revfac = new long[10000003];
		fac[0] = 1;
		for(int i=1;i<=10000002;i++){
			fac[i] = (fac[i-1] * i)%mod;
		}
		revfac[10000002] = rev(fac[10000002])%mod;
		for(int i=10000001;i>=0;i--) {
			revfac[i] = (revfac[i+1] * (i+1))%mod;
		}
		isBuild = true;
	}
	void buildFacn(int n){
		fac = new long[n+1];
		revfac = new long[n+1];
		fac[0] = 1;
		for(int i=1;i<=n;i++){
			fac[i] = (fac[i-1] * i)%mod;
		}
		revfac[n] = rev(fac[n])%mod;
		for(int i=n-1;i>=0;i--) {
			revfac[i] = (revfac[i+1] * (i+1))%mod;
		}
		isBuild = true;
	}
	public long[] buildrui(int[] a) {
		int n = a.length;
		long[] ans = new long[n];
		ans[0] = a[0];
		for(int i=1;i<n;i++) {
			ans[i] = ans[i-1] + a[i];
		}
		return ans;
	}
	public int[][] ibuildrui(int[][] a) {
		int n = a.length;
		int m = a[0].length;
		int[][] ans = new int[n][m];
		for(int i=1;i<n;i++) {
			for(int j=1;j<m;j++) {
				ans[i][j] = a[i][j];
			}
		}
		for(int i=1;i<n;i++) {
			for(int j=1;j<m;j++) {
				ans[i][j] += ans[i][j-1] + ans[i-1][j] - ans[i-1][j-1];
			}
		}
		return ans;
	}
	public void buildruin(int[][] a) {
		int n = a.length;
		int m = a[0].length;
		for(int i=1;i<n;i++) {
			for(int j=1;j<m;j++) {
				a[i][j] += a[i][j-1] + a[i-1][j] - a[i-1][j-1];
			}
		}
	}
	public long[][] buildrui(int[][] a) {
		int n = a.length;
		int m = a[0].length;
		long[][] ans = new long[n][m];
		for(int i=1;i<n;i++) {
			for(int j=1;j<m;j++) {
				ans[i][j] = a[i][j];
			}
		}
		for(int i=1;i<n;i++) {
			for(int j=1;j<m;j++) {
				ans[i][j] += ans[i][j-1] + ans[i-1][j] - ans[i-1][j-1];
			}
		}
		return ans;
	}
	public int getrui(int[][] r,int a,int b,int c,int d) {
		return r[c][d] - r[a-1][d] - r[c][b-1] + r[a-1][b-1];
	}
	public long getrui(long[][] r,int a,int b,int c,int d) {
		if(a<0||b<0||c>=r.length||d>=r[0].length) return mod;
		return r[c][d] - r[a-1][d] - r[c][b-1] + r[a-1][b-1];
	}

	long divroundup(long n,long d) {
		if(n==0)return 0;
		return (n-1)/d+1;
	}
	public long sigma(long i) {
		return i*(i+1)/2;
	}
	public int digit(long i) {
		int ans = 1;
		while(i>=10) {
			i /= 10;
			ans++;
		}
		return ans;

	}
	public int digitsum(long n) {
		int ans = 0;
		while(n>0) {
			ans += n%10;
			n /= 10;
		}
		return ans;
	}
	public int popcount(int i) {
		int ans = 0;
		while(i>0) {
			ans += i%2;
			i /= 2;
		}
		return ans;
	}
	public boolean contains(int S,int i) {return (S>>i&1)==1;}
	public int bitremove(int S,int i) {return S&(~(1<<i));}
	public int bitadd(int S,int i) {return S|(1<<i);}
	public boolean isSubSet(int S,int T) {return (S-T)==(S^T);}
	public boolean isDisjoint(int S,int T) {return (S+T)==(S^T);}
	public boolean contains(long S,int i) {return (S>>i&1)==1;}
	public long bitremove(long S,int i) {return S&(~(1<<i));}
	public long bitadd(long S,int i) {return S|(1<<i);}
	public boolean isSubSet(long S,long T) {return (S-T)==(S^T);}
	public boolean isDisjoint(long S,long T) {return (S+T)==(S^T);}
	public int isBigger(int[] d, int i) {
		int ok = d.length;
		int ng = -1;
		while(Math.abs(ok-ng)>1) {
			int mid = (ok+ng)/2;
			if(d[mid]>i) {
				ok = mid;
			}else {
				ng = mid;
			}
		}
		return ok;
	}
	public int isSmaller(int[] d, int i) {
		int ok = -1;
		int ng = d.length;
		while(Math.abs(ok-ng)>1) {
			int mid = (ok+ng)/2;
			if(d[mid]<i) {
				ok = mid;
			}else {
				ng = mid;
			}
		}
		return ok;
	}
	public int isBigger(long[] d, long i) {
		int ok = d.length;
		int ng = -1;
		while(Math.abs(ok-ng)>1) {
			int mid = (ok+ng)/2;
			if(d[mid]>i) {
				ok = mid;
			}else {
				ng = mid;
			}
		}
		return ok;
	}
	public int isSmaller(long[] d, long i) {
		int ok = -1;
		int ng = d.length;
		while(Math.abs(ok-ng)>1) {
			int mid = (ok+ng)/2;
			if(d[mid]<i) {
				ok = mid;
			}else {
				ng = mid;
			}
		}
		return ok;
	}
	public int isBigger(ArrayList<Integer> d, int i) {
		int ok = d.size();
		int ng = -1;
		while(Math.abs(ok-ng)>1) {
			int mid = (ok+ng)/2;
			if(d.get(mid)>i) {
				ok = mid;
			}else {
				ng = mid;
			}
		}
		return ok;
	}
	public int isSmaller(ArrayList<Integer> d, int i) {
		int ok = -1;
		int ng = d.size();
		while(Math.abs(ok-ng)>1) {
			int mid = (ok+ng)/2;
			if(d.get(mid)<i) {
				ok = mid;
			}else {
				ng = mid;
			}
		}
		return ok;
	}
	public int isBigger(ArrayList<Long> d, long i) {
		int ok = d.size();
		int ng = -1;
		while(Math.abs(ok-ng)>1) {
			int mid = (ok+ng)/2;
			if(d.get(mid)>i) {
				ok = mid;
			}else {
				ng = mid;
			}
		}
		return ok;
	}
	public int isSmaller(ArrayList<Long> d, long i) {
		int ok = -1;
		int ng = d.size();
		while(Math.abs(ok-ng)>1) {
			int mid = (ok+ng)/2;
			if(d.get(mid)<i) {
				ok = mid;
			}else {
				ng = mid;
			}
		}
		return ok;
	}
	public HashSet<Integer> primetable(int m) {
		HashSet<Integer> pt = new HashSet<Integer>();
		for(int i=2;i<=m;i++) {
			boolean b = true;
			for(int d:pt) {
				if(i%d==0) {
					b = false;
					break;
				}
			}
			if(b) {
				pt.add(i);
			}
		}
		return pt;
	}
	public ArrayList<Integer> primetablearray(int m) {
		ArrayList<Integer> al = new ArrayList<Integer>();
		Queue<Integer> q = new ArrayDeque<Integer>();
		for(int i=2;i<=m;i++) {
			q.add(i);

		}
		boolean[] b = new boolean[m+1];
		while(!q.isEmpty()) {
			int e = q.poll();
			if(!b[e]) {
				al.add(e);
				for(int j=1;e*j<=1000000;j++) {
					b[e*j] = true;
				}
			}
		}
		return al;
	}

	public boolean isprime(int e) {
		if(e==1) return false;
		for(int i=2;i*i<=e;i++) {
			if(e%i==0) return false;
		}
		return true;
	}
	public MultiSet Factrization(int e) {
		MultiSet ret = new MultiSet();
		for(int i=2;i*i<=e;i++) {
			while(e%i==0) {
				ret.add(i);
				e /= i;
			}
		}
		if(e!=1)ret.add(e);
		return ret;
	}
	public int[] hipPush(int[] a){
		int[] r = new int[a.length];
		int[] s = new int[a.length];
		for(int i=0;i<a.length;i++) {
			s[i] = a[i];
		}
		Arrays.sort(s);
		HashMap<Integer,Integer> m = new HashMap<Integer,Integer>();
		for(int i=0;i<a.length;i++) {
			m.put(s[i],i);
		}
		for(int i=0;i<a.length;i++) {
			r[i] = m.get(a[i]);
		}
		return r;
	}
	public HashMap<Integer,Integer> hipPush(ArrayList<Integer> l){
		HashMap<Integer,Integer> r = new HashMap<Integer,Integer>();
		TreeSet<Integer> s = new TreeSet<Integer>();
		for(int e:l)s.add(e);
		int p = 0;
		for(int e:s) {
			r.put(e,p);
			p++;
		}
		return r;
	}
	public TreeMap<Integer,Integer> thipPush(ArrayList<Integer> l){
		TreeMap<Integer,Integer> r = new TreeMap<Integer,Integer>();
		Collections.sort(l);
		int b = -(1000000007+9393);
		int p = 0;
		for(int e:l) {
			if(b!=e) {
				r.put(e,p);
				p++;
			}
			b=e;
		}
		return r;
	}
	int[] count(int[] a) {
		int[] c = new int[max(a)+1];
		for(int i=0;i<a.length;i++) {
			c[a[i]]++;
		}
		return c;
	}
	int[] count(int[] a, int m) {
		int[] c = new int[m+1];
		for(int i=0;i<a.length;i++) {
			c[a[i]]++;
		}
		return c;
	}
	long max(long[] a){
		long M = Long.MIN_VALUE;
		for(int i=0;i<a.length;i++){
			if(M<=a[i]){
				M =a[i];
				maxdex = i;
			}
		}
		return M;
	}
	int max(int[] a){
		int M = Integer.MIN_VALUE;
		for(int i=0;i<a.length;i++){
			if(M<=a[i]){
				M =a[i];
				maxdex = i;
			}
		}
		return M;
	}
	long min(long[] a){
		long m = Long.MAX_VALUE;
		for(int i=0;i<a.length;i++){
			if(m>a[i]){
				m =a[i];
				mindex = i;
			}
		}
		return m;
	}
	int min(int[] a){
		int m = Integer.MAX_VALUE;
		for(int i=0;i<a.length;i++){
			if(m>a[i]){
				m =a[i];
				mindex = i;
			}
		}
		return m;
	}
	long sum(long[] a){
		long s = 0;
		for(int i=0;i<a.length;i++)s += a[i];
		return s;
	}
	long sum(int[] a){
		long s = 0;
		for(int i=0;i<a.length;i++)s += a[i];
		return s;
	}
	long  sum(ArrayList<Integer> l) {
		long s = 0;
		for(int e:l)s += e;
		return s;
	}
	long gcd(long a, long b){
		a = Math.abs(a);
		b = Math.abs(b);
		if(a==0)return b;
		if(b==0)return a;
		if(a%b==0) return b;
		else return gcd(b,a%b);
	}
	int igcd(int a, int b) {
		if(a%b==0) return b;
		else return igcd(b,a%b);
	}
	long lcm(long a, long b) {return a / gcd(a,b) * b;}
	public long perm(int a,int num) {
		if(!isBuild)buildFac();
		return fac[a]*(rev(fac[a-num]))%mod;
	}
	void buildComb(int N) {
		comb = new long[N+1][N+1];
		comb[0][0] = 1;
		for(int i=1;i<=N;i++) {
			comb[i][0] = 1;
			for(int j=1;j<N;j++) {
				comb[i][j] = comb[i-1][j-1]+comb[i-1][j];
				if(comb[i][j]>mod)comb[i][j]-=mod;
			}
			comb[i][i] = 1;
		}
	}
	public long comb(int a,int num){
		if(a-num<0)return 0;
		if(num<0)return 0;
		if(!isBuild)buildFac();
		if(a>10000000) return combN(a,num);
		return fac[a] * ((revfac[num]*revfac[a-num])%mod)%mod;
	}
	long combN(int a,int num) {
		long ans = 1;
		for(int i=0;i<num;i++) {
			ans *= a-i;
			ans %= mod;
		}
		return ans * revfac[num] % mod;
	}
	long mulchoose(int n,int k) {
		if(k==0) return 1;
		return comb(n+k-1,k);
	}
	long rev(long l) {return pow(l,mod-2);}

	void buildpow(int l,int i) {
		pow = new long[i+1];
		pow[0] = 1;
		for(int j=1;j<=i;j++) {
			pow[j] = pow[j-1]*l;
			if(pow[j]>mod)pow[j] %= mod;
		}
	}
	void buildrevpow(int l,int i) {
		revpow = new long[i+1];
		revpow[0] = 1;
		long r = rev(l);
		for(int j=1;j<=i;j++) {
			revpow[j] = revpow[j-1]*r;
			if(revpow[j]>mod) revpow[j] %= mod;
		}
	}
	long pow(long l, long i) {
		if(i==0)return 1;
		else{
			if(i%2==0){
				long val = pow(l,i/2);
				return val * val % mod;
			}
			else return pow(l,i-1) * l % mod;
		}
	}
	long mon(int i) {
		long ans = 0;
		for(int k=2;k<=i;k++) {
			ans += (k%2==0?1:-1) * revfac[k];
			ans += mod;
		}
		ans %= mod;
		ans *= fac[i];
		return ans%mod;
	}
	long tent(int[] a, int l, int r) {
		if(l+1==r) return 0;
		int mid = (l+r)/2;
		long ans = tent(a,l,mid)+tent(a,mid,r);
		int[] L = new int[mid-l];
		int[] R = new int[r-mid];
		for(int i=l;i<mid;i++) {
			L[i-l] = a[i];
		}
		for(int i=mid;i<r;i++) {
			R[i-mid] = a[i];
		}
		Arrays.sort(L);
		Arrays.sort(R);
		int X = L.length;
		int Y = R.length;
		int k = -1;
		for(int i=0;i<X;i++) {
			while(k!=Y-1&&R[k+1]<L[i])k++;
			ans += k+1;
		}
		return ans;
		
	}

	long dictnum(int[] A) {
		int N = A.length;
		long ans = 0;
		BinaryIndexedTree bit = new BinaryIndexedTree(N+1);
		buildFacn(N);
		for(int i=1;i<=N;i++) {
			bit.add(i,1);
		}
		for(int i=1;i<=N;i++) {
			int a = A[i-1];
			ans += bit.sum(a-1) * fac[N-i] % mod;
			bit.add(a,-1);
		}
		return (ans+1)%mod;
	}

}




Submission Info

Submission Time
Task E - Interrupt Array
User Suunn
Language Java8 (OpenJDK 1.8.0)
Score 0
Code Size 73409 Byte
Status
Exec Time 826 ms
Memory 122772 KB

Compile Error

Note: ./Main.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 s1.txt
All 0 / 100 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt, 41.txt, 42.txt, 43.txt, 44.txt, 45.txt, 46.txt, 47.txt, 48.txt, 49.txt, 50.txt, 51.txt, 52.txt, 53.txt, 54.txt, 55.txt, s1.txt
Case Name Status Exec Time Memory
01.txt 524 ms 103836 KB
02.txt 573 ms 121620 KB
03.txt 463 ms 100296 KB
04.txt 431 ms 92208 KB
05.txt 605 ms 116908 KB
06.txt 559 ms 110928 KB
07.txt 463 ms 99672 KB
08.txt 510 ms 93332 KB
09.txt 579 ms 117808 KB
10.txt 441 ms 87688 KB
11.txt 475 ms 101456 KB
12.txt 590 ms 122772 KB
13.txt 620 ms 119636 KB
14.txt 552 ms 109316 KB
15.txt 533 ms 108720 KB
16.txt 455 ms 106216 KB
17.txt 481 ms 104904 KB
18.txt 494 ms 96564 KB
19.txt 616 ms 120484 KB
20.txt 456 ms 103880 KB
21.txt 479 ms 104136 KB
22.txt 826 ms 99748 KB
23.txt 479 ms 95724 KB
24.txt 488 ms 94892 KB
25.txt 454 ms 109748 KB
26.txt 501 ms 97788 KB
27.txt 601 ms 120460 KB
28.txt 541 ms 111700 KB
29.txt 452 ms 102280 KB
30.txt 488 ms 95704 KB
31.txt 470 ms 103292 KB
32.txt 461 ms 100292 KB
33.txt 543 ms 110776 KB
34.txt 548 ms 112968 KB
35.txt 469 ms 100000 KB
36.txt 415 ms 92756 KB
37.txt 572 ms 113360 KB
38.txt 550 ms 113076 KB
39.txt 488 ms 101936 KB
40.txt 507 ms 95824 KB
41.txt 578 ms 113208 KB
42.txt 426 ms 90544 KB
43.txt 490 ms 96180 KB
44.txt 576 ms 111280 KB
45.txt 563 ms 115204 KB
46.txt 493 ms 100080 KB
47.txt 572 ms 112624 KB
48.txt 513 ms 103300 KB
49.txt 650 ms 122056 KB
50.txt 552 ms 111432 KB
51.txt 479 ms 104908 KB
52.txt 547 ms 112776 KB
53.txt 613 ms 121076 KB
54.txt 586 ms 117276 KB
55.txt 494 ms 98268 KB
s1.txt 370 ms 91076 KB