#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <list>
#include <queue>
#include <map>
#include <set>
#include <algorithm>

using namespace std;

// Definitions
#define FORI(i,s) for (int i = 0; i < s.size(); i++)
#define RFORI(i,s) for (int i = s.size() - 1; i >= 0; i--)
#define ALL(v) (v).begin(), (v).end()
#define FORALL(it,st) for(typeof(st.begin())it=st.begin();it!=st.end();it++)

//From ACRush Orz
#define two(x) (1<<(x))
#define twoL(x) ( ( (long long)(x) ) << (x) )
#define contain(s,x) ( ( (s) & two(x) ) != 0 )
#define containL(s,x) ( ( (s) & twoL(x)) != 0 )

//By me ,hou hou
#define pb push_back
#define mp make_pair
#define br break
#define cn continue
#define sz size()
#define nil string::npos

template<class T> inline T sqr(T x) { return x*x;}

// Types
typedef double dbl;
typedef long double ld;
typedef unsigned long long ull;
typedef long long ll;
typedef pair <int, int> pii;
typedef vector <int> vi;
typedef vector <pii> vp;
typedef vector <ld> vd;
typedef vector <string> vs;
typedef vector <bool> vb;
typedef queue <pii> qp;
typedef map <string, int> msi;

// Constants
const int INF = 1000000000;
const ld EPS = 1e-10;
const ld PI = 3.141592653589793238462;