class tool
{
static void swap(int a[],int x,int y)
{
int t=a[x];
a[x]=a[y];
a[y]=t;
}
static long qpow(long x,long y)
{
long mod=1000000007,res=1;
for(x%=mod;y!=0;y>>=1,x=x*x%mod)
if((y&1)!=0)res=res*x%mod;
return res;
}
static void sort(int a[],int l,int r)
{
if(l>=r)return;
Random rd=new Random();
int x=rd.nextInt(r)%(r-l+1)+l;
swap(a,x,r);
int i=l,j=r-1;
while(true)
{
while(a[i]<a[r])i++;
while(a[j]>a[r])j--;
if(j<i)break;
swap(a,i++,j--);
}
swap(a,i,r);
if(l<i-1)sort(a,l,i-1);
if(i<r)sort(a,i,r);
}
};
static class InputReader
{
public BufferedReader reader;
public StringTokenizer tokenizer;
public InputReader(InputStream stream)
{
reader=new BufferedReader(new InputStreamReader(stream),32768);
tokenizer=null;
}
public String next()
{
while(tokenizer == null || !tokenizer.hasMoreTokens())
{
try
{
tokenizer=new StringTokenizer(reader.readLine());
}
catch(IOException e)
{
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
public int nextInt()
{
return Integer.parseInt(next());
}
}
