public class TowersOfHanoi {
    public static void move(int n, int startPole, int endPole) {
        if (n== 0){
            return;
        }
        int intermediatePole = 6 - startPole - endPole;
        move(n-1, startPole, intermediatePole);
        System.out.println("Move " +n + " from " + startPole + " to " +endPole);
        move(n-1, intermediatePole, endPole);
    }
    public static void main(String[] args) {
        move(5, 1, 3);
    }
}

public class HeapSort
{
    private static int[] a;
    private static int n;
    private static int left;
    private static int right;
    private static int largest;
    public static void buildheap(int []a){
        n=a.length-1;
        for(int i=n/2;i>=0;i--){
            maxheap(a,i);
        }
    }
    public static void maxheap(int[] a, int i){
        left=2*i;
        right=2*i+1;
        if(left <= n && a[left] > a[i]){
            largest=left;
        }
        else{
            largest=i;
        }
        if(right <= n && a[right] > a[largest]){
            largest=right;
        }
        if(largest!=i){
            exchange(i,largest);
            maxheap(a, largest);
        }
    }
    public static void exchange(int i, int j){
        int t=a[i];
        a[i]=a[j];
        a[j]=t;
    }
    public static void sort(int []a0){
        a=a0;
        buildheap(a);
        for(int i=n;i>0;i--){
            exchange(0, i);
            n=n-1;
            maxheap(a, 0);
        }
    }
    public static void main(String[] args) {
        int []a1={4,1,3,2,16,9,10,14,8,7};
        sort(a1);
        for(int i=0;i<a1.length;i++){
            System.out.print(a1[i] + " ");
        }
    }
}

public class Adicom {
    public static void quickSort(int array[], int start, int end) {
        int i = start;
        int k = end;
        
        if (end - start >= 1) {
            int pivot = array[start];
            
            while (k > i) {
                while (array[i] <= pivot && i <= end && k > i)
                i++;
                while (array[k] > pivot && k >= start && k >= i)
                k--;
                if (k > i)
                swap(array, i, k);
            }
            swap(array, start, k);
            
            quickSort(array, start, k - 1);
            quickSort(array, k + 1, end);
        }
    }
    
    public static void swap(int array[], int index1, int index2) {
        int temp = array[index1];
        array[index1] = array[index2];
        array[index2] = temp;
    }
    
    public static void main(String[] args) {
        int[] arr = {
            5,
            66,
            13,
            87,
            19,
            1,
            94,
            10
        };
        quickSort(arr, 0, arr.length - 1); // از صفر تا اخرین اندیس ارایه
        for (int x: arr) {
            System.out.println(x);
        }
    }
}

public void binarySearch(int[] array, int search) {
    int first,last,middle;
    first  = 0;
    last   = n - 1;
    middle = (first + last)/2;
    while( first <= last ) {
        if ( array[middle] < search ) {
            first = middle + 1;
        } else if ( array[middle] == search ) {
            System.out.println(search + " found at location " + (middle + 1) + ".");
            break;
        } else {
            last = middle - 1;
        }
        middle = (first + last)/2;
    }
    if ( first > last ) {
        System.out.println(search + " is not present in the list.n");
    }
}

public boolean isPalindrome(String str) {
	boolean palindrome = false;
         
        str = str.toLowerCase();

        for (int i = 0, j = str.length() - 1; i < str.length(); i++, j-- ) {
            if (i < j) {
                if (str.charAt(i) != str.charAt(j)) {
                    return false;
                }
            }
            else { return true; }
        }   
		
        return palindrome;
}

public static double sqrt(double number) { 
        double c = number;
        double epsilon = 1e-15;
        double t = c;

        while (Math.abs(t - c/t) > epsilon*t) {
            t = (c/t + t) / 2.0;
        }
        
        return t;
    }

public static void InsertionSort( int [ ] num) {
     int j;
     int key;
     int i;  

     for (j = 1; j < num.length; j++) {
           key = num[ j ];
           for(i = j - 1; (i >= 0) && (num[ i ] < key); i--) {
                 num[ i+1 ] = num[ i ];
          }
         num[ i+1 ] = key;
     }
}

static void bubbleSort(String[] array) {
	for(int i = array.length - 1; i > 0; --i) {
		boolean bSwaped = false;
		for(int j = 0; j < i; ++j) {
			if(array[j].compareTo(array[j + 1]) > 0) {
				swap(array, j, j + 1);
				bSwaped = true;
			}
		}
		if(!bSwaped) {
			break;
		}
	}
}

static void swap(String[] array, int pos1, int pos2) {
	String temp = array[pos1];
	array[pos1] = array[pos2];
	array[pos2] = temp;
}

public static void selection_sort (int[] arr) {
      int i , j;
      int max , temp;
      for (i = arr.length-1 ; i> 0 ; i--) {
        max = 0;
        for (j = 1 ; j <= i ; j++)
          if (arr[max] <arr[j])
            max = j;
        temp = arr[i];
        arr[i] = arr[max];
        arr[max] = temp;
      }
    }

int n = 5;
for(int i=0; i<n; i++) {
	if(i<n/2+1) {
		for(int j=0; j<i*2+1; j++) {
			System.out.print("*");
		}
	} else {
		for(int j=(n-i)*2-2; j>=0; j--) {
			System.out.print("*");
		}
	}
	System.out.println();
}

public static void magicSquare(int size) {
        int[][] square = new int[10][10];

        if (size < 1 || size > 10) {
            System.out.println("Error! Size is out of range");
            return;
        }

        if (size % 2 == 0) {
            System.out.println("Error! Size is even");
            return;
        }

        for (int k = 0; k < size; k++)
            for (int l = 0; l < size; l++)
                square[k][l] = 0;

        square[0][(size - 1) / 2] = 1;

        int i, j, row, column;
        i = 0;
        j = (size - 1) / 2;
        for (int c = 2; c <= size * size; c++) {
            row = (i - 1 < 0) ? (size - 1) : (i - 1);
            column = (j - 1 < 0) ? (size - 1) : (j - 1);
            if (square[row][column] > 0)
                i = (++i) % size;
            else {
                i = row;
                j = (j - 1 < 0) ? (size - 1) : --j;
            }
            square[i][j] = c;
        }

        for (int k = 0; k < size; k++) {
            for (int l = 0; l < size; l++) {
                if (square[k][l] < 10)
                    System.out.print("0" + square[k][l] + " | ");
                else
                    System.out.print(square[k][l] + " | ");
            }
            System.out.println("");
        }
    }

public static void toPostfix(String str) {
        String temp = "";
        Stack<Character> stack = new Stack<Character>();
        for (int i = 0; i < str.length(); i++) {
            if ((str.charAt(i) >= 'a' && str.charAt(i) <= 'z') || (str.charAt(i) >= 'A' && str.charAt(i) <= 'Z')) {
                temp += str.charAt(i);
            } else if (str.charAt(i) == '+' || str.charAt(i) == '-') {
                while (stack.size() > 0) {
                    if (stack.peek() != '(')
                        temp += stack.pop();
                    else
                        stack.pop();
                }
                stack.push(str.charAt(i));
            } else if (str.charAt(i) == '*' || str.charAt(i) == '/') {
                try {
                    while (stack.peek() == '*' || stack.peek() == '/') {
                        temp += stack.pop();
                    }
                }
                catch (EmptyStackException e) {}
                stack.push(str.charAt(i));
            } else if (str.charAt(i) == '(') {
                stack.push(str.charAt(i));
            } else if (str.charAt(i) == ')') {
                try {
                    while (stack.peek() != '(') {
                        temp += stack.pop();
                    }
                }
                catch (EmptyStackException e) {}
            }
        }
        while (stack.size() > 0) {
            if (stack.peek() != '(')
                temp += stack.pop();
            else
                stack.pop();
        }

        System.out.println(temp);
    }

class Hello
{

    public static char[] list = { 'a', 'b', 'c' };


    public static void main(String[] args) throws java.lang.Exception
    {
        perm(0, list.length - 1);
    }


    public static void perm(int i, int n) {
        int j, temp;
        if (i == n) {
            for (j = 0; j <= n; j++)
                System.out.print("" + list[j]);
            System.out.println();
        } else {
            for (j = i; j <= n; j++) {
                swap(i, j);
                perm(i + 1, n);
                swap(i, j);
            }
        }
    }


    public static void swap(int i, int j) {
        char temp;
        temp = list[i];
        list[i] = list[j];
        list[j] = temp;
    }
}

public boolean makeBricks(int small, int big, int goal) {
	while(goal>=5 && big>0){
		goal -= 5;
		big--;
	}
	while(goal>=1 && small>0){
		goal -= 1;
		small--;
	}
	if(goal==0)
		return true;
	else
		return false;
}

import java.util.*;
import java.lang.*;
import java.io.*;

class Adicom
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		for (int i=0; i<n; i++) {
		    int len = sc.nextInt();
		    String str = sc.nextLine();
		    str = str.trim();
		    
		    if(len<0) {
		        len = str.length() + len;
		    }
		    String first = str.substring(len);
		    String end = str.substring(0, len);
		    
		    System.out.print(" " + first + end);
		} 
	}
}

public static boolean isPalindrome(String str) {
        System.out.println(str);
        int len = str.length();
        if (len == 1)
            return true;
        if (len == 2)
            return (str.charAt(0) == str.charAt(1));
        if (str.charAt(0) != str.charAt(len - 1)) {
            return false;
        }
        return isPalindrome(str.substring(1, len - 1));
    }

import java.util.*;
import java.lang.*;
import java.io.*;

class Adicom
{
    public static void main (String[] args)
    {
        int num = sc.nextInt();
        String str = Integer.toBinaryString(num);
        int one = 0;
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == '1') {
                one++;
            }
        }
        System.out.print(" " + one);
    }
}

import java.util.*;
import java.lang.*;
import java.io.*;
import java.math.*;

class Test
{
	public static void main (String[] args) throws java.lang.Exception
	{
	    Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int temp = n;
        int m = sc.nextInt();
        boolean[] arr = new boolean[n];
        int index = -1;
        while(n>1) {
            for(int i=0; i<m; i++){
                index += 1;
                if(index>temp-1) {
                    index -= temp;
                }
                while(arr[index]==true) {
                    index += 1;
                    if(index>temp-1) {
                        index -= temp;
                    }
                }
            }
            arr[index] = true;
            n--;
        }
        for(int i=0; i<temp; i++) {
            if(arr[i]==false) {
                System.out.print(" " + (i+1));
            }
        }
        sc.close();
	}
}

function compute_expression($expr) {
    $arr = array();
    for($i=0; $i<strlen($expr); $i++) {
        if($expr[$i]==')') {
            $a = array_pop($arr);
            $opr = array_pop($arr);
            $b = array_pop($arr);
            if($opr == '+')
                $b += $a;
            else 
                $b -= $a;
            array_pop($arr);
            $arr[] = $b;
        } else {
            $arr[] = $expr[$i];
        }
    }
    while(count($arr)>1) {
        $a = array_shift($arr);
        $opr = array_shift($arr);
        $b = array_shift($arr);
        if($opr == '+')
            $b += $a;
        else 
            $b -= $a;
        $arr[] = $b;
    }
    echo array_pop($arr);
} 

#include <iostream>
#include <string>
#include <vector>
using namespace std;

bool in_array(vector<int> *players_done, int player);
void roundRobin(int num) {
	num = (num > 0) ? (int)num : 4;
	num += num % 2;
	int opponent = 0;
	for (int round = 1; round < num; round++) {
		vector<int> players_done;

		for (int player = 1; player < num; player++) {

			if (!in_array(&players_done, player)) {
				// opponent.
				opponent = round - player;
				opponent += (opponent < 0) ? num : 1;

				if (opponent != player) {
					if ((player + opponent) % 2 == 0 ^ (player < opponent)) {
						// ^ = xor
						players_done.push_back(player);
						players_done.push_back(opponent);
					}
					else {
						players_done.push_back(opponent);
						players_done.push_back(player);
					}					
				}
			}
		}

		if (round % 2 == 0) {
			opponent = (round + num) / 2;
			players_done.push_back(num);
			players_done.push_back(opponent);
		}
		else {
			opponent = (round + 1) / 2;
			players_done.push_back(opponent);
			players_done.push_back(num);
		}


		for (int i = 0; i < players_done.size(); i+=2) {
			cout << players_done.at(i) << "-" << players_done.at(i + 1) << " ";
		}
		cout << endl;
		players_done.clear();
	}
}

bool in_array(vector<int> *players_done, int player) {
	for (int i = 0; i < players_done->size(); i++) {
		if (players_done->at(i) == player)
			return true;
	}
	return false;
}

int main() {
	int n = 6;
	roundRobin(n);

	system("PAUSE");
	return 0;
}

#include <iostream>
#include<string>
using namespace std;

string ThirdGreatest(string strArr[], int size) {
	string temp;
	for (int i = 0; i < size; i++) {
		for (int j = i+1; j < size; j++) {
			if (strArr[j].length() > strArr[i].length()) {
				temp = strArr[j];
				strArr[j] = strArr[i];
				strArr[i] = temp;
			}
		}
	}  
	return strArr[2];
}

int main() {

	string A[] = {"aaaa","www","eeeeeee", "bbbb"};
	cout << ThirdGreatest(A,sizeof(A)/sizeof(*A));

	system("PAUSE");
	return 0;
}

#include <iostream>

using namespace std;

void change(int n, int arr[], const int size)
{
	int *s = new int[size];
	for (int i = 0; i < size; i++)
		s[i] = 0;
	int i = 0;
	int R = n;
	while (R != 0 && i < size) {
		int x = R / arr[i];
		if (x != 0) {
			s[i] = x;
		}
		R = R%arr[i];
		i++;
	}

	if (R != 0)
		cout << "no Solution!";
	else {
		for (int i = 0; i < size; i++)
			cout << s[i] << "*" << arr[i] << endl;
	}
}

int main(int argc, char **argv)
{
	int a[] = { 25, 10, 5, 2, 1 };
	change(193, a, sizeof(a) / sizeof(*a));
	return 0;
}