//package util;

import java.net.*;
import java.io.*;
import java.util.*;
import javax.swing.*;
import java.lang.reflect.*;

public class my

{
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 final double eps = Float.MIN_VALUE,
			EPS = Math.sqrt(Double.MIN_VALUE);
public static boolean violetai = !true;
//public static boolean dummyprint = violetai&&false;
public static boolean dummyprint = !true;
public static boolean pause = !true;
public static boolean whileNotEnterPause = true;
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 final double db=10/log10,
		DB = db;
public static double	maxDB=30;
public static int minPok=8; // naudoja getMinPokycius
public static int testCount=0;
public static final double pi2=Math.PI*2;

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 {
			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 int[] copy2(int[] a){ // b=[a zeros(a.length/2+1)]
	int n = a.length;
	int[] b = new int[n+n/2+1];
	for (int i=0; i<n; i++) b[i] = a[i];
	return b;
}

//	Didinama atmintis tik pirmam indeksui !!
public static int[][] copy2(int[][] a){ // b=[a zeros(a.length/2+1)]
	int n = a.length, m = a[0].length;
	int[][] b = new int[n+n/2+1][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[] copy2(byte[] a){ // b=[a zeros(a.length/2+1)]
	int n = a.length;
	byte[] b = new byte[n+n/2+1];
	for (int i=0; i<n; i++) b[i] = a[i];
	return b;
}

public static float[] copy2(float[] a){ // b=[a zeros(a.length/2+1)]
	int n = a.length;
	float[] b = new float[n+n/2+1];
	for (int i=0; i<n; i++) b[i] = a[i];
	return b;
}

public static boolean[] move(boolean[] a) // b=a
{
	boolean[] b = null;
	if (a==null) return null;
	int n = a.length;
	b = new boolean[n];
	for (int i=0; i<n; i++) b[i] = a[i];
	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 byte[] move(byte[] a, int nstart, int nstop) // b=a
{
	if (nstart>nstop){
		warning("nstart>nstop: "+nstart+">"+nstop);
		return null;
	}
	int n = a.length;
	if (nstop>n) warning("nstop>n: "+nstop+">"+n);
	byte[] b = new byte[nstop-nstart];
	for (int i=nstart; i<nstop; i++) b[i-nstart] = a[i];
	return b;
}
public static short[] move(short[] a, int nstart, int nstop) // b=a
{
	if (nstart>nstop){
		warning("nstart>nstop: "+nstart+">"+nstop);
		return null;
	}
	int n = a.length;
	if (nstop>n) warning("nstop>n: "+nstop+">"+n);
	short[] b = new short[nstop-nstart];
	for (int i=nstart; i<nstop; i++) b[i-nstart] = a[i];
	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 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 double[] move(double[] a, int nstart, int nstop) // b=a
{
	if (nstart>nstop){
		warning("nstart>nstop: "+nstart+">"+nstop);
		return null;
	}
	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 float[] move(float[] a, int nstart, int nstop) // b=a
{
	if (nstart>nstop){
		warning("nstart>nstop: "+nstart+">"+nstop);
		return null;
	}
	int n = a.length;
	if (nstop>n) warning("nstop>n");
	float[] b = new float[nstop-nstart];
	for (int i=nstart; i<nstop; i++) b[i-nstart] = a[mod(i,n)];
	return b;
}
public static long[] move(long[] a, int nstart, int nstop) // b=a
{
	if (nstart>nstop){
		warning("nstart>nstop: "+nstart+">"+nstop);
		return null;
	}
	int n = a.length;
	if (nstop>n) warning("nstop>n: "+nstop+">"+n);
	long[] b = new long[nstop-nstart];
	for (int i=nstart; i<nstop; i++) b[i-nstart] = a[i];
	return b;
}
public static int[] move(int[] a, int nstart, int nstop) // b=a
{
	if (nstart>nstop){
		warning("nstart>nstop: "+nstart+">"+nstop);
		return null;
	}
	int n = a.length;
	if (nstop>n) warning("nstop>n: "+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]
{
	if ((a==null)&&(b==null)) return null;
	if (a==null) return move(b);
	if (b==null) return move(a);
	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[] appen(double[] a, double b)// c=[a;b]
{
	return join(a,new double[]{b});
}
public static double[] join(double[] a, double[] b) // c=[a;b]
{
	if ((a==null)&&(b==null)) return null;
	if (a==null) return move(b);
	if (b==null) return move(a);
	int n = a.length;
	int m = b.length;
	double c[] = new double[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 byte[] join(byte[] a, byte[] b) // c=[a;b]
{
	if ((a==null)&&(b==null)) return null;
	if (a==null) return move(b);
	if (b==null) return move(a);
	int n = a.length;
	int m = b.length;
	byte c[] = new byte[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 double[][] crop(double[][] a, int n, int m) // b=a[0..n-1][0..m-1]
{
	int N = a.length, M = a[0].length;
	if ((n>N)||(m>M)) error("crop: (n>N)||(m>M) n="+n+" N="+N+" m="+m+" M="+M);
	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[] 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 int[] find(byte[] a, byte 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 findc(boolean[] a, boolean c) // suranda skaiciu indeksu, kuriems a==c
{
	int N=a.length, n=0;
	for (int i=0; i<N; i++) if (a[i]==c) n++;
	return n;
} //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 variation(double[] a)
{
	int n = a.length;
	if (n==1) return 0.0;
	double D=0;
	for (int i=1; i<n; i++) D += Math.abs(a[i]-a[i-1]);
	return D/(n-1);
}

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));
}
// std atmetus didziausius nuokrypius
public static double stdsixt(int[] a)
{
	int n = a.length;
	if (n==1) return 0.0;
	int[] ii=sort(a);
	int n0=n/16,n1=15*n/16,nx=n1-n0;
	double[] b = new double[nx];
	for (int i=0; i<nx; i++) b[i]=a[ii[n0+i]];
	return std(b);
}
public static double stdsixt(double[] a)
{
	int n = a.length;
	if (n==1) return 0.0;
	int[] ii=sort(a);
	int n0=n/16,n1=15*n/16,nx=n1-n0;
	double[] b = new double[nx];
	for (int i=0; i<nx; i++) b[i]=a[ii[n0+i]];
	return std(b);
}

public static double maxAbs(double[] a)
{
	int n = a.length;
	int j = 0;
	for (int i=1; i<n; i++) if (Math.abs(a[j])<Math.abs(a[i])) j = i;
	return Math.abs(a[j]);
}
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;
//	int j1=j; while ((j1+1<n)&&(a[j1+1]==a[j])) j1++;
	return a[j];
}
public static double max(double[][] a)
{
	int n = a.length;
	double p=max(a[0]);
	for (int i=1; i<n; i++) p=Math.max(p,max(a[i]));
	return p;
}
public static double min(double[][] a)
{
	int n = a.length;
	double p=min(a[0]);
	for (int i=1; i<n; i++) p=Math.min(p,min(a[i]));
	return p;
}
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 byte max(byte[] 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 byte min(byte[] 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 min(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 int min(int[][] a)
{
	return min(a2a1(a,1));
}
public static int max(int[][] a)
{
	return max(a2a1(a,1));
}
public static int indOfMin(int[] a)
{
	int n = a.length, m=0;
	for (int i=1; i<n; i++)
		if (a[m]>a[i]) m = i;
	return m;
}
public static int indOfMax(int[] a)
{
	int n = a.length, m=0;
	for (int i=1; i<n; i++)
		if (a[m]<a[i]) m = i;
	return m;
}
public static int indOfMax(double[] a)
{
	int n = a.length, m=0;
	for (int i=1; i<n; i++)
		if (a[m]<a[i]) m = i;
	return m;
}
public static int indOfAbsMax(double[] a)
{
	int n = a.length, m=0;
	for (int i=1; i<n; i++)
		if (Math.abs(a[m])<Math.abs(a[i])) m = i;
	return m;
}
public static int indOfAbsMax(int[] a)
{
	int n = a.length, m=0;
	for (int i=1; i<n; i++)
		if (Math.abs(a[m])<Math.abs(a[i])) m = 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];
//		my.print(new int[] {a.length,a[0].length},"my.max a");
		for (int i=0; i<n; i++){
//			my.print(new int[] {i,k},"i,k");
//			my.print(new int[] {a.length,a[i].length},"a.length,a[i].length");
			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)
{
	int N=s.length(), L=80, K=N/L;
	for (int k=K; k>0; k--) s=s.substring(0,k*L)+"\n\r"+s.substring(k*L+1,s.length());
	JOptionPane.showMessageDialog(null,s,"Klaida",JOptionPane.ERROR_MESSAGE);
	System.out.println(s);
//	int i=1; while (i==1) i=1;
//	System.out.print("\07");
	int[] ex=new int[0]; ex[0]=0;
	System.exit(0);
}
//Sinonimas
public static void error(String s){ print_exit(s);}
public static void warning(String s)
{
//	JOptionPane.showMessageDialog(null,s,"Perspejimas",JOptionPane.WARNING_MESSAGE);
	System.out.println("Warning: "+s);
}
public static void warningError(String s)
{
	JOptionPane.showMessageDialog(null,s,"Perspejimas",JOptionPane.ERROR_MESSAGE);
	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;
	for (int i=0; i<a.length; i++) print(a[i],s+"["+i+"]");
}//print
public static void print(float[] a, String s)
{
	if (dummyprint) return;
	println(s);
	int m = a.length;
	String S = "";
	for (int i=0; i<m; i++)
			S = S + toString(a[i]);
	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;
	int n = a.length;
	System.out.println(s+"["+n+"]"+":");
	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(Object s)
{
	if (dummyprint) return;
	System.out.println(s);
}//print

public static void p(Object s)
{
	println(s);
}//p

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;
}
public static int[][] trans(int[][] a){
 int n = a.length;
 int m = a[0].length;
 int[][] b = new int[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(byte a[], int ia[], int lo0, int hi0)
{
int lo = lo0;
int hi = hi0,k;
byte mid,T;

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(byte[] A)
{
 boolean test = false;
 int na = A.length;
 // padarau kopija, kad nesugadinti A
 byte[] a = new byte[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 );
 }
}
private static void QuickSort(float a[], int ia[], int lo0, int hi0)
{
int lo = lo0;
int hi = hi0,k;
float mid,T;

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(float[] A)
{
 boolean test = false;
 int na = A.length;
 // padarau kopija, kad nesugadinti A
 float[] a = new float[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(Float.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(Float.toString(A[ia[i]]));
	}
 return ia;
}

public static int[] sort(long[] A)
{
 boolean test = false;
 int na = A.length;
 // padarau kopija, kad nesugadinti A
 long[] a = new long[na];
 int[] ia = new int[na];
 for (int i = 0; i<na; i++) { a[i] = A[i]; ia[i] = i;}
 QuickSort(a, ia, 0, na - 1);
 return ia;
}
private static void QuickSort(long a[], int ia[], int lo0, int hi0)
{
int lo = lo0;
int hi = hi0;
long mid,T;
int k;

if (hi0>lo0){
 mid = a[(lo0+hi0)/2];
 while (lo<=hi){
	while ((lo<hi0)&&(a[lo]<mid)) ++lo;
	while ((hi>lo0)&&(a[hi]>mid)) --hi;
	if (lo<=hi){
		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 int[][] sort(double a[][], int dim)
{
	int m = a.length;
	int k = a[0].length;
	int[][] ia = new int[m][k];
	if (dim==2)
		for (int j = 0; j<m; j++) ia[j] = sort(a[j]);
	else
		print_exit("sort Dar neatiderinta su dim!=2");
	return ia;
}

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

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

 // loop through the array until indices cross
 while( lo <= hi )
 {
	while( ( lo < hi0 ) && ( a[lo].compareTo(mid)<0 ) ) ++lo;
	while( ( hi > lo0 ) && ( a[hi].compareTo(mid)>0 ) ) --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(String[] A)
{
 boolean test = true;
 int na = A.length;
 // padarau kopija, kad nesugadinti A
 String[] a = new String[na];
 int[] ia = new int[na];
 for (int i = 0; i<na; i++) { a[i] = new String(A[i]); ia[i] = i;}
 if (test) { System.out.println("Init:");
	for (int i = 0; i<na; i++) System.out.println(A[i]);
	}
 QuickSort(a, ia, 0, na - 1);
 if (test) { System.out.println("Sorted:");
	for (int i = 0; i<na; i++) System.out.println(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 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 CloseDataOutputStream(DataOutputStream fout){
 try {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
synchronized public static int readShort2Int(DataInputStream f){
 byte b1,b2=b1=0;
 try { b1=f.readByte(); b2=f.readByte();}
 catch(IOException e) {error("readShort: " + e); }
// if (testCount++<4) my.println("b12: "+b1+" "+b2+" "+((((short)b2)<<8)));
 return (0xFF&b1|(((short)b2)<<8));
} //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
public static double scalar_product(double[] a){
	return scalar_product(a,a);
} //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 int[] a2a1(int[][] a, int dim){
 testdim(dim);
 int n = a.length;
 int m = a[0].length;
 int[] b = new int[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 int[][] a1a2(int[] a, int nx,int ny){
 int n = a.length;
 if (n!=nx*ny) my.error("n!=nx*ny");
 int[][] b=new int[nx][ny];
 int k = 0;
 for (int j=0; j<ny; j++) for (int i=0; i<nx; i++) b[i][j]=a[k++];
	return b;
} //a1a2
public static double[][] a1a2(double[] a, int nx,int ny){
 int n = a.length;
 if (n!=nx*ny) my.error("n!=nx*ny");
 double[][] b=new double[nx][ny];
 int k = 0;
 for (int j=0; j<ny; j++) for (int i=0; i<nx; i++) b[i][j]=a[k++];
	return b;
} //a1a2

public static double[] getColumn(double[][] a, int col){
 int n = a.length;
 int m = a[0].length;
 if (col>=m) error("col>=m");
 double[] b = new double[n];
 for (int i=0; i<n; i++) b[i] = a[i][col];
 return b;
} //getColumn
public static int[] getColumn(int[][] a, int col){
 int n = a.length;
 int m = a[0].length;
 if (col>=m) error("col>=m");
 int[] b = new int[n];
 for (int i=0; i<n; i++) b[i] = a[i][col];
 return b;
} //getColumn
public static void putColumn(double[][] a, double[] c,int col){
 int n = a.length; int m = a[0].length;
 if (col>=m) error("col>=m");
 if (c.length!=n) error("c.length!=n "+c.length+" "+m);
 for (int i=0; i<n; i++) a[i][col] = c[i];
} //putColumn

public static String toString(double[] a){
	int N1=a.length-1; String S="[";
	for (int n=0; n<N1; n++) S+=toString(a[n])+",";
	return S+toString(a[N1])+"]";
}

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(double[][] a, String vardas, int npokabl){
 String S=vardas+":\n";
 for (int j=0; j<a.length; j++){
	for (int i=0; i<a[0].length; i++) S+=" "+toString(a[j][i],npokabl);
	S+="\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;
} //
public static String toString(int[] a, int maxElements){
 String S; S="";
 if (maxElements<1||a.length<1) return S;
 if (a.length==1) return S+Integer.toString(a[0]);
 if (a.length<=maxElements){
	for (int i=0; i<a.length-1; i++) S += Integer.toString(a[i])+",";
 }
 else{
	for (int i=0; i<maxElements-1; i++) S += Integer.toString(a[i])+",";
	S+="...";
 }
 return S + Integer.toString(a[a.length-1]);
} //

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 boolean exists(String failas, int minLength){
 if (!exists(failas)) return false;
 return length(new File(failas))>=minLength;
}

public static long length(File F){
 long n=-1;
 RandomAccessFile f=null;
 try{f=new RandomAccessFile(F,"r");}
 catch(FileNotFoundException e){return n;}
 try{n=f.length(); f.close();}
 catch(IOException e){return -1;}
 return n;
}

public static boolean copy(File Source, File Dest){
 long n=-1;
 byte[] b=null;
 RandomAccessFile f=null, w=null;
 try{
	f=new RandomAccessFile(Source,"r");
	w=new RandomAccessFile(Dest,"w");
 }
 catch(FileNotFoundException e){return false;}
 try{
	n=f.length(); if (n>Integer.MAX_VALUE) error("copy: per ilgas failas "+f+" : "+n);
	b=new byte[(int)n]; f.read(b); f.close();
 }
 catch(IOException e){return false;}
 try{w.write(b); w.close();}
 catch(IOException e){return false;}
 return true;
}

public static RandomAccessFile RandomAccessFile(String failas, String mode){
 RandomAccessFile f=null;
 try {f=new RandomAccessFile(new File(failas),mode);}
 catch(IOException e){warning("RandomAccessFile "+failas+": "+e); return null;}
 return f;
}
public static void close(RandomAccessFile f){
 try {f.close();}
 catch(IOException e){error("close "+f+": "+e);}
}
public static String readLine(RandomAccessFile f){
 String S=null;
 try {S=f.readLine();}
 catch(IOException e){warning("readLine "+f+": "+e);}
 return S;
}

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;
}
public static int[] randperm(int n){
 Random R=new Random(n+((long)n)<<31);
 int[] j = new int[n];
 int w,k;
 for (int i=0; i<n; i++) j[i]=i;
 for (int i=0; i<n; i++) {
	w=(int)(n*R.nextDouble());
	if (w==n) w=n-1;
	k=j[i]; j[i]=j[w]; j[w]=k;
 }
 return j;
}

public static int[] randperm(int n,int[] j0){
 Random R=new Random(n+((long)n)<<31);
 int[] j = new int[n];
 int w,k;
 if (j0==null)	for (int i=0; i<n; i++) j[i]=i;
	else	for (int i=0; i<n; i++) j[i]=j0[i];
 for (int i=0; i<n; i++) {
	w=(int)(n*R.nextDouble());
	if (w==n) w=n-1;
	k=j[i]; j[i]=j[w]; j[w]=k;
 }
 return j;
}

public static void pause(int times, int pauseTimeMillisSek){
	MyPause.wait(times,pauseTimeMillisSek);
	my.println("pause after wait:"+pause);
}
public static void pause(){
 if (whileNotEnterPause) whileNotEnterPause();
 else{ pause=!pause; while (pause) ;}
// try{System.in.read();} catch(IOException er){};
// try{System.in.read();} catch(IOException er){};
}

public static void whileNotEnterPause(){
 try{System.in.read();} catch(IOException er){};
 try{System.in.read();} catch(IOException er){};
}

public static int[] getUniqueInd(int[] x, int[] y){
 int n=x.length,m=0;
 int[] ind=new int[n];
 Vector V=new Vector();
 for (int i=0; i<n; i++) if (!V.contains(new java.awt.Point(x[i],y[i]))){
	ind[m++]=i;
	V.add(new java.awt.Point(x[i],y[i]));
 }
 return move(ind,0,m);
}
public static double median(double[] u){
 int[] ix=sort(u);
 return u[ix[ix.length/2]];
}
public static int median(int[] u){
 int[] ix=sort(u);
 return u[ix[ix.length/2]];
}
public static String getExtension(String S) {
 if(S != null) {
	int i = S.lastIndexOf('.');
	if(i>0&&i<S.length()-1)
		return S.substring(i+1);
 }
 return null;
}
public static int[] stack2int(Stack st)
{
	int n = st.size();
	int[] a = new int[n];
	for (int i=0; i<n; i++) a[i]=((Integer)st.pop()).intValue();
	return a;
}
public static double[] int2double(int[] a)
{
	int n = a.length;
	double[] A=new double[n];
	for (int i=0; i<n; i++) A[i]=a[i];
	return A;
}
public static double[][] int2double(int[][] a)
{
	int n = a.length,	m = a[0].length;
	double[][] A=new double[n][m];
	for (int i=0; i<n; i++)	for (int j=0; j<m; j++)
		A[i][j]=a[i][j];
	return A;
}
public static int[] double2int(double[] a)
{
	int n = a.length;
	int[] A=new int[n];
	for (int i=0; i<n; i++) A[i]=(int)Math.round(a[i]);
	return A;
}
public static int[][] double2int(double[][] a)
{
	int n = a.length,m = a[0].length;
	int[][] A=new int[n][m];
	for (int i=0; i<n; i++) for (int j=0; j<m; j++)
		A[i][j]=(int)Math.round(a[i][j]);
	return A;
}
// decibelu diapozona apibrezia maxDB
public static int[] double2db(double[] a)

{
	int n = a.length;
	int[] A=new int[n];
	double mx=Math.max(Math.abs(max(a)),Math.abs(min(a)))+eps,
		q=255.0/maxDB;
	for (int i=0; i<n; i++) A[i]=(int)(q*Math.max(0,maxDB+db*Math.log(Math.max(Math.abs(a[i])/mx,Double.MIN_VALUE))));
	return A;
}
public static int[] vect2int(Vector v){
 int n=v.size(); int[] j=new int[n];
 for (int l=0; l<n; l++) j[l]=((Integer)(v.get(l))).intValue();
 return j;
}

public static int[] localMAX(double[] u){
 int n=u.length,n1=n-1,L=0;
 int[] l=new int[n];
 for (int i=1; i<n1; i++) if ((u[i-1]<=u[i])&&(u[i+1]<u[i])) l[L++]=i;
 if (L==0) if (u[0]>u[n1]) l[L++]=0; else l[L++]=n1;
 return move(l,0,L);
}
public static int[] localMIN(double[] u){
 int n=u.length,n1=n-1,L=0;
 int[] l=new int[n];
 for (int i=1; i<n1; i++) if ((u[i-1]>u[i])&&(u[i+1]>=u[i])) l[L++]=i;
 if (L==0) if (u[0]<=u[n1]) l[L++]=0; else l[L++]=n1;
 return move(l,0,L);
}
public static int[] localMAX(int[] u){
 int n=u.length,n1=n-1,L=0;
 int[] l=new int[n];
 if (u[0]>=u[1]) l[L++]=0; if ((n1>0)&&(u[n1]>=u[n1-1])) l[L++]=n1;
 for (int i=1; i<n1; i++) if ((u[i-1]<=u[i])&&(u[i+1]<u[i])) l[L++]=i;
 return move(l,0,L);
}
public static int[] localMIN(int[] u){
 int n=u.length,n1=n-1,L=0;
 int[] l=new int[n];
 if (u[0]<=u[1]) l[L++]=0; if ((n1>0)&&(u[n1]<=u[n1-1])) l[L++]=n1;
 for (int i=1; i<n1; i++) if ((u[i-1]>u[i])&&(u[i+1]>=u[i])) l[L++]=i;
 return move(l,0,L);
}
public static int[] localMINMAX(int[] u){
 int[] mi=localMIN(u),ma=localMAX(u);
 int N=u.length, Mi=mi.length, Ma=ma.length;
 boolean[] b=new boolean[N];
 for (int i=0; i<N; i++) b[i]=false;
 for (int i=0; i<Mi; i++) b[mi[i]]=true;
 for (int i=0; i<Ma; i++) b[ma[i]]=true;
 int[] loc=new int[Mi+Ma];
 int nb=0; for (int i=0; i<N; i++) if (b[i]) loc[nb++]=i;
 if (loc.length==nb)	return loc; else return move(loc,0,nb);
}
public static boolean arVyras(String S){
//	my.print(new boolean[]{my.arVyras("  Algirdas    Bastys "),my.arVyras("  Algirdas    Basty "), my.arVyras("  Algirda    Basty ")},"ttn");
 if (S==null) return true;
 int visoZod=0, vyrZod=0;
 String z;
 StringTokenizer st=new StringTokenizer(S);
 while (st.hasMoreTokens()){
	visoZod++;
	z=st.nextToken();
	if (z.toLowerCase().lastIndexOf("s")>=z.length()-1) vyrZod++;
 }
 return vyrZod*2>=visoZod;
}

// tikrina ar duotojo klaseje yra laukai
public static void setField(Class C, String laukas, String value){
 Field F=null;
 try{ F=C.getField(toField(laukas)); }
 catch(NoSuchFieldException ev){error("Nerastas "+C+" laukas "+laukas);}
 try{ F.set(C,value);}
 catch(IllegalAccessException ev){my.error("F.set error "+C+" "+laukas+" "+value);}
} //setField

public static String getField(Class C, String laukas){
 Field F=null;
 String S=null;
 try{ F=C.getField(toField(laukas)); }
 catch(NoSuchFieldException ev){error("Nerastas "+C+" laukas "+laukas);}
 try{ S=""+F.get(C);}
 catch(IllegalAccessException ev){my.error("F.get error "+C+" "+laukas);}
 return S;
} //getField

public static double[][] getFieldArr2(Class C, String laukas){
 Field F=null;
 double[][] S=null;
 try{ F=C.getField(toField(laukas)); }
 catch(NoSuchFieldException ev){error("Nerastas "+C+" laukas "+laukas);}
 try{ S=(double[][])F.get(C);}
 catch(IllegalAccessException ev){my.error("F.get error "+C+" "+laukas);}
 return S;
} //getFieldArr2
public static void setFieldArr2(Class C, String laukas, double[][] u){
 Field F=null;
 try{ F=C.getField(toField(laukas)); }
 catch(NoSuchFieldException ev){error("Nerastas "+C+" laukas "+laukas);}
 try{ F.set(C,u);}
 catch(IllegalAccessException ev){my.error("F.get error "+C+" "+laukas);}
} //setFieldArr2

//randame eiluciu kryptimi maziausiu pokyciu stdsixt variacijas
// maziausi pokycius ieskodami 2^l, l=0,1,...,minPok (8) atstumu
// grazinamas rez[u.length][minPok]
public static double[][] getMinPokycius(double[][] u){
 int L2=minPok;
 int N=u.length, M=u[0].length;
 int[] o=new int[M], k0=new int[M], k1=new int[M];
 double[][] v=new double[N][M], rez=new double[N][L2];
 double[] w=new double[M],pMin=new double[M];
 double p,q;
 int L,K,k;
 for (int l=0; l<L2; l++){
    L=Math.min(M-1,1<<l);
    for (int i=0; i<M; i++){
	if (l==0){
		pMin[i]=Double.MAX_VALUE; o[i]=i; k0[i]=i-1; k1[i]=i+1;
	}
	p=pMin[i]; K=0;
	while (K<L){
	    k=k0[i];
	    if (k!=-1) {
		k0[i]--; K++; q=0;
		for (int j=0; j<N; j++) q+=(u[j][i]-u[j][k])*(u[j][i]-u[j][k]);
		if (p>q) { p=q; o[i]=k;}
	    }
		else if (k1[i]==M) K=L;
	    k=k1[i];
	    if (k!=M) {
		k1[i]++; K++; q=0;
		for (int j=0; j<N; j++) q+=(u[j][i]-u[j][k])*(u[j][i]-u[j][k]);
		if (p>q) { p=q; o[i]=k;}
	    }
		else if (k0[i]==-1) K=L;
	}
	pMin[i]=p;
	for (int j=0; j<N; j++) v[j][i]=u[j][i]-u[j][o[i]];
    }
    for (int j=0; j<N; j++) rez[j][l]=stdsixt(v[j]);
 }
 return rez;
}

public static byte[] int2byte(int[] u){
 int l=u.length; byte[] b = new byte[l];
 for (int i=0; i<l; i++) b[i]=(byte)((u[i] & 0xff)-128);
 return b;
} //int2byte
public static int[] byte2int(byte[] b){
 int l=b.length; int[] u = new int[l];
 int R,G,B,a=(255 << 24);
 for (int i=0; i<l; i++){ B=((int)b[i])+128; u[i]=a|(B<<16)|(B<<8)|B;}
 return u;
} //byte2int
public static int[][] simpleByte2int(byte[][] b){
 int nx=b.length, ny=b[0].length;
 int[][] u = new int[nx][ny];
 for (int j=0; j<ny; j++) for (int i=0; i<nx; i++)
 	u[i][j] = b[i][j];
 return u;
} //byte2int
//	pvz: sampleDown(b,0,2) su lyginiais, sampleDown(b,1,2) su nelyginiais lyginiais,
public static byte[] sampleDown(byte[] b, int initIndex, int scale){
 int N=b.length, M=(N-1-initIndex)/scale+1,j=0;
 byte[] bScaled=new byte[M];
 for (int i=initIndex; i<N; i+=scale) bScaled[j++]=b[i];
 return bScaled;
}
public static int nextPow2(int n){
 int N=1; while (N<n) N<<=1;
	return N;
}
public static short[] int2short(int X[]){
	int N=X.length;
	short[] x=new short[N];
	for (int n=0; n<N; n++) x[n]=int2short(X[n]);
	return x;
}
public static short int2short(int x){
	if (x>Short.MAX_VALUE) x=Short.MAX_VALUE;
	else if (x<Short.MIN_VALUE) x=Short.MIN_VALUE;
	return (short) x;
}
public static int[] invert(int[] x){
 int n=x.length, n1=n-1;
 int[] x_=new int[n];
 for (int i=0; i<n; i++) x_[i]=x[n1-i];
 return x_;
}
public static void invert(byte[] x){
 int n=x.length, n1=n-1,n2=n/2;
 byte b;
 for (int i=0; i<n2; i++) {b=x[i];x[i]=x[n1-i];x[n1-i]=b;}
}
public static String invert(String S){
 byte[] b=S.getBytes(); invert(b);
 return new String(b);
}
public static String toField(String S){
 return S.replace('.','_');
}

public static String[] file(String failas, int rows){
 RandomAccessFile f=RandomAccessFile(failas,"r");
 String[] S=new String[rows];
 for (int i=0; i<rows; i++) S[i]=readLine(f);
 close(f);
 return S;
}
public static void saveToFile(String failas, String tekstas, boolean append){
	saveToFile(failas,new String[]{tekstas},append);
}
public static void saveToFile(String failas, String tekstas){
	saveToFile(failas,new String[]{tekstas},true);
}
public static void saveToFile(String failas, String[] tekstas,boolean append){
 RandomAccessFile f = RandomAccessFile(failas,"rw");
 int rows=tekstas.length;
 try{
	 if (append) f.seek(f.length());
	for (int i=0; i<rows; i++) f.write(tekstas[i].getBytes());
 	close(f);
}
 catch(IOException err){error(failas+" : "+err);};
}

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 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 writeChars(DataOutputStream fout,String S){
 try {fout.writeChars(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());
 }
}

} //my

class MyPause extends Thread{

	private int waitTimeMillis = -1;
	private int times = 1;

	public static void wait(int times,int waitTimeMillis){
		MyPause p = new MyPause(times, waitTimeMillis);
		p.start();
	}
	public MyPause(int times,int waitTimeMillis){
		this.waitTimeMillis = waitTimeMillis;
		this.times = times;
	}

	public void run(){
		for (int n = 0; n<times; n++){
			my.pause = !my.pause;
			my.p("n="+n+", pause="+my.pause);
			try{
				sleep(waitTimeMillis);
			}
			catch(InterruptedException ie){};
			my.pause = !my.pause;
			my.p("n="+n+", pause="+my.pause);
			try{
				sleep(waitTimeMillis);
			}
			catch(InterruptedException ie){};
		}
		my.pause = !my.pause;
		stop();
	}
}