import java.net.*;
import java.io.*;

class my

{

public static final double eps = Float.MIN_VALUE;
public static boolean violetai = !true;
//public static boolean dummyprint = violetai&&false;
public static boolean dummyprint = violetai;
public static int printcolumns = 72;
public static final int LeftMouseMask1 = 0;
public static final int LeftMouseMask2 = 8192;
public static double log10=Math.log(10);
public static void error(String s){ print_exit(s);}
public final static int A=255<<24;
public final static int R=255<<16;
public final static int G=255<<8;
public final static int B=255;
public final static int Y=A|R|G;
public final static int W=A|R|G|B;
public final static int AR=A|R;
public final static int AG=A|G;
public final static int AB=A|B;

public static double[] linsolve2(double[][] a, double[] b){ // ax = b
// test
// my.print(my.linsolve2(new double[][]{{1,-2},{3,4}},new double[]{5,0}),"linsolve2 teisingas{2,1}");

	
	if ((a.length!=2)|(b.length!=2)) print_exit("linsolve2 parashyta tik 2x2 lygciu sistemai");
	double[] x = new double[2];
	double D = a[0][0]*a[1][1]-a[0][1]*a[1][0];
	double D0 = b[0]*a[1][1]-b[1]*a[1][0];
	double D1 = a[0][0]*b[1]-a[0][1]*b[0];
	if (Math.abs(D)>eps*(Math.abs(D0)+Math.abs(D1))){
		x[0] = D0/D; x[1] = D1/D;
	}
		else {
			println("Warning linsolve2: - eps tikslumu priklausomos lygtys");
			if (Math.abs(a[0][0])>Math.abs(a[1][1])) {x[0] = b[0]/a[0][0]; x[1]=0;}
				else if (Math.abs(a[1][1])>eps) {x[0]=0; x[1] = b[1]/a[1][1];}
				else print_exit("linsolve2: nera sprendiniu");
		}
	return x;
}
public static int[] sgn(int[] a) // b=sgn(a)
{
	int n = a.length;
	int[] b = new int[n];
	for (int i=0; i<n; i++) if (a[i]>0) {b[i] = 1;}
		else if (a[i]<0) {b[i] = -1;}
	return b;
}

public static double[] move(double[] a) // b=a
{
	double[] b = null; 
	if (a==null) return null;
	int n = a.length;
	b = new double[n];
	for (int i=0; i<n; i++) b[i] = a[i];
	return b;
}
public static double[] move(double[] a, int last) // b=a[0..last-1]
{
	double[] b = null; 
	if (a==null) return null;
	int n = a.length;
	if (last>n) error("last>n");
	b = new double[last];
	for (int i=0; i<last; i++) b[i] = a[i];
	return b;
}
public static int[][] move(int[][] a) // b=a
{
	int[][] b = null; 
	if (a==null) return null;
	int n = a.length;
	int m = a[0].length;
	b = new int[n][m];
	for (int i=0; i<n; i++) for (int j=0; j<m; j++) b[i][j] = a[i][j];
	return b;
}
public static byte[] move(byte[] a) // b=a
{
	byte[] b = null; 
	if (a==null) return null;
	int n = a.length;
	b = new byte[n];
	for (int i=0; i<n; i++) b[i] = a[i];
	return b;
}
public static double[] move(double[] a, int nstart, int nstop) // b=a
{
	if (nstart>=nstop) print_exit("nstart>=nstop");
	int n = a.length;
	if (nstop>n) warning("nstop>n");
	double[] b = new double[nstop-nstart];
	for (int i=nstart; i<nstop; i++) b[i-nstart] = a[mod(i,n)];
	return b;
}
public static int[] move(int[] a, int nstart, int nstop) // b=a
{
	if (nstart>=nstop) print_exit("nstart>=nstop");
	int n = a.length;
	if (nstop>n) print_exit("nstop>n");
	int[] b = new int[nstop-nstart];
	for (int i=nstart; i<nstop; i++) b[i-nstart] = a[i];
	return b;
}
public static int[] move(int[] a, int[] ind) // b=a(ind)
{
	int[] b=null;
	if (ind==null) return b;
	int n = ind.length;
	b = new int[n];
	for (int i=0; i<n; i++) b[i] = a[ind[i]];
	return b;
}
public static int[] remove(int[] a, int[] ind) // b=a(ind)
{
	int[] is = sort(ind);
	int n = a.length;
	int m = ind.length;
	int[] b = new int[n-m]; int j=0, k=0;
	for (int i=0; i<n; i++) 
		if (i!=ind[is[j]]) {b[k] = a[i]; k++;}
			else {j++; if (j==m) j=0;}
	return b;
}

public static int[] join(int[] a, int[] b) // c=[a;b]
{
	int n = a.length;
	int m = b.length;
	int c[] = new int[n+m];	
	for (int i=0; i<n; i++) c[i] = a[i]; 
	for (int i=0; i<m; i++) c[i+n]=b[i]; 
	return c;
}

public static double[][] move(double[][] a) // b=a
{
	int n = a.length;
	int m = a[0].length;
	double[][] b = new double[n][m];
	for (int i=0; i<n; i++) 
	 for (int j=0; j<m; j++) b[i][j] = a[i][j];
	return b;
}
public static int[] move(int[] a) // b=a
{
	int n = a.length;
	int [] b = new int[n];
	for (int i=0; i<n; i++) b[i] = a[i];
	return b;
}
public static int[] find(int[] a, int c) // suranda indeksus kuriems a==c
{
	int m = a.length;
	int[] iw = new int[m];
	int n = 0;
	for (int i = 0; i<m; i++) if (a[i]==c)	{iw[n] = i; ++n;}
	int[] ic = new int[n];
	for (int i = 0; i<n; i++) ic[i] = iw[i];
	return ic;
} //find
public static int[] find(int[] a, int[] c) // suranda indeksus kuriems a==c
{
	int m = a.length;
	if (m!=c.length) print_exit("m!=c.length");
	int[] iw = new int[m];
	int n = 0;
	for (int i = 0; i<m; i++) if (a[i]==c[i]) {iw[n] = i; ++n;}
	int[] ic = new int[n];
	for (int i = 0; i<n; i++) ic[i] = iw[i];
	return ic;
} //find
public static int findc(int[] a, int c) // suranda skaiciu indeksu, kuriems a==c
{
	int[] i = find(a,c);
	return i.length;
} //find

public static double mean(double[] a) 
{
	int n = a.length;
	double m = a[0];
	for (int i=1; i<n; i++) m += a[i];
	return m/n;
}

public static double std(double[] a) 
{
	int n = a.length;
	if (n==1) return 0.0;
	double m = mean(a);
	double D=0;
	for (int i=0; i<n; i++) D += (a[i]-m)*(a[i]-m);
	return Math.sqrt(D/(n-1));
}

public static double max(double[] a) 
{
	int n = a.length;
	int j = 0;
	for (int i=1; i<n; i++) if (a[j]<a[i]) j = i;
	return a[j];
}
public static int max(int[] a) 
{
	int n = a.length;
	int j = 0;
	for (int i=1; i<n; i++) if (a[j]<a[i]) j = i;
	return a[j];
}
public static double min(double[] a) 
{
	int n = a.length;
	double m = a[0];
	for (int i=1; i<n; i++) if (m>a[i]) m = a[i];
	return m;
}
public static double[] max(double[][] a, int dim) 
{
	double[] m;
	int n = a.length;
	int k = a[0].length;
	double x;
	testdim(dim);
//	if ((dim!=1)&&(dim!=2)) print_exit("((dim!=1)&&(dim!=2))");
	if (dim==1){
		m = new double[k];
		for (int j=0; j<k; j++){
			x=a[0][j];
			for (int i=1; i<n; i++) if (x<a[i][j]) x = a[i][j];
			m[j] = x;
		}
	}
	else{
		m = new double[n];
		for (int i=0; i<n; i++){
			x=a[i][0];
			for (int j=1; j<k; j++) if (x<a[i][j]) x = a[i][j];
			m[i] = x;
		}
	}		
	return m;
}

public static double[] min(double[][] a, int dim) 
{
	double[] m;
	int n = a.length;
	int k = a[0].length;
	double x;
	testdim(dim);
//	if ((dim!=1)&&(dim!=2)) print_exit("((dim!=1)&&(dim!=2))");
	if (dim==1){
		m = new double[k];
		for (int j=0; j<k; j++){
			x=a[0][j];
			for (int i=1; i<n; i++) if (x>a[i][j]) x = a[i][j];
			m[j] = x;
		}
	}
	else{
		m = new double[n];
		for (int i=0; i<n; i++){
			x=a[i][0];
			for (int j=0; j<k; j++) if (x>a[i][j]) x = a[i][j];
			m[i] = x;
		}
	}		
	return m;
}

private static void testdim(int dim){
	if ((dim!=1)&&(dim!=2)) print_exit("((dim!=1)&&(dim!=2))");
}

public static void print_exit(String s)
{
	System.out.println(s);
//	int i=1; while (i==1) i=1;
//	System.out.print("\07"); 
	System.exit(0);
}
public static void warning(String s)
{
	System.out.println("Warning: "+s);
}

public static void print(double[][] a, String s)
{
	if (dummyprint) return;
	println(s);
	int m = a.length;
	int n = a[0].length;
	for (int i=0; i<m; i++){
		String S = "";
		for (int j=0; j<n; j++)
			S = S + toString(a[i][j]);
		println(S);		
	}
}//print

public static void print(double[] a, String s)
{
	if (dummyprint) return;
	System.out.println(s + ":");
	int n = a.length;
	String S = "";
	for (int i=0; i<n; i++)	{S = S + toString(a[i]);
		if (S.length()>=printcolumns) {println(S); S = "";}
	}
	println(S);
}//print
public static void print(int[] a, String s)
{
	if (dummyprint) return;
	System.out.println(s + ":");
	int n = a.length;
	String S = " ";
	for (int i=0; i<n; i++)	{S = S + Integer.toString(a[i]) + " ";
		if (S.length()>printcolumns) {System.out.println(S); S = " ";}
	}
	System.out.println(S);
}//print
public static void print(int[][] a, String s)
{
	if (dummyprint) return;
	System.out.println(s + ":");
	int n = a.length, m=a[0].length;
	String S="";
	for (int j=0; j<n; j++)	{
		S = " ";
		for (int i=0; i<m; i++)	{S = S + Integer.toString(a[j][i]) + " ";
			if (S.length()>printcolumns) {System.out.println(S); S = " ";}
		}
		System.out.println(S);
	}
}//print

public static void print(byte[] a, String s)
{
	if (dummyprint) return;
	System.out.println(s + ":");
	int n = a.length;
	String S = " ";
	for (int i=0; i<n; i++)	{S = S + Byte.toString(a[i]) + " ";
		if (S.length()>printcolumns) {System.out.println(S); S = " ";}
	}
	System.out.println(S);
}//print

public static void print(boolean[] a, String s)
{
	if (dummyprint) return;
	System.out.println(s + ":");
	int n = a.length;
	String S = " ";
	for (int i=0; i<n; i++)	{if (a[i]) S += "T"; else S += "F";
		if (S.length()>printcolumns) {System.out.println(S); S = " ";}
	}
	System.out.println(S);
}//print
public static void print(boolean a, String s)
{
	if (dummyprint) return;
	if (a) System.out.println(s + " = true");
		else System.out.println(s + " = false");
}//print
public static void print(int a, String s)
{
	if (dummyprint) return;
	System.out.println(s + " = " + Integer.toString(a));
}//print
public static void print(double a, String s)
{
	if (dummyprint) return;
	System.out.println(s + " = " + Double.toString(a));
}//print

public static void println(String s)
{
	if (dummyprint) return;
	System.out.println(s);
}//print

public static String toPercent(double x){
 String S = Double.toString(((int)(1000*x+0.5))/10.0) + "%";
return S;
} //toPercent

public static double[][] trans(double[][] a){
 int n = a.length;
 int m = a[0].length;
 double[][] b = new double[m][n];
 for (int j = 0; j < m ; j++) 
  for (int i = 0; i < n ; i++) b[j][i] = a[i][j];
	return b;
}

private static void QuickSort(int a[], int ia[], int lo0, int hi0)
{
int lo = lo0;
int hi = hi0;
int mid,T,k;

if ( hi0 > lo0)
 {
 mid = a[ ( lo0 + hi0 ) / 2 ];

 // loop through the array until indices cross
 while( lo <= hi )
 {
	while( ( lo < hi0 ) && ( a[lo] < mid ) ) ++lo;
	while( ( hi > lo0 ) && ( a[hi] > mid ) ) --hi;
	if( lo <= hi ) 
	{
	// swap(int a[], int ia[], int i, int j)
		T = a[lo]; k = ia[lo];
		a[lo] = a[hi]; ia[lo] = ia[hi];
		a[hi] = T; ia[hi] = k;
		++lo;
		--hi;
	}
	}
	if( lo0 < hi )
		QuickSort( a, ia, lo0, hi );
	if( lo < hi0 )
		QuickSort( a, ia, lo, hi0 );
 }
}

public static int[] sort(int[] A) 
{
 boolean test = false;
 int na = A.length;
 // padarau kopija, kad nesugadinti A
 int[] a = new int[na];
 int[] ia = new int[na];
 for (int i = 0; i<na; i++) { a[i] = A[i]; ia[i] = i;}
 if (test) { System.out.println("Init:");
	for (int i = 0; i<na; i++) System.out.println(Integer.toString(A[i]));
	}
 QuickSort(a, ia, 0, na - 1);
 if (test) { System.out.println("Sorted:");
	for (int i = 0; i<na; i++) System.out.println(Integer.toString(A[ia[i]]));
	}
 return ia;
}

private static void QuickSort(double a[], int ia[], int lo0, int hi0)
{
int lo = lo0;
int hi = hi0;
double mid,T;
int k;

if ( hi0 > lo0)
 {
 mid = a[ ( lo0 + hi0 ) / 2 ];

 // loop through the array until indices cross
 while( lo <= hi )
 {
	while( ( lo < hi0 ) && ( a[lo] < mid ) ) ++lo;
	while( ( hi > lo0 ) && ( a[hi] > mid ) ) --hi;
	if( lo <= hi ) 
	{
	// swap(int a[], int ia[], int i, int j)
		T = a[lo]; k = ia[lo];
		a[lo] = a[hi]; ia[lo] = ia[hi];
		a[hi] = T; ia[hi] = k;
		++lo;
		--hi;
	}
	}
	if( lo0 < hi )
		QuickSort( a, ia, lo0, hi );
	if( lo < hi0 )
		QuickSort( a, ia, lo, hi0 );
 }
}

public static int[] sort(double[] A) 
{
 boolean test = !true;
 int na = A.length;
 // padarau kopija, kad nesugadinti A
 double[] a = new double[na];
 int[] ia = new int[na];
 for (int i = 0; i<na; i++) { a[i] = A[i]; ia[i] = i;}
 if (test) { System.out.println("Init:");
	for (int i = 0; i<na; i++) System.out.println(Double.toString(A[i]));
	}
 QuickSort(a, ia, 0, na - 1);
 if (test) { System.out.println("Sorted:");
	for (int i = 0; i<na; i++) System.out.println(Double.toString(A[ia[i]]));
	}
 return ia;
}

public static DataInputStream OpenDataInputStream(String failas){
 DataInputStream f = null;
 try {
	if (failas.indexOf("h")==0){
		my.println("Kviesiu URL " + failas + " faila");
		URL urlfailas = null; URL urlrwfailas = new URL(failas);
		f = new DataInputStream (urlrwfailas.openStream() );
	}		
	else { //(failas.indexOf("h")==0)
//		my.println("Kviesiu nauja " + failas + " faila");
		f = new DataInputStream(new FileInputStream(failas));
	} //(failas.indexOf("h")==0)
 } //try
	catch(ArrayIndexOutOfBoundsException e) { 
		my.print_exit("Turite nurodyti binariniu duomenu varda: " + e);}
	catch (FileNotFoundException e) {my.print_exit("Negaliu atidaryti failo: " + e);}
	catch(IOException e) {my.print_exit("Klaida atidarant faila:" + e);}
	catch (Exception e) {my.print_exit("Neklasifikuota klaida: " + e);}
// finally {};
 return f;
}
public static String readUTF(DataInputStream fin){
 String S=null;
 try {S=fin.readUTF();}
 catch (Exception e) {
      my.print_exit("Neklasifikuota klaida: " + e + " skaitant " + fin.toString());
 }
 return S;
}
public static void CloseDataInputStream(DataInputStream fin){
 try {fin.close();}
 catch (Exception e) {
      my.print_exit("Neklasifikuota klaida: " + e + " uzdarant " + fin.toString());
 }
}

public static DataOutputStream OpenDataOutputStream(String failas){
 DataOutputStream f = null;
 try {f = new DataOutputStream(new FileOutputStream(failas));}
 catch (Exception e) {print_exit("Neklasifikuota klaida: " + e + " atidarant " + failas);}
 return f;
}
public static void writeUTF(DataOutputStream fout,String S){
 try {fout.writeUTF(S);}
 catch (Exception e) {
      my.print_exit("Neklasifikuota klaida: " + e + " irasant i " + fout.toString());
 }
}
public static void write(DataOutputStream fout,byte[] b){
 try {fout.write(b,0,b.length);}
 catch (Exception e) {
      my.print_exit("Neklasifikuota klaida: " + e + " irasant byte[] b i " + fout.toString());
 }
}
public static void CloseDataOutputStream(DataOutputStream fout){
 try {fout.flush();fout.close();}
 catch (Exception e) {
      my.print_exit("Neklasifikuota klaida: " + e + " uzdarant " + fout.toString());
 }
}

public static void skipBytes(DataInputStream f, int skip, String s){
 try { int i = f.skipBytes(skip); }
 catch(IOException e) {print_exit("skipBytes: " + s + " " + e); }
} //skipBytes

public static double scalar_product(double[] a, double[] b){
 int n = a.length;
 if (n!=b.length) print_exit("a.length!=b.length");
 double s = 0;
 for (int i = 0; i<n; i++) s += a[i]*b[i];
	return s;
} //scalar_product

// dim=1 - apjungti pirma keichiant eilutes
public static double[] a2a1(double[][] a, int dim){

 testdim(dim);
 int n = a.length;
 int m = a[0].length;
 double[] b = new double[n*m];
 int k = 0;
 if (dim==1){
	 for (int j=0; j<m; j++) for (int i=0; i<n; i++) {b[k] = a[i][j]; k++;}
 }
  else if (dim==2){
	 for (int i=0; i<n; i++) for (int j=0; j<m; j++) {b[k] = a[i][j]; k++;}
 }

	return b;

} //a2a1

public static String toString(double a){
 String s, S;
 int ndigits = 5; double c = 1.0; 
 for (int i=0; i<ndigits-1; i++) c *= 10; // c=10^ndigits;
 if (Math.abs(a)<=1e-99) S = "           0";
  else{
	if (a>0) S="  "; else S=" -";
	a = Math.abs(a);
	int i=0; while ((i!=-99)&(a<1)) {a=a*10; i--;} 
	while ((i!=99)&(a>=10)) {a=a/10; i++;}
	S += Double.toString(Math.round(a*c)/c);
	while (S.length()<(3+ndigits)) S += "0";
 	S += "e";
	s = Integer.toString(Math.abs(i));
	if (i<-9) S = S + "-" + s; 
		else if (i>9) S = S + "+" + s; 
			else if (i<0) S = S + "-0" + s; 
				else S = S + "+0" + s; 
 }
	return S; 
} //


public static String toString(double a, int npokabl){ //skaiciu po kablelio
 String s,S;
 for (int i=0; i<npokabl; i++) a *= 10; // a=a*10^npokabl
 if (a<0) {S="-"; a=Math.abs(a);} else S="";
 s = Integer.toString((int) Math.round(a));
 while (s.length()<=npokabl) s = "0"+s;
 int n = s.length();
 S = S+s.substring(0,n-npokabl)+"."+s.substring(n-npokabl,n);
	return S; 
} //

public static String toString(int[] a){ //sveiku skaichiu masyvo konvertavimas
 String S; S="";
 for (int i=0; i<a.length; i++) S += Integer.toString(a[i])+" ";
	return S; 
} //

private static double[] kryptis(double xa, double ya, double xb, double yb) {
	double q = Math.sqrt((xb-xa)*(xb-xa)+(yb-ya)*(yb-ya)+1e-77);
	double[] e = {(xb-xa)/q, (yb-ya)/q};
	return e;
}
public static boolean exists(String failas){
 DataInputStream f = null;
 try {if (failas.indexOf("h")==0){
		URL urlfailas = new URL(failas);
		f = new DataInputStream ( urlfailas.openStream() );}		
 else {f = new DataInputStream(new FileInputStream(failas));}
}//try
 catch (Exception e) {
	f=null; return false;
 }
 try {f.close();}
 catch (Exception e) {f=null; return false;}
 return true;
}

public static int mod(int i, int m){
	if (i<0) i += m*(-i/m+1); 
	return (int) (i-m*(int)(i/m));
} //mod

public static int length(int[] a){
int n=0;
if (a==null) return n;
 n=a.length;
 return n; 
}
public static double lg(double p){
 return Math.log(p)/log10;
}
} //my