#include <bits/stdc++.h>
#define MOD 1000000007

using namespace std;

int gcd (long long int a, long long int b) {
	if (b == 0)
		return a;
	else
		return gcd (b, a % b);
}

long long int lcd(long long int a, long long int b) {
    return (a * b) / gcd(a, b);
}

long long int fact(long long int N) {
    if(N < 0)
        return 0;
    if (N == 0)
        return 1;
    else
        return N * fact(N - 1);
}

long long int cnk(long long int n, long long int k) {
    return fact(n) / (fact(k) * fact(n - k));
}

long long int powermod(long long int base, long long int power) {
    if (power == 0) {
        return 1;
    }
    else {
        long long int cur = powermod(base, power / 2);
        cur = cur * cur;
        cur = cur % MOD;
        if (power % 2 == 1)
            cur = cur * base;
        cur = cur % MOD;
        return cur;
    }
}

long double distance(long long int x1, long long int y1, long long int x2, long long int y2) {
    return sqrt((x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2));
}

bool lex(string lhs, string rhs) {
    int n = min(lhs.size(), rhs.size());
        for(int i = 0; i < n; i++) {
            char a = tolower(lhs[i]);
            char b = tolower(rhs[i]);
            if(a != b)
                return a < b;
        }
    return lhs.size() < rhs.size();
}

int main()
{
    ios::sync_with_stdio(false);
	cin.tie(nullptr);
    // cout << fixed << setprecision(50);


	return 0;
}