/* package whatever; // don't place package name! */
 
import java.util.*;
import java.lang.*;
import java.io.*;
 
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
	static void quickSort(int[] x,int l,int r){
if(l<r){
    int pivIdx=l;
    int pivVal=x[l];
    x[pivIdx]=x[r];
    x[r]=pivVal;
    int i=l-1;
    int j=r;
    do{
do{i++;}while (x[i]<pivVal);
do{j--;
    if(j<0){
        break;
    }
}while (x[j]>pivVal);
if(i<j){
    int temp =x[i];
    x[i]=x[j];
    x[j]=temp;
}
    }while (i<j);
    x[r]=x[i];
    x[i]=pivVal;
    quickSort(x,l,i-1);
    quickSort(x,i+1,r);
}
    }
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
	}
}

LyogcGFja2FnZSB3aGF0ZXZlcjsgLy8gZG9uJ3QgcGxhY2UgcGFja2FnZSBuYW1lISAqLwoKaW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5sYW5nLio7CmltcG9ydCBqYXZhLmlvLio7CgovKiBOYW1lIG9mIHRoZSBjbGFzcyBoYXMgdG8gYmUgIk1haW4iIG9ubHkgaWYgdGhlIGNsYXNzIGlzIHB1YmxpYy4gKi8KY2xhc3MgSWRlb25lCnsKCXN0YXRpYyB2b2lkIHF1aWNrU29ydChpbnRbXSB4LGludCBsLGludCByKXsKaWYobDxyKXsKICAgIGludCBwaXZJZHg9bDsKICAgIGludCBwaXZWYWw9eFtsXTsKICAgIHhbcGl2SWR4XT14W3JdOwogICAgeFtyXT1waXZWYWw7CiAgICBpbnQgaT1sLTE7CiAgICBpbnQgaj1yOwogICAgZG97CmRve2krKzt9d2hpbGUgKHhbaV08cGl2VmFsKTsKZG97ai0tOwogICAgaWYoajwwKXsKICAgICAgICBicmVhazsKICAgIH0KfXdoaWxlICh4W2pdPnBpdlZhbCk7CmlmKGk8ail7CiAgICBpbnQgdGVtcCA9eFtpXTsKICAgIHhbaV09eFtqXTsKICAgIHhbal09dGVtcDsKfQogICAgfXdoaWxlIChpPGopOwogICAgeFtyXT14W2ldOwogICAgeFtpXT1waXZWYWw7CiAgICBxdWlja1NvcnQoeCxsLGktMSk7CiAgICBxdWlja1NvcnQoeCxpKzEscik7Cn0KICAgIH0KCXB1YmxpYyBzdGF0aWMgdm9pZCBtYWluIChTdHJpbmdbXSBhcmdzKSB0aHJvd3MgamF2YS5sYW5nLkV4Y2VwdGlvbgoJewoJCS8vIHlvdXIgY29kZSBnb2VzIGhlcmUKCX0KfQ==