template

#define fileName string ("")

//#define TEST_GENERATOR

#define INP (fileName + ".inp").c_str ()
#define OUT (fileName + ".out").c_str ()
#define ERR (fileName + ".err").c_str ()

/* ---------------------------------------------------------------------------------------- */

#include <algorithm>
#include <iostream>
#include <sstream>
#include <cstdlib>
#include <climits>
#include <cstring>
#include <iomanip>
#include <limits>
#include <locale>
#include <cstdio>
#include <vector>
#include <cmath>
#include <stack>
#include <queue>
#include <deque>
#include <ctime>
#include <map>
#include <set>

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back

#define rp(i, n) for (int i = 0; i < (n); ++i)
#define rd(i, n) for (int i = (n); i--;)
#define rs(i, x) rp (i, sz (x))
#define fr(i, a, b) for (int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (int i = (a); i >= (b); --i)
#define fe(i, x) for (__typeof ((x).begin ()) i = (x).begin (); i != (x).end (); ++i)
#define fer(i, x) for (__typeof ((x).rbegin ()) i = (x).rbegin (); i != (x).rend (); ++i)
#define cd(x) while ((x)--)
#define nt(n) for (int i = (n); i--;)
#define srt(v) sort (all (v))

#define mn(x, y) x = min (x, y)
#define mx(x, y) x = max (x, y)

#define sz(x) (int) (x).size ()
#define all(x) (x).begin (), (x).end ()

#define cl(x) memset (x, 0, sizeof (x))

#define sqr(x) ((x) * (x))

const double pi = acos(-1.0);

typedef unsigned long long llu;
typedef long long ll;

typedef pair <int, int> ii;
typedef vector <string> vs;
typedef vector <ii> vii;
typedef vector <int> vi;
typedef vector <vi> vvi;
typedef vector <vii> vvii;
typedef vector <bool> vb;
typedef vector <vb> vvb;

template <class T>
inline string ns (const T &number)
{
    stringstream ss;
    ss << number;
    return ss.str ();
}

template <class T>
inline T sn (const string &text)
{
    stringstream ss (text);
    T result;
    return ss >> result ? result : 0;
}

template <class T>
inline T pow2 (const int &x)
{
    return (T) 1 << x;
}

template <class T>
inline int log2 (T x)
{
    int res = 0;
    while (x >>= 1) ++res;
    return res;
}

struct disjoint_set
{
    vi pset;
    int _sz;
    inline int size () {return _sz;}
    inline void init (const int &n)
    {
        pset.resize (n);
        rp (i, n) pset [i] = i;
        _sz = n;
    }
    disjoint_set () {};
    disjoint_set (const int &n) {init (n);}
    int find (const int &x) {return (x == pset [x] ? x : pset [x] = find (pset [x]));}
    inline bool same (const int &x, const int &y) {return (find (x) == find (y));}
    inline bool join (const int &x, const int &y)
    {
        int xx = find (x), yy = find (y);
        if (xx == yy) return false;
        --_sz; pset [xx] = yy; return true;
    }
};

template <class T>
inline T rand ()
{
    int cnt = sizeof (T) * 8 / 15 + 1;
    T res = 0;
    cd (cnt) res = (res << 15) + rand ();
    return res;
}

template <class T>
inline T rand (T x, T y)
{
    if (x > y) swap (x, y);
    T diff = y - x + 1, tmp = rand <T> () % diff;
    if (tmp >= 0) return tmp + x;
    return tmp + diff + x;
}

/* ---------------------------------------------------------------------------------------- */



int main ()
{
    srand (time (NULL));
    #ifndef ONLINE_JUDGE
        #ifdef TEST_GENERATOR
            freopen (INP, "w", stdout);
        #else
            freopen (INP, "r", stdin);
            freopen (OUT, "w", stdout);
            //freopen (ERR, "w", stderr);
        #endif
    #endif

    return 0;
}