#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
using namespace std;
#define REP(i,n) for(int i = 0; i < (int)n; ++i)
#define FOR(it,c) for(__typeof((c).begin()) it = (c).begin(); it != (c).end(); ++it)
#define DEBUG(x) cerr << #x << " = " << x << endl
template<class T, class U> T lexical_cast(const U& from)
{ T to; stringstream ss; ss << from; ss >> to; return to; }
template<class T> void pv(T a,T b)
{ for(T it = a; it != b; ++it) cerr << *it << '_'; cerr << endl; }
const int INF = (int)1e9;
const double PI = M_PI, EPS = 1e-8;
typedef long long int lli;
struct $CLASSNAME$ {
$RC$ $METHODNAME$($METHODPARMS$) {
}
};
$BEGINCUT$
$TESTCODE$
$DEFAULTMAIN$
$ENDCUT$