import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.Writer;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.*;
import java.io.*;
import java.math.*;
public class Main6{

static class Pair
	{ 
		int x;
		int y;
		int z;
		public Pair(int x,int y,int z) 
		{	 
			this.x= x; 
			this.y= y;
			this.z=z;
		}	 
		
	@Override
			public int hashCode() 
			{ 
				final int temp = 14; 
				int ans = 1; 
				ans =x*31+y*13; 
				return ans; 
			} 
	  
			// Equal objects must produce the same 
			// hash code as long as they are equal 
		@Override
		public boolean equals(Object o) 
		{ 
			if (this == o) { 
				return true; 
			} 
			if (o == null) { 
				return false; 
			} 
			if (this.getClass() != o.getClass()) { 
				return false; 
			} 
			Pair other = (Pair)o; 
			if (this.x != other.x || this.y!=other.y) { 
				return false; 
			} 
			return true; 
		} 
			
	} 
	static class Pair1
	{
		String x;
		int y;
		int z;
		
	}
	static class Compare
	{ 
		static void compare(Pair arr[], int n) 
		{ 
			// Comparator to sort the pair according to second element 
		/*	Arrays.sort(arr, new Comparator<Pair>() { 
				@Override public int compare(Pair p1, Pair p2) 
				{ 
					if(p1.start>p2.start)
					{
						return 1;
					}
					else if(p1.start==p2.start)
					{
						return 0;
					}
					else
					{
						return -1;
					}
				} 
			}); */
		}
		
	}
	
	
	public static long pow(long a, long b)
	{
		long result=1;
		while(b>0)
		{
			if (b % 2 != 0)
			{
				result=(result*a)%998244353;
				b--;
			} 
			a=(a*a)%998244353;
			b /= 2;
		}   
		return result;
	}
	public static long fact(long num)
	{
				long value=1;
				int i=0;
				for(i=2;i<num;i++)
				{
					value=((value%mod)*i%mod)%mod;
				}
				return value;
			}
			public static int gcd(int a, int b)
			{
				if (a == 0)
					return b;
				return gcd(b%a, a);
			}
			
	/*		public static... What is the time complexity of the previous code?