template_codeC++

// ~~~ From Coo@King with love and peace ~~~
#include<bits/stdc++.h>
#define FILE "sample"
using namespace std;

namespace FastIO
{
    template<class T > inline bool read(T &x) // signed int and long long
    {
        char c; bool flag = 0;
        do { c = getchar(); } while (!isdigit(c) && c != '-' && c != EOF);
        if (c == EOF) return 0;
        if (c == '-') flag = 1, c = getchar();
        x = c - '0';
        do
        {
            c = getchar();
            if (c == EOF || !isdigit(c)) break;
            x = x * 10 + c - '0';
        }
        while (1);
        if (flag) x = -x;
        return 1;
    }

    inline bool read(string &x) // normal string with [0..9], [a..z], [A..Z]
    {
        char c;
        do { c = getchar(); } while (!isalnum(c) && c != EOF);
        if (c == EOF) return 0;
        x.clear(); x += c;
        do
        {
            c = getchar();
            if (c == EOF || !isalnum(c)) break;
            x += c;
        }
        while (1);
        return 1;
    }

    template<class T > inline void write(T x)
    {
        if (x < 0) putchar('-'), write(-x);
        else
        if (x < 10) putchar(x + '0');
        else write(x / 10), putchar(x % 10 + '0');
    }

    inline void write(string &x)
    {
        for (char c : x) putchar(c);
    }
}



main()
{
    if (fopen("main.in", "r"))
        // assert(freopen("main.out", "w", stdout)),
        // assert(freopen("main.err", "w", stderr)),
        assert(freopen("main.in", "r", stdin));
    else
        // assert(freopen(FILE".out", "w", stdout)),
        assert(freopen(FILE".inp", "r", stdin));

}