1 2
9
 7 6
4 20 16 14 3 17 4
 1 1
1000000000
 4 2
45 44 35 38
 2 1
4 1000000000
 2 1
1 4
 100 10
246 286 693 607 87 612 909 312 621 37 801 558 504 914 416 762 187 974 976 123 635 488 416 659 988 998 93 662 92 749 889 78 214 786 735 625 921 372 713 617 975 119 402 411 878 138 548 905 802 762 940 336 529 373 745 835 805 880 816 94 166 114 475 699 974 462 61 337 555 805 968 815 392 746 591 558 740 380 668 29 881 151 387 986 174 923 541 520 998 947 535 651 103 584 664 854 180 852 726 93
 3 3
1 5 20
 2 2
7 14
 9 30111088
824713578 11195876 458715185 731769293 680826358 189542586 550198537 860586039 101083021
 5 1
23 8 83 26 18
 3 1
4 8 16
 50 100
74 55 33 5 83 24 75 59 30 36 13 4 62 28 96 17 6 35 45 53 33 11 37 93 34 79 61 72 13 31 44 75 7 3 63 46 18 16 44 89 62 25 32 12 38 55 75 56 61 82
 9 1
1 2 4 9 15 32 64 128 1024
 2 5
10 11
 3 1
1 3 6
 3 19905705
263637263 417905394 108361057
 4 1
88 55 14 39
 3 1
4 5 6
 1 1
4
 3 2
4 9 18
 2 2
3 6
 1 1
20
 2 60669400
95037700 337255240
 29 2
1 3 7 15 31 63 127 255 511 1023 2047 4095 8191 16383 32767 65535 131071 262143 524287 1048575 2097151 4194303 8388607 16777215 33554431 67108863 134217727 268435455 536870911
 5 1
100 200 400 1000 2000
 2 10
21 42
 5 3
6 6 6 13 27
 3 1
1 4 6
 2 1
3 6
 1 1
3
 2 2
2 8
 1 1000000000
1
 4 1
2 4 8 32
 4 28
34 1 86 90
 4 25
100 11 1 13
 3 6
13 26 52
 3 3
1 7 13
 3 1
2 3 6
 2 1
3 5
 2 1
2 3
 2 2
8 16
 10 295206008
67980321 440051990 883040288 135744260 96431758 242465794 576630162 972797687 356406646 547451696
 5 3
1024 4096 16384 65536 536870913
 1 4
9
 2 1
5 10
 2 1
1 1000000000
 3 165219745
737649884 652879952 506420386
 3 72014068
430005292 807436976 828082746
 3 1
3 6 9
 2 2
8 11
 5 2
86 81 53 25 18
 1 1
2
 2 1
4 8
 3 2
4 5 6

2 1 29 4 28 1 1 1 1 2 4 1 0 4 0 1 3 4 1 1 1 0 4 1 27 7 1 2 1 1 1 1 0 1 1 1 1 1 0 1 0 1 0 24 1 2 29 1 2 1 1 4 0 1 0
import java.io.*;
import java.math.*;
import java.security.KeyStore.Entry;
import java.util.*;
	
		
		
		
		
			public class Q1 {
				
				static long MOD = 1000000007;
				static boolean b[], b1[], check;
				static ArrayList<Integer>[] amp, pa;
				static ArrayList<Pair>[] amp1;
				static ArrayList<Pair>[][] damp;
				static int left[],right[],end[],sum[],dist[],cnt[],start[],color[],parent[],prime[],size[];
				static int ans = 0,k;
				static int p = 0;
				static FasterScanner sc = new FasterScanner(System.in);
				static Queue<Integer> q = new LinkedList<>();
				static BufferedWriter log;
				static HashSet<Pair> hs;
				static HashMap<Pair,Integer> hm;
				static PriorityQueue<Integer> pri[];
				static ArrayList<Integer>[] level;
				static Stack<Integer> st;
				static boolean boo[][];
				static Pair prr[];
				static long parent1[],parent2[],size1[],size2[],arr1[],SUM[],lev[], fibo[];
				static int arr[], ver[][];
				static private PrintWriter out = new PrintWriter(System.out);
				public static void main(String[] args) throws Exception {
			    	/*new Thread(null, new Runnable() {
						public void run() {
							try {
		
						} catch (Exception e) {
								System.out.println(e);
							}
						}
					}, "1", 1 << 26).start();*/
					soln();
				}
				private static boolean oj = System.getProperty("ONLINE_JUDGE") != null;
				private static void tr(Object... o) {
					if (!oj)
						System.out.println(Arrays.deepToString(o));
				}
				static int dp[][];
				static int N,K,T,A,B;
				static long time;
				static int cost[][];
				static boolean b11[];
				static HashMap<Integer,Integer> h = new HashMap<>();
				static HashSet<Pair> chec;
				static long ans1;		static long ans2;
				static int BLOCK, MAX = 200000;
				static double pi = Math.PI;
				static int Arr[], Brr[], pow[],  M;
				static long fact[] = new long[100000+1];
				static HashMap<Integer,Long> hm1;
				static HashSet<Integer> hs1[], hs2[];
				static String[] str2;
				static char[] ch1, ch2;
				static int[] s,f,D;
				static int tf,ts;
				//static PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
				public static void soln() throws IOException {
					//FasterScanner sc = new FasterScanner(new FileInputStream("C:\\Users\\Admin\\Desktop\\QAL2.txt"));
					//PrintWriter log = new PrintWriter("C:\\Users\\Admin\\Desktop\\out");
					log = new BufferedWriter(new OutputStreamWriter(System.out));
					
					log.close();
				}
				static int fa = -1;
				static long nCr1(int n, int r){
					if(n<r) return 0;
					return (((fact[n] * modInverse(fact[n-r], MOD))%MOD)*modInverse(fact[r], MOD))%MOD;
				}
				static class Node{
					Node arr[] = new Node[2]; 
					int cnt[] = new int[2];
				}
				public static class Trie{
					Node root;
					public Trie(){
						root = new Node();
					}
					public void insert(String x){
						Node n = root;
						for(int i = 0;i < x.length() ;i++){
							int a1 = x.charAt(i)-'0';
							if(n.arr[a1]!=null){
								n.cnt[a1]++;
								n = n.arr[a1];
								continue;
							}
							n.arr[a1] = new Node();
							n.cnt[a1]++;
							n = n.arr[a1];
						}
					}
					public void delete(String x){
						Node n = root;
						for(int i = 0;i < x.length() ;i++){
							int a1 = x.charAt(i)-'0';
							if(n.cnt[a1]==1){
								n.arr[a1] = null;
								return;
							}
							else {
								n.cnt[a1]--;
								n = n.arr[a1];
							}
						}
					}
					public long get(String x){
						Node n = root;
						long ans = 0;
						for(int i = 0;i < x.length() ;i++){
							int a1 = '1' - x.charAt(i);
							if(n.arr[a1]!=null){
								ans += Math.pow(2, 30-i);
								n = n.arr[a1];
							}
							else n = n.arr[1-a1];
						//	System.out.println(ans);
						}
						return ans;
					}
				}
				public static class FenwickTree {
					
				    int[] array; // 1-indexed array, In this array We save cumulative information to perform efficient range queries and updates
	
				    public FenwickTree(int size) {
				        array = new int[size + 1];
				    }
				    public int rsq(int ind) {
				        assert ind > 0;
				        int sum = 0;
				        while (ind > 0) {
				            sum += array[ind];
				            //Extracting the portion up to the first significant one of the binary representation of 'ind' and decrementing ind by that number
				            ind -= ind & (-ind);
				        }
				        return sum;
				    }
				    public int rsq(int a, int b) {
				        assert b >= a && a > 0 && b > 0;
				        return rsq(b) - rsq(a - 1);
				    }
				    public void update(int ind, int value) {
				        assert ind > 0;
				        while (ind < array.length) {
				            array[ind] += value;
				            //Extracting the portion up to the first significant one of the binary representation of 'ind' and incrementing ind by that number
				            ind += ind & (-ind);
				        }
				    }
	
				    public int size() {
				        return array.length - 1;
				    }
				}
				static double power(double x, long y)
				{
				    if (y == 0)
				        return 1;
				    double p = power(x, y/2);
				    p = (p * p);
				 
				    return (y%2 == 0)? p : (x * p);
				}
				static void Bfs(int x){
					q.add(x);
					b[x] = true;
					while(!q.isEmpty()){
						int y = q.poll();
						b[y] = true;
						for(int p:hs2[y]){
							if(!b[p]){
								if(!hs1[y].contains(p)) dist[p] = dist[y]-1;
								else dist[p] = dist[y]+1;
								q.add(p);
							}
						}
					}
				}
				static int Dfs(int x, int val){
					b[x] = true;
					for(int p:hs2[x]){
						if(!b[p]){
							if(!hs1[x].contains(p)) val++;
							val += Dfs(p,0);
						}
					}
					return val;
				}
				static long nCr(int n, int r){
					if(n<r) return 0;
					else return (((fact[n]*modInverse(fact[r], MOD))%MOD)*modInverse(fact[n-r], MOD))%MOD;
				}
				static void dfs1(int x, int p){
					arr1[x] += lev[x];
					for(int v:amp[x]){
						if(v!=p){
							dfs1(v,x);
						}
					}
				}
				static void bfs(){
					q = new LinkedList<>();
					q.add(0);
					while(!q.isEmpty()){
						int y = q.poll();
						b[y] = true;
						level[dist[y]].add(start[y]);
						for(int x:amp[y]){
							if(!b[x]){
								q.add(x);
								dist[x] = 1+dist[y];	
							}
						}
					}
				}
				
				
				static void bfs(int x){
					
				}
				public static void seive(int n){
					b = new boolean[(n+1)];
					Arrays.fill(b, true);
					b[1] = true;
					for(int i = 2;i*i<=n;i++){
						if(b[i]){
							for(int p = 2*i;p<=n;p+=i){
								b[p] = false;
							}
						}
					}
					/*for(int i = 2;i<=n;i++){
						if(b[i]) prime[i] = i;
					}*/
				}
				
				static class Graph{
					int vertex;
					int weight;
					Graph(int v, int w){
						vertex = v;
						weight = w;
					}
				}
				static class Pair implements Comparable<Pair> {
					int u;
					long v;
					int ans;
					public Pair(){
						u = 0;
						v = 0;
					}
					public Pair(int u, long v, int ans) {
						this.u = u;
						this.v = v;
						this.ans = ans;
					}
					public int hashCode() {
						return Objects.hash();
					}
					public boolean equals(Object o) {
						Pair other = (Pair) o;
						return ((u == other.u && v == other.v && ans == other.ans));
					}
			 
					public int compareTo(Pair other) {
						//return Double.compare(ans, other.ans);
						return Long.compare(u, other.u) != 0 ? (Long.compare(u, other.u)) : 
							(Long.compare(v, other.v) != 0 ? (Long.compare(v, other.v)):(Long.compare(ans, other.ans)));
					}
					
					public String toString() {
						return "[u=" + u + ", v=" + v + "]";
					}
				}
				
				public static void buildGraph(int n){
					for(int i =0;i<n;i++){
						int x = sc.nextInt()-1, y = sc.nextInt()-1;
						//hm.put(new Pair(x,y), i+1);
						hs1[x].add(y);
						hs2[y].add(x);
						hs2[x].add(y);
					}
				}
				
				
				public static int getParent(long x){
					while(parent[(int) x]!=x){
						parent[ (int) x] = parent[(int) parent[ (int) x]];
						x = parent[ (int) x];
					}
					return (int) x;
				}
				static long min(long a, long b, long c){
					if(a<b && a<c) return a;
					if(b<c) return b;
					return c;
				}
				/*
				
				static class Pair3{
					int x, y ,z;
					Pair3(int x, int y, int z){
						this.x = x;
						this.y = y;
						this.z = z;
					}
				}*/
				 static void KMPSearch(String pat, String txt)
				    {
				        int M = pat.length();
				        int N = txt.length();
				 
				        // create lps[] that will hold the longest
				        // prefix suffix values for pattern
				        int lps[] = new int[M];
				        int j = 0;  // index for pat[]
				 
				        // Preprocess the pattern (calculate lps[]
				        // array)
				        computeLPSArray(pat,M,lps);
				 
				        int i = 0;  // index for txt[]
				        while (i < N)
				        {
				            if (pat.charAt(j) == txt.charAt(i))
				            {
				                j++;
				                i++;
				            }
				            if (j == M)
				            {
				               // parent.add((i-j));
				                j = lps[j-1];
				            }
				 
				            // mismatch after j matches
				            else if (i < N && pat.charAt(j) != txt.charAt(i))
				            {
				                // Do not match lps[0..lps[j-1]] characters,
				                // they will match anyway
				                if (j != 0)
				                    j = lps[j-1];
				                else
				                    i = i+1;
				            }
				        }
				    }
				 static void computeLPSArray(String pat, int M, int lps[])
				    {
				        // length of the previous longest prefix suffix
				        int len = 0;
				        int i = 1;
				        lps[0] = 0;  // lps[0] is always 0
				 
				        // the loop calculates lps[i] for i = 1 to M-1
				        while (i < M)
				        {
				            if (pat.charAt(i) == pat.charAt(len))
				            {
				                len++;
				                lps[i] = len;
				                i++;
				            }
				            else  // (pat[i] != pat[len])
				            {
				                // This is tricky. Consider the example.
				                // AAACAAAA and i = 7. The idea is similar 
				                // to search step.
				                if (len != 0)
				                {
				                    len = lps[len-1];
				 
				                    // Also, note that we do not increment
				                    // i here
				                }
				                else  // if (len == 0)
				                {
				                    lps[i] = len;
				                    i++;
				                }
				            }
				        }
				    }
				private static void permutation(String prefix, String str) {
				    int n = str.length();
				    if (n == 0); //hs.add(prefix);
				    else {
				        for (int i = 0; i < n; i++)
				            permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n));
				    }
				}
				
				public static void buildTree(int n){
					int arr[] = sc.nextIntArray(n);
					for(int i = 0;i<n;i++){
						int x = arr[i]-1;
						amp[i+1].add(x);
						amp[x].add(i+1);
					}
				}
				
				static class SegmentTree {
					boolean st[];
					boolean lazy[];
		
					SegmentTree(int n) {
						int size = 4 * n;
						st = new boolean[size];
						Arrays.fill(st, true);
						lazy = new boolean[size];
						Arrays.fill(lazy, true);
						//build(0, n - 1, 1);
					}
					
					/*long[] build(int ss, int se, int si) {
						if (ss == se) {
							st[si][0] = 1;
							st[si][1] = 1;
							st[si][2] = 1;
							return st[si];
						}
						int mid = (ss + se) / 2;
						long a1[] = build(ss, mid, si * 2), a2[] = build(mid + 1, se,
								si * 2 + 1);
						long ans[] = new long[3];
						if (arr[mid] < arr[mid + 1]) {
							ans[1] = Math.max(a2[1], Math.max(a1[1], a1[2] + a2[0]));
							if (a1[1] == (mid - ss + 1))
								ans[0] = ans[1];
							else
								ans[0] = a1[0];
							if (a2[2] == (se - mid))
								ans[2] = ans[1];
							else
								ans[2] = a2[2];
						} else {
							ans[1] = Math.max(a1[1], a2[1]);
							ans[0] = a1[0];
							ans[2] = a2[2];
						}
						st[si] = ans;
						return st[si];
					}*/
		
					void update(int si, int ss, int se, int idx, long x) {
						if (ss == se) {
							//arr[idx] += val;
							st[si]=false;
						} 
						else {
							int mid = (ss + se) / 2;
							if(ss <= idx && idx <= mid)
					        {
					             update(2*si, ss, mid, idx, x);
					        }
					        else
					        { update(2*si+1, mid+1, se, idx, x);
					        }
							st[si] = st[2*si]|st[2*si+1];
						}
					}
					/*boolean get(int qs, int qe, int ss, int se, int si){
						if(qs>se || qe<ss) return 0;
						if (qs <= ss && qe >= se) {
							return st[si];
						}
						int mid = (ss+se)/2;
						return get(qs, qe, ss, mid, si * 2)+get(qs, qe, mid + 1, se, si * 2 + 1);
					}*/
					void updateRange(int node, int start, int end, int l, int r, boolean val)
					{
					    if(!lazy[node])
					    { 
					        // This node needs to be updated
					        st[node] = lazy[node];    // Update it
					        if(start != end)
					        {
					            lazy[node*2] = lazy[node];                  // Mark child as lazy
					            lazy[node*2+1] = lazy[node];                // Mark child as lazy
					        }
					        lazy[node] = true;                                  // Reset it
					    }
					    if(start > end || start > r || end < l)              // Current segment is not within range [l, r]
					        return;
					    if(start >= l && end <= r)
					    {
					        // Segment is fully within range
					        st[node] =  val;
					        if(start != end)
					        {
					            // Not leaf node
					            lazy[node*2] = val;
					            lazy[node*2+1] = val;
					        }
					        return;
					    }
					    int mid = (start + end) / 2;
					    updateRange(node*2, start, mid, l, r, val);        // Updating left child
					    updateRange(node*2 + 1, mid + 1, end, l, r, val);   // Updating right child
					    st[node] = st[node*2] | st[node*2+1];        // Updating root with max value 
					}
		
					boolean queryRange(int node, int start, int end, int l, int r)
					{
					    if(start > end || start > r || end < l)
					        return false;         // Out of range
					    if(!lazy[node])
					    {
					        // This node needs to be updated
					        st[node] = lazy[node];            // Update it
					        if(start != end)
					        {
					            lazy[node*2] = lazy[node];         // Mark child as lazy
					            lazy[node*2+1] = lazy[node];    // Mark child as lazy
					        }
					        lazy[node] = true;                 // Reset it
					    }
					    if(start >= l && end <= r)             // Current segment is totally within range [l, r]
					        return  st[node];
					    int mid = (start + end) / 2;
					    boolean p1 = queryRange(node*2, start, mid, l, r);         // Query left child
					    boolean b = queryRange(node*2 + 1, mid + 1, end, l, r); // Query right child
					    return (p1 | b);
					}
					void print() {
						for (int i = 0; i < st.length; i++) {
							System.out.print(st[i]+" ");
						}
						System.out.println();
					}
				}
				static int convert(int x){
					int cnt = 0;
					String str = Integer.toBinaryString(x);
					//System.out.println(str);
					for(int i = 0;i<str.length();i++){
						if(str.charAt(i)=='1'){
							cnt++;
						}
					}
					int ans = (int) Math.pow(3, 6-cnt);
					return ans;
				}
				static class Node2{
					Node2 left = null;
					Node2 right = null;
					Node2 parent = null;
					int data;
				}
				static boolean check(char ch[][], int i, int j){
					if(ch[i][j]=='O') return false;
					char c = ch[i][j];
					ch[i][j] = 'X';
					if(c=='X'){
					if(i>=4){
						int x = 0;
						int l = 0;
						for(x = 0;x<=4;x++){
							if(ch[i-x][j]!='X'){ if(ch[i-x][j]!='.') break;else l++;}
						}
						if(x==5 && l<=1) return true;
						l = 0;
						if(j>=4){
							for(x = 0;x<=4;x++){
								if(ch[i-x][j-x]!='X'){ if(ch[i-x][j-x]!='.') break; else l++;}
							}
							if(x==5 && l<=1) return true;
							 l =0;
							for(x = 0;x<=4;x++){
								if(ch[i][j-x]!='X'){ if(ch[i][j-x]!='.') break; else l++;}
							}
							if(x==5 && l<=1) return true;
						}
						if(j<=5){
							l = 0;
							for(x = 0;x<=4;x++){
								if(ch[i][j+x]!='X'){ if(ch[i][j+x]!='.') break; else l++;}
							}
							if(x==5 && l<=1) return true;
							l = 0;
							for(x = 0;x<=4;x++){
								if(ch[i-x][j+x]!='X'){ if(ch[i-x][j+x]!='.') break; else l++;}
							}
							if(x==5 && l<=1) return true;
						}
					}
					if(i<=5){
						int x = 0;
						int l = 0;
						for(x = 0;x<=4;x++){
							if(ch[i+x][j]!='X'){ if(ch[i+x][j]!='.') break; else l++;}
						}
						if(x==5 && l<=1) return true;
						l = 0;
						if(j>=4){
							for(x = 0;x<=4;x++){
								if(ch[i+x][j-x]!='X'){ if(ch[i+x][j-x]!='.') break; else l++;}
							}
							if(x==5 && l<=1) return true;
							 l =0;
							for(x = 0;x<=4;x++){
								if(ch[i][j-x]!='X'){ if(ch[i][j-x]!='.') break; else l++;}
							}
							if(x==5 && l<=1) return true;
						}
						if(j<=5){
							l = 0;
							for(x = 0;x<=4;x++){
								if(ch[i][j+x]!='X'){ if(ch[i][j+x]!='.') break; else l++;}
							}
							if(x==5 && l<=1) return true;
							l = 0;
							for(x = 0;x<=4;x++){
								if(ch[i+x][j+x]!='X'){ if(ch[i+x][j+x]!='.') break; else l++;}
							}
							if(x==5 && l<=1) return true;
						}
					}
					}
					else{
						if(i>=4){
							int x = 0;
							int l = 0;
							for(x = 0;x<=4;x++){
								if(ch[i-x][j]!='X'){ if(ch[i-x][j]!='.') break;else l++;}
							}
							if(x==5 && l<=0) return true;
							l = 0;
							if(j>=4){
								for(x = 0;x<=4;x++){
									if(ch[i-x][j-x]!='X'){ if(ch[i-x][j-x]!='.') break; else l++;}
								}
								if(x==5 && l<=0) return true;
								 l =0;
								for(x = 0;x<=4;x++){
									if(ch[i][j-x]!='X'){ if(ch[i][j-x]!='.') break; else l++;}
								}
								if(x==5 && l<=0) return true;
							}
							if(j<=5){
								l = 0;
								for(x = 0;x<=4;x++){
									if(ch[i][j+x]!='X'){ if(ch[i][j+x]!='.') break; else l++;}
								}
								if(x==5 && l<=0) return true;
								l = 0;
								for(x = 0;x<=4;x++){
									if(ch[i-x][j+x]!='X'){ if(ch[i-x][j+x]!='.') break; else l++;}
								}
								if(x==5 && l<=0) return true;
							}
						}
						if(i<=5){
							int x = 0;
							int l = 0;
							for(x = 0;x<=4;x++){
								if(ch[i+x][j]!='X'){ if(ch[i+x][j]!='.') break; else l++;}
							}
							if(x==5 && l<=0) return true;
							l = 0;
							if(j>=4){
								for(x = 0;x<=4;x++){
									if(ch[i+x][j-x]!='X'){ if(ch[i+x][j-x]!='.') break; else l++;}
								}
								if(x==5 && l<=0) return true;
								 l =0;
								for(x = 0;x<=4;x++){
									if(ch[i][j-x]!='X'){ if(ch[i][j-x]!='.') break; else l++;}
								}
								if(x==5 && l<=0) return true;
							}
							if(j<=5){
								l = 0;
								for(x = 0;x<=4;x++){
									if(ch[i][j+x]!='X'){ if(ch[i][j+x]!='.') break; else l++;}
								}
								if(x==5 && l<=0) return true;
								l = 0;
								for(x = 0;x<=4;x++){
									if(ch[i+x][j+x]!='X'){ if(ch[i+x][j+x]!='.') break; else l++;}
								}
								if(x==5 && l<=0) return true;
							}
						}
					}
					ch[i][j] = c;
					
					return false;
				}
				static class BinarySearchTree{
					Node2 root = null;
					int height = 0;
					int max = 0;
					int cnt = 1;
					ArrayList<Integer> parent = new ArrayList<>();
					HashMap<Integer, Integer> hm = new HashMap<>();
					public void insert(int x){
						Node2 n = new Node2();
						n.data = x;
						if(root==null){
							root = n;
						}
						else{
							Node2 temp = root,temb = null;
							while(temp!=null){
								temb = temp;
								if(x>temp.data) temp = temp.right;
								else temp = temp.left;
							}
							if(x>temb.data) temb.right = n;
							else temb.left = n;
							n.parent = temb;
							parent.add(temb.data);
						}
					}
					public Node2 getSomething(int x, int y, Node2 n){
						if(n.data==x || n.data==y) return n;
						else if(n.data>x && n.data<y) return n;
						else if(n.data<x && n.data<y) return getSomething(x,y,n.right);
						else return getSomething(x,y,n.left);
					}
					public Node2 search(int x,Node2 n){
						if(x==n.data){
							max = Math.max(max, n.data);
							return n;
						}
						if(x>n.data){
							max = Math.max(max, n.data);
							return search(x,n.right);
						}
						else{
							max = Math.max(max, n.data);
							return search(x,n.left);
						}
					}
					public int getHeight(Node2 n){
						if(n==null) return 0;
						height = 1+ Math.max(getHeight(n.left), getHeight(n.right));
						return height;
					}
				}
				static long findDiff(long[] arr, long[] brr, int m){
					int i = 0, j = 0;
					long fa = 1000000000000L;
					while(i<m && j<m){
						long x = arr[i]-brr[j];
						if(x>=0){
							if(x<fa) fa = x;
							j++;
						}
						else{
							if((-x)<fa) fa = -x;
							i++;
						}
					}
					return fa;
				}
				public static long max(long x, long y, long z){
					if(x>=y && x>=z) return x;
					if(y>=x && y>=z) return y;
					return z;
				}
				
				static long modInverse(long a, long mOD2){
				            return  power(a, mOD2-2, mOD2);
				}
				static long power(long x, long y, long m)
				{
				    if (y == 0)
				        return 1;
				    long p = power(x, y/2, m) % m;
				    p = (p * p) % m;
				 
				    return (y%2 == 0)? p : (x * p) % m;
				}
				static long d,x,y;
				public static void extendedEuclidian(long a, long b){
					if(b == 0) {
				        d = a;
				        x = 1;
				        y = 0;
				    }
				    else {
				        extendedEuclidian(b, a%b);
				        int temp = (int) x;
				        x = y;
				        y = temp - (a/b)*y;
				    }
				}
				
				public static long gcd(long n, long m){
					if(m!=0) return gcd(m,n%m);
					else return n;
				}
				
				static BufferedReader reader;
			    static StringTokenizer tokenizer;
			    static PrintWriter writer;
			
			
			   
			    static class FasterScanner {
		
					private final InputStream stream;
					private final byte[] buf = new byte[8192];
					private int curChar, snumChars;
					private SpaceCharFilter filter;
		
					public FasterScanner(InputStream stream) {
						this.stream = stream;
					}
		
					public int snext() {
						if (snumChars == -1)
							throw new InputMismatchException();
						if (curChar >= snumChars) {
							curChar = 0;
							try {
								snumChars = stream.read(buf);
							} catch (IOException e) {
								throw new InputMismatchException();
							}
							if (snumChars <= 0)
								return -1;
						}
						return buf[curChar++];
					}
		
					public int nextInt() {
						int c = snext();
						while (isSpaceChar(c)) {
							c = snext();
						}
						int sgn = 1;
						if (c == '-') {
							sgn = -1;
							c = snext();
						}
						int res = 0;
						do {
							if (c < '0' || c > '9')
								throw new InputMismatchException();
							res *= 10;
							res += c - '0';
							c = snext();
						} while (!isSpaceChar(c));
						return res * sgn;
					}
		
					public long nextLong() {
						int c = snext();
						while (isSpaceChar(c)) {
							c = snext();
						}
						int sgn = 1;
						if (c == '-') {
							sgn = -1;
							c = snext();
						}
						long res = 0;
						do {
							if (c < '0' || c > '9')
								throw new InputMismatchException();
							res *= 10;
							res += c - '0';
							c = snext();
						} while (!isSpaceChar(c));
						return res * sgn;
					}
		
					public int[] nextIntArray(int n) {
						int a[] = new int[n];
						for (int i = 0; i < n; i++) {
							a[i] = nextInt();
						}
						return a;
					}
		
					public long[] nextLongArray(int n) {
						long a[] = new long[n];
						for (int i = 0; i < n; i++) {
							a[i] = nextLong();
						}
						return a;
					}
			                
					public String readString() {
						int c = snext();
						while (isSpaceChar(c)) {
							c = snext();
						}
						StringBuilder res = new StringBuilder();
						do {
							res.appendCodePoint(c);
							c = snext();
						} while (!isSpaceChar(c));
						return res.toString();
					}
		
					public String nextLine() {
						int c = snext();
						while (isSpaceChar(c))
							c = snext();
						StringBuilder res = new StringBuilder();
						do {
							res.appendCodePoint(c);
							c = snext();
						} while (!isEndOfLine(c));
						return res.toString();
					}
		
					public boolean isSpaceChar(int c) {
						if (filter != null)
							return filter.isSpaceChar(c);
						return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
					}
		
					private boolean isEndOfLine(int c) {
						return c == '\n' || c == '\r' || c == -1;
					}
		
					public interface SpaceCharFilter {
						public boolean isSpaceChar(int ch);
					}
				}
			}  