import java.awt.Point;
import java.io.*;
import java.math.BigInteger;
import java.nio.charset.*;
import java.util.*;
import java.util.function.*;
class Main{
	static boolean autoFlush = false;
	static SimpleScanner sc = new SimpleScanner(System.in);
	static SimpleWriter out = new SimpleWriter(System.out,autoFlush);
	public static void main(String[] args){

		int N = sc.nextInt();
		int K = sc.nextInt();
		long[] A = sc.nextLong(N);
		HashMap<Long,Integer> map = new HashMap<>();
		for(int i=0;i<=K;i++){
			map.merge(A[i]+i,i,Integer::min);
			map.merge(Math.max(A[i]-i,0),i,Integer::min);
		}
		for(int i=1;i<N;i++){
			HashMap<Long,Integer> next = new HashMap<>();
			for(Map.Entry<Long,Integer> entry:map.entrySet()){
				long num = entry.getKey();
				int count = entry.getValue();
				for(int j=0;j+count<=K;j++){
					next.merge(MathFunction.gcd(A[i]+j,num),j+count,Integer::min);
					next.merge(MathFunction.gcd(Math.max(A[i]-j,0),num),j+count,Integer::min);
				}
			}
			map = next;
		}
		long ans = 1;
		for(long key:map.keySet())
			ans = Math.max(ans,key);
		out.println(ans);

		out.close();
	}
}
/*////////////////////////////
	* My Library *
	@author  viral
*/////////////////////////////
class Factorial{
	long[] fact, inFact;
	long mod;
	Factorial(int N,long mod){
		fact = new long[N+1];
		fact[0] = fact[1] = 1;
		for(int i = 2;i<=N;++i)
			fact[i] = fact[i-1]*i%mod;
		inFact = new long[N+1];
		inFact[N] = MathFunction.modPow(fact[N],mod-2,mod);
		for(int i = N;i>0;--i)
			inFact[i-1] = inFact[i]*i%mod;
		inFact[0] = 1;
		this.mod = mod;
	}
	long getFact(int num){
		return fact[num];
	}
	long getInFact(int num){
		return inFact[num];
	}
	long getInverse(int num){
		return fact[num-1]*inFact[num]%mod;
	}
	long getCombi(int a,int b){
		if(a<b||a<0||b<0)
			return 0;
		return (fact[a]*inFact[a-b]%mod)*inFact[b]%mod;
	}
}
class ArrayFunction{
	static int[][] rotateR(int[][] array){
		int[][] ans = new int[array[0].length][array.length];
		for(int i = 0;i<ans.length;++i)
			for(int j = 0;j<ans[i].length;++j)
				ans[i][j] = array[ans[i].length-j-1][i];
		return ans;
	}
	static long[][] rotateR(long[][] array){
		long[][] ans = new long[array[0].length][array.length];
		for(int i = 0;i<ans.length;++i)
			for(int j = 0;j<ans[i].length;++j)
				ans[i][j] = array[ans[i].length-j-1][i];
		return ans;
	}
	static char[][] rotateR(char[][] array){
		char[][] ans = new char[array[0].length][array.length];
		for(int i = 0;i<ans.length;++i)
			for(int j = 0;j<ans[i].length;++j)
				ans[i][j] = array[ans[i].length-j-1][i];
		return ans;
	}
	static double[][] rotateR(double[][] array){
		double[][] ans = new double[array[0].length][array.length];
		for(int i = 0;i<ans.length;++i)
			for(int j = 0;j<ans[i].length;++j)
				ans[i][j] = array[ans[i].length-j-1][i];
		return ans;
	}
	static boolean[][] rotateR(boolean[][] array){
		boolean[][] ans = new boolean[array[0].length][array.length];
		for(int i = 0;i<ans.length;++i)
			for(int j = 0;j<ans[i].length;++j)
				ans[i][j] = array[ans[i].length-j-1][i];
		return ans;
	}
	static <E> E[][] rotateR(E[][] array,E[][] ans){
		for(int i = 0;i<ans.length;++i)
			for(int j = 0;j<ans[i].length;++j)
				ans[i][j] = array[ans[i].length-j-1][i];
		return ans;
	}
	static int[][] rotateL(int[][] array){
		int[][] ans = new int[array[0].length][array.length];
		for(int i = 0;i<ans.length;++i){
			int index = i;
			Arrays.setAll(ans[i],k->array[k][ans.length-index-1]);
		}
		return ans;
	}
	static long[][] rotateL(long[][] array){
		long[][] ans = new long[array[0].length][array.length];
		for(int i = 0;i<ans.length;++i){
			int index = i;
			Arrays.setAll(ans[i],k->array[k][ans.length-index-1]);
		}
		return ans;
	}
	static char[][] rotateL(char[][] array){
		char[][] ans = new char[array[0].length][array.length];
		for(int i = 0;i<ans.length;++i)
			for(int j = 0;j<ans[i].length;++j)
				ans[i][j] = array[j][ans.length-i-1];
		return ans;
	}
	static double[][] rotateL(double[][] array){
		double[][] ans = new double[array[0].length][array.length];
		for(int i = 0;i<ans.length;++i)
			for(int j = 0;j<ans[i].length;++j)
				ans[i][j] = array[j][ans.length-i-1];
		return ans;
	}
	static boolean[][] rotateL(boolean[][] array){
		boolean[][] ans = new boolean[array[0].length][array.length];
		for(int i = 0;i<ans.length;++i)
			for(int j = 0;j<ans[i].length;++j)
				ans[i][j] = array[j][ans.length-i-1];
		return ans;
	}
	static <E> E[][] rotateL(E[][] array,E[][] ans){
		for(int i = 0;i<ans.length;++i)
			for(int j = 0;j<ans[i].length;++j)
				ans[i][j] = array[j][ans.length-i-1];
		return ans;
	}
	static int lis(int[] array){
		return lis(array,false);
	}
	static int lis(int[][] arrays,int p){
		return lis(arrays,p,false);
	}
	static int lis(long[] array){
		return lis(array,false);
	}
	static int lis(long[][] arrays,int p){
		return lis(arrays,p,false);
	}
	static int lis(int[] array,boolean include){
		int[] list = new int[array.length];
		Arrays.fill(list,Integer.MAX_VALUE);
		for(int num: array){
			int index = include?Searcher.overSearch(list,num):Searcher.upSearch(list,num);
			list[index] = Math.min(list[index],num);
		}
		int answer = Searcher.underSearch(list,Integer.MAX_VALUE);
		return answer+1;
	}
	static int lis(int[][] arrays,int p,boolean include){
		int[] list = new int[arrays.length];
		Arrays.fill(list,Integer.MAX_VALUE);
		for(int[] array: arrays){
			int index = include?Searcher.overSearch(list,array[p]):Searcher.upSearch(list,array[p]);
			list[index] = Math.min(list[index],array[p]);
		}
		int answer = Searcher.underSearch(list,Integer.MAX_VALUE);
		return answer+1;
	}
	static int lis(long[] array,boolean include){
		long[] list = new long[array.length];
		Arrays.fill(list,Long.MAX_VALUE);
		for(long num: array){
			int index = include?Searcher.overSearch(list,num):Searcher.upSearch(list,num);
			list[index] = Math.min(list[index],num);
		}
		int answer = Searcher.underSearch(list,Long.MAX_VALUE);
		return answer+1;
	}
	static int lis(long[][] arrays,int p,boolean include){
		long[] list = new long[arrays.length];
		Arrays.fill(list,Long.MAX_VALUE);
		for(long[] array: arrays){
			int index = include?Searcher.overSearch(list,array[p]):Searcher.upSearch(list,array[p]);
			list[index] = Math.min(list[index],array[p]);
		}
		int answer = Searcher.underSearch(list,Long.MAX_VALUE);
		return answer+1;
	}
	static int[][] topologicalSort(ArrayList<ArrayList<Integer>> route){
		int[] count = new int[route.size()];
		int pathCount = 0;
		for(ArrayList<Integer> path: route){
			for(int point: path){
				++pathCount;
				++count[point];
			}
		}
		ArrayDeque<Integer> deq = new ArrayDeque<>();
		for(int i = 1;i<count.length;++i)
			if(count[i]==0)
				deq.add(i);
		int[][] ans = new int[pathCount][2];
		int index = 0;
		while(deq.size()>0){
			int nowP = deq.pollFirst();
			for(int nextP: route.get(nowP)){
				ans[index][0] = nowP;
				ans[index++][1] = nextP;
				if(--count[nextP]==0)
					deq.add(nextP);
			}
		}
		return ans;
	}
	static int[][] topologicalSort(int[][] route){
		int[] count = new int[route.length];
		int pathCount = 0;
		for(int[] path: route){
			for(int point: path){
				++pathCount;
				++count[point];
			}
		}
		ArrayDeque<Integer> deq = new ArrayDeque<>();
		for(int i = 1;i<count.length;++i)
			if(count[i]==0)
				deq.add(i);
		int[][] ans = new int[pathCount][2];
		int index = 0;
		while(deq.size()>0){
			int nowP = deq.pollFirst();
			for(int nextP: route[nowP]){
				ans[index][0] = nowP;
				ans[index++][1] = nextP;
				if(--count[nextP]==0)
					deq.add(nextP);
			}
		}
		return ans;
	}
	static boolean nextPermutation(int[] array){
		int index1 = 0;
		for(int i = 1;i<array.length;++i)
			if(array[i-1]<array[i])
				index1 = i;
		if(--index1<0)
			return false;
		int index2 = 0;
		int min = Integer.MAX_VALUE;
		for(int i = index1+1;i<array.length;++i){
			if(MathFunction.rangeCheckOpen(array[i],array[index1],min)){
				min = array[i];
				index2 = i;
			}
		}
		int temp = array[index1];
		array[index1] = array[index2];
		array[index2] = temp;
		Arrays.sort(array,index1+1,array.length);
		return true;
	}
	static boolean nextPermutation(long[] array){
		int index1 = 0;
		for(int i = 1;i<array.length;++i)
			if(array[i-1]<array[i])
				index1 = i;
		if(--index1<0)
			return false;
		int index2 = 0;
		long min = Long.MAX_VALUE;
		for(int i = index1+1;i<array.length;++i){
			if(MathFunction.rangeCheckOpen(array[i],array[index1],min)){
				min = array[i];
				index2 = i;
			}
		}
		long temp = array[index1];
		array[index1] = array[index2];
		array[index2] = temp;
		Arrays.sort(array,index1+1,array.length);
		return true;
	}
	static boolean nextPermutation(char[] array){
		int index1 = 0;
		for(int i = 1;i<array.length;++i)
			if(array[i-1]<array[i])
				index1 = i;
		if(--index1<0)
			return false;
		int index2 = 0;
		int min = Integer.MAX_VALUE;
		for(int i = index1+1;i<array.length;++i){
			if(MathFunction.rangeCheckOpen(array[i],array[index1],min)){
				min = array[i];
				index2 = i;
			}
		}
		char temp = array[index1];
		array[index1] = array[index2];
		array[index2] = temp;
		Arrays.sort(array,index1+1,array.length);
		return true;
	}
	static <E extends Comparable<E>> boolean nextPermutation(E[] array){
		int index1 = 0;
		for(int i = 1;i<array.length;++i)
			if(array[i-1].compareTo(array[i])<0)
				index1 = i;
		if(--index1<0)
			return false;
		int index2 = -1;
		E min = null;
		int subIndex = -1;
		E max = array[index1];
		for(int i = index1+1;i<array.length;++i){
			if(min==null||MathFunction.rangeCheckOpen(array[i],array[index1],min)){
				min = array[i];
				index2 = i;
			}
			if(max.compareTo(array[i])<0){
				subIndex = i;
				max = array[i];
			}
		}
		E temp;
		if(index2==-1){
			temp = array[subIndex];
			array[subIndex] = array[index1];
		}
		else{
			temp = array[index2];
			array[index2] = array[index1];
		}
		array[index1] = temp;
		Arrays.sort(array,index1+1,array.length);
		return true;
	}
}
class Converter{
	static String reverse(String str){
		StringBuilder sb = new StringBuilder();
		for(int i = str.length()-1;i>=0;--i)
			sb.append(str.charAt(i));
		return sb.toString();
	}
}
class MathFunction{
	static int[] numberForIntPrime = {2,7,61};
	static long[] numberForLongPrime = {2,7,61,325,9375,28178,450775,9780504,1795265022};
	static long gcd(long a,long b){
		a = Math.abs(a);
		b = Math.abs(b);
		if(b==0)
			return a;
		long temp;
		while((temp = a%b)!=0){
			a = b;
			b = temp;
		}
		return b;
	}
	static long lcm(long a,long b){
		return a/gcd(a,b)*b;
	}
	static boolean isPrime(long n){
		n = Math.abs(n);
		if(n==2L)
			return true;
		if(n==1L||(n&1L)==0L)
			return false;
		if(n<=4_759_123_141L)
			return isPrimeForInt(n);
		return isPrimeForBigInteger(n);
	}
	static boolean isPrimeForInt(long n){
		long d = n-1;
		while((d&1)==0L)
			d >>= 1;
		for(long a: numberForIntPrime){
			if(a>=n)
				return true;
			long t = d;
			long y = MathFunction.modPow(a,t,n);
			while(t<n-1L&&y!=1&&y!=n-1){
				y = y*y%n;
				t <<= 1;
			}
			if(y!=n-1&&(t&1L)==0)
				return false;
		}
		return true;
	}
	static boolean isPrimeForBigInteger(long n){
		long d = n-1L;
		while((d&1)==0L)
			d >>= 1;
		BigInteger bigN = BigInteger.valueOf(n);
		BigInteger bigNSubOne = bigN.subtract(BigInteger.ONE);
		BigInteger bigD = BigInteger.valueOf(d);
		for(long a: numberForLongPrime){
			if(a>=n)
				return true;
			BigInteger t = bigD;
			BigInteger y = BigInteger.valueOf(a).modPow(t,bigN);
			while(t.compareTo(bigNSubOne)<0&&!y.equals(BigInteger.ONE)&&!y.equals(bigNSubOne)){
				y = y.multiply(y).mod(bigN);
				t = t.shiftLeft(1);
			}
			if(!y.equals(bigNSubOne)&&(t.intValue()&1)==0)
				return false;
		}
		return true;
	}
	static int[] primes(int num){
		if(num<2)
			return new int[0];
		BitSet numbers = new BitSet(num+1);
		numbers.set(2,num+1);
		int limit = (int)Math.sqrt(num);
		for(int i=2;i<=limit;++i)
			if(numbers.get(i))
				for(int j=i*i;j<=num;j+=i)
					if(numbers.get(j))
						numbers.clear(j);
		int[] answer = new int[numbers.cardinality()];
		int i = 2, index = 0;
		do{
			i = numbers.nextSetBit(i);
			answer[index++] = i++;
		}
		while(index!=answer.length);
		return answer;
	}
	static long pow(long a,long b){
		long ans = 1;
		while(b>0){
			if((b&1)==1)
				ans *= a;
			a *= a;
			b >>= 1;
		}
		return ans;
	}
	static long modPow(long a,long b,long mod){
		long ans = 1;
		a %= mod;
		while(b>0){
			if((b&1)==1)
				ans *= a;
			ans %= mod;
			a *= a;
			a %= mod;
			b >>= 1;
		}
		return ans;
	}
	static long fact(int N){
		long ans = 1;
		for(int i = 2;i<=N;++i)
			ans *= i;
		return ans;
	}
	static long modFact(int N,long mod){
		long ans = 1;
		for(int i = 2;i<=N;++i){
			ans *= i;
			ans %= mod;
		}
		return ans;
	}
	static long combi(long n,long r){
		if(r<0||n<r)
			return 0;
		long ans = 1;
		r = Math.min(n-r,r);
		for(int i = 0;i<r;++i){
			ans *= n-i;
			ans /= i+1;
		}
		return ans;
	}
	static long modCombi(long n,long r,long mod){
		if(r<0||n<r)
			return 0;
		long ans = 1;
		r = Math.min(n-r,r);
		for(int i = 0;i<r;++i){
			ans *= (n-i)%mod;
			ans %= mod;
			ans *= modPow(i+1,mod-2,mod);
			ans %= mod;
		}
		return ans;
	}
	static boolean rangeCheck(int num,int l,int r){
		return l<=num&&num<r;
	}
	static boolean rangeCheck(long num,long l,long r){
		return l<=num&&num<r;
	}
	static boolean rangeCheck(double num,double l,double r){
		return l<=num&&num<r;
	}
	static <E extends Comparable<E>> boolean rangeCheck(E num,E l,E r){
		return 0<=l.compareTo(num)&&0<num.compareTo(r);
	}
	static boolean rangeCheckOpen(int num,int l,int r){
		return l<num&&num<r;
	}
	static boolean rangeCheckOpen(long num,long l,long r){
		return l<num&&num<r;
	}
	static boolean rangeCheckOpen(double num,double l,double r){
		return l<num&&num<r;
	}
	static <E extends Comparable<E>> boolean rangeCheckOpen(E num,E l,E r){
		return 0<l.compareTo(num)&&0<num.compareTo(r);
	}
	static boolean rangeCheckClose(int num,int l,int r){
		return l<=num&&num<=r;
	}
	static boolean rangeCheckClose(long num,long l,long r){
		return l<=num&&num<=r;
	}
	static boolean rangeCheckClose(double num,double l,double r){
		return l<=num&&num<=r;
	}
	static <E extends Comparable<E>> boolean rangeCheckClose(E num,E l,E r){
		return 0<=l.compareTo(num)&&0<=num.compareTo(r);
	}
}
class Searcher{
	static int CYCLE_COUNT = Double.MAX_EXPONENT+53;
	static int downSearch(int[] array,int value){
		int a = 0,b = array.length-1,ans = -1,c;
		while(a-b<1){
			c = (a+b)/2;
			if(array[c]>value)
				b = c-1;
			else
				a = (ans=c)+1;
		}
		return ans;
	}
	static int downSearch(long[] array,long value){
		int a = 0,b = array.length-1,ans = -1,c;
		while(a-b<1){
			c = (a+b)/2;
			if(array[c]>value)
				b = c-1;
			else
				a = (ans=c)+1;
		}
		return ans;
	}
	static int downSearch(double[] array,double value){
		int a = 0,b = array.length-1,ans = -1,c;
		while(a-b<1){
			c = (a+b)/2;
			if(array[c]>value)
				b = c-1;
			else
				a = (ans=c)+1;
		}
		return ans;
	}
	static int downSearch(char[] array,int value){
		int a = 0,b = array.length-1,ans = -1,c;
		while(a-b<1){
			c = (a+b)/2;
			if(array[c]>value)
				b = c-1;
			else
				a = (ans=c)+1;
		}
		return ans;
	}
	static <E extends Comparable<E>> int downSearch(E[] array,E value){
		int a = 0,b = array.length-1,ans = -1,c;
		while(a-b<1){
			c = (a+b)/2;
			if(array[c].compareTo(value)>0)
				b = c-1;
			else
				a = (ans=c)+1;
		}
		return ans;
	}
	static <E extends Comparable<E>> int downSearch(List<E> list,E value){
		int a = 0,b = list.size()-1,ans = -1,c;
		while(a-b<1){
			c = (a+b)/2;
			if(list.get(c).compareTo(value)>0)
				b = c-1;
			else
				a = (ans=c)+1;
		}
		return ans;
	}
	static int downSearch(int a,int b,int value,IntUnaryOperator func){
		int ans = a-1,c;
		while(a-b<1){
			c = (a+b)/2;
			if(func.applyAsInt(c)>value)
				b = c-1;
			else
				a = (ans=c)+1;
		}
		return ans;
	}
	static long downSearch(long a,long b,long value,LongUnaryOperator func){
		long ans = a-1,c;
		while(a-b<1){
			c = (a+b)/2;
			if(func.applyAsLong(c)>value)
				b = c-1;
			else
				a = (ans=c)+1;
		}
		return ans;
	}
	static double search(double a,double b,double value,DoubleUnaryOperator func){
		double ans = a-Math.abs(a),c;
		for(int $ = 0;$<CYCLE_COUNT;++$){
			c = (a+b)/2;
			if(func.applyAsDouble(c)>value)
				b = c;
			else
				a = (ans=c);
		}
		return ans;
	}
	static int upSearch(int[] array,int value){
		int a = 0,b = array.length-1,ans = array.length,c;
		while(a-b<1){
			c = (a+b)/2;
			if(array[c]>=value)
				b = (ans=c)-1;
			else
				a = c+1;
		}
		return ans;
	}
	static int upSearch(long[] array,long value){
		int a = 0,b = array.length-1,ans = array.length,c;
		while(a-b<1){
			c = (a+b)/2;
			if(array[c]>=value)
				b = (ans=c)-1;
			else
				a = c+1;
		}
		return ans;
	}
	static int upSearch(double[] array,double value){
		int a = 0,b = array.length-1,ans = array.length,c;
		while(a-b<1){
			c = (a+b)/2;
			if(array[c]>=value)
				b = (ans=c)-1;
			else
				a = c+1;
		}
		return ans;
	}
	static int upSearch(char[] array,char value){
		int a = 0,b = array.length-1,ans = array.length,c;
		while(a-b<1){
			c = (a+b)/2;
			if(array[c]>=value)
				b = (ans=c)-1;
			else
				a = c+1;
		}
		return ans;
	}
	static <E extends Comparable<E>> int upSearch(E[] array,E value){
		int a = 0,b = array.length-1,ans = array.length,c;
		while(a-b<1){
			c = (a+b)/2;
			if(array[c].compareTo(value)>=0)
				b = (ans=c)-1;
			else
				a = c+1;
		}
		return ans;
	}
	static <E extends Comparable<E>> int upSearch(List<E> list,E value){
		int a = 0,b = list.size()-1,ans = list.size(),c;
		while(a-b<1){
			c = (a+b)/2;
			if(list.get(c).compareTo(value)>=0)
				b = (ans=c)-1;
			else
				a = c+1;
		}
		return ans;
	}
	static int upSearch(int a,int b,int value,IntUnaryOperator func){
		int ans = b+1,c;
		while(a-b<1){
			c = (a+b)/2;
			if(func.applyAsInt(c)>=value)
				b = (ans=c)-1;
			else
				a = c+1;
		}
		return ans;
	}
	static long upSearch(long a,long b,long value,LongUnaryOperator func){
		long ans = b+1,c;
		while(a-b<1){
			c = (a+b)/2;
			if(func.applyAsLong(c)>=value)
				b = (ans=c)-1;
			else
				a = c+1;
		}
		return ans;
	}
	static int underSearch(int[] array,int value){
		int a = 0,b = array.length-1,ans = -1,c;
		while(a-b<1){
			c = (a+b)/2;
			if(array[c]>=value)
				b = c-1;
			else
				a = (ans=c)+1;
		}
		return ans;
	}
	static int underSearch(long[] array,long value){
		int a = 0,b = array.length-1,ans = -1,c;
		while(a-b<1){
			c = (a+b)/2;
			if(array[c]>=value)
				b = c-1;
			else
				a = (ans=c)+1;
		}
		return ans;
	}
	static int underSearch(double[] array,double value){
		int a = 0,b = array.length-1,ans = -1,c;
		while(a-b<1){
			c = (a+b)/2;
			if(array[c]>=value)
				b = c-1;
			else
				a = (ans=c)+1;
		}
		return ans;
	}
	static int underSearch(char[] array,char value){
		int a = 0,b = array.length-1,ans = -1,c;
		while(a-b<1){
			c = (a+b)/2;
			if(array[c]>=value)
				b = c-1;
			else
				a = (ans=c)+1;
		}
		return ans;
	}
	static <E extends Comparable<E>> int underSearch(E[] array,E value){
		int a = 0,b = array.length-1,ans = -1,c;
		while(a-b<1){
			c = (a+b)/2;
			if(array[c].compareTo(value)>=0)
				b = c-1;
			else
				a = (ans=c)+1;
		}
		return ans;
	}
	static <E extends Comparable<E>> int underSearch(List<E> list,E value){
		int a = 0,b = list.size()-1,ans = -1,c;
		while(a-b<1){
			c = (a+b)/2;
			if(list.get(c).compareTo(value)>=0)
				b = c-1;
			else
				a = (ans=c)+1;
		}
		return ans;
	}
	static int underSearch(int a,int b,int value,IntUnaryOperator func){
		int ans = a-1,c;
		while(a-b<1){
			c = (a+b)/2;
			if(func.applyAsInt(c)>=value)
				b = c-1;
			else
				a = (ans=c)+1;
		}
		return ans;
	}
	static long underSearch(long a,long b,long value,LongUnaryOperator func){
		long ans = a-1,c;
		while(a-b<1){
			c = (a+b)/2;
			if(func.applyAsLong(c)>=value)
				b = c-1;
			else
				a = (ans=c)+1;
		}
		return ans;
	}
	static int overSearch(int[] array,int value){
		int a = 0,b = array.length-1,ans = array.length,c;
		while(a-b<1){
			c = (a+b)/2;
			if(array[c]>value)
				b = (ans=c)-1;
			else
				a = c+1;
		}
		return ans;
	}
	static int overSearch(long[] array,long value){
		int a = 0,b = array.length-1,ans = array.length,c;
		while(a-b<1){
			c = (a+b)/2;
			if(array[c]>value)
				b = (ans=c)-1;
			else
				a = c+1;
		}
		return ans;
	}
	static int overSearch(double[] array,double value){
		int a = 0,b = array.length-1,ans = array.length,c;
		while(a-b<1){
			c = (a+b)/2;
			if(array[c]>value)
				b = (ans=c)-1;
			else
				a = c+1;
		}
		return ans;
	}
	static int overSearch(char[] array,char value){
		int a = 0,b = array.length-1,ans = array.length,c;
		while(a-b<1){
			c = (a+b)/2;
			if(array[c]>value)
				b = (ans=c)-1;
			else
				a = c+1;
		}
		return ans;
	}
	static <E extends Comparable<E>> int overSearch(E[] array,E value){
		int a = 0,b = array.length-1,ans = array.length,c;
		while(a-b<1){
			c = (a+b)/2;
			if(array[c].compareTo(value)>0)
				b = (ans=c)-1;
			else
				a = c+1;
		}
		return ans;
	}
	static <E extends Comparable<E>> int overSearch(List<E> list,E value){
		int a = 0,b = list.size()-1,ans = list.size(),c;
		while(a-b<1){
			c = (a+b)/2;
			if(list.get(c).compareTo(value)>0)
				b = (ans=c)-1;
			else
				a = c+1;
		}
		return ans;
	}
	static int overSearch(int a,int b,int value,IntUnaryOperator func){
		int ans = b+1,c;
		while(a-b<1){
			c = (a+b)/2;
			if(func.applyAsInt(c)>value)
				b = (ans=c)-1;
			else
				a = c+1;
		}
		return ans;
	}
	static long overSearch(long a,long b,long value,LongUnaryOperator func){
		long ans = b+1,c;
		while(a-b<1){
			c = (a+b)/2;
			if(func.applyAsLong(c)>value)
				b = (ans=c)-1;
			else
				a = c+1;
		}
		return ans;
	}
}
class BIT{
	int size;
	long[] tree;
	BIT(int n){
		size = n;
		tree = new long[n+1];
	}
	long sum(int i){
		long sum = 0;
		while(i>0){
			sum += tree[i];
			i ^= i&(-i);
		}
		return sum;
	}
	void add(int i,long x){
		while(i<=size){
			tree[i] += x;
			i += i&(-i);
		}
	}
	void clear(){
		Arrays.fill(tree,0L);
	}
}
class RollingHash implements Comparable<RollingHash>{
	static long BASE = new Random().nextInt(1000)+Character.MAX_VALUE+1;
	static long MASK30 = (1L<<30)-1;
	static long MASK31 = (1L<<31)-1;
	static long MOD = (1L<<61)-1;
	static long MASK61 = MOD;
	long[] hash;
	String string;
	RollingHash(String str){
		string = str;
		hash = new long[str.length()+1];
		roll();
	}
	void roll(){
		int len = string.length();
		for(int i = 1;i<=len;++i){
			hash[i] = multiply(hash[i-1],BASE)+string.charAt(i-1)-' '+1;
			if(MOD<=hash[i])
				hash[i] -= MOD;
		}
	}
	static long multiply(long a,long b){
		long au = a>>31;
		long ad = a&MASK31;
		long bu = b>>31;
		long bd = b&MASK31;
		long mid = ad*bu+au*bd;
		long midu = mid>>30;
		long midd = mid&MASK30;
		return mod(au*bu*2+midu+(midd<<31)+ad*bd);
	}
	static long mod(long x){
		long xu = x>>61;
		long xd = x&MASK61;
		long ans = xu+xd;
		if(MOD<=ans)
			ans -= MOD;
		return ans;
	}
	long getHash(int l,int r){
		return (hash[r]-multiply(hash[l],modBasePow(r-l))+MOD)%MOD;
	}
	static long modBasePow(long b){
		long ans = 1;
		long a = BASE;
		while(b>0){
			if((b&1)==1)
				ans = multiply(ans,a);
			a = multiply(a,a);
			b >>= 1;
		}
		return ans;
	}
	boolean equals(RollingHash rh,int l1,int r1,int l2,int r2){
		if(r1-l1!=r2-l2)
			return false;
		return getHash(l1,r1)==rh.getHash(l2,r2);
	}
	int length(){
		return string.length();
	}
	public int hashCode(){
		return string.hashCode();
	}
	public String toString(){
		return string;
	}
	public boolean equals(Object o){
		if(o instanceof RollingHash rh)
			return equals(rh,0,length(),0,rh.length());
		return false;
	}
	public int compareTo(RollingHash rh){
		return string.compareTo(rh.toString());
	}
	int compareTo(String str){
		return string.compareTo(str);
	}
	char charAt(int i){
		return string.charAt(i);
	}
	int compareToIgnoreCase(RollingHash rh){
		return string.compareToIgnoreCase(rh.toString());
	}
	int compareToIgnoreCase(String str){
		return string.compareToIgnoreCase(str);
	}
	void concat(RollingHash rh){
		concat(rh.toString());
	}
	void concat(String str){
		string = string.concat(str);
		hash = new long[string.length()+1];
		roll();
	}
	boolean contains(RollingHash rh){
		long hash = rh.getHash(0,rh.length());
		int len = length()-rh.length();
		for(int i = 0;i<=len;++i)
			if(hash==getHash(i,rh.length()+i))
				return true;
		return false;
	}
	boolean contains(String str){
		return indexOf(str)!=-1;
	}
	int indexOf(int ch){
		return indexOf(ch,0);
	}
	int indexOf(int ch,int fromIndex){
		int len = length();
		for(int i = fromIndex;i<len;++i)
			if(string.charAt(i)==ch)
				return i;
		return -1;
	}
	int indexOf(String str){
		return indexOf(str,0);
	}
	int indexOf(String str,int fromIndex){
		long hash = 0;
		for(char c: str.toCharArray()){
			hash = multiply(hash,BASE)+c-' '+1;
			if(MOD<=hash)
				hash -= MOD;
		}
		int len = length()-str.length();
		for(int i = fromIndex;i<=len;++i)
			if(hash==getHash(i,str.length()+i))
				return i;
		return -1;
	}
	boolean isEmpty(){
		return length()==0;
	}
	int lastIndexOf(int ch,int fromIndex){
		for(int i = fromIndex;i>=0;--i)
			if(string.charAt(i)==ch)
				return i;
		return -1;
	}
	int lastIndexOf(int ch){
		return lastIndexOf(ch,length()-1);
	}
}
@SuppressWarnings("unchecked") abstract class SegmentTree<E>{
	int N, size;
	E def;
	Object[] node;
	SegmentTree(int n,E def,boolean include){
		int num = 2;
		while(num<n<<1)
			num <<= 1;
		N = num;
		size = num>>1-(include?1:0);
		node = new Object[N];
		this.def = def;
		Arrays.fill(node,this.def);
	}
	SegmentTree(E[] arr,E def,boolean include){
		int num = 2;
		while(num<arr.length<<1)
			num <<= 1;
		N = num;
		size = num>>1-(include?1:0);
		node = new Object[N];
		this.def = def;
		System.arraycopy(arr,0,node,N>>1,arr.length);
		for(int i = arr.length+(N>>1);i<N;i++)
			node[i] = def;
		updateAll();
	}
	SegmentTree(int n,E def){
		this(n,def,false);
	}
	void updateAll(){
		for(int i = (N>>1)-1;i>0;i--)
			node[i] = function((E)node[i<<1],(E)node[(i<<1)+1]);
	}
	void update(int n,E value){
		n += size;
		node[n] = value;
		n >>= 1;
		while(n>0){
			node[n] = function((E)node[n<<1],(E)node[(n<<1)+1]);
			n >>= 1;
		}
	}
	E get(int a){
		return (E)node[a+size];
	}
	E answer(){
		return (E)node[1];
	}
	E query(int l,int r){
		l += size;
		r += size;
		E answer = def;
		while(l>0&&r>0&&l<=r){
			if(l%2==1)
				answer = function((E)node[l++],answer);
			l >>= 1;
			if(r%2==0)
				answer = function(answer,(E)node[r--]);
			r >>= 1;
		}
		return answer;
	}
	abstract E function(E a,E b);
}
class UnionFind{
	int[] par, rank, size, path;
	int count;
	UnionFind(int N){
		count = N;
		par = new int[N];
		rank = new int[N];
		size = new int[N];
		path = new int[N];
		Arrays.fill(par,-1);
		Arrays.fill(size,1);
	}
	int root(int ind){
		if(par[ind]==-1)
			return ind;
		else
			return par[ind] = root(par[ind]);
	}
	boolean isSame(int x,int y){
		return root(x)==root(y);
	}
	boolean unite(int x,int y){
		int rx = root(x);
		int ry = root(y);
		++path[rx];
		if(rx==ry)
			return false;
		if(rank[rx]<rank[ry]){
			int temp = rx;
			rx = ry;
			ry = temp;
		}
		par[ry] = rx;
		if(rank[rx]==rank[ry])
			++rank[rx];
		path[rx] += path[ry];
		size[rx] += size[ry];
		--count;
		return true;
	}
	int groupCount(){
		return count;
	}
	int pathCount(int x){
		return path[root(x)];
	}
	int size(int x){
		return size[root(x)];
	}
}
class SimpleScanner{
	int BUFF_SIZE = 1<<17;
	InputStream is;
	byte[] buff;
	int point, length;
	SimpleScanner(InputStream is){
		this.is = is;
		buff = new byte[BUFF_SIZE];
		point = length = 0;
	}
	void reload(){
		do{
			try{
				length = is.read(buff,point = 0,BUFF_SIZE);
			}catch(IOException e){
				e.printStackTrace();
				System.exit(1);
			}
		}
		while(length==-1);
	}
	byte read(){
		if(point==length)
			reload();
		return buff[point++];
	}
	byte nextByte(){
		byte c = read();
		while(c<=' ')
			c = read();
		return c;
	}
	int nextInt(){
		int ans = 0;
		byte c = nextByte();
		boolean negate = c=='-';
		if(!MathFunction.rangeCheckClose(c,'0','9'))
			c = read();
		while(MathFunction.rangeCheckClose(c,'0','9')){
			ans = ans*10+c-'0';
			c = read();
		}
		return negate?-ans:ans;
	}
	long nextLong(){
		long ans = 0;
		byte c = nextByte();
		boolean negate = c=='-';
		if(!MathFunction.rangeCheckClose(c,'0','9'))
			c = read();
		while(MathFunction.rangeCheckClose(c,'0','9')){
			ans = ans*10L+c-'0';
			c = read();
		}
		return negate?-ans:ans;
	}
	char nextChar(){
		return (char)nextByte();
	}
	String next(){
		StringBuilder ans = new StringBuilder();
		byte c = nextByte();
		while(c>' '){
			ans.append((char)c);
			c = read();
		}
		return ans.toString();
	}
	BigInteger nextBigInteger(){
		return new BigInteger(next());
	}
	byte[] nextByte(int n){
		byte[] ans = new byte[n];
		for(int i = 0;i<n;++i)
			ans[i] = nextByte();
		return ans;
	}
	int[] nextInt(int n){
		int[] ans = new int[n];
		for(int i = 0;i<n;++i)
			ans[i] = nextInt();
		return ans;
	}
	long[] nextLong(int n){
		long[] ans = new long[n];
		for(int i = 0;i<n;++i)
			ans[i] = nextLong();
		return ans;
	}
	String[] next(int n){
		String[] ans = new String[n];
		for(int i = 0;i<n;++i)
			ans[i] = next();
		return ans;
	}
	byte[][] nextByte(int n,int m){
		byte[][] ans = new byte[n][];
		for(int i = 0;i<n;++i)
			ans[i] = nextByte(m);
		return ans;
	}
	int[][] nextInt(int n,int m){
		int[][] ans = new int[n][];
		for(int i = 0;i<n;++i)
			ans[i] = nextInt(m);
		return ans;
	}
	long[][] nextLong(int n,int m){
		long[][] ans = new long[n][];
		for(int i = 0;i<n;++i)
			ans[i] = nextLong(m);
		return ans;
	}
	String[][] next(int n,int m){
		String[][] ans = new String[n][];
		for(int i = 0;i<n;++i)
			ans[i] = next(m);
		return ans;
	}
	char[] nextCharArray(){
		return next().toCharArray();
	}
	char[][] nextCharArray(int n){
		char[][] ans = new char[n][];
		for(int i = 0;i<n;++i)
			ans[i] = nextCharArray();
		return ans;
	}
	int[][] nextGraph(int N,int M){
		if(M==0)
			return new int[N+1][0];
		int[][] ans = new int[N+1][];
		int[] count = new int[N+1];
		int[][] path = nextInt(M,2);
		for(int[] temp: path){
			++count[temp[0]];
			++count[temp[1]];
		}
		for(int i = 1;i<=N;++i)
			ans[i] = new int[count[i]];
		for(int[] temp: path){
			ans[temp[0]][--count[temp[0]]] = temp[1];
			ans[temp[1]][--count[temp[1]]] = temp[0];
		}
		ans[0] = new int[0];
		return ans;
	}
	Point nextPoint(){
		return new Point(nextInt(),nextInt());
	}
	Point[] nextPoint(int n){
		Point[] ans = new Point[n];
		for(int i = 0;i<n;++i)
			ans[i] = nextPoint();
		return ans;
	}
	public void close(){
		try{
			is.close();
		}catch(IOException e){
			e.printStackTrace();
			System.exit(1);
		}
	}
}
class SimpleOutputStream extends FilterOutputStream{
	byte[] buf;
	int count;
	SimpleOutputStream(OutputStream out){
		this(out,1<<17);
	}
	SimpleOutputStream(OutputStream out,int size){
		super(out);
		if(size<=0)
			throw new IllegalArgumentException("Buffer size <= 0");
		buf = new byte[size];
	}
	void flushBuffer() throws IOException{
		if(count>0){
			out.write(buf,0,count);
			count = 0;
		}
	}
	public void write(int b) throws IOException{
		if(count>=buf.length)
			flushBuffer();
		buf[count++] = (byte)b;
	}
	public void write(byte[] b,int off,int len) throws IOException{
		if(len>=buf.length){
			flushBuffer();
			out.write(b,off,len);
			return;
		}
		if(len>buf.length-count)
			flushBuffer();
		System.arraycopy(b,off,buf,count,len);
		count += len;
	}
	public void flush() throws IOException{
		flushBuffer();
		out.flush();
	}
}
class SimpleWriter implements Appendable, Closeable, Flushable, AutoCloseable{
	Writer out;
	boolean autoFlush;
	boolean trouble = false;
	Formatter formatter;
	PrintStream psOut = null;
	static Charset toCharset(String csn){
		if(csn==null)
			throw new NullPointerException("charsetName");
		try{
			return Charset.forName(csn);
		}catch(IllegalCharsetNameException|UnsupportedCharsetException e){
			e.printStackTrace();
			System.exit(1);
			return null;
		}
	}
	SimpleWriter(Writer out){
		this(out,false);
	}
	SimpleWriter(Writer out,boolean autoFlush){
		this.out = out;
		this.autoFlush = autoFlush;
	}
	SimpleWriter(OutputStream out){
		this(out,false);
	}
	SimpleWriter(OutputStream out,boolean autoFlush){
		this(out,autoFlush,Charset.defaultCharset());
	}
	SimpleWriter(OutputStream out,boolean autoFlush,Charset charset){
		this(new BufferedWriter(new OutputStreamWriter(new SimpleOutputStream(out),charset)),autoFlush);
		if(out instanceof PrintStream)
			psOut = (PrintStream)out;
	}
	void ensureOpen() throws IOException{
		if(out==null)
			throw new IOException("Stream closed");
	}
	public void flush(){
		try{
			ensureOpen();
			out.flush();
		}catch(IOException x){
			trouble = true;
		}
	}
	public void close(){
		try{
			if(out==null)
				return;
			out.close();
			out = null;
		}catch(IOException x){
			trouble = true;
		}
	}
	boolean checkError(){
		if(out!=null)
			flush();
		else if(psOut!=null)
			return psOut.checkError();
		return trouble;
	}
	void setError(){
		trouble = true;
	}
	void clearError(){
		trouble = false;
	}
	void write(int c){
		try{
			ensureOpen();
			out.write(c);
		}catch(InterruptedIOException x){
			Thread.currentThread().interrupt();
		}catch(IOException x){
			trouble = true;
		}
	}
	void write(char[] buf,int off,int len){
		try{
			ensureOpen();
			out.write(buf,off,len);
		}catch(InterruptedIOException x){
			Thread.currentThread().interrupt();
		}catch(IOException x){
			trouble = true;
		}
	}
	void write(char[] buf){
		write(buf,0,buf.length);
	}
	void write(String s,int off,int len){
		try{
			ensureOpen();
			out.write(s,off,len);
		}catch(InterruptedIOException x){
			Thread.currentThread().interrupt();
		}catch(IOException x){
			trouble = true;
		}
	}
	void write(String s){
		write(s,0,s.length());
	}
	void newLine(){
		try{
			ensureOpen();
			out.write(System.lineSeparator());
			if(autoFlush)
				out.flush();
		}catch(InterruptedIOException x){
			Thread.currentThread().interrupt();
		}catch(IOException x){
			trouble = true;
		}
	}
	void print(boolean b){
		write(b?"true":"false");
	}
	void print(char c){
		write(c);
	}
	void print(int i){
		write(String.valueOf(i));
	}
	void print(long l){
		write(String.valueOf(l));
	}
	void print(float f){
		write(String.valueOf(f));
	}
	void print(double d){
		write(String.valueOf(d));
	}
	void print(char[] s){
		write(s);
	}
	void print(String s){
		write(s);
	}
	void print(Object obj){
		write(obj.toString());
	}
	void println(){
		newLine();
	}
	void println(boolean x){
		print(x);
		println();
	}
	void println(char x){
		print(x);
		println();
	}
	void println(int x){
		print(x);
		println();
	}
	void println(long x){
		print(x);
		println();
	}
	void println(float x){
		print(x);
		println();
	}
	void println(double x){
		print(x);
		println();
	}
	void println(char[] x){
		print(x);
		println();
	}
	void println(String x){
		print(x);
		println();
	}
	void println(Object x){
		print(x.toString());
		println();
	}
	SimpleWriter printf(String format,Object... args){
		return format(format,args);
	}
	SimpleWriter printf(Locale l,String format,Object... args){
		return format(l,format,args);
	}
	SimpleWriter format(String format,Object... args){
		try{
			ensureOpen();
			if((formatter==null)||(formatter.locale()!=Locale.getDefault()))
				formatter = new Formatter(this);
			formatter.format(Locale.getDefault(),format,args);
			if(autoFlush)
				out.flush();
		}catch(InterruptedIOException x){
			Thread.currentThread().interrupt();
		}catch(IOException x){
			trouble = true;
		}
		return this;
	}
	SimpleWriter format(Locale l,String format,Object... args){
		try{
			ensureOpen();
			if((formatter==null)||(formatter.locale()!=l))
				formatter = new Formatter(this,l);
			formatter.format(l,format,args);
			if(autoFlush)
				out.flush();
		}catch(InterruptedIOException x){
			Thread.currentThread().interrupt();
		}catch(IOException x){
			trouble = true;
		}
		return this;
	}
	public SimpleWriter append(CharSequence csq){
		write(String.valueOf(csq));
		return this;
	}
	public SimpleWriter append(CharSequence csq,int start,int end){
		if(csq==null)
			csq = "null";
		return append(csq.subSequence(start,end));
	}
	public SimpleWriter append(char c){
		write(c);
		return this;
	}
	void println(int[] array){
		println(array,' ');
	}
	void println(int[] array,String str){
		print(array[0]);
		for(int i = 1;i<array.length;++i){
			print(str);
			print(array[i]);
		}
		println();
	}
	void println(int[] array,char c){
		print(array[0]);
		for(int i = 1;i<array.length;++i){
			print(c);
			print(array[i]);
		}
		println();
	}
	void println(int[][] array){
		println(array,' ');
	}
	void println(int[][] arrays,String str){
		for(int[] array: arrays)
			println(array,str);
	}
	void println(int[][] arrays,char c){
		for(int[] array: arrays)
			println(array,c);
	}
	void println(long[] array){
		println(array,' ');
	}
	void println(long[] array,String str){
		print(array[0]);
		for(int i = 1;i<array.length;++i){
			print(str);
			print(array[i]);
		}
		println();
	}
	void println(long[] array,char c){
		print(array[0]);
		for(int i = 1;i<array.length;++i){
			print(c);
			print(array[i]);
		}
		println();
	}
	void println(long[][] array){
		println(array,' ');
	}
	void println(long[][] arrays,String str){
		for(long[] array: arrays)
			println(array,str);
	}
	void println(long[][] arrays,char c){
		for(long[] array: arrays)
			println(array,c);
	}
	void println(double[] array){
		println(array,' ');
	}
	void println(double[] array,String str){
		print(array[0]);
		for(int i = 1;i<array.length;++i){
			print(str);
			print(array[i]);
		}
		println();
	}
	void println(double[] array,char c){
		print(array[0]);
		for(int i = 1;i<array.length;++i){
			print(c);
			print(array[i]);
		}
		println();
	}
	void println(double[][] array){
		println(array,' ');
	}
	void println(double[][] arrays,String str){
		for(double[] array: arrays)
			println(array,str);
	}
	void println(double[][] arrays,char c){
		for(double[] array: arrays)
			println(array,c);
	}
	void println(char[] cs,String str){
		print(cs[0]);
		for(int i = 1;i<cs.length;++i){
			print(str);
			print(cs[i]);
		}
		println();
	}
	void println(char[] cs,char c){
		print(cs[0]);
		for(int i = 1;i<cs.length;++i){
			print(c);
			print(cs[i]);
		}
		println();
	}
	void println(char[][] cs){
		for(char[] c: cs)
			println(c);
	}
	void println(char[][] cs,String str){
		for(char[] c: cs)
			println(c,str);
	}
	void println(char[][] cs,char c){
		for(char[] cc: cs)
			println(cc,c);
	}
	<E> void println(E[] array){
		println(array,' ');
	}
	<E> void println(E[] array,String str){
		print(array[0]);
		for(int i = 1;i<array.length;++i){
			print(str);
			print(array[i]);
		}
		println();
	}
	<E> void println(E[] array,char c){
		print(array[0]);
		for(int i = 1;i<array.length;++i){
			print(c);
			print(array[i]);
		}
		println();
	}
	<E> void println(E[][] arrays){
		println(arrays,' ');
	}
	<E> void println(E[][] arrays,String str){
		for(E[] array: arrays)
			println(array,str);
	}
	<E> void println(E[][] arrays,char c){
		for(E[] array: arrays)
			println(array,c);
	}
	<E> void println(List<E> list){
		println(list,' ');
	}
	<E> void println(List<E> list,String str){
		if(list.size()==0){
			println();
			return;
		}
		print(list.get(0));
		for(int i = 1;i<list.size();++i){
			print(str);
			print(list.get(i));
		}
		println();
	}
	<E> void println(List<E> list,char c){
		if(list.size()==0){
			println();
			return;
		}
		print(list.get(0));
		for(int i = 1;i<list.size();++i){
			print(c);
			print(list.get(i));
		}
		println();
	}
}