#include 
     
      #define F first#define S second#define pb push_back#define NL cout << "\n";#define rep(x,y) for(int i = x;i < y;i++)#define INF 2147483647#define M 1000000007#define MAX 105#define MOD %#define NE !=#define EE ==using namespace std;typedef long long int lld;typedef pair
      
        pii;typedef pair
       
         pis;typedef pair
        
          pss;typedef vector
         
           vi; typedef vector
          
            vii;typedef vector
           
             vs;typedef vector
            
              vis;typedef set
             
               si;typedef set
              
                sii;typedef set
               
                 sis;typedef map
                
                  mii;typedef map
                 
                   mis;|--Global Declarations--|/// int alpha[26] = { 0}, dig[MAX] = { 0};lld gcd(lld a, lld b){ if (a == 0) return b; return gcd(b % a, a);}lld lcm(lld a, lld b){ return ((a * b) / gcd(a, b));}bool isPrime(int n){ if (n <= 1) return false; if (n <= 3) return true; if (n % 2 == 0 || n % 3 == 0) return false; for (int i = 5; i * i <= n; i = i + 6) if (n % i == 0 || n % (i + 2) == 0) return false; return true;}void getArr(int a[], int n){ rep(0, n) cin >> a[i];}void putArr(int a[], int n){ rep(0, n) cout << a[i] << " "; NL}void initAlpha(string s){ int n = s.size(); rep(0, n) alpha[s[i] - 'a']++;}void initDigit(int a[], int n){ rep(0, n) dig[a[i]]++;}bool isPalindrome(string input){ if(input == string(input.rbegin(), input.rend())) return true; return false;}int numLen(int n){ int len =0; while(n !=0) { n /=10; len++; } return len;}