Std Algo
#define CLEAR(a,b) memset(a,b,sizeof(a))
int s2i(string s) { istringstream i(s); int x; i>>x; return x; }
string & i2s(int c)
template<class T> string toString(T n){ostringstream ost;ost<<n;ost.flush();return ost.str();}
vs s2vi(string s,string del=" ")
vi s2vs(string s,string del=" ")
template<class T> void s2a(string s,int &n,T A[]){n=0;istringstream sin(s);for(T v;sin>>v;A[n++]=v);}
VS split(string s,string del=" ") {
  string w;
  VS res;
  FOREACH(it,s) {
    if(find(del.begin(),del.end(),*it)==del.end()) w+=*it;
    else if(w!="") { res.push_back(w); w=""; }
  return res;
VI s2vi(string s,string del=" ") {
  VS v=split(s,del);
  VI res; FOREACH(it,v) res.push_back(s2i(*it));
  return res;
int i = INT_MAX, INT_MIN
typedef long long int64;
typedef unsigned long long uint64;
#define two(X) (1<<(X))
#define twoL(X) (((int64)(1))<<(X))
#define contain(S,X) (((S)&two(X))!=0)
#define containL(S,X) (((S)&twoL(X))!=0) 
#define all(v)  (v).begin(),  (v).end()
#define allr(v) (v).rbegin(), (v).rend()
typedef long long i64;
template <class T> void make_unique(T& v) {sort(all(v)); v.resize(unique(all(v)) - v.begin());} 
#define ss        stringstream
#define cstr(x)      ((ss&)((ss()<<(x)))).str()
struct Matrix{
  ll a[50][50];
  Matrix(int x=0){for(int i=0;i<n;++i)for(int j=0;j<n;++j)a[i][j]=i==j?x:0;}
Matrix operator*(const Matrix &a,const Matrix &b){
  Matrix c;
  for(int i=0;i<n;++i)
    for(int j=0;j<n;++j){
      ll v=0;
      for(int k=0;k<n;++k) v = v + (a.a[i][k]*b.a[k][j]);
  return c;
00039     __cmath_power(_Tp __x, unsigned int __n)
00040     {
00041       _Tp __y = __n % 2 ? __x : 1;
00043       while (__n >>= 1)
00044         {
00045           __x = __x * __x;
00046           if (__n % 2)
00047             __y = __y * __x;
00048         }
00050       return __y;
00051     }
template<typename T> inline T gcd(T a, T b) { return b ? gcd(b, a%b) : abs(a); }
template<class T> inline int cpop(T n){return (n==0)?0:(1+cpop(n&(n-1)));}
#define two(X) (1<<(X))
#define contain(S,X) (((S)&two(X))!=0)
template<class T> inline void checkmin(T &a,T b){if(b<a) a=b;}
template<class T> inline int countbit(T n){return (n==0)?0:(1+countbit(n&(n-1)));}
template<class T> T cross(T x0,T y0,T x1,T y1,T x2,T y2){return (x1-x0)*(y2-y0)-(x2-x0)*(y1-y0);}
template<class T> inline void checkmin(T &a,T b){if(b<a) a=b;}
template<class T> inline void checkmax(T &a,T b){if(b>a) a=b;} 
template<class T> inline T lowbit(T n){return (n^(n-1))&n;} 
vi color;
vvi E;
int dfs(int v)
vector<bool> color; &&&&&&
  void DFS(int v,int s)
    if (s<0 || s>m) return;
    if (f[v][s]) return;
    if (v==n) return;
template<class T> inline vector<pair<T,int> > factorize(T n)
  {vector<pair<T,int> > R;for (T i=2;n>1;){if (n%i==0){int C=0;for (;n%i==0;C++,n/=i);R.push_back(make_pair(i,C));}
   i++;if (i>n/i) i=n;}if (n>1) R.push_back(make_pair(n,1));return R;}
distance arrays
int[] dx={+0,+0,+1,-1,+1,+1,-1,-1};
int[] dy={+1,-1,+0,+0,+1,-1,+1,-1};
void split(string str, string delim, vector<string>& results)
    int _p;
    while( (_p = str.find_first_of(delim)) != str.npos )
        if(_p > 0)
            results.push_back(str.substr(0, _p));
        str = str.substr(_p+1);
    if(str.length() > 0)
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-Share Alike 2.5 License.