Problem: You are given an integer n from 1 to 10^{18} without leading zeroes.

In one move you can swap any two adjacent digits in the given number in such a way that the resulting number will not contain leading zeroes. In other words, after each move the number you have cannot contain any leading zeroes.

What is the minimum number of moves you have to make to obtain a number that is divisible by 25? Print -1 if it is impossible to obtain a number that is divisible by 25.

Input

The first line contains an integer n (1 ≤ n ≤ 10^{18}). It is guaranteed that the first (left) digit of the number n is not a zero.

Output

If it is impossible to obtain a number that is divisible by 25, print -1. Otherwise print the minimum number of moves required to obtain such number.

Note that you can swap only adjacent digits in the given number.

Examples

Input

5071


Output

4


Input

705


Output

1


Input

1241367


Output

-1

Note

In the first example one of the possible sequences of moves is 5071 → 5701 → 7501 → 7510 → 7150.

Solution (in JAVA):

Solution:
import java.io.*;
import java.lang.*;
import java.text.DecimalFormat;
import java.util.*;

public class Codeforces
{
	static InputReader in = new InputReader(System.in);
	static FastReader fr = new FastReader();
	static OutputWriter out = new OutputWriter(System.out);
	
	static int MOD = 1000000007, prime[];
	static long gcd, x, y;
	static boolean isPrime[];
	static long nCr[][] = new long[1004][1004];
	
	public static void main(String[] args) throws IOException
	{
		String number = in.nextLine();
		int length = number.length();
		int freq[] = new int[10];
		int last[] = new int[10];
		Arrays.fill(last, -1);
		for(int i = 0; i < length; i++) {
			freq[(int)(number.charAt(i) - '0')]++;
			last[(int)(number.charAt(i) - '0')] = i;
		}
		/*for(int i = 0; i < 10; i++)
			System.out.println(i+" "+freq[i]+" "+last[i]);*/
		int min_swaps = Integer.MAX_VALUE;
		if(freq[0] >= 2) {
			//System.out.println("00");
			char temp[] = number.toCharArray();
			int min_temp = 0;
			int index_1 = last[0], index_2 = 0;
			for(int i = last[0]-1; i >= 0; i--) {
				if(temp[i] == '0') {
					index_2 = i;
					break;
				}
			}
			for(int i = index_1; i < length-1; i++) {
				char d = temp[i];
				temp[i] = temp[i+1];
				temp[i+1] = d;
				min_temp++;
				/*for(int j = 0; j < length; j++)
					System.out.print(temp[j]);
				System.out.println();*/
			}
			for(int i = index_2; i < length-2; i++) {
				char d = temp[i];
				temp[i] = temp[i+1];
				temp[i+1] = d;
				min_temp++;
				/*for(int j = 0; j < length; j++)
					System.out.print(temp[j]);
				System.out.println();*/
			}
			if(temp[length-2] == '0' && temp[length-1] == '0' && min_swaps > min_temp)
				min_swaps = min_temp;
			//System.out.println(min_swaps);
		}
		if(freq[2] >= 1 && freq[5] >= 1) {
			//System.out.println("25");
			char temp[] = number.toCharArray();
			int min_temp = 0;
			int index_2 = last[2], index_5 = last[5];
			if(index_2 > index_5) {
				for(int i = index_2; i < length-1; i++) {
					char d = temp[i];
					temp[i] = temp[i+1];
					temp[i+1] = d;
					min_temp++;
					/*for(int j = 0; j < length; j++)
						System.out.print(temp[j]);
					System.out.println();*/
				}
				if(index_5 == 0 && temp[1] == '0') {
					for(int i = 2; i < length-1; i++) {
						if(temp[i] != '0') {
							for(int j = i; j >= 2; j--) {
								char d = temp[j];
								temp[j] = temp[j-1];
								temp[j-1] = d;
								min_temp++;
							}
							/*for(int j = 0; j < length; j++)
								System.out.print(temp[j]);
							System.out.println();*/
							break;
						}
					}
				}
				for(int i = index_5; i < length-1; i++) {
					char d = temp[i];
					temp[i] = temp[i+1];
					temp[i+1] = d;
					min_temp++;
					/*for(int j = 0; j < length; j++)
						System.out.print(temp[j]);
					System.out.println();*/
				}
			}
			else {
				for(int i = index_5; i < length-1; i++) {
					char d = temp[i];
					temp[i] = temp[i+1];
					temp[i+1] = d;
					min_temp++;
					/*for(int j = 0; j < length; j++)
						System.out.print(temp[j]);
					System.out.println();*/
				}
				if(index_2 == 0 && temp[1] == '0') {
					for(int i = 2; i < length-1; i++) {
						if(temp[i] != '0') {
							for(int j = i; j >= 2; j--) {
								char d = temp[j];
								temp[j] = temp[j-1];
								temp[j-1] = d;
								min_temp++;
							}
							/*for(int j = 0; j < length; j++)
								System.out.print(temp[j]);
							System.out.println();*/
							break;
						}
					}
				}
				for(int i = index_2; i < length-2; i++) {
					char d = temp[i];
					temp[i] = temp[i+1];
					temp[i+1] = d;
					min_temp++;
					/*for(int j = 0; j < length; j++)
						System.out.print(temp[j]);
					System.out.println();*/
				}
			}
			if(temp[length-2] == '2' && temp[length-1] == '5' && min_swaps > min_temp)
				min_swaps = min_temp;
			//System.out.println(min_swaps);
		}
		if(freq[5] >= 1 && freq[0] >= 1) {
			//System.out.println("50");
			char temp[] = number.toCharArray();
			int min_temp = 0;
			int index_0 = last[0], index_5 = last[5];
			if(index_5 > index_0) {
				for(int i = index_5; i < length-1; i++) {
					char d = temp[i];
					temp[i] = temp[i+1];
					temp[i+1] = d;
					min_temp++;
					/*for(int j = 0; j < length; j++)
						System.out.print(temp[j]);
					System.out.println();*/
				}
				for(int i = index_0; i < length-1; i++) {
					char d = temp[i];
					temp[i] = temp[i+1];
					temp[i+1] = d;
					min_temp++;
					/*for(int j = 0; j < length; j++)
						System.out.print(temp[j]);
					System.out.println();*/
				}
			}
			else {
				for(int i = index_0; i < length-1; i++) {
					char d = temp[i];
					temp[i] = temp[i+1];
					temp[i+1] = d;
					min_temp++;
					/*for(int j = 0; j < length; j++)
						System.out.print(temp[j]);
					System.out.println();*/
				}
				if(index_5 == 0 && temp[1] == '0') {
					for(int i = 2; i < length-1; i++) {
						if(temp[i] != '0') {
							for(int j = i; j >= 2; j--) {
								char d = temp[j];
								temp[j] = temp[j-1];
								temp[j-1] = d;
								min_temp++;
							}
							/*for(int j = 0; j < length; j++)
								System.out.print(temp[j]);
							System.out.println();*/
							break;
						}
					}
				}
				for(int i = index_5; i < length-2; i++) {
					char d = temp[i];
					temp[i] = temp[i+1];
					temp[i+1] = d;
					min_temp++;
					/*for(int j = 0; j < length; j++)
						System.out.print(temp[j]);
					System.out.println();*/
				}
			}
			if(temp[length-2] == '5' && temp[length-1] == '0' && min_swaps > min_temp)
				min_swaps = min_temp;
			//System.out.println(min_swaps);
		}
		if(freq[7] >= 1 && freq[5] >= 1) {
			//System.out.println("75");
			char temp[] = number.toCharArray();
			int min_temp = 0;
			int index_7 = last[7], index_5 = last[5];
			if(index_7 > index_5) {
				for(int i = index_7; i < length-1; i++) {
					char d = temp[i];
					temp[i] = temp[i+1];
					temp[i+1] = d;
					min_temp++;
					/*for(int j = 0; j < length; j++)
						System.out.print(temp[j]);
					System.out.println();*/
				}
				if(index_5 == 0 && temp[1] == '0') {
					for(int i = 2; i < length-1; i++) {
						if(temp[i] != '0') {
							for(int j = i; j >= 2; j--) {
								char d = temp[j];
								temp[j] = temp[j-1];
								temp[j-1] = d;
								min_temp++;
							}
							/*for(int j = 0; j < length; j++)
								System.out.print(temp[j]);
							System.out.println();*/
							break;
						}
					}
				}
				for(int i = index_5; i < length-1; i++) {
					char d = temp[i];
					temp[i] = temp[i+1];
					temp[i+1] = d;
					min_temp++;
					/*for(int j = 0; j < length; j++)
						System.out.print(temp[j]);
					System.out.println();*/
				}
			}
			else {
				for(int i = index_5; i < length-1; i++) {
					char d = temp[i];
					temp[i] = temp[i+1];
					temp[i+1] = d;
					min_temp++;
					/*for(int j = 0; j < length; j++)
						System.out.print(temp[j]);
					System.out.println();*/
				}
				if(index_7 == 0 && temp[1] == '0') {
					for(int i = 2; i < length-1; i++) {
						if(temp[i] != '0') {
							for(int j = i; j >= 2; j--) {
								char d = temp[j];
								temp[j] = temp[j-1];
								temp[j-1] = d;
								min_temp++;
							}
							/*for(int j = 0; j < length; j++)
								System.out.print(temp[j]);
							System.out.println();*/
							break;
						}
					}
				}
				for(int i = index_7; i < length-2; i++) {
					char d = temp[i];
					temp[i] = temp[i+1];
					temp[i+1] = d;
					min_temp++;
					/*for(int j = 0; j < length; j++)
						System.out.print(temp[j]);
					System.out.println();*/
				}
			}
			if(temp[length-2] == '7' && temp[length-1] == '5' && min_swaps > min_temp)
				min_swaps = min_temp;
			//System.out.println(min_swaps);
		}
		if(min_swaps != Integer.MAX_VALUE)
			out.printLine(min_swaps);
		else
			out.printLine(-1);
		out.flush();
		out.close();
	}
	
	static boolean BinarySearch(Long a[], int n, long x) {
		int l = 0, h = n-1, mid;
		while(l <= h) {
			mid = (l+h)>>1;
			if(a[mid] == x)
				return true;
			else if(a[mid] < x)
				l = mid + 1;
			else
				h = mid - 1;
		}
		return false;
	}
	
	static int isSubstring(String s1, String s2)
	{
        int M = s1.length();
        int N = s2.length();
     
        /* A loop to slide pat[] one by one */
        for (int i = 0; i <= N - M; i++)
        {
            int j;
     
            /* For current index i, check for
            pattern match */
            for (j = 0; j < M; j++)
                if (s2.charAt(i + j) != s1.charAt(j))
                    break;
     
            if (j == M)
                return i;
        }
     
        return -1;
    }
	
	static class Pair
    {
        int v;
        int w;
        
        Pair(int v, int w)
        {
            this.v = v;
            this.w = w;
        }
    }
	
	// Function returns the minimum number of swaps
	// required to sort the array
	static int minSwapsUtil(int arr[], int n)
	{
	    // Create an array of pairs where first
	    // element is array element and second element
	    // is position of first element
		Pair arrPos[] = new Pair[n];
	    for (int i = 0; i < n; i++)
	    {
	    	arrPos[i] = new Pair(arr[i], i);
	    }
	 
	    // Sort the array by array element values to
	    // get right position of every element as second
	    // element of pair.
	    Arrays.sort(arrPos, new CustomComp());
	 
	    // To keep track of visited elements. Initialize
	    // all elements as not visited or false.
	    boolean vis[] = new boolean[n];
	 
	    // Initialize result
	    int ans = 0;
	 
	    // Traverse array elements
	    for (int i = 0; i < n; i++)
	    {
	        // already swapped and corrected or
	        // already present at correct pos
	        if (vis[i] || arrPos[i].w == i)
	            continue;
	 
	        // find out the number of  node in
	        // this cycle and add in ans
	        int cycle_size = 0;
	        int j = i;
	        while (!vis[j])
	        {
	            vis[j] = true;
	 
	            // move to next node
	            j = arrPos[j].w;
	            cycle_size++;
	        }
	 
	        // Update answer by adding current cycle.
	        ans += (cycle_size - 1);
	    }
	 
	    // Return result
	    return ans;
	}
	static long min_3(long a, long b, long c)
	{
		if(a < b && a < c)
			return a;
		if(b < c)
			return b;
		return c;
	}
	
	static long max_3(long x, long y, long z)
	{
		if(x >= y && x >= z)
			return x;
		if(y >= x && y >= z)
			return y;
		return z;
	}
	
	static long power(long x, long y, long m)
	{
	    if (y == 0)
	        return 1;
	    long p = power(x, y/2, m) % m;
	    p = (p * p) % m;
	    return (y%2 == 0) ? p : (x * p) % m;
	}
	
	static void prime_sieve(int N)
	{
        isPrime = new boolean[N+1];
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;
        for(int i = 2; i*i <= N; i++)
        {
            if(isPrime[i]==true)
            {
            	for(int j = 2*i; j <= N; j += i)
            	{
            		isPrime[j] = false;
            		prime[j] = i;
				}
            }
        }
    }
	
	static void Calc_nCr()
	{
		for(int i = 0; i <= 1000; i++)
			nCr[i][0] = 1;
		for(int i = 1; i <= 1000; i++)
			for(int j = 1; j <= 1000; j++)
				nCr[i][j] = (nCr[i-1][j-1] + nCr[i-1][j]) % MOD;
	}
	
	static long factorial(long num)
	{
		long result = 1;
		for(int i = 1; i <= num; i++)
			result = result * (long)i;
		return result;
	}
	
	static void ExtendedEuclidian(long a, long b)
	{
		if(b == 0)
		{
	        gcd = a;
	        x = 1;
	        y = 0;
	    }
	    else
	    {
	        ExtendedEuclidian(b, a%b);
	        int temp = (int) x;
	        x = y;
	        y = temp - (a/b)*y;
	    }
	}
	
	static long GCD(long n, long m)
	{
		if(m != 0)
			return GCD(m, n % m);
		else
			return n;
	}
	
	static class CustomComp implements Comparator<Pair>
	{
		@Override
        public int compare(Pair p1, Pair p2)
		{
			if(p1.v <= p2.v)
				return -1;
			else
				return 1;
        }
	}
	
	static int[][] graph(int from[], int to[], int n) // return 2D Array of the graph
	{
		int g[][] = new int[n][];
		int cnt[] = new int[n];
		for (int i = 0; i < from.length; i++)
		{
			cnt[from[i]]++;
			cnt[to[i]]++;
		}
		for (int i = 0; i < n; i++)
			g[i] = new int[cnt[i]];
		Arrays.fill(cnt, 0);
		for (int i = 0; i < from.length; i++)
		{
			g[from[i]][cnt[from[i]]++] = to[i];
			g[to[i]][cnt[to[i]]++] = from[i];
		}
		return g;
	}
	
	static class Graph
	{
		
	    private int V;
	    long dist[];
	    private LinkedList<Pair> adj1[];
	    private LinkedList<Integer> adj2[];
	    boolean visited[];
	    
	    class Pair
	    {
	        int v;
	        long w;
	        
	        Pair(int v, long w)
	        {
	            this.v = v;
	            this.w = w;
	        }
	    }
	    
	    Graph(int v)
	    {
	    	V = v + 1;
	        adj1 = new LinkedList[V];
	        adj2 = new LinkedList[V];
	        visited = new boolean[V];
	        dist = new long[V];
	        Arrays.fill(dist, Long.MAX_VALUE);
	        dist[1] = 0;
	        for(int i = 0; i < V; i++)
	            adj1[i] = new LinkedList<Pair>();
	        for(int i = 0; i < V; i++)
	            adj2[i] = new LinkedList<Integer>();
	    }
	    
	    public void addEdge1(int u, int v, int w)
	    {
	        adj1[u].add(new Pair(v, w));
	        adj1[v].add(new Pair(u, w));
	    }
	 
	    void addEdge2(int v, int w)
	    {
	        adj2[v].add(w);
	        adj2[w].add(v);
	    }
	    
	    public void dijkstra()
	    {
	        Queue<Pair> pQueue = new PriorityQueue<Pair>(V, new pQueueComp());
	        pQueue.add(new Pair(1, 0));
	        while(!pQueue.isEmpty())
	        {
	            Pair p1 = pQueue.poll();
	            int x = p1.v;
	            long wei = p1.w;
	            if(visited[x])
	                continue;
	            visited[x] = true;
	            Iterator<Pair> itr = adj1[x].listIterator();
	            while(itr.hasNext()) {
	                Pair p2 = itr.next();
	                int e = p2.v;
	                long w = p2.w;
	                if(dist[x] + w < dist[e])
	                {
	                    dist[e] = dist[x] + w;
	                    pQueue.add(new Pair(e, dist[e]));
	                }
	            }
	        }
	    }
	    
	    class pQueueComp implements Comparator<Pair>
	    {
	        @Override
	        public int compare(Pair p1, Pair p2)
	        {
	            return (int)(p1.w - p2.w);
	        }
	    }
	    
	    // prints BFS traversal from a given source s
	    void BFS(int s)
	    {
	        LinkedList<Integer> queue = new LinkedList<Integer>();
	        visited[s] = true;
	        queue.add(s);
	        while (queue.size() != 0)
	        {
	            s = queue.poll();
	            System.out.print(s+" ");
	            Iterator<Integer> i = adj2[s].listIterator();
	            while (i.hasNext())
	            {
	                int n = i.next();
	                if (!visited[n])
	                {
	                    visited[n] = true;
	                    queue.add(n);
	                }
	            }
	        }
	    }
	    
	    int count = 0;
	    
	    int DFS(int u, int v) {
	    	visited = new boolean[26];
	    	for(int i = 0; i < 26; i++)
	    	{
	    		if(visited[i] == false)
	    		{
	    			count = 0;
	    			DFSUtil(i, u, v);
	    			//System.out.println(i+" "+u+" "+v+" "+count);
	    			if(count == 0 && visited[u] == true && visited[v] == true)
	    				return 1;
	    			if(count == 1 && (visited[u] == true || visited[v] == true))
	    				return 1;
	    			if(count == 2)
	    				break;
	    		}
	    	}
	    	return 0;
	    }
	    
	    void DFSUtil(int s, int u, int v)
	    {
	        visited[s] = true;
	        //System.out.println(s);
	        if(s == u)
	        	count++;
	        if(s == v)
	        	count++;
	        if(count == 2)
	        	return;
	        //System.out.println("count "+count);
	        Iterator<Integer> i = adj2[s].listIterator();
	        while(i.hasNext())
	        {
	            int n = i.next();
	            if(!visited[n])
	                DFSUtil(n, u, v);
	        }
	    }
	    
	    boolean isCyclicUndirectedUtil(int v, boolean visited[], int parent)
	    {
	        // Mark the current node as visited
	        visited[v] = true;
	        Integer i;
	 
	        // Recur for all the vertices adjacent to this vertex
	        Iterator<Integer> it = adj2[v].iterator();
	        while (it.hasNext())
	        {
	            i = it.next();
	 
	            // If an adjacent is not visited, then recur for that
	            // adjacent
	            if (!visited[i])
	            {
	                if (isCyclicUndirectedUtil(i, visited, v))
	                    return true;
	            }
	 
	            // If an adjacent is visited and not parent of current
	            // vertex, then there is a cycle.
	            else if (i != parent)
	                return true;
	        }
	        return false;
	    }
	 
	    // Returns true if the graph contains a cycle, else false.
	    boolean isCyclicUndirected()
	    {
	        // Mark all the vertices as not visited and not part of
	        // recursion stack
	        boolean visited[] = new boolean[V];
	 
	        // Call the recursive helper function to detect cycle in
	        // different DFS trees
	        for (int u = 1; u <= V; u++)
	            if (!visited[u]) // Don't recur for u if already visited
	                if (isCyclicUndirectedUtil(u, visited, -1))
	                    return true;
	 
	        return false;
	    }
	    
	    boolean isCyclicDirectedUtil(int v, boolean visited[], boolean recStack[])
	    {
	    	if(visited[v] == false)
	    	{
	            // Mark the current node as visited and part of recursion stack
	            visited[v] = true;
	            recStack[v] = true;
	     
	            // Recur for all the vertices adjacent to this vertex
	            Iterator<Integer> i = adj2[v].listIterator();
	            while(i.hasNext())
	            {
	            	int n = i.next();
	                if (!visited[n] && isCyclicDirectedUtil(n, visited, recStack))
	                    return true;
	                else if (recStack[n])
	                    return true;
	            }
	        }
	        recStack[v] = false;  // remove the vertex from recursion stack
	        return false;
	    }
	    
	    boolean isCyclicDirected()
	    {
	    	boolean visited[] = new boolean[V];
	    	boolean recStack[] = new boolean[V];
	    	for(int i = 1; i <= V; i++)
	            if (isCyclicDirectedUtil(i, visited, recStack))
	                return true;
	    	return false;
	    }
	    
	    void topologicalSortUtil(int v, boolean visited[], Stack stack)
	    {
			// Mark the current node as visited.
			visited[v] = true;
			
			// Recur for all the vertices adjacent to this vertex
			Iterator<Integer> it = adj2[v].iterator();
			while (it.hasNext()) {
				int i = it.next();
				if (!visited[i])
					topologicalSortUtil(i, visited, stack);
			}
			
			// Push current vertex to stack which stores result
			stack.push(new Integer(v));
		}
			
		// The function to do Topological Sort. It uses recursive topologicalSortUtil()
		void topologicalSort()
		{
			Stack stack = new Stack();
			
			// Mark all the vertices as not visited
			boolean visited[] = new boolean[V];
			
			// Call the recursive helper function to store Topological Sort starting from all
			// vertices one by one
			for (int i = 1; i <= V; i++)
			if (visited[i] == false)
				topologicalSortUtil(i, visited, stack);
			
			// Print contents of stack
			while (stack.empty()==false)
				System.out.print(stack.pop() + " ");
		}
	}
}

class InputReader
{

    private final InputStream stream;
    private final byte[] buf = new byte[8192];
    private int curChar, snumChars;
    private SpaceCharFilter filter;

    public InputReader(InputStream stream)
    {
            this.stream = stream;
    }

    public int snext()
    {
            if (snumChars == -1)
                    throw new InputMismatchException();
            if (curChar >= snumChars)
            {
                    curChar = 0;
                    try
                    {
                    	snumChars = stream.read(buf);
                    } 
                    catch (IOException e)
                    {
                        throw new InputMismatchException();
                    }
                    if (snumChars <= 0)
                        return -1;
            }
            return buf[curChar++];
    }

    public int nextInt()
    {
            int c = snext();
            while (isSpaceChar(c))
            {
                    c = snext();
            }
            int sgn = 1;
            if (c == '-')
            {
                    sgn = -1;
                    c = snext();
            }
            int res = 0;
            do
            {
                    if (c < '0' || c > '9')
                            throw new InputMismatchException();
                    res *= 10;
                    res += c - '0';
                    c = snext();
            } 
            while (!isSpaceChar(c));
            return res * sgn;
    }

    public long nextLong()
    {
            int c = snext();
            while (isSpaceChar(c))
            {
                    c = snext();
            }
            int sgn = 1;
            if (c == '-')
            {
                    sgn = -1;
                    c = snext();
            }
            long res = 0;
            do
            {
                    if (c < '0' || c > '9')
                            throw new InputMismatchException();
                    res *= 10;
                    res += c - '0';
                    c = snext();
            } while (!isSpaceChar(c));
            return res * sgn;
    }

    public int[] nextIntArray(int n)
    {
            int a[] = new int[n];
            for (int i = 0; i < n; i++)
            {
                    a[i] = nextInt();
            }
            return a;
    }

    public long[] nextLongArray(int n)
    {
            long a[] = new long[n];
            for (int i = 0; i < n; i++)
            {
                    a[i] = nextLong();
            }
            return a;
    }

    public String readString()
    {
            int c = snext();
            while (isSpaceChar(c))
            {
                    c = snext();
            }
            StringBuilder res = new StringBuilder();
            do
            {
                    res.appendCodePoint(c);
                    c = snext();
            } while (!isSpaceChar(c));
            return res.toString();
    }

    public String nextLine()
    {
            int c = snext();
            while (isSpaceChar(c))
                    c = snext();
            StringBuilder res = new StringBuilder();
            do
            {
                    res.appendCodePoint(c);
                    c = snext();
            } while (!isEndOfLine(c));
            return res.toString();
    }

    public boolean isSpaceChar(int c)
    {
            if (filter != null)
                    return filter.isSpaceChar(c);
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }

    private boolean isEndOfLine(int c)
    {
            return c == '\n' || c == '\r' || c == -1;
    }

    public interface SpaceCharFilter
    {
            public boolean isSpaceChar(int ch);
    }

}

class FastReader
{
	
    BufferedReader br;
    StringTokenizer st;
 
    public FastReader()
    {
        br = new BufferedReader(new
                 InputStreamReader(System.in));
    }
 
    String next()
    {
        while (st == null || !st.hasMoreElements())
        {
            try
            {
                st = new StringTokenizer(br.readLine());
            }
            catch (IOException  e)
            {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }
 
    int nextInt()
    {
        return Integer.parseInt(next());
    }
 
    long nextLong()
    {
        return Long.parseLong(next());
    }
 
    double nextDouble()
    {
        return Double.parseDouble(next());
    }
 
    String nextLine()
    {
        String str = "";
        try
        {
            str = br.readLine();
        }
        catch (IOException e)
        {
            e.printStackTrace();
        }
        return str;
    }
}
 
class OutputWriter {
	
	private final PrintWriter writer;
 
	public OutputWriter(OutputStream outputStream)
	{
		writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
	}
 
	public OutputWriter(Writer writer)
	{
		this.writer = new PrintWriter(writer);
	}
 
	public void print(Object...objects)
	{
		for (int i = 0; i < objects.length; i++)
		{
			if (i != 0)
				writer.print(' ');
			writer.print(objects[i]);
		}
	}
 
	public void printLine(Object...objects)
	{
		print(objects);
		writer.println();
	}
 
	public void close()
	{
		writer.close();
	}
 
	public void flush()
	{
		writer.flush();
	}
}