ACM

//by NotOnlySuccess
 
#include "cstdlib"
#include "cctype"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "algorithm"
#include "vector"
#include "string"
#include "iostream"
#include "sstream"
#include "set"
#include "queue"
#include "stack"
#include "fstream"
#include "iomanip"
#include "bitset"
#include "list"
#include "strstream"
#include "ctime"
using namespace std;
 
typedef long long LL;
typedef unsigned long long ULL;
#define CC(m,what)		memset(m,what,sizeof(m))
#define FOR(i,a,b)		for( int i = (a) ; i < (b) ; i ++ )
#define FF(i,a)			for( int i = 0 ; i < (a) ; i ++ )
#define FFD(i,a)		for( int i = (a)-1 ; i >= 0 ; i --)
#define SS(a)			scanf("%d",&a)
#define LL(a)			((a)<<1)
#define RR(a)			(((a)<<1)+1)
#define SZ(a)			((int)a.size())
#define PP(n,m,a)		puts("---");FF(i,n){FF(j,m)cout << a[i][j] << ' ';puts("");}
const double eps = 1e-11;
const double Pi = acos(-1.0);
 
#define read			freopen("in.txt","r",stdin)
#define write			freopen("out.txt","w",stdout)
 
#define two(x)			((LL)1<<(x))
#define include(a,b)		(((a)&(b))==(b))
template<class T> inline T countbit(T n)	{return n?1+countbit(n&(n-1)):0;}
template<class T> inline T sqr(T a)	{return a*a;}
template<class T> inline void checkmin(T &a,T b)	{if(a == -1 || a > b)a = b;}
template<class T> inline void checkmax(T &a,T b)	{if(a < b)	a = b;}
 
int dx[] = {-1,0,1,0};//up Right down Left
int dy[] = {0,1,0,-1};