import java.util.*;

import java.math.*;

import static java.lang.Math.*;

public class Multifactorial {

	public String calcMultiFact(int n, int k) {

		long result=1;

		final long nlimit=1000000000000000000l;

		while(true) {

			if(result>nlimit/n) {

				return "overflow";

			}

			result*=n;

			if(n<=k) {

				break;

			}

			n-=k;

		}

		return Long.toString(result);

	}

}

import java.util.*;

import java.math.*;

import static java.lang.Math.*;

public class ExpensiveTravel {

	static class Fraction {

		public int a,b;

		public Fraction() {

			a=1;

			b=1;

		}

		public Fraction(int a,int b) {

			this.a=a;

			this.b=b;

		}

		public static int gcd(int x,int y) {

			if(y==0) {

				return x;

			}

			return gcd(y,x%y);

		}

		private Fraction simple() {

			int t=gcd(a,b);

			a/=t;

			b/=t;

			return this;

		}

		public Fraction add(Fraction p) {

			int bb=p.b*b;

			int aa=a*p.b+p.a*b;

			return new Fraction(aa,bb).simple();

		}

		public boolean ok() {

			return a>b;

		}

		public boolean less(Fraction p) {

			return a*p.b<p.a*b;

		}

	}

	static class Node {

		public Fraction pref;

		public Fraction f;

		public int cost;

		public boolean inq;

		public Node() {

			f=new Fraction(0,1);

			cost=0;

			inq=false;

		}

		Node add(int t) {

			Node p=new Node();

			p.f=new Fraction(f.a,f.b).add(new Fraction(1,t));

			p.cost=cost;

			p.inq=inq;

			if(p.f.ok()) {

				++p.cost;

				p.f=pref.add(new Fraction(1,t));

			}

			p.pref=new Fraction(1,t);

			return p;

		}

		public boolean less(Node p) {

			return cost<p.cost||cost==p.cost&&f.less(p.f);

		}

		public int result() {

			if(cost==-1) {

				return -1;

			}

			return cost+1;

		}

	}

	public int minTime(String[] m, int startRow, int startCol, int endRow, int endCol) {

		final int N=m.length;

		final int M=m[0].length();

		int[][] g=new int[N][M];

		for(int i=0;i<N;++i) {

			for(int j=0;j<M;++j) {

				char c=m[i].charAt(j);

				g[i][j]=c-'0';

			}

		}

		--startRow;

		--startCol;

		--endRow;

		--endCol;

		if(g[startRow][startCol]==1||g[endRow][endCol]==1) {

			return -1;

		}

		Node[][] f=new Node[N][];

		for(int i=0;i<N;++i) {

			f[i]=new Node[M];

			for(int j=0;j<M;++j) {

				f[i][j]=new Node();

				f[i][j].cost=-1;

			}

		}

		Queue<Integer> queue=new LinkedList<>();

		f[startRow][startCol].f=new Fraction(1,g[startRow][startCol]);

		f[startRow][startCol].pref=new Fraction(1,g[startRow][startCol]);

		f[startRow][startCol].inq=true;

		f[startRow][startCol].cost=0;

		queue.offer(startRow*100+startCol);

		final int[] dx={0,0,1,-1};

		final int[] dy={1,-1,0,0};

		while(!queue.isEmpty()) {

			final int x=queue.peek()/100;

			final int y=queue.peek()%100;

			queue.poll();

			f[x][y].inq=false;

			if(x==endRow&&y==endCol) {

				continue;

			}

			for(int i=0;i<4;++i) {

				final int xx=x+dx[i];

				final int yy=y+dy[i];

				if(xx<0||xx>=N||yy<0||yy>=M) {

					continue;

				}

				if(g[xx][yy]==1) {

					continue;

				}

				Node t=f[x][y].add(g[xx][yy]);

				if(f[xx][yy].cost==-1||t.less(f[xx][yy])) {

					f[xx][yy]=t;

					if(!f[xx][yy].inq) {

						f[xx][yy].inq=true;

						queue.offer(xx*100+yy);

					}

				}

			}

		}

		return f[endRow][endCol].result();

	}

}

import java.util.*;

import java.math.*;

import static java.lang.Math.*;

public class RandomFights {

	int[] get(int[] X,int n) {

		final int m=X.length;

		int j=0;

		int[] R=new int[n];

		for(int i=0;i<n;++i) {

			R[i]=X[j];

			int s=(j+1)%m;

			X[j]=((X[j]^X[s])+13)%49999;

			j=s;

		}

		return R;

	}

	BigInteger int2big(long x) {

		return new BigInteger(Long.toString(x));

	}

	public double expectedNrOfPoints(int[] A,int[] B,int n) {

		int[] a=get(A,n);

		int[] b=get(B,n);

		Arrays.sort(a);

		Arrays.sort(b);

		BigInteger nxt=BigInteger.ZERO,nxt2=BigInteger.ZERO;

		for(int i=0;i<n;++i) {

			nxt=nxt.add(int2big(b[i]));

			nxt2=nxt2.add(int2big((long)b[i]*b[i]));

		}

		BigInteger result=BigInteger.ZERO;

		BigInteger pre=BigInteger.ZERO,pre2=BigInteger.ZERO;

		int k=0;

		for(int i=0;i<n;++i) {

			while(k<n&&b[k]<=a[i]) {

				pre=pre.add(int2big(b[k]));

				pre2=pre2.add(int2big((long)b[k]*b[k]));

				nxt=nxt.subtract(int2big(b[k]));

				nxt2=nxt2.subtract(int2big((long)b[k]*b[k]));

				++k;

			}

			BigInteger tmp=int2big((long)k*a[i]*a[i]).subtract(pre.multiply(int2big(a[i]*2))).add(pre2);

			result=result.add(tmp);

			tmp=int2big((long)(n-k)*a[i]*a[i]).subtract(nxt.multiply(int2big(a[i]*2))).add(nxt2);

			result=result.subtract(tmp);

		}

		BigInteger[] last=result.divideAndRemainder(int2big(n));

		return Double.valueOf(last[0].toString())+Double.valueOf(last[1].toString())/n;

	}

}