#include <iostream>
#include <iomanip>
#include <cstdio>
#include <sstream>
#include <fstream>
#include <climits>
#include <cfloat>
#include <functional>
#include <ctime>
#include <numeric>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <utility>
#include <bitset>
#include <string>
#include <list>
#include <stack>
#include <vector>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <cstring>
#include <typeinfo>
#include <cassert>
#include <ctime>

using namespace std;

#define DEBUG

#ifdef DEBUG
#define dbg(x) cerr<<#x<<" = "<<x;
#define de() cerr<<endl;
#else
#define dbg(x)
#define de()
#endif
#define FileName "out.deb"
#define foreach(it,v) for(typeof (v).begin() it=(v).begin();it!=(v).end();it++)
#define forl(p,s,n,u) for((p)=(s);(p)<(n);(p)+=(u))
#define fore(p,s,n,u) for((p)=(s);(p)<=(n);(p)+=(u))
#define loop(i,s,n) for((i)=(s);(i)<(n);(i)++)
#define pool(i,s,n) for((i)=(s);(i)>(n);(i)--)
#define fs first
#define ins insert
#define sc second
#define mp make_pair
#define pb push_back
#define sqr(x) (x)*(x)
#define all(v) (v).begin(),(v).end()
typedef long double ld;

const ld EPS=1e-9;
const ld PI=3.1415926535897932384626433832795;

const int INF=1000*1000*1000;
const int NMAX=1000*1000;