<repo_name>maraghuram/Codechef-Solutions<file_sep>/HELPLIRA.cpp
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <limits>
#include <cfloat>
using namespace std;
const double epsilon=0.01;
double modDouble(double x)
{
	if(x<0) return -x;
	return x;
}
int main()
{
	int N;
	scanf("%d",&N);
	double minArea,maxArea;
	int minIndex,maxIndex;
	minArea=DBL_MAX;
	maxArea=DBL_MIN;
	for(int i=1;i<=N;++i)
	{
		int x1,x2,x3,y1,y2,y3;
		double area=0.0;
		scanf("%d %d %d %d %d %d",&x1,&y1,&x2,&y2,&x3,&y3);
		area=0.5*modDouble((((double)(x1-x3)*(y2-y1))-((x1-x2)*(y3-y1))));
		if(area<=minArea) minArea=area,minIndex=i;
		if(area>=maxArea) maxArea=area,maxIndex=i;
	}
	printf("%d %d\n",minIndex,maxIndex);
	return 0;
}
<file_sep>/PNTNG.cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int,ll> pil;
int main(){
  ll N,M,H;
  scanf("%lld %lld %lld",&N,&M,&H);
  ll res=0;
  ll sqrs = N*M;
  vector<pil> paint(H);
  for(int i=0;i<H;++i) scanf("%lld %d",&paint[i].second,&paint[i].first);
  sort(paint.begin(),paint.end());
  
  for(int i=0;i<H;++i){
    ll get = min( sqrs, paint[i].second );
    res = res + (get*(ll) paint[i].first);
    sqrs = sqrs - get;
    if( sqrs == 0 ) break;
  }
  if( sqrs != 0 ) printf("Impossible\n");
  else printf("%lld\n",res);
  return 0;
}
<file_sep>/HEADBOB.cpp
#include <bits/stdc++.h>
#define NMAX 1111
using namespace std;
char buf[NMAX];
int main(){
  int T;
  scanf("%d",&T);
  for(int t=0;t<T;++t){
    int n,flag=0;
    scanf("%d\n",&n);
    gets(buf);
    for(int i=0;i<n;++i){
      if(buf[i]=='Y'){
	flag=1;	break;
      }
      else if(buf[i]=='I'){
	flag=2; break;
      }
    }
    if(flag==1) puts("NOT INDIAN");
    else if(flag==2) puts("INDIAN");
    else puts("NOT SURE");
  }
  return 0;
}
<file_sep>/ANUGCD.cpp
#include <bits/stdc++.h>
	#define NMAX 1000010
	#define NLIM 1000000
	#define pb push_back
	#define sz size()
	#define L(x) (x<<1)
	#define R(x) ((x<<1)+1)
	#define ALL(x) ( x.begin(),x.end() )
	using namespace std;
	struct node{
		int val,freq;
		node(){
			val=freq=-1;
		}
		node(int x,int y){
			val=x,freq=y;
		}
	};
	vector<node> trees[NMAX];
	vector<int> primes,primeFactors[NMAX],primesList[NMAX];
	int flag[NMAX],N,Q,input[NMAX];
	void factorise(){
		memset(flag,0,sizeof(flag));
		for(int i=2;i<=NLIM;++i){
			if(flag[i]==0){
				primes.pb(i);
				primeFactors[i].pb(i);
				for(int j=i<<1;j<=NLIM;j+=i) {
					flag[j]=1;
					primeFactors[j].pb(i);
				}
			}
		}
	}
	node merge(node y,node z){
		node x;
		if(y.val>z.val) x=node(y.val,y.freq);
		else if(z.val>y.val) x=node(z.val,z.freq);
		else x=node(y.val,y.freq+z.freq);
		if(x.val==-1) x.freq=-1;
		return x;
	}
	void build(int t,int index,int i,int j){
		if(i==j) {
			trees[t][index]=node(input[primesList[t][i-1]-1],1);
			return;
		}
		int mid=(i+j)>>1;
		build(t,L(index),i,mid);
		build(t,R(index),mid+1,j);
		trees[t][index]=merge(trees[t][L(index)],trees[t][R(index)]);
	}
	node query(int t,int index,int i,int j,int left,int right){
		if(i==left && j==right) return trees[t][index];
		if(left>right || i>right || j<left) return node(-1,-1);
		int mid=(i+j)>>1;
		if(right<=mid) return query(t,L(index),i,mid,left,right);
		else if(left>mid) return query(t,R(index),mid+1,j,left,right);
		else return merge(query(t,L(index),i,mid,left,mid),query(t,R(index),mid+1,j,mid+1,right));
	}
	void printTree(int t,int index,int i,int j){
		if(i==j){
			printf("%d,%d - %d %d\n",i,j,trees[t][index].val,trees[t][index].freq);
			return;
		}
		int mid=(i+j)>>1;
		printTree(t,L(index),i,mid);
		printTree(t,R(index),mid+1,j);
		printf("%d,%d - %d %d\n",i,j,trees[t][index].val,trees[t][index].freq);
	}
void solve1();
	int main(){
		solve1();
		return 0;
	}
void solve1(){
	factorise();
	scanf("%d %d",&N,&Q);
	for(int i=0;i<N;++i){
		scanf("%d",&input[i]);
		for(int j=0;j<primeFactors[input[i]].sz;++j) primesList[primeFactors[input[i]][j]].pb(i+1);
	}
	for(int i=0;i<primes.sz;++i)
		if(primesList[primes[i]].sz>0){
			trees[primes[i]]=vector<node>(primesList[primes[i]].sz<<3);
			build(primes[i],1,1,primesList[primes[i]].sz);
			//printf("%d\n",primes[i]);
			//printTree(primes[i],1,1,primesList[primes[i]].sz);
		}
	for(int i=0;i<Q;++i){
		int g,x,y;
		scanf("%d %d %d",&g,&x,&y);
		node res;
		for(int j=0;j<primeFactors[g].sz;++j){
			int l,r;
			if(primesList[primeFactors[g][j]].sz==0) continue;
			l=lower_bound(primesList[primeFactors[g][j]].begin(),primesList[primeFactors[g][j]].end(),x)-primesList[primeFactors[g][j]].begin();
			r=upper_bound(primesList[primeFactors[g][j]].begin(),primesList[primeFactors[g][j]].end(),y)-primesList[primeFactors[g][j]].begin();
			//printf("-->%d,%d - %d %d\n",x,y,l,r);
			if(l>r-1) continue;
			++l,++r;
			node temp=query(primeFactors[g][j],1,1,primesList[primeFactors[g][j]].sz,l,r-1);
			if(temp.val>res.val) res=temp;
		}
		printf("%d %d\n",res.val,res.freq);
	}
}
<file_sep>/CLPERM.cpp
// author noob333
// H + Shift C + B + E + B + E
#include <bits/stdc++.h>
#define NMAX 55
//#define DEBUG 1
using namespace std;
// Input macros
#define s(n)                        scanf("%d",&n)
#define sc(n)                       scanf("%c",&n)
#define sl(n)                       scanf("%lld",&n)
#define sf(n)                       scanf("%lf",&n)
#define ss(n)                       scanf("%s",n)
// Useful constants
#define INF                         (int)1e9
#define EPS                         1e-9
// Useful hardware instructions
#define bitcount                    __builtin_popcount
#define gcd                         __gcd
// Useful container manipulation / traversal macros
#define REP(i,a,b)                  for(int i=a;i<b;i++)
#define RREP(i,a,b)                 for(int i=a;i>b;i--)
#define foreach(v, c)               for( typeof( (c).begin()) v = (c).begin();  v != (c).end(); ++v)
#define all(a)                      a.begin(), a.end()
#define in(a,b)                     ( (b).find(a) != (b).end())
#define pb                          push_back
#define fill(a,v)                    memset(a, v, sizeof a)
#define sz(a)                       ((int)(a.size()))
#define mp                          make_pair
#define fi                          first
#define se                          second
// Some common useful functions
#define maX(a,b)                     ( (a) > (b) ? (a) : (b))
#define miN(a,b)                     ( (a) < (b) ? (a) : (b))
#define checkbit(n,b)                ( (n >> b) & 1)
#define DREP(a)                      sort(all(a)); a.erase(unique(all(a)),a.end())
#define INDEX(arr,ind)               (lower_bound(all(arr),ind)-arr.begin())
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<ll> vl;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef set<int> si;
typedef map<string, int> msi;
#ifdef DEBUG
     #define debug(args...)            {dbg,args; cerr<<endl;}
#else
    #define debug(args...)              // Just strip off all debug tokens
#endif
struct debugger
{
    template<typename T> debugger& operator , (const T& v)
    {    
        cerr<<v<<" ";    
        return *this;    
    }
} dbg;
template <typename T1, typename T2>
    inline std::ostream& operator << (std::ostream& os, const std::pair<T1, T2>& p)
    {
        return os << "(" << p.first << ", " << p.second << ")";
    }
    template<typename T>
    inline std::ostream &operator << (std::ostream & os,const std::vector<T>& v)
    {
        bool first = true;
        os << "[";
        for(unsigned int i = 0; i < v.size(); i++)
        {
            if(!first)
                os << ", ";
            os << v[i];
            first = false;
        }
        return os << "]";
    }
    template<typename T>
    inline std::ostream &operator << (std::ostream & os,const std::set<T>& v)
    {
        bool first = true;
        os << "[";
        for (typename std::set<T>::const_iterator ii = v.begin(); ii != v.end(); ++ii)
        {
            if(!first)
                os << ", ";
            os << *ii;
            first = false;
        }
        return os << "]";
    }
template<typename T1, typename T2>
inline std::ostream &operator << (std::ostream & os,const std::map<T1, T2>& v)
{
  bool first = true;
  os << "[";
  for (typename std::map<T1, T2>::const_iterator ii = v.begin(); ii != v.end(); ++ii)
    {
      if(!first)
	os << ", ";
      os << *ii ;
      first = false;
    }
  return os << "]";
}
inline ll ssum(int x){
  return (((ll)x)*(x+1))/2;
}
int main(){
  ios::sync_with_stdio(false);
  int T;
  cin >> T;
  while(T--){
    int n,k;
    cin >> n >> k;
    vi a(k+2);
    a[0] = 0; a[k+1]=n+1;
    REP(i,1,k+1) cin >> a[i];
    
    sort(all(a));
    ll sum = 0;
    REP(i,1,k+2){
      int st = a[i-1]+1;
      int en = a[i]-1;
      if(st>sum+1 && st<=en) break;
      sum += ssum(en)-ssum(st-1);
    }
    if((sum+1)%2) cout << "Chef"<< endl;
    else cout << "Mom" <<  endl;
  }
  return 0;
}
<file_sep>/LELEMON.cpp
#include <cstdio>
#include <vector>
#include <algorithm>
typedef long long int x64;
using namespace std;
vector<vector<int> > input;
vector<int> visits;
int N,M;
inline void fastRead_int(int &x) {
    register int c = getchar();
    x = 0;
    int neg = 0;
    for(; ((c<48 || c>57) && c != '-'); c = getchar());
    if(c=='-') {
    	neg = 1;
    	c = getchar();
    }
    for(; c>47 && c<58 ; c = getchar()) {
    	x = (x<<1) + (x<<3) + c - 48;
    }
    if(neg)
    	x = -x;
}
x64 solve()
{
	x64 res=0;
	for(int i=0;i<N;++i)
		sort(input[i].begin(),input[i].end());
	for(int k=0;k<M;++k)
	{
		if(input[visits[k]].size()>0)
		{
			res+=input[visits[k]][input[visits[k]].size()-1];
			input[visits[k]].pop_back();
		}
	}
	return res;
}
int main()
{
	int T;
	fastRead_int(T);
	while(T>0)
	{
		fastRead_int(N);
		fastRead_int(M);
		input=vector<vector<int> >(N,vector<int>(0));
		visits=vector<int>(M,0);
		for(int i=0;i<M;++i) fastRead_int(visits[i]);
		for(int i=0;i<N;++i)
		{
			int lim;
			fastRead_int(lim);
			for(int j=0;j<lim;++j)
			{
				int V;
				fastRead_int(V);
				input[i].push_back(V);
			}
		}
		printf("%lld\n",solve());
		--T;
	}
	return 0;
}
<file_sep>/CHEFCIRC.cpp
#include <bits/stdc++.h>
#define NMAX 502
#define eps 0.00001
using namespace std;
typedef pair<double,int> pdi;
inline double sq(double x){
  return x*x;
}
double X[NMAX], Y[NMAX];
int N,M;
void solve(){
  // double minX,minY,maxX,maxY;
  // minX=X[0], maxX=X[0];
  // minY=Y[0], maxY=Y[0];
  // for(int i=1;i<N;++i){
  //   minX = min(minX,X[i]);
  //   maxX = max(maxX,X[i]);
  //   minY = min(minY,Y[i]);
  //   maxY = max(maxY,Y[i]);
  // }
  double maxRadius = 707106.000;
  double minRadius = 0.0;
  while(maxRadius-minRadius > eps){
    double checkRadius = (maxRadius + minRadius)/2;
    int maxInside = 0;
    //cout << maxRadius << " " << minRadius << " " << checkRadius << endl;
    for(int i=0;i<N;++i){
      double x1=X[i], y1=Y[i];
      vector<pdi> events;
      //cout << x1 << "," << y1 << endl;
      for(int j=0;j<N;++j){
	if(i==j) continue;
	double x2=X[j], y2=Y[j];
	double d = sqrt(sq(x1-x2) + sq(y1-y2))/2;
	if(d>checkRadius) continue;
	double delta = atan2(y2-y1,x2-x1);
	double phi = acos(d/checkRadius);
	//cout << x2 << "," << y2 << " " << delta << " " << phi << endl;
	events.push_back(pdi(delta-phi,-1));
	events.push_back(pdi(delta+phi,+1));
      }
    
      sort(events.begin(),events.end());
      
      int currentCount, maxCount;
      currentCount = maxCount = 0;
      
      for(int i=0;i<events.size();++i){
	if(events[i].second == -1) ++currentCount;
	else --currentCount;
	maxCount = max(maxCount, currentCount);
	//cout << events[i].first << ":"  << events[i].second << " " << currentCount << endl;
      }
      maxCount++;
      maxInside = max(maxInside, maxCount);
      //cout << "maxOn:" << maxCount << endl;
    }
    //cout << "maxInside: " << maxInside << endl;
    if(maxInside<M) minRadius = checkRadius + 0.01;
    else maxRadius = checkRadius;
  }
  cout << maxRadius << endl;
}
int main(){
  ios::sync_with_stdio(false);
  cin >> N >> M;
  for(int i=0;i<N;++i)
    cin >> X[i] >> Y[i];
  solve();
  return 0;
}
<file_sep>/REN2013K.cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long int LL;
int main(){
  int T;
  scanf("%d",&T);
  while(T--){
    LL x,y,r,res;
    scanf("%lld %lld",&x,&y);
    r=(max(x,y)-min(x,y))+1;
    if(r%2==0){
      res=r-1;
      r=r/2;
      res=res*r;
    }
    else {
      res=r;
      res=res*((r-1)/2);
    }
    printf("%lld\n",res);
    
  }
}
<file_sep>/SEATSR.cpp
#include <bits/stdc++.h>
#define NMAX 111111
#define inf 1111111
using namespace std;
time_t start=clock();
int aCost,bCost;
char buffer[NMAX];
int editDistance(string a,string b,int k){
  if(a.size() < b.size()) swap(a,b);
  if(aCost==0) return 0;
  //else if(bCost==0)
	//return (a.size()-b.size()<=k?a.size()-b.size():-1);
  int sz=b.size()+1;
  //sz=max(sz,k+1);
  vector<int> pre(sz,inf),dis(sz,inf);
  for(int i = 0 ; i <= b.size(); i++){
    pre[i] = aCost*i;
  }
  for(int j=1 ; j <= a.size(); j++) {
    dis[0] = j*aCost;
    int minIdx = max(j - k, 1);
    int maxIdx = min(j + k, (int)b.size());
    if(minIdx > 1){
      dis[minIdx -1] = inf;
    }
    int minVal = inf;
    for(int i = minIdx ; i <= maxIdx ; i++){
      if(a[j-1] == b[i-1]){
  	dis[i] = pre[i-1];
      } else {
  	dis[i] = min(pre[i]+aCost, min(dis[i-1]+aCost, pre[i-1]+bCost));
      }
      if(dis[i] < minVal) minVal = dis[i];
    }
    swap(pre,dis);
    if(minVal > k) break;
  }
  if(pre[b.size()]<=k) return pre[b.size()];
  return -1;
}
int main(){
  int t;
  scanf("%d",&t);
  while(t--){
    string x,y;
    int k;
    scanf("%s",buffer);
    x=string(buffer);
    scanf("%s",buffer);
    y=string(buffer);
    scanf("%d %d %d",&aCost,&bCost,&k);
    //assert(!(k<aCost && k<bCost));
    int res=editDistance(x,y,k);
    if(res!=inf)
      printf("%d\n",res);
    else printf("-1\n");
  }
  //printf("%.6f",((double)clock()-start)/CLOCKS_PER_SEC);
  return 0;
}
<file_sep>/FGFS.cpp
#include <bits/stdc++.h>
#define pb push_back
#define x first
#define y second
using namespace std;
typedef pair<int,int> pi;
typedef pair<pi,int> pii;
vector<pii> input;
bool comp(const pii &f,const pii &s){
	if(f.y<s.y) return true;
	if(f.y==s.y) return f.x.y<s.x.y;
	return false;
}
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		int res=0;
		input.clear();
		int N,K;
		scanf("%d %d",&N,&K);
		for(int i=0;i<N;++i){
			int s,f,p;
			scanf("%d %d %d",&s,&f,&p);
			input.pb(pii(pi(s,f),p));
		}
		sort(input.begin(),input.end(),comp);
		int comp,prev,curr;
		prev=-1;
		for(int i=0;i<N;++i){
			comp=input[i].y;
			if(comp!=prev){
				++res;
				prev=comp;
				curr=i;
				continue;
			}
			if(input[i].x.x>=input[curr].x.y) ++res,curr=i;
			prev=comp;
		}
		printf("%d\n",res);
	}
	return 0;
}
<file_sep>/CAOS2.cpp
#include <cstdio>
#include <cstring>
#include <climits>
#include <iostream>
using namespace std;
const int MAX=502;
char array[MAX][MAX];
int dp[MAX][MAX],prime[MAX];
int R,C;
void solve()
{
	int counter=0;
	for(int i=0;i<R;++i)
		for(int j=0;j<C;++j)
			dp[i][j]=INT_MAX;
	for(int i=0;i<R;++i)
	{
		counter=0;
		for(int j=0;j<C;++j)
		{
			if(array[i][j]=='#')
			{
				counter=0;
				dp[i][j]=0;
				continue;
			}
			dp[i][j]=min(dp[i][j],counter);
			++counter;
		}
	}
	for(int i=0;i<R;++i)
	{
		counter=0;
		for(int j=C-1;j>=0;--j)
		{
			if(array[i][j]=='#')
			{
				counter=0;
				dp[i][j]=0;
				continue;
			}
			dp[i][j]=min(dp[i][j],counter);
			++counter;
		}
	}
	for(int j=0;j<C;++j)
	{
		counter=0;
		for(int i=R-1;i>=0;--i)
		{
			if(array[i][j]=='#')
			{
				counter=0;
				dp[i][j]=0;
				continue;
			}
			dp[i][j]=min(dp[i][j],counter);
			++counter;
		}
	}
	for(int j=0;j<C;++j)
	{
		counter=0;
		for(int i=0;i<R;++i)
		{
			if(array[i][j]=='#')
			{
				counter=0;
				dp[i][j]=0;
				continue;
			}
			dp[i][j]=min(dp[i][j],counter);
			++counter;
		}
	}
	int result=0;
	for(int i=0;i<R;++i)
		for(int j=0;j<C;++j)
			result+=prime[dp[i][j]];
	printf("%d\n",result);
}
int main()
{
	int T;
	for(int i = 2; i <= 500; i++) prime[i] = 1;
	for(int i = 2; i <= 500; i++)
		if(prime[i])
		{
			for(int j = i + i; j <= 500; j += i)
				prime[j] = 0;
		}
	for(int i = 2; i <= 500; i++) prime[i] += prime[i - 1];
	scanf("%d",&T);
	while(T>0)
	{
		scanf("%d %d",&R,&C);
		for(int i=0;i<R;++i)
			scanf("%s",array[i]);
		//printf("%d\n",solve());
		solve();
		--T;
	}
	return 0;
}
<file_sep>/DGCD.cpp
#include <bits/stdc++.h>
#define NMAX 55555
#define _abs(x) ( x>0?x:-x )
using namespace std;
int N,Q;
int input[NMAX];
int gcd(int a,int b){
  if(b==0) return _abs(a);
  return gcd(b,a%b);
}
// Begin Segment Tree Definition
struct node{
  node *l, *r;
  int diffG, lazy;
  int first, last;
  node(int a=0,int b=0,int c=0,int d=0,node *e=0,node *f=0){
    first=a;last=b;diffG=c;lazy=d;l=e;r=f;
  }
  node(node *x){
    first=x->first; last=x->last;
    diffG=x->diffG; lazy=x->lazy;
    l=x->l;r=x->r;
  }
};
struct segTree{
  node *root;
  vector<int> A;
  int sz;
  int value;
  segTree(vector<int> _A){
    A = vector<int>(_A);
    sz = A.size();
    root = build(1,sz);
  }
  void update(int st,int en,int val){
    value=val;
    root=update(root,1,sz,st,en);
  }
  int query(int st,int en){
    node *tmp=query(root,1,sz,st,en);
    return gcd(tmp->first,tmp->diffG);
  }
  node* modify(node *x,int val){
    x->first += val; x->last += val;
    x->lazy += val;
    return x;
  }
  node* push(node *x){
    if(x->l){
      if(x->lazy){
	modify(x->l,x->lazy);
	modify(x->r,x->lazy);
	x->lazy=0;
      }
    }
  }
  void merge(node *x, node*y, node *z){
    z->first=x->first;z->last=y->last;
    z->diffG = gcd(x->diffG,gcd(x->last-y->first,y->diffG));
  }
  
  node* build(int i,int j){
    node *tmp=new node();
    if(i==j){
      modify(tmp,A[i-1]);
      return tmp;
    }
    int mid=(i+j)>>1;
    tmp->l=build(i,mid);
    tmp->r=build(mid+1,j);
    merge(tmp->l,tmp->r,tmp);
    return tmp;
  }
  node* update(node *root,int i,int j,int st,int en){
    //node *tmp = new node(root->first,root->last,root->diffG,root->lazy,root->l,root->r);
    node *tmp = new node(root);
    if(i==st && j==en){
      modify(tmp,value);
      return tmp;
      //modify(root,value);
      //return root;
    }
    push(root); tmp->lazy=0;// push(tmp);
    int mid=(i+j)>>1;
    if(en<=mid) tmp->l = update(root->l,i,mid,st,en);
    else if(st>mid) tmp->r = update(root->r,mid+1,j,st,en);
    else{
      tmp->l = update(root->l,i,mid,st,mid);
      tmp->r = update(root->r,mid+1,j,mid+1,en);
    }
    merge(tmp->l,tmp->r,tmp);
    return tmp;
  }
  node* query(node *root,int i,int j,int st,int en){
    if(i==st && j==en) return root;
    push(root);
    int mid=(i+j)>>1;
    if(en<=mid) return query(root->l,i,mid,st,en);
    else if(st>mid) return query(root->r,mid+1,j,st,en);
    else{
      node *tmp=new node();
      merge(query(root->l,i,mid,st,mid),query(root->r,mid+1,j,mid+1,en),tmp);
      return tmp;
    }
  }
  void debug(){
    // cout << "----------------" << endl;
    // _print(root,1,sz);
    // cout << "----------------" << endl;   
  }
  void _print(node *root,int i,int j){
    if(i==j){
      printf("%d,%d - %d %d %d %d\n",i,j,root->first,root->last,root->diffG,root->lazy);
      return;
    }
    int mid=(i+j)>>1;
    _print(root->l,i,mid);
    _print(root->r,mid+1,j);
    printf("%d,%d - %d %d %d %d\n",i,j,root->first,root->last,root->diffG,root->lazy);
  }
};
// End of Segment Tree Definition
// -----------------------------------------------------------------------------------
// Begin LCA Functions
const int L = 19;
int p[NMAX][L];
int _log;
int ti[NMAX], to[NMAX], _tm;
int h[NMAX];
void buildLCA(){
  for(_log=0; 1<<_log<N; ++_log);
  ++_log;
  _tm = 0;
}
bool upper(int v, int u){
  return v==-1 || u!=-1 && ti[v]<ti[u] && to[v]>to[u];
}
int lca(int v, int u){
  if(v==u || upper(v,u)) return v;
  if(upper(u,v)) return u;
  for(int i=_log-1;i>=0;--i) if(!upper(p[v][i], u)) v = p[v][i];
  return p[v][0];
}
        
int nextDownTo(int from, int downto){
  for(int i=_log-1;i>=0;--i) if(upper(from, p[downto][i])) downto = p[downto][i];
  return downto;
}
// End LCA Functions
//---------------------------------------------------------------------------------
// Begin Graph Routines
vector<int> adj[NMAX];
int subt[NMAX];
inline void addEdge(int u,int v){
  adj[u].push_back(v);
  adj[v].push_back(u);
}
int dfs(int u,int par){
  ti[u] = ++_tm;
  p[u][0] = par;
  h[u] = (par==-1 ? 0 : h[par]+1);
  subt[u]=1;
  for(int i=1;i<_log;++i)
    p[u][i] = (p[u][i-1]==-1 ? -1: p[p[u][i-1]][i-1]);
  for(int i=0;i<adj[u].size();++i){
    int v=adj[u][i];
    if(v!=par) subt[u]+=dfs(v,u);
  }
  to[u] = ++_tm;
  return subt[u];
}
// End Graph Routines
//--------------------------------------------------------------------------
// Begin HLD Functions
vector<segTree*> trees;
vector<int> chain[NMAX];
int chId[NMAX], chPos[NMAX],chHd[NMAX];
int chNum;
int q[NMAX], qn;
int hld(int u,int p){
  if(chain[chNum].size()==0) chHd[chNum]=u;
  chain[chNum].push_back(input[u]);
  chId[u]=chNum; chPos[u]=chain[chNum].size();
  int most,ind;
  most = 0; ind = -1;
  for(int i=0;i<adj[u].size();++i){
    int v=adj[u][i];
    if(v!=p && subt[v]>most) most=subt[v], ind=v;
  }
  if(ind!=-1) hld(ind,u);
  for(int i=0;i<adj[u].size();++i){
    int v=adj[u][i];
    if(v!=ind && v!=p){
      ++chNum;
      hld(v,u);
    }
  }
}
void getPath(int from, int to){
  qn=0;
  for(;;){
    int fi = chId[from];
    int end = chHd[fi];
    if(fi==chId[to]) end = to;
    q[qn++]=fi;
    q[qn++]=chPos[end];
    q[qn++]=chPos[from];
    if(end==to) break;
    from = p[end][0];
  }
}
void buildSegTrees(){
  for(int i=0;i<=chNum;++i){
    segTree *tmp = new segTree(chain[i]);
    trees.push_back(tmp);
    tmp->debug();
  }
}
void changePath(int u,int p,int val){
  getPath(u,p);
  for(int i=0;i<qn;i+=3){
    int id=q[i];
    trees[id]->update(q[i+1],q[i+2],val);
  }
}
int queryPath(int u,int p){
  int res=0;
  getPath(u,p);
  for(int i=0;i<qn;i+=3)
    res = gcd(res, trees[q[i]]->query(q[i+1],q[i+2]));
  return res;
}
// End HLD functions
//-------------------------------------------------------------------------
// Solve Problem
void solve(){
  buildLCA();
  dfs(1,-1);
  hld(1,-1);
  buildSegTrees();
  char buf[3];
  int u,v,val,lc;
  for(int i=0;i<Q;++i){
    scanf("%s %d %d",buf,&u,&v);
    ++u;++v;
    lc = lca(u,v);
    if(buf[0]=='F')
      printf("%d\n",gcd(queryPath(u,lc),queryPath(v,lc)));
    else{
      scanf("%d",&val);
      changePath(u,lc,val);
      if(v!=lc) changePath(v,nextDownTo(lc,v),val);
    }
    // for(int i=0;i<=chNum;++i){
    //   cout << i << endl;
    //   trees[i]->debug();
    // }
      
  }
}
int main(){
  int u,v;
  scanf("%d",&N);
  for(int i=0;i<N-1;++i){
    scanf("%d %d",&u,&v);
    ++u;++v;
    addEdge(u,v);
  }
  for(int i=0;i<N;++i) scanf("%d",&input[i+1]);
  scanf("%d",&Q);
  solve();
  return 0;
}
<file_sep>/BUY1GET1.c
#include <stdio.h>
int alpha[52];
void setZero();
main()
{
 int T,i,j,cost=0;
 char str[101][201] ;
 scanf("%d",&T);
  for(i=0;i<T;++i)
   scanf("%s",str[i]);
  for(i=0;i<T;++i)
 {
   setZero();
   cost=0;
   for( j=0;str[i][j]!='\0';++j)
   {
     if(str[i][j]<91)
      ++alpha[str[i][j]-65];
     else
      ++alpha[str[i][j]-71];
   }
   for( j=0;j<52;++j)
 {    cost+=(alpha[j]/2+alpha[j]%2);
  }
  printf("\n%d",cost);
 }
 return 0;
}
void setZero()
{
  int i;
  for(i=0;i<52;++i)
   alpha[i]=0;
}
<file_sep>/PROSUM.cpp
#include <bits/stdc++.h>
#define NMAX 111111
using namespace std;
typedef long long int LL;
LL input[NMAX];
int main(){
	LL T;
	scanf("%lld",&T);
	while(T--){
		LL N,zeroes,ones,twos;
		LL res=0;
		scanf("%lld",&N);
		zeroes=ones=twos=0;
		for(LL i=0;i<N;++i){
			scanf("%lld",&input[i]);
			if(input[i]==0) ++zeroes;
			else if(input[i]==1) ++ones;
			else if(input[i]==2) ++twos;
		}
		res=N*(N-1)>>1;
		for(LL i=0;i<zeroes;++i) res-=(N-i-1);
		N=N-zeroes;
		for(LL i=0;i<ones;++i) res-=(N-i-1);
		res-=(twos*(twos-1)>>1);
		printf("%lld\n",res);
	}
	return 0;
}
<file_sep>/COMPILER.cpp
#include <bits/stdc++.h>
#define NMAX 1111111
using namespace std;
char str[NMAX];
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		scanf("%s",str);
		int len=strlen(str);
		stack<int> t;
		int match=0;
		for(int i=0;i<len;++i){
			if(str[i]=='<') t.push(1);
			else if(str[i]=='>'){
				if(t.empty()) break;
				t.pop();
			}
			if(t.empty()) match=i+1;
		}
		printf("%d\n",match);
	}
	return 0;
}
<file_sep>/RECTQUER.cpp
//============================================================================
// Name        : RECTQUER.cpp
// Author      : 
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================
#include <cstdio>
#include <cstring>
using namespace std;
#define NMAX 333
int input[NMAX][NMAX],state[NMAX][NMAX][10];
int main(){
	int N;
	scanf("%d",&N);
	memset(state,0,sizeof(state));
	for(int i=0;i<N;++i)
		for(int j=0;j<N;++j){
			scanf("%d",&input[i][j]);
			if(i>0) for(int k=0;k<10;++k) state[i][j][k]+=state[i-1][j][k];
			if(j>0) for(int k=0;k<10;++k) state[i][j][k]+=state[i][j-1][k];
			if(i>0 && j>0) for(int k=0;k<10;++k) state[i][j][k]-=state[i-1][j-1][k];
			state[i][j][input[i][j]-1]+=1;
		}
/*	printf("\n STATE SPACE");
	for(int i=0;i<N;++i)
		for(int j=0;j<N;++j)
		{
			printf("\n @ %d,%d - ",i,j);
			for(int k=0;k<10;++k) printf(" %d",state[i][j][k]);
		}
*/
	int Q;
	scanf("%d",&Q);
	for(int i=0;i<Q;++i){
		int x1,y1,x2,y2,res;
		scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
		--x1;
		--x2;
		--y1;
		--y2;
		res=0;
		for(int i=0;i<10;++i){
			int ans=state[x2][y2][i];
			if(x1>0) ans-=state[x1-1][y2][i];
			if(y1>0) ans-=state[x2][y1-1][i];
			if(x1>0 && y1>0) ans+=state[x1-1][y1-1][i];
			if(ans>0) ++res;
		}
		printf("%d\n",res);
	}
	return 0;
}
<file_sep>/FOURSQ.cpp
#include <bits/stdc++.h>
#define NMAX 1000000
#define SMAX 100000
#define L(x) (x<<1)
#define R(x) ((x<<1)|1)
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
const ull ten11 = 100000000000LL;
const ull ten10 = 10000000000LL;
const ull ten9  = 1000000000LL;
const int ten3  = 1000;
const int ten6  = 1000000;
vector<int> squares;
vector<int> splits[NMAX+1];
int sqRoot[NMAX+1], input[SMAX+1], fourSquares[NMAX+1];
ll MOD;
int check(int x,int depth){
if(x>NMAX) assert(false);
if(depth>3) return 0;
if(fourSquares[x] == 1 ) return 1;
int pos = upper_bound(squares.begin(),squares.end(),x)-squares.begin()-1;
if(squares[pos] == x){
fourSquares[x] = 1;
splits[x].push_back(x);
return 1;
}
while(pos>=0){
if(check(x-squares[pos], depth+1)){
if(splits[x-squares[pos]].size()<=3){
for(int i=0;i<splits[x-squares[pos]].size();++i)
splits[x].push_back(splits[x-squares[pos]][i]);
splits[x].push_back(squares[pos]);
//splits[x].push_back(squares[pos]);
//splits[x].push_back(x-squares[pos]);
fourSquares[x] = 1;
return 1;
}
}
--pos;
}
//assert(false);
return 0;
}
struct node{
ll a,b,c,d;
node(): a(0), b(0), c(0), d(0) {};
node(ll _a, ll _b, ll _c, ll _d): a(_a), b(_b), c(_c), d(_d) {};
}tree[SMAX<<3];
inline ull mulmod(ull A, ull B)
{
  register int x1,y1,x2,y2;
  register ull res;
  x1 = A/ten3;
  y1 = (A-(x1*ten3));
  x2 = B/ten3;
  y2 = (B-(x2*ten3));
  res = ((ull)x1*x2);
  if(res>=MOD) res %= MOD;
  res *= ten6;
  ull tmp = ((ull)x1*y2*ten3) + ((ull)x2*y1*ten3) + (y1*y2);
  res += tmp;
  if(res>=MOD) res %= MOD;
  // register ull x1,y1,res;
  // register ull x2,x3,y2,y3;
  // x3 = A/ten11;
  // x2 = (A-(x3*ten11))/ten10;
  // x1 = (A-(x3*ten11)-(x2*ten10));
  // y3 = B/ten11;
  // y2 = (B-(y3*ten11))/ten10;
  // y1 = (B-(y3*ten11)-(y2*ten10));
  // res = (x1*y1);
  // if(res>=MOD) res %= MOD;
  // ull tmp = (y1*ten9);
  // if(tmp>=MOD) tmp %= MOD;
  // tmp *= (10*x2+100*x3);
  // if(tmp>=MOD) tmp %= MOD;
  // res += tmp;
  // if(res>=MOD) res -= MOD;
  // res += ((y1*ten9))*(10*x2+100*x3);
  // res += ((x1*ten9))*(10*y2+100*y3);
  //res += ((x2+10*x3)*y1*1000);
//res += ((y2+10*y3)*x1*1000)%MOD;
  //res += ((((x1*y2 + y1*x2 + 10*x1*y3 + 10*y1*x3)*1000)%MOD)*10000000LL)%MOD;
  // //res += ((((((x2*y2 + 10*x2*y3 + 10*x3*y2 + 100*x3*y3)*ten10)%MOD)*100000)%MOD)*100000)%MOD;
  // res %= MOD;
  // if ( A == 0 || B == 0 ) return 0;
  // if ( 128-__builtin_clzll(A)-__builtin_clzll(B) <= 64 ) return (A*B)%MOD;
  // ull u = multiply(A, B>>1);
  // ull res = 0;
  // u <<= 1;
  // res += u;
  // if ( B&1 )
  //   res += A;
  //res %= MOD;
  return res;
}
// ull hand_multiply(ull a, ull b) {
//    if(b == 0 || b<=10000000) {
//      return (a*b)%MOD;
//    }
//    else {
//      ll result = (hand_multiply(a, b/10)*10)%MOD;
//      ll lastDigit = b%10;
//      result = (result+((a*lastDigit)))%MOD;
//      return result;
//    }
// }
//long long mulmod(long long A, long long B){
// if(A == 0 || LLONG_MAX/A >= B)
// return (A*B)%MOD;
//return multiply(max(A,B), min(A,B));
//}
// inline ll mulmod(ll a, ll b) {
// if(a == | LLONG_MAX/a >= b)
// return (a*b)%MOD;
// ll res = 0;
// while (a != 0) {
// if (a & 1) res = (res + b) % MOD;
// a >>= 1;
// b = (b << 1) % MOD;
// }
// return res;
// }
inline node splitToNode(int x){
vector<int> splitX = splits[x];
if(splitX.size()==1) return node(sqRoot[splitX[0]], 0, 0, 0);
else if(splitX.size()==2) return node(sqRoot[splitX[0]], sqRoot[splitX[1]], 0, 0);
else if(splitX.size()==3) return node(sqRoot[splitX[0]], sqRoot[splitX[1]], sqRoot[splitX[2]], 0);
else return node(sqRoot[splitX[0]], sqRoot[splitX[1]], sqRoot[splitX[2]], sqRoot[splitX[3]]);
}
inline node merge(node x, node y){
  register ll a,b,c,d;
  a = mulmod(x.a,y.a);
  a += mulmod(x.b,y.b); if(a>=MOD) a-= MOD;
  a += mulmod(x.c,y.c); if(a>=MOD) a-= MOD;
  a += mulmod(x.d,y.d); if(a>=MOD) a-= MOD;
  b = mulmod(x.a,y.b);
  b -= mulmod(x.b,y.a); if(b<0) b += MOD;
  b += mulmod(x.c,y.d); if(b>=MOD) b -= MOD;
  b -= mulmod(x.d,y.c); if(b<0) b += MOD;
  c = mulmod(x.a,y.c);
  c -= mulmod(x.c,y.a); if(c<0) c += MOD;
  c += mulmod(x.d,y.b); if(c>=MOD) c -= MOD;
  c -= mulmod(x.b,y.d); if(c<0) c += MOD;
  d = mulmod(x.a,y.d);
  d -= mulmod(x.d,y.a); if(d<0) d += MOD;
  d += mulmod(x.b,y.c); if(d>=MOD) d -= MOD;
  d -= mulmod(x.c,y.b); if(d<0) d += MOD;
// ll a = mulmod(x.a,y.a) + mulmod(x.b,y.b) + mulmod(x.c,y.c) + mulmod(x.d,y.d);
// ll b = mulmod(x.a,y.b) - mulmod(x.b,y.a) + mulmod(x.c,y.d) - mulmod(x.d,y.c);
// ll c = mulmod(x.a,y.c) - mulmod(x.c,y.a) + mulmod(x.d,y.b) - mulmod(x.b,y.d);
// ll d = mulmod(x.a,y.d) - mulmod(x.d,y.a) + mulmod(x.b,y.c) - mulmod(x.c,y.b);
//  a = a%MOD;
//  if(a<0) a+= MOD;
// b = b%MOD;
// if(b<0) b+= MOD;
// c = c%MOD;
// if(c<0) c+= MOD;
// d = d%MOD;
// if(d<0) d+= MOD;
return node(a,b,c,d);
}
void init(int idx, int i, int j){
if(i==j){
tree[idx] = splitToNode(input[i-1]);
return;
}
int mid = (i+j)>>1;
init(L(idx),i,mid);
init(R(idx),mid+1,j);
tree[idx] = merge(tree[L(idx)],tree[R(idx)]);
}
void update(int idx, int i, int j, int pos, int Y){
if(i==j && i==pos){
tree[idx] = splitToNode(Y);
return;
}
int mid=(i+j)>>1;
if(pos<=mid) update(L(idx),i,mid,pos,Y);
else update(R(idx),mid+1,j,pos,Y);
tree[idx] = merge(tree[L(idx)],tree[R(idx)]);
}
node query(int idx, int i, int j, int left, int right){
if(i==left && j==right) return tree[idx];
int mid = (i+j)>>1;
if(right<=mid) return query(L(idx),i,mid,left,right);
else if(left>mid) return query(R(idx),mid+1,j,left,right);
else{
return merge(query(L(idx),i,mid,left,mid)
,query(R(idx),mid+1,j,mid+1,right));
}
}
int main(){
  //ios::sync_with_stdio(false);
//clock_t start = clock();
for(int a=0;a*a<=NMAX;++a){
squares.push_back(a*a);
sqRoot[a*a]=a;
}
for(int i=0;i<=NMAX;++i){
  check(i,0);
// int s=0;
// for(int j=0;j<splits[i].size();++j)
// s += splits[i][j];
// if(splits[i].size()==0 || splits[i].size()>4 || s != i)
// assert(false);
}
int T;
//cin >> T;
 scanf("%d",&T);
while(T--){
int N,Q;
//cin >> N >> Q >> MOD;
 scanf("%d %d %lld", &N, &Q, &MOD);
 for(int i=0;i<N;++i) scanf("%d", &input[i]);
  // cin >> input[i];
//for(int i=0;i<N;++i) check(input[i], 0);
init(1,1,N);
for(int i=0;i<Q;++i){
int type, u, v;
//cin >> type >> u >> v;
 scanf("%d %d %d", &type, &u, &v);
if(type == 1){
  //check(v, 0);
update(1,1,N,u,v);
}
else{
node res = query(1,1,N,u,v);
//cout << res.a << " " << res.b << " " << res.c << " " << res.d << endl;
 printf("%lld %lld %lld %lld\n", res.a, res.b, res.c, res.d);
}
}
}
//clock_t stop = clock();
//cout << (stop - start)*1.0 / CLOCKS_PER_SEC << endl;
return 0;
}
<file_sep>/README.md
## Codechef solutions
Solutions to some of the problems on [Codechef](http://www.codechef.com).

(\<problem-code>.cpp)

I intend to add detailed solutions to some of the problems [here](http://maraghuram.github.io).
<file_sep>/RETPO.cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
inline ll abs_(ll x){
  if( x>0 ) return x;
  return -x;
}
int main(){
  int T;
  scanf("%d",&T);
  while(T--){
    ll x,y,res=0;
    scanf("%lld %lld",&x,&y);
    x=abs_(x);
    y=abs_(y);
    if( x==y )res=x+y;
    else if(x>y){
      res = y+y;
      res += (((x-y-1)/2)*4)+1-((x-y)%2)+3;
      }
    else{
      res = x+x;
      res += (((y-x)/2)*4)+(y-x)%2;
    }
    printf("%lld\n",res);
  }
  return 0;
}
<file_sep>/FROGV.cpp
#include <bits/stdc++.h>
#define NMAX 111111
using namespace std;
typedef long long int ll;
ll A[NMAX];
int rank[NMAX],maxInd[NMAX];
inline void swap(int &x,int &y){
  int t;
  t=x,x=y,y=t;
}
int main(){
  int N,P;
  ll K;
  vector<ll> B;
  scanf("%d %lld %d",&N,&K,&P);
  for(int i=0;i<N;++i){
    scanf("%lld",&A[i]);
    B.push_back(A[i]);
  }      
  sort(B.begin(),B.end());
  B.erase(unique(B.begin(),B.end()),B.end());
  for(int i=0;i<N;++i){
    rank[i]= lower_bound(B.begin(),B.end(),A[i])-B.begin();
  }
  int best=B.size()-1;
  maxInd[best]=best;
  for(int i=B.size()-2;i>=0;--i){
    if(B[i+1]-B[i]>K) best=i;
    maxInd[i]=best;
    //cout<<B[i]<<"<<- "<<maxInd[i]<<endl;
  }
  for(int i=0;i<P;++i){
    int u,v;
    scanf("%d %d",&u,&v);
    --u,--v;
    int x,y;
    if(rank[u]<rank[v]) x=u,y=v;
    else x=v,y=u;
    if(rank[y]<=maxInd[rank[x]]) printf("Yes\n");
    else printf("No\n");
  }
  
  return 0;
}
<file_sep>/SPCANDY.cpp
#include <cstdio>
typedef long long int x64;
int main()
{
	int T;
	scanf("%d",&T);
	while(T>0)
	{
		x64 N,K;
		scanf("%lld %lld",&N,&K);
		if(K==0)
			printf("%d %lld\n",0,N);
		else
			printf("%lld %lld\n",N/K,N%K);
		--T;
	}
	return 0;
}
<file_sep>/PLZLYKME.cpp
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long int LL;
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		LL L,D,S,C;
		scanf("%llu %llu %llu %llu",&L,&D,&S,&C);
		int flag=0;
		LL res=S;
		LL days=1;
		while(1){
			if(res>=L){
				flag=1;
				break;
			}
			++days;
			if(days>D) break;
			res=res*(C+1);
		}
		if(flag) printf("ALIVE AND KICKING\n");
		else printf("DEAD AND ROTTING\n");
	}
	return 0;
}
<file_sep>/MARBLEGF.cpp
#include <cstdio>
#include <cstring>
#define NMAX 1111111
typedef long long int LL;
LL tree[NMAX];
void update(int idx,LL val){
	for(int i=idx;i<NMAX;i+=(i&-i))
		tree[i]+=val;
}
LL read(int idx){
	LL val=0;
	for(int i=idx;i>0;i-=(i&-i))
		val+=tree[i];
	return val;
}
int main(){
	int N,Q;
	memset(tree,0,sizeof(tree));
	scanf("%d %d",&N,&Q);
	for(int i=0;i<N;++i){
		int in;
		scanf("%d",&in);
		update(i+1,in);
	}
	for(int i=0;i<Q;++i){
		char type[3];
		int u,v;
		scanf("%s %d %d",type,&u,&v);
		switch(type[0]){
		case 'S' : 	++u,++v;
					printf("%lld\n",u>1?read(v)-read(u-1):read(v));
					break;
		case 'G' :  ++u;
					update(u,v);
					break;
		case 'T' :  ++u;
					update(u,-v);
					break;
		}
	}
	return 0;
}
<file_sep>/DOWNLOAD.cpp
// By noob.
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <list>
#include <complex>
#pragma comment(linker, "/STACK:266777216")
using namespace std;
#define assert(f) { if(!(f)) { fprintf(stderr,"Assertion failed: "); fprintf(stderr,#f); fprintf(stderr,"\n"); exit(1); } }
typedef long long LL;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef pair<int,int> PII;
typedef vector<PII> VPII;
typedef vector<double> VD;
typedef pair<double,double> PDD;
const int inf=1000000000;
const LL INF=LL(inf)*inf;
const double eps=1e-9;
const double PI=2*acos(0.0);
#define bit(n) (1<<(n))
#define bit64(n) ((LL(1))<<(n))
#define pb push_back
#define sz size()
#define mp make_pair
#define cl clear()
#define all(a) (a).begin(),(a).end()
#define fill(ar,val) memset((ar),(val),sizeof (ar))
#define MIN(a,b) {if((a)>(b)) (a)=(b);}
#define MAX(a,b) {if((a)<(b)) (a)=(b);}
#define sqr(x) ((x)*(x))
#define X first
#define Y second
clock_t start=clock();
#define N 330000
#define G 5010
int x[N],y[N],tree[N];
VI aliens[G];
int previous[G],result[G],m;
void update (int i, int delta) {
	for (; i < m; i |= i + 1)
		tree[i] += delta;
}
int read(int r)
{
		int res = 0;
		for (; r >= 0; r = (r & (r + 1)) - 1)
			res += tree[r];
		return res;
}
int main()
{
#ifdef OFFLINE_JUDGE
	freopen("1.in","r",stdin);
#endif
#ifdef WRITE_JUDGE
	freopen("1.out","w",stdout);
#endif
	int n,q;
	scanf("%d",&n);
	for(int i=0;i<n;++i)	scanf("%d %d",&x[i],&y[i]);
	scanf("%d",&q);
	for(int i=0;i<q;++i)
	{
		int k;
		scanf("%d",&k);
		aliens[i].resize(k);
		for(int j=0;j<k;++j)	scanf("%d",&aliens[i][j]);
	}
	//Mix everything and compress (mix masala)
	VI mixture;
	vector<pair<int,pair<int,int> > > queue;
	mixture.clear();
	queue.clear();
	for(int i=0;i<n;++i)
	{
		mixture.pb(x[i]);
		mixture.pb(y[i]);
	}
	for(int i=0;i<q;++i)
		for(int j=0;j<aliens[i].sz;++j)
			mixture.pb(aliens[i][j]);
	sort(all(mixture));
	mixture.erase(unique(all(mixture)),mixture.end());
	m=mixture.sz;
	for(int i=0;i<n;++i)
	{
		x[i]=lower_bound(all(mixture),x[i])-mixture.begin();
		y[i]=lower_bound(all(mixture),y[i])-mixture.begin();
		queue.pb(mp(x[i],mp(-1,i)));
		queue.pb(mp(y[i],mp(+1,i)));
	}
	for(int i=0;i<q;++i)
		for(int j=0;j<aliens[i].sz;++j)
		{
			aliens[i][j]=lower_bound(all(mixture),aliens[i][j])-mixture.begin();
			queue.pb(mp(aliens[i][j],mp(0,i)));
		}
	sort(all(queue));
	memset(result,0,sizeof(result));
	memset(previous,-1,sizeof(previous));
	memset(tree,0,sizeof(tree));
	for(int i=0;i<queue.sz;++i)
	{
		int point=queue[i].X;
		int type=queue[i].Y.X;
		int id=queue[i].Y.Y;
		if(type)
		{
			update(x[id],-type);
		}
		else
		{
			result[id]+=read(point);
			if(previous[id]!=-1)	result[id]-=read(previous[id]);
			previous[id]=point;
		}
	}
	for(int i=0;i<q;++i)	printf("%d\n",result[i]);
#ifdef OFFLINE_JUDGE
fprintf(stderr,"time=%.3lfsec\n",0.001*(clock()-start));
#endif
return 0;
}
<file_sep>/LAPIN.cpp
#include <cstdio>
#include <cstring>
#include <vector>
const int MAX=1005;
using namespace std;
vector<int> count;
int main()
{
	int T;
	scanf("%d",&T);
	while(T>0)
	{
		char str[MAX];
		int len,i;
		bool flag=true;
		scanf("%s",str);
		len=strlen(str);
		count.clear();
		count.resize(26,0);
		for(i=0;i<len/2;++i)
			++count[str[i]-'a'];
		for(i=(len+1)/2;i<len;++i)
			--count[str[i]-'a'];
		for(i=0;i<26;++i)
			if(count[i])
			{
				flag=false;
				break;
			}
		if(!flag)
			printf("NO\n");
		else
			printf("YES\n");
		--T;
	}
	return 0;
}
<file_sep>/WALK.cpp
#include <bits/stdc++.h>
#define NMAX 111111
using namespace std;
int input[NMAX];
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		int N;
		int diff=0,res=-1;
		scanf("%d",&N);
		for(int i=0;i<N;++i){ scanf("%d",&input[i]); res=max(res,input[i]+i); }
		printf("%d\n",res);
	}
	return 0;
}
<file_sep>/MAXDIFF.cpp
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> weights;
int solve(int n,int k)
{
	int chefSum,kidSum,mid;
	sort (weights.begin(), weights.end());
	chefSum=kidSum=0;
	mid=k<n-k?k:n-k;
	for(int i=0;i<n;++i)
		if(i<mid)
			kidSum+=weights[i];
		else
			chefSum+=weights[i];
	return chefSum-kidSum;
}
int main()
{
	int T,N,K,R[102];
	scanf("%d",&T);
	for(int i=0;i<T;++i)
	{
		scanf("%d %d",&N,&K);
		weights.resize(N,0);
		for(int j=0;j<N;++j)
		{
			int temp;
			scanf("%d",&temp);
			weights[j]=temp;
		}
		R[i]=solve(N,K);
	}
	for(int i=0;i<T;++i)
	{
		printf("%d\n",R[i]);
	}
	return 0;
}
<file_sep>/DIGJUMP.cpp
#include <bits/stdc++.h>
#define SMAX 11
#define NMAX 111111
#define inf 99999
#define x first
#define y second
using namespace std;
typedef pair<int,int> pii;
pii dist[SMAX];
char input[NMAX];
void solve1();
int main(){
  solve1();
  return 0;
}
void solve1(){
  int len;
  
  for(int i=0;i<SMAX;++i) dist[i]=pii(inf,inf);
  
  scanf("%s",input);
  
  len=strlen(input);
  dist[input[0]-'0'].x=dist[input[0]-'0'].y=0;
  for(int T=0;T<50;++T){
  for(int i=1;i<len-1;++i){
    int prevNum=input[i-1]-'0';
    int num=input[i]-'0';
    int nextNum=input[i+1]-'0';
    
    int currDist=(dist[num].y==i?0:1);
    currDist+=dist[num].x;
    
    int prevdist=(dist[prevNum].y==i-1?0:1);
    prevdist+=dist[prevNum].x+1;
    if(prevdist<currDist) dist[num].x=prevdist,dist[num].y=i;
    
    currDist=(dist[num].y==i?0:1);
    currDist+=dist[num].x;
    
    int nextDist=(dist[nextNum].y==i+1?0:1);
    nextDist+=dist[nextNum].x+1;
    if(nextDist<currDist) dist[num].x=nextDist,dist[num].y=i;
    
    currDist=(dist[num].y==i?0:1);
    currDist+=dist[num].x;    
    
    int prevDist=(dist[prevNum].y==i-1?0:1);
    prevDist+=dist[prevNum].x;
    
    nextDist=(dist[nextNum].y==i+1?0:1);
    nextDist+=dist[nextNum].x;
    
    if(nextDist>currDist+1) dist[nextNum].x=currDist+1,dist[nextNum].y=i+1;
    if(prevDist>currDist+1) dist[prevNum].x=currDist+1,dist[prevNum].y=i-1;
    
  }
  if(len>1) {
    int prevDist=(dist[input[len-2]-'0'].y==len-2?0:1);
    prevDist+=dist[input[len-2]-'0'].x+1;
    int currDist=(dist[input[len-1]-'0'].y==len-1?0:1);
    currDist+=dist[input[len-1]-'0'].x;
    if(currDist>prevDist) dist[input[len-1]-'0'].x=prevDist,dist[input[len-1]-'0'].y=len-1;
  }
  }
  //printf("%d\n",dist[1].x);
  printf("%d\n",(dist[input[len-1]-'0'].y==len-1?dist[input[len-1]-'0'].x:dist[input[len-1]-'0'].x+1));
  
  
  //return 0;
}
<file_sep>/TOTR.cpp
#include <map>
#include <iostream>
#include <stdio.h>
std::map< char,char > lookupTable;
void createMap(char s[])
{
	char c='a';
	for(int i=0;s[i]!='\0';++i,++c)
	{
		lookupTable[c]=s[i];
		lookupTable[(char)(c-32)]=(char)(s[i]-32);
	}
	lookupTable['_']=' ';
}
int main()
{
	int T;
	char str[30],N[101][101];
	scanf("%d %s",&T,str);
	createMap(str);
	for(int i=0;i<T;++i)
	{
		scanf("%s",N[i]);
	}
	for(int i=0;i<T;++i)
	{
		for(int j=0;N[i][j]!='\0';++j)
		{
			if(lookupTable.find(N[i][j])!=lookupTable.end())
				N[i][j]=lookupTable[N[i][j]];
		}
		printf("%s\n",N[i]);
	}
}
<file_sep>/QSET.cpp
// author noob333
// H + Shift C + B + E + B + E
#include <bits/stdc++.h>
#define NMAX 111111
//#define DEBUG 1
using namespace std;
// Input macros
#define s(n)                        scanf("%d",&n)
#define sc(n)                       scanf("%c",&n)
#define sl(n)                       scanf("%lld",&n)
#define sf(n)                       scanf("%lf",&n)
#define ss(n)                       scanf("%s",n)
// Useful constants
#define INF                         (int)1e9
#define EPS                         1e-9
// Useful hardware instructions
#define bitcount                    __builtin_popcount
#define gcd                         __gcd
// Useful container manipulation / traversal macros
#define REP(i,a,b)                  for(int i=a;i<b;i++)
#define RREP(i,a,b)                 for(int i=a;i>b;i--)
#define foreach(v, c)               for( typeof( (c).begin()) v = (c).begin();  v != (c).end(); ++v)
#define all(a)                      a.begin(), a.end()
#define in(a,b)                     ( (b).find(a) != (b).end())
#define pb                          push_back
#define fill(a,v)                    memset(a, v, sizeof a)
#define sz(a)                       ((int)(a.size()))
#define mp                          make_pair
#define fi                          first
#define se                          second
#define L(x)                        ((x<<1))
#define R(x)                        ((x<<1)+1)
// Some common useful functions
#define maX(a,b)                     ( (a) > (b) ? (a) : (b))
#define miN(a,b)                     ( (a) < (b) ? (a) : (b))
#define checkbit(n,b)                ( (n >> b) & 1)
#define DREP(a)                      sort(all(a)); a.erase(unique(all(a)),a.end())
#define INDEX(arr,ind)               (lower_bound(all(arr),ind)-arr.begin())
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<ll> vl;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef set<int> si;
typedef map<string, int> msi;
#ifdef DEBUG
     #define debug(args...)            {dbg,args; cerr<<endl;}
#else
    #define debug(args...)              // Just strip off all debug tokens
#endif
struct debugger
{
    template<typename T> debugger& operator , (const T& v)
    {    
        cerr<<v<<" ";    
        return *this;    
    }
} dbg;
template <typename T1, typename T2>
    inline std::ostream& operator << (std::ostream& os, const std::pair<T1, T2>& p)
    {
        return os << "(" << p.first << ", " << p.second << ")";
    }
    template<typename T>
    inline std::ostream &operator << (std::ostream & os,const std::vector<T>& v)
    {
        bool first = true;
        os << "[";
        for(unsigned int i = 0; i < v.size(); i++)
        {
            if(!first)
                os << ", ";
            os << v[i];
            first = false;
        }
        return os << "]";
    }
    template<typename T>
    inline std::ostream &operator << (std::ostream & os,const std::set<T>& v)
    {
        bool first = true;
        os << "[";
        for (typename std::set<T>::const_iterator ii = v.begin(); ii != v.end(); ++ii)
        {
            if(!first)
                os << ", ";
            os << *ii;
            first = false;
        }
        return os << "]";
    }
template<typename T1, typename T2>
inline std::ostream &operator << (std::ostream & os,const std::map<T1, T2>& v)
{
  bool first = true;
  os << "[";
  for (typename std::map<T1, T2>::const_iterator ii = v.begin(); ii != v.end(); ++ii)
    {
      if(!first)
	os << ", ";
      os << *ii ;
      first = false;
    }
  return os << "]";
}
struct node{
  int val[3];
  int lazy;
  node(){
    val[0] = val[1] = val[2] = 0;
    lazy = 0;
  }
}tree[NMAX<<2];
inline void oneswap(node &x){
  swap(x.val[0],x.val[1]);
  swap(x.val[0],x.val[2]);
}
int a[NMAX];
int mod3[NMAX];
char input[NMAX];
void merge(node &a,node b,node c){
  REP(i,0,3)
    a.val[i] = b.val[i] + c.val[i];
}
void build(int idx,int i,int j){
  if(i==j){
    REP(k,0,3) tree[idx].val[k]=0; tree[idx].lazy=0;
    tree[idx].val[mod3[i-1]]=1;
    return;
  }
  int mid=(i+j)>>1;
  build(L(idx),i,mid);
  build(R(idx),mid+1,j);
  merge(tree[idx],tree[L(idx)],tree[R(idx)]);
}
node get(int idx,int i,int j,int st,int en){
  //debug("GET",i,j);
  if(tree[idx].lazy){
    if(tree[idx].lazy%3){
      REP(k,0,tree[idx].lazy%3) oneswap(tree[idx]);
      if(i!=j){
  	tree[L(idx)].lazy += tree[idx].lazy;
  	tree[R(idx)].lazy += tree[idx].lazy;
      }
    }
    tree[idx].lazy=0;
  }
  if(i>en || j <st) return node();
  if(st<=i && j<=en) return tree[idx];
  //if(i==st && j==en) return tree[idx];
  int mid=(i+j)>>1;
  node res,r1,r2;
  r1=get(L(idx),i,mid,st,en);
  r2=get(R(idx),mid+1,j,st,en);
  merge(res,r1,r2);
  //debug("***",vi(res.val,res.val+3),"***");
  return res;
}
void add(int idx,int i,int j,int st,int en,int newMod){
  if(tree[idx].lazy){
    if(tree[idx].lazy%3){
      REP(k,0,tree[idx].lazy%3) oneswap(tree[idx]);
      if(i!=j){
	tree[L(idx)].lazy += tree[idx].lazy;
	tree[R(idx)].lazy += tree[idx].lazy;
      }
    }
    tree[idx].lazy=0;
  }
  if(i>en || j<st) return;
  if(st<=i && j<=en){
    REP(k,0,newMod) oneswap(tree[idx]);
    if(i!=j){
      tree[L(idx)].lazy += newMod;
      tree[R(idx)].lazy += newMod;
    }
    return;
  }
  int mid = (i+j)>>1;
  add(L(idx),i,mid,st,en,newMod);
  add(R(idx),mid+1,j,st,en,newMod);
  merge(tree[idx],tree[L(idx)],tree[R(idx)]);
}
 
void printTree(int idx,int i,int j){
  if(i==j){
    //debug(i,j,vi(tree[idx].val,tree[idx].val+3),tree[idx].lazy);
    return;
  }
  int mid = (i+j)>>1;
  printTree(L(idx),i,mid);
  printTree(R(idx),mid+1,j);
  //debug(i,j,vi(tree[idx].val,tree[idx].val+3),tree[idx].lazy);
}
int main(){
  ios::sync_with_stdio(false);
  int n,m;
  cin >> n >> m;
  cin >> input;
  int tot = 0;
  REP(i,0,n){
    a[i] = (input[i]-'0')%3;
    tot += input[i]-'0';
    tot %= 3;
    mod3[i] = tot;
    //add(tot,i+1,1);
  }
  build(1,1,n);
  REP(i,0,m){
    int ty,u,v;
    cin >> ty >> u >> v;
    if(ty==1){
      v %= 3;
      //debug("-->",a[u-1],v,"<--");
      if(a[u-1]==v) continue;
      else{
      	int delta = (v-a[u-1]+3)%3;
	add(1,1,n,u,n,delta);
	// REP(j,0,3){
      	//   cur[j] = get(j,n)-get(j,u-1);
      	//   add(j,u,-cur[j]);
      	// }
      	// REP(j,0,3) add(j,u,cur[(j+delta)%3]);
      	// //add(a[u-1],u,-1);
      	// //add(v,u,1);
      	a[u-1] = v;
      }
    }
    else{
      ll ans = 0;
      node res= get(1,1,n,u,v);
      REP(j,0,3){
	ans += ((ll)res.val[j]*((ll)res.val[j]-1))/2;
      }
      //debug(vi(res.val,res.val+3));
      int prevMod = 0;
      if(u>1){
	node tmp = get(1,1,n,u-1,u-1);
	REP(j,0,3){
	  if(tmp.val[j]>0){
	    prevMod = j;
	    break;
	  }
	}
      }
      //debug(prevMod);
      ans += res.val[prevMod];
      cout << ans << endl;
    }
    //debug('\n');
    //printTree(1,1,n);
  }
  return 0;
}
<file_sep>/LEMUSIC.cpp
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
typedef unsigned long long x64;
int main()
{
	int T,N;
	x64 B,L;
	scanf("%d",&T);
	while(T>0)
	{
		scanf("%d",&N);
		vector<x64> bands,songs;
		map<x64,x64> flags;
		x64 sweetness=0;
		for(int i=0;i<N;++i)
		{
			scanf("%llu %llu",&B,&L);
			if(flags.find(B)==flags.end())
				flags[B]=L;
			else
			{
				x64 min=flags[B];
				if(L<min)
				{
					flags[B]=L;
					songs.push_back(min);
				}
				else
				{
					songs.push_back(L);
				}
			}
		}
		map<x64,x64>::iterator itr;
		for(itr=flags.begin();itr!=flags.end();++itr)
		{
			bands.push_back(itr->second);
		}
		sort(bands.begin(),bands.end());
		int count=1;
		sweetness=0;
		for(vector<x64>::iterator itr2=bands.begin();itr2!=bands.end();++itr2)
		{
			sweetness+=count*(*itr2);
			++count;
		}
		--count;
		for(vector<x64>::iterator itr3=songs.begin();itr3!=songs.end();++itr3)
		{
			sweetness+=count*(*itr3);
		}
		printf("%llu\n",sweetness);
		--T;
	}
}
<file_sep>/REN2013A.cpp
#include <bits/stdc++.h>
using namespace std;
int main(){
  int T;
  scanf("%d",&T);
  while(T--){
    int A,B,res;
    scanf("%d %d",&A,&B);
    res=0;
    int temp=A;
    int base=-1;
    while(temp){
      base=max(base,temp%10);
      temp=temp/10;
    }
    ++base;
    temp=A;
    int x=1;
    while(temp){
      res+=((temp%10)*x);
      x*=base;
      temp/=10;
    }
    temp=B;
    base=-1;
    while(temp){
      base=max(base,temp%10);
      temp=temp/10;
      
    }
    ++base;
    temp=B;
    x=1;
    while(temp){
      res+=((temp%10)*x);
      x*=base;
      temp/=10;
    }
    printf("%d\n",res);   
  }
  
  return 0;
}
<file_sep>/OJUMPS.cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long int LL;
int main(){
	LL x;
	scanf("%lld",&x);
	if(x%6==0 || x%6==1 || x%6==3) printf("yes\n");
	else printf("no\n");
	return 0;
}
<file_sep>/GIFTCHEF.cpp
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
//typedef unsigned long long ull;
typedef long long int ll;
ll hash(const string & s)
{
  ll ret = 0;
  for(int i = 0; i < s.size(); ++i){
    ret *= 257;
    ret += s[i];
    ret %= MOD;
  }
  return ret;
}
ll pow2(ll base, ll exp){
  ll res = 1;
  while( exp > 0 ){
    if( exp & 1 ) res *= base, res %= MOD;
    base *= base, base %= MOD;
    exp >>= 1;
  }
  return res;
}
vector<int> rollingHashMatch(const string& needle, const string& haystack)
{
  vector<int> isMatch(haystack.size(),0);
  ll hash1 = hash(needle);
  ll hash2 = 0;
  ll maxCoff = pow2( 257, needle.size() );
  
  for (int i = 0; i < haystack.size(); i++){
    hash2 = hash2 * 257 + haystack[i];
    hash2 %= MOD;
    if (i >= needle.size()){
      hash2 -= (maxCoff * haystack[i-needle.size()])%MOD;
      hash2 += MOD, hash2 %= MOD;
    }
    
    if (i >= needle.size()-1 && hash1 == hash2)
      isMatch[i] = 1;
  }
  
  return isMatch;
}
ll solve(const string& needle, const string& haystack){
  int n = needle.size();
  vector<int> matches = rollingHashMatch( needle, haystack );
  vector<ll> dp(haystack.size(),0), cumulativeDp(haystack.size(),0);
  for(int i=0;i<haystack.size();++i){
    dp[i] = 0;
    if( matches[i] ){
      //cout << "HERE" << i << endl;
      ll res = 1;
      if( i - n >= 0 ) res += cumulativeDp[i-n], res %= MOD;
      dp[i] = res;      
    }
    cumulativeDp[i] = dp[i];
    if( i > 0 ) cumulativeDp[i] += cumulativeDp[i-1], cumulativeDp[i] %= MOD;
  }
  return cumulativeDp[haystack.size()-1];
}
int main(){
  ios::sync_with_stdio( false );
  int T;
  cin >> T;
  while( T-- ){
    string haystack,needle;
    cin >> haystack >> needle;
    cout << solve( needle, haystack ) << endl;
  }
  
  return 0;
}
<file_sep>/CHEFZOT.cpp
#include <bits/stdc++.h>
#define NMAX 111111
using namespace std;
int N;
int main(){
  int res,count;
  
  scanf("%d",&N);
  res=count=0;
  
  for(int i=0;i<N;++i){
    int x;
    scanf("%d",&x);
    if(x==0) res=max(res,count),count=0;
    else ++count;
  }
  res=max(res,count);
  printf("%d\n",res);
  
  return 0;
}
<file_sep>/GUESS.cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long int S64;
int main(){
  int T;
  scanf("%d",&T);
  while(T--){
    S64 N,M;
    S64 num,denom;
    scanf("%lld %lld",&N,&M);
    if(N%2==0 || M%2==0) num=1,denom=2;
    else{
      denom=M*N;
      num=denom>>1;
    }
    printf("%lld/%lld\n",num,denom);
  } 
}
<file_sep>/CPERM.cpp
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
typedef long long int ll;
ll powmod( ll base, ll exp ){
  ll res = 1;
  while( exp ){
    if( exp & 1 ) res *= base, res %= MOD;
    base *= base, base %= MOD;
    exp >>= 1;
  }
  return res;
}
int main(){
  ios::sync_with_stdio( false );
  int T;
  cin >> T;
  while( T-- ){
    int N;
    cin >> N;
    
    if( N < 2 ){
      cout << 0 << endl;
      continue;
    }
    cout << (powmod( 2, N-1 )+MOD-2)%MOD << endl;
  }
  return 0;
}
<file_sep>/CHEFLR.cpp
#include <bits/stdc++.h>
#define NMAX 111111
#define MOD 1000000007
using namespace std;
typedef long long int ll;
char buffer[NMAX];
ll modpow( int base, int exp ){
  ll res=1;
  ll b = (ll) base;
  while( exp > 0 ){
    if( exp&1 ) res = ( res * b ) % MOD; 
    b = ( b * b ) % MOD;
    exp >>= 1;
  }
  return res;
}
int main(){
  //cout << modpow(2,4) << " " << modpow(2,5) << " " << modpow(2,6)<< endl;
  int T;
  scanf("%d\n",&T);
  while(T--){
    scanf("%s",buffer);
    int n = strlen( buffer )+1;
    ll ignore = 0;
    for(int i=0;i<n;++i){
      if( buffer[i] == 'r' ) {
	ignore += modpow( 2, n-i-2 );
	ignore %= MOD;
      }
    }
    ll upto = 0;
    ll start;
    if( n%2 ) start = 1;
    else start = 2;
    while( start < n ){
      upto += modpow( 2, start-1 );
      upto %= MOD;
      start +=2 ;
    }
    //cout << ignore << " " << upto << endl;
    ll res = ( ( ( ignore + upto ) %MOD ) * 2 ) %MOD;
    res = ( res + (n%2?1:2) ) %MOD;
    printf("%lld\n", res );
  }
  return 0;
}
<file_sep>/CHEFGR.cpp
#include <bits/stdc++.h>
using namespace std;
int main(){
  int t;
  scanf("%d",&t);
  while(t--){
    int m,n,bst=-1;
    scanf("%d %d",&n,&m);
    vector<int> a(n);
    for(int i=0;i<n;++i){
      scanf("%d",&a[i]);
      bst=max(a[i],bst);
    }
    int res=0;
    for(int i=0;i<n;++i) res += (bst-a[i]);
    if(m==res) printf("Yes\n");
    else if(m>res && (res-m)%n==0) printf("Yes\n");
    else printf("No\n");
  }
  return 0;
}
<file_sep>/TUX03.cpp
#include <bits/stdc++.h>
using namespace std;
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		int bestTeam,diff;
		diff=1111111;
		for(int i=0;i<10;++i){
			int small,large;
			large=-1;
			small=1111111;
			for(int j=0;j<15;++j){
				int x;
				scanf("%d",&x);
				small=min(small,x);
				large=max(large,x);
			}
			if(large-small<=diff) diff=large-small,bestTeam=i;
		}
		printf("%d %d\n",bestTeam+1,diff);
	}
	return 0;
}
<file_sep>/PHYSICS.cpp
#include <bits/stdc++.h>
#define NMAX 11111
using namespace std;
typedef long long int ll;
typedef pair<int,int> pi;
ll f,s,l;
int n;
vector<ll> a;
int main(){
  int T;
  scanf("%d",&T);
  for(int t=0;t<T;++t){
    ll res=0;
    l=0;
    scanf("%d %lld",&n,&f);
    a=vector<ll>(n);
    for(int i=0;i<n;++i){
      scanf("%lld",&a[i]);
      l=max(l,a[i]);
    }
    sort(a.begin(),a.end());
    for(int i=0;i<n;++i){
      ll val=a[i]; ll cnt=0;
      while(val<=l){
	cnt = upper_bound(a.begin(),a.end(),val)-a.begin();
	cnt -= lower_bound(a.begin(),a.end(),val)-a.begin();
	res += cnt;
	val *= f;
      }
      ll _f=f;
      val=a[i];
      while(val/_f>=1){
	if(val%_f==0){
	  cnt = upper_bound(a.begin(),a.end(),val/_f)-a.begin();
	  cnt -= lower_bound(a.begin(),a.end(),val/_f)-a.begin();
	  res += cnt;
	}
	_f=_f*f;
      }
    }
    printf("%lld\n",(res-n)/2);
  }
  return 0;
}
<file_sep>/PRLADDU.cpp
#include <bits/stdc++.h>
#define NMAX 111111
using namespace std;
inline int _abs(int x){
  return (x>=0?x:(-x));
}
int a[NMAX];
int main(){
  int t;
  scanf("%d",&t);
  while(t--){
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;++i) scanf("%d",&a[i]);
    int x,y;
    x=y=0;
    long long res=0;
    while(1){
      while(x<n && a[x]<=0) ++x;
      while(y<n && a[y]>=0) ++y;
      if(x>=n || y>=n ) break;
      int tmp=min(a[x],_abs(a[y]));
      res += (_abs(x-y)*tmp);
      a[x]-=tmp;
      a[y]+=tmp;
      //cout << x << " " << y <<endl;
    }
    printf("%lld\n",res);
  }
  return 0;
}
<file_sep>/ALEXTASK.cpp
#include <bits/stdc++.h>
using namespace std;
int computeGcd( int x, int y ){
  int tmp;
  while( y > 0 ){
    tmp = x%y;
    x = y;
    y = tmp;
  }
  return x;
}
int main(){
  ios::sync_with_stdio(false);
  int T;
  cin >> T;
  while( T-- ){
    int N;
    cin >> N;
    vector<int> a(N);
    for(int i=0;i<N;++i) cin >> a[i];
    unsigned long long int res = ULLONG_MAX;
    for(int i=0;i<N;++i){
      for(int j=i+1;j<N;++j){
	int gcd = computeGcd( a[i], a[j] );
	unsigned long long int mul, lcm;
	if( a[i] % gcd ){
	  mul = a[i]/gcd;
	  lcm = a[j]*mul;
	}
	else{
	  mul = a[j]/gcd;
	  lcm = a[i]*mul;
	}
	res = min( res, lcm );
      }
    }
    cout << res << endl;
  }
  return 0;
}
<file_sep>/EQUAKE.cpp
#include <bits/stdc++.h>
#define NMAX 800011
#define DMAX 12
#define L(x) (x<<1)
#define R(x) ((x<<1)+1)
#define gc getchar_unlocked
void _scan(int &x)
{
    register int c = gc();
    x = 0;
    for(;(c<48 || c>57);c = gc());
    for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
}
using namespace std;
time_t start=clock();
struct node{
  int lazy,currPtr;
  int best[DMAX];
  node(){
    lazy=0;
    currPtr=0;
  }
}tree[NMAX<<2];
int N,M;
int A[NMAX],B[NMAX];
node null;
vector<int> pre[10000];
int cnt[10000];
int st,en,f;
void preCompute(){
  for(int i=0;i<10;++i){    
    pre[i].push_back(i);
    for(int j=0;j<11;++j) pre[i].push_back(i);
    cnt[i]=1;
  }
  for(int i=10;i<100;++i){
    pre[i].push_back(i);
    pre[i].push_back((i%10)*10 + i/10);
    for(int j=0;j<5;++j){
      pre[i].push_back(pre[i][0]);
      pre[i].push_back(pre[i][1]);
    }
    cnt[i]=2;
  }
  for(int i=100;i<1000;++i){
    pre[i].push_back(i);
    pre[i].push_back((i%10)*10 + ((i/10)%10)*100 + i/100);
    pre[i].push_back((i%10)*100 + (i/100)*10 + (i/10)%10);
    for(int j=0;j<3;++j){
      pre[i].push_back(pre[i][0]);
      pre[i].push_back(pre[i][1]);
      pre[i].push_back(pre[i][2]);
    }
    cnt[i]=3;
  }
  for(int i=1000;i<10000;++i){
    pre[i].push_back(i);
    pre[i].push_back((i%10)*10 + ((i/10)%10)*100 + ((i/100)%10)*1000 + i/1000);
    pre[i].push_back((i%10)*100 + ((i/10)%10)*1000 + ((i/100)%10) + (i/1000)*10);
    pre[i].push_back((i%10)*1000 + ((i/10)%10) + ((i/100)%10)*10 + (i/1000)*100);
    for(int j=0;j<2;++j){
      pre[i].push_back(pre[i][0]);
      pre[i].push_back(pre[i][1]);
      pre[i].push_back(pre[i][2]);
      pre[i].push_back(pre[i][3]);
    }
    cnt[i]=4;
  }
}
inline node merge( node x, node y ){
  node z;
  for(int i=0;i<DMAX;++i)
    z.best[i]=max(x.best[(x.currPtr+i)%DMAX],y.best[(y.currPtr+i)%DMAX]);
  return z;
}
inline void setVal(int index,int i,int j,int val){
  int cnt=val%DMAX;
  tree[index].currPtr += cnt;
  tree[index].currPtr %= DMAX;
  if(i!=j){
    tree[L(index)].lazy += cnt;
    tree[L(index)].lazy %= DMAX;
    tree[R(index)].lazy += cnt;
    tree[R(index)].lazy %= DMAX;
  }
}
inline void propagate(int index,int i,int j){
  if(tree[index].lazy){
    setVal(index,i,j,tree[index].lazy);
    tree[index].lazy=0;
  }
}
inline void build(int index,int i,int j){
  tree[index].currPtr=tree[index].lazy=0;
  if(i==j){
    tree[index].currPtr=0;
    for(int k=0;k<DMAX;++k) 
      tree[index].best[k]=pre[A[i]][k];
    return;
  }
  int mid=(i+j)>>1;
  build(L(index),i,mid);
  build(R(index),mid+1,j);
  tree[index]=merge(tree[L(index)],tree[R(index)]);
}
inline void update(int index,int i,int j){
  propagate(index,i,j);
  if(i>=st && j<=en){
    setVal(index,i,j,f);
    return;
  }
  if(i>en || j<st) return;
  int mid=(i+j)>>1;
  update(L(index),i,mid);
  update(R(index),mid+1,j);
  tree[index]=merge(tree[L(index)],tree[R(index)]);
}
inline int query(int index,int i,int j){
  propagate(index,i,j);
  if(i>=st && j<=en){
    return tree[index].best[tree[index].currPtr];
  }
  if(i>en || j<st) return 0;
  int mid=(i+j)>>1;
  int x=query(L(index),i,mid);
  int y=query(R(index),mid+1,j);
  tree[index]=merge(tree[L(index)],tree[R(index)]);
  return max(x,y);
}
void printTree(int index,int i,int j){
  if(i==j){
    cout<<i<<","<<j<<" ";
    for(int k=tree[index].currPtr;(k+1)%DMAX!=tree[index].currPtr;k=(k+1)%DMAX) cout<<tree[index].best[k]<<" ";
    cout<<"--"<<tree[index].lazy<<" "<<tree[index].currPtr<<endl;
    return;
  }
  int mid=(i+j)>>1;
  printTree(L(index),i,mid);
  printTree(R(index),mid+1,j);
  cout<<i<<","<<j<<" ";
  for(int k=tree[index].currPtr;(k+1)%DMAX!=tree[index].currPtr;k=(k+1)%DMAX) cout<<tree[index].best[k]<<" ";
  cout<<"--"<<tree[index].lazy<<" "<<tree[index].currPtr<<endl;    
}
void debug(){
#ifdef deb
  cout<<endl<< "---- DEBUGGIING ----"<<endl;
  printTree(1,1,N);
  cout<<endl<< "--- END ------" <<endl;
#endif
}
int main(){
  //  freopen("1.in","r",stdin);
  //freopen("5.out","w",stdout);
  preCompute();
  //scanf("%d",&N);
  _scan(N);
  //N=fi.ReadNext();
  for(int i=1;i<=N;++i){
    //scanf("%d",&A[i]);
    _scan(A[i]);    
    //A[i]=fi.ReadNext();    
    //B[i]=cnt[A[i]];
  }
  build(1,1,N);
  //scanf("%d",&M);
  _scan(M);
  //M=fi.ReadNext();
  for(int i=0;i<M;++i){
    int type,u,v;
    //scanf("%d %d %d",&type,&u,&v);
    //type=fi.ReadNext();u=fi.ReadNext();v=fi.ReadNext();
    _scan(type);_scan(u);_scan(v);
    ++u,++v;
    if( type == 1 ){
    //fo.PrintUint(query(u,v),'\n');
      st=u;en=v;
      printf("%d\n",query(1,1,N));
    }
    else{
      //scanf("%d",&f);
      //f=fi.ReadNext();
      _scan(f);
      st=u;en=v;
      update(1,1,N);
      //update(u,v,f);
    }
  }
  //fo.Flush();
  //fprintf(stderr,"%.3lf\n",(((double)clock())-start)/CLOCKS_PER_SEC);
  return 0;
}
<file_sep>/FUNC.cpp
#include <bits/stdc++.h>
#define NMAX 11111
#define MOD 1000000007
#define pb push_back
using namespace std;
typedef long long int ll;
const ll MAXVAL = 1000000000000000000LL;
vector<ll> powers[65];
void pre_compute( ) {
  for( int i = 3; i<65; ++i ) powers[i].pb( (ll)1 );
  for( ll i = 2; i<=1000000; ++i ) {
    ll cnt,prod;
    cnt = 2;
    prod = i*i;
    while( i <= MAXVAL / prod ) {
      ++cnt;
      prod = prod * i;
      powers[cnt].pb( prod );
    }
  }
}
ll power( ll n, ll exp ) {
  ll res = 1;
  while( exp > 0 ){
    if( exp%2 ) res = res * n, exp = exp-1;
    else n = n * n, exp = exp>>1;
  }
  return res;
}
int main() {
  pre_compute();
  
  int T;
  scanf( "%d", &T );
  while( T-- ) {
    int N, Q;
    scanf( "%d %d", &N, &Q );
    
    vector<ll> A(N+5), B(N+5);
    B[0]=0;
    for(int i=1;i<=N;++i) {
      scanf("%lld",&A[i]);
      B[i]=B[i-1]+A[i];
      A[i]=A[i]%MOD;
      if( A[i] < 0 ) A[i] += MOD;
    }
    for(int i=0;i<Q;++i){
      ll x,res;
      int j;
      scanf("%lld",&x);
      
      res=0;
      for(j=1;j<=N;++j){
	ll root;
	
	if( j==1 ) root = x;
	else if( j==2 ) root = (ll) sqrt(x);
	else{
	  ll index = (ll) ( upper_bound( powers[j].begin(), powers[j].end(), x ) - powers[j].begin()  + 3 ); 
	  while( pow(index, j) > x ) --index;
	  root = index;
	}
	
	if( root == 1 ) break;
	
	root = root % MOD;
	res = ( res + ( root * A[j] ) %MOD ) % MOD;
      }
      ll temp = ( B[N] - B[j-1] ) % MOD;
      if( temp < 0 ) temp += MOD;
      res = ( res + temp ) % MOD;
      if( res < 0 ) res += MOD;
      printf("%lld",res);
      if(i < Q-1 ) printf(" ");
    }
    
    printf("\n");
  }
 
  return 0;
}
<file_sep>/FATCHEF.cpp
#include <bits/stdc++.h>
#define NMAX 111111
#define MOD 1000000009
using namespace std;
typedef pair<int,char> pic;
pic a[NMAX];
int main(){
	int t;
	char buf[3];
	scanf("%d",&t);
	while(t--){
		int n,m;
		scanf("%d %d",&n,&m);
		for(int i=0;i<m;++i){
			scanf("%s %d",buf,&a[i].first);
			a[i].second=buf[0];
		}
		sort(a,a+m);
		long long res=1;
		for(int i=0;i<m-1;++i){
			pic next=a[i+1];
			if(next.second!=a[i].second){
				res *= (next.first-a[i].first);
				res %= MOD;
			}
		}
		printf("%lld\n",res);	
	}
	return 0;
}
<file_sep>/JOHNY.cpp
#include <cstdio>
#define NMAX 111
using namespace std;
int input[NMAX];
int main(){
	int T;
	scanf("%d",&T);
	while(T>0){
		int N,K,count=0;
		scanf("%d",&N);
		for(int i=0;i<N;++i) scanf("%d",&input[i]);
		scanf("%d",&K);
		for(int i=0;i<N;++i) if(input[i]<input[K-1]) ++count;
		printf("%d\n",count+1);
		--T;
	}
	return 0;
}
<file_sep>/CHODE.cpp
#include <cstring>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <iostream>
#define NMAX 155555
using namespace std;
typedef pair<int,char> pic;
vector<pic> calc;
char input[NMAX],freq[26],output[NMAX];
int pos[26];
inline bool alpha(char x){
	if(x>=65 && x<=90) return true;
	if(x>=97 && x<=122) return true;
	return false;
}
void solve(){
	int len=strlen(input);
	calc=vector<pic>(26,pic(0,' '));
	for(int i=0;i<26;++i) calc[i].second='A'+i;
	//puts(input);
	for(int i=0;i<len;++i){
		if(alpha(input[i]))
		{
			char t=input[i];
			if(input[i]>=97) t=t-'a'+'A';
			calc[t-'A'].first+=1;
			//printf("\nHERE");
		}
	}
	sort(calc.begin(),calc.end());
	for(int i=0;i<26;++i){
		pos[calc[i].second-'A']=i;
	}
	for(int i=0;i<len;++i){
		if(alpha(input[i])){
			char t=input[i];
			int temp=(t>=97)?t-'a':t-'A';
			output[i]=(t>=97?freq[pos[temp]]:freq[pos[temp]]-'a'+'A');
		}
		else output[i]=input[i];
	}
}
int main(){
	int T;
	scanf("%d\n",&T);
	while(T>0){
		memset(input,'\0',sizeof(input));
		memset(freq,'\0',sizeof(freq));
		memset(output,'\0',sizeof(output));
		gets(freq);
		gets(input);
		solve();
		puts(output);
		--T;
	}
	return 0;
}
<file_sep>/MCHAIRS.cpp
#include <cstdio>
#define NMAX	100000005
#define MOD		1000000007
using namespace std;
typedef long long int x64;
x64 compute(int exp){
	x64 res=1;
	x64 base=2;
	while(exp>0){
		if(exp%2)
			res=(res*base)%MOD;
		exp=exp>>1;
		base=(base*base)%MOD;
	}
	return res;
}
int main(){
	int T;
	scanf("%d",&T);
	while(T>0){
		int N;
		scanf("%d",&N);
		printf("%lld\n",compute(N)-1);
		--T;
	}
	return 0;
}
<file_sep>/CHEFKEY.cpp
#include <bits/stdc++.h>
using namespace std;
int main(){
  ios::sync_with_stdio(false);
  int T;
  
  cin >> T;
  while( T-- ){
      int n,m,c, res = 0;
      cin >> n >> m >> c;
      
      for(int i=1; i*i <= c; ++i ){
	if( c%i == 0 ){
	  int h = i, w = c/i;
	  if( h <= n && w <= m ) ++res;
	  if( h != w ){
	    swap( h, w );
	    if( h <= n && w <= m ) ++res;
	  }
	}
      }
      
      cout << res << endl;
  }
  
}
<file_sep>/CHEFPATH.cpp
#include <bits/stdc++.h>
using namespace std;
int main(){
	ios::sync_with_stdio(false);
	int T;
	cin >> T;
	while( T-- ){
		long long int N,M;
		cin >> N >> M;
		if( (N==1 && M==2) || (N==2 && M==1))
			cout << "Yes" << endl;
		else if( N==1 || M==1 )
			cout << "No" << endl;
		else if( N%2==0 || M%2==0 )
			cout << "Yes" << endl;
		else
			cout << "No" << endl;
	}
	return 0;
}
<file_sep>/MAXPR.cpp
#include <bits/stdc++.h>
#define NMAX 222222
#define MOD 1000000007	    
#define gc getchar_unlocked
using namespace std;
typedef long int ll;
int input[NMAX]; 
int N;
ll sum[111],pow2[NMAX];
inline void scan(int &x)
{
    register int c = gc();
    x = 0;
    int neg = 0;
    for(;((c<48 || c>57) && c != '-');c = gc());
    if(c=='-') {neg=1;c=gc();}
    for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
    if(neg) x=-x;
}
void solve() {
  ll total = 0;
  ll subs = pow2[N];
  for(int diff=-100; diff<=100; ++diff){
    ll curr=0;
    memset(sum,0,sizeof(sum));
    for(int i=0;i<N;++i ){
      ll res = 0;
      if(input[i]-diff >= 0 && input[i]-diff <= 100 )
	res = ( sum[input[i]-diff] );	        
	if( res>=MOD ) res=res%MOD;
      sum[input[i]] = ( sum[input[i]] + res + 1 );
      if( sum[input[i]] >= MOD ) sum[input[i]] = sum[input[i]] %MOD;
      curr = ( curr + res + 1);
      if( curr >= MOD ) curr = curr % MOD;
    }    
    curr = ( curr - N ) % MOD;
    if( curr < 0 ) curr += MOD;
    total = ( curr + total );
    if( total >= MOD ) total = total % MOD;
  }
  total = ( total + N );
  if( total >= MOD ) total = total % MOD;
  subs = (subs - 1 - total)%MOD;
  if( subs<0 ) subs += MOD;
	   
  printf("%ld\n",subs);
	   
}
int main(){
  int T;
  //scanf("%d",&T);
  scan(T);
  pow2[0]=1;
  for(int i=1;i<=200000; ++i){
    pow2[i]=pow2[i-1]<<1;
    if(pow2[i]>=MOD) pow2[i]=pow2[i]%MOD;
  }
  while( T-- ) {
    //scanf("%d",&N);        
    scan(N);
    
    for(int i=0;i<N;++i ){
      //scanf("%d",&input[i]) ;
      scan(input[i]);      
    }
    solve();  
  }
  return 0;
}
<file_sep>/CHDOGS.cpp
#include <bits/stdc++.h>
using namespace std;
int main(){
  ios::sync_with_stdio( false );
  int T;
  
  cin >> T;
  while( T-- ){
    int s,v;
    cin >> s >> v;
    
    double tmp = (2.0/3.0) * s;
    cout << setprecision (6) << fixed << tmp/v << endl;
  }
}
<file_sep>/SGARDEN.cpp
#include <bits/stdc++.h>
#define NMAX 111111
#define MOD 1000000007
using namespace std;
vector<int> primes;
vector<int> factors[NMAX];
int flag[NMAX];
int next[NMAX];
int highest[NMAX];
void sieve(){
  memset(flag,0,sizeof(flag));
  flag[0]=flag[1]=1;
  for(int i=2;i<NMAX;++i){
    if(flag[i]==0){
      primes.push_back(i);      
      highest[i]=1;
      for(int j=i;j<NMAX;j+=i){
	flag[j]=1;
	factors[j].push_back(i);
      }
    }
  }
}
int main(){
  sieve();
  int T;
  scanf("%d",&T);
  while(T--){
    int N;
    scanf("%d",&N);
    for(int i=0;i<N;++i){
      scanf("%d",&next[i+1]);
      flag[i+1]=0;
    }
    
    int cnt=0;  
    vector<int> val;
    for(int i=0;i<primes.size();++i){
      if(primes[i]>N) break;
      highest[primes[i]]=1;
    }
    for(int i=1;i<=N;++i){
      if(flag[i]==0){
	int pos=i;
	int cnt=0;
	do{
	  flag[pos]=1;
	  pos=next[pos];
	  ++cnt;
	}while(pos!=i);
	val.push_back(cnt);
      }
    }
    for(int i=0;i<val.size();++i){
      int x=val[i];
      for(int j=0;j<factors[x].size();++j){
	int temp=x;
	int u=factors[x][j];
	int cnt=1;
	while(temp%u==0) temp=temp/u,cnt=cnt*u;
	highest[u]=max(highest[u],cnt);
      }
    }
    
    long long int res=1;
    
    for(int i=0;i<primes.size();++i){
      if(primes[i]>N) break;
      res = ( res * (long long int)highest[primes[i]] ) % MOD;
    }
    printf("%lld\n",res);
  }
  return 0;
}
<file_sep>/CHSQR.cpp
#include <bits/stdc++.h>
using namespace std;
int main(){
  ios::sync_with_stdio( false );
  int T;
  cin >> T;
  while( T-- ){
    int K;
    cin >> K;
    if( K == 1 ){
      cout << 1 << endl;
      continue;
    }
    vector<vector<int> > a(K, vector<int>(K));
    for(int i=0;i<K;++i)
      for(int j=0;j<K;++j)
	a[i][j] = (j-i+K)%K;
    for(int i=0,j=K/2-1;i<j;++i,--j)
      swap( a[i], a[j] );
    for(int i=K/2,j=K-1;i<j;++i,--j)
      swap( a[i], a[j] ); 
    //swap( a[K/2], a[K/2+1] );
    for(int i=0;i<K;++i){
      for(int j=0;j<K-1;++j)
	cout << a[i][j] + 1 << " ";
      cout << a[i][K-1] + 1 << endl;
    }
  }
  return 0;
}
<file_sep>/SSTORY.cpp
#include <bits/stdc++.h>
#define MAXLEN 555555
using namespace std;
struct state{
  int len,link;
  map<char,int> next;
};
state st[MAXLEN];
int sz,last;
int v,l,bestpos,best;
void sa_init(){
  sz=last=0;
  st[0].link=-1;
  st[0].len=0;
  ++sz;
}
void sa_extend(char c){
  int cur=sz++;
  st[cur].len=st[last].len+1;
  int p;
  for(p=last;p!=-1 && !st[p].next.count(c); p=st[p].link)
    st[p].next[c]=cur;
  if(p==-1)
    st[cur].link=0;
  else{
    int q=st[p].next[c];
    if(st[q].len== st[p].len+1)
      st[cur].link=q;
    else{
      int clone=sz++;
      st[clone].len=st[p].len+1;
      st[clone].next=st[q].next;
      st[clone].link=st[q].link;
      for(;p!=-1 && st[p].next[c]==q;p=st[p].link)
	st[p].next[c]=clone;
      st[q].link=st[cur].link=clone;
    }
  }
  last=cur;
}
string lcs(string s,string t){
  sa_init();
  for(int i=0;i<s.length();++i)
    sa_extend(s[i]);
  
  v=l=bestpos=best=0;
  for(int i=0;i<t.length();++i){
    while(v && !st[v].next.count(t[i])){
      v=st[v].link;
      l=st[v].len;
    }
    if(st[v].next.count(t[i])){
      v=st[v].next[t[i]];
      ++l;
    }
    if(l>best)
      best=l,bestpos=i;
  }
  return t.substr(bestpos-best+1,best);
}
int main(){
  string s,t,res;
  cin>>s>>t;
  
  res=lcs(s,t);
  if(best>0)
    cout<<res<<endl<<best<<endl;
  else
    cout<<0;
  
  return 0;
}
<file_sep>/REVERSE.cpp
#include <bits/stdc++.h>
#define NMAX 111111
#define gc getchar
//#define debug 1
#define inf NMAX<<2
using namespace std;
typedef pair<int,int> pii;
time_t start=clock();
inline void _scan(int &x)
{
    register int c = gc();
    x = 0;
    for(;((c<48 || c>57) && c != '-');c = gc());
    for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
}
vector<pii> adjList[NMAX];
int dist[NMAX],visited[NMAX];
void genTest(){
	FILE *fp=freopen("1.in","w",stdout);
	printf("%d %d\n",100000,100000);
	for(int i=0;i<100000;++i){
		int u=rand()%100000+1;
		int v=rand()%100000+1;
		printf("%d %d\n",u,v);
	}
	fclose(fp);
}
int N,M;
int main(){
	//scanf("%d %d",&N,&M);
#ifdef debug
	genTest();
	start=clock();
	freopen("1.in","r",stdin);
#endif
	_scan(N);
	_scan(M);
	for(int i=0;i<M;++i){
		int u,v;
		//scanf("%d %d",&u,&v);
		_scan(u);
		_scan(v);
		if(u==v) continue;
		adjList[u].push_back(pii(v,0));
		adjList[v].push_back(pii(u,1));
	}
	for(int i=1;i<=N;++i) dist[i]=inf;
	set<pii> q;
	q.insert(pii(0,1));
	while(!q.empty()){
		pii best=*q.begin();
		q.erase(q.begin());
		int u=best.second;
		int cst=best.first;
		if(u==N){
			printf("%d\n",cst);
//#ifdef debug
//			fprintf(stderr,"%.5lf",((double)clock()-start)/CLOCKS_PER_SEC);
//			assert(((double)clock()-start)/CLOCKS_PER_SEC<1.0);
//#endif
			return 0;
		}
		visited[u]=1;
		for(int i=0;i<adjList[u].size();++i){
			int v=adjList[u][i].first;
			int w=adjList[u][i].second;
			if(visited[v]) continue;
			if(dist[v]>w+cst){
				q.erase(pii(dist[v],v));
				dist[v]=w+cst;
				q.insert(pii(dist[v],v));
			}
		}
	}
	printf("-1\n");
//#ifdef debug
//	fprintf(stderr,"%.5lf",((double)clock()-start)/CLOCKS_PER_SEC);
//	assert(((double)clock()-start)/CLOCKS_PER_SEC<1.0);
//#endif
	return 0;
}
<file_sep>/TRIQUERY.cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define NMAX 999999
#define TX 0
#define TY 1
using namespace std;
struct query{
	int x,y,type;
	int d,index;
}q[NMAX];
int res[NMAX/3],tree[NMAX][2];
int N,Q;
void update(int idx,int val,int t){
	for(int i=idx;i<NMAX;i+=(i&-i))
		tree[i][t]+=val;
}
bool comp(const query &l,const query &r){
		if(l.x+l.y<r.x+r.y) return true;
		if((l.x+l.y==r.x+r.y) && (l.type<r.type)) return true;
		return false;
}
int read(int idx,int t){
	int res=0;
	for(int i=idx;i>0;i-=(i&-i))
		res+=tree[i][t];
	return res;
}
int main(){
	int qptr=0;
	scanf("%d %d",&N,&Q);
	for(int i=0;i<N;++i){
		scanf("%d %d",&q[qptr].x,&q[qptr].y);
		q[qptr].type=0;
		++qptr;
	}
	for(int i=0;i<Q;++i){
		scanf("%d %d %d",&q[qptr].x,&q[qptr].y,&q[qptr].d);
		q[qptr].index=i;
		q[qptr].type=-1;
		++qptr;
		q[qptr].x=q[qptr-1].x,q[qptr].y=q[qptr-1].y+q[qptr-1].d,q[qptr].d=q[qptr-1].d,q[qptr].index=q[qptr-1].index;
		q[qptr].type=1;
		++qptr;
	}
	sort(q,q+qptr,comp);
	memset(tree,0,sizeof(tree));
	int pts=0;
	for(int i=0;i<qptr;++i){
		query qry=q[i];
		//printf("%d %d %d\n",qry.x,qry.y,qry.type);
		if(qry.type==0){
			update(qry.x,+1,TX);
			update(qry.y,+1,TY);
			++pts;
		}
		else if(qry.type==-1){
			res[qry.index]=read(qry.x-1,TX)+read(qry.y-1,TY)-pts;
			//printf("%d\n",res[qry.index]);
		}
		else{
			res[qry.index]+=pts-read(qry.x-1,TX)-read(qry.y-qry.d-1,TY);
			//printf("%d\n",res[qry.index]);
		}
	}
	for(int i=0;i<Q;++i) printf("%d\n",res[i]);
	return 0;
}
<file_sep>/CLMBSTRS.c
#include <stdio.h>
#define MAX 1000001
 
unsigned long array[MAX];
unsigned long mod=1000000007;
 
main()
{
	unsigned int T,G[100000],i,j;
	unsigned long n[100000];
	#ifdef _MSC_VER
	freopen("input.txt","r",stdin);
        #endif
 
	array[0]=1;
	array[1]=1;
 
	scanf("%u",&T);
 
	for(i=2;i<MAX;++i)
	{
		array[i]=array[i-1]+array[i-2];
		if(array[i]>mod)
			array[i]=array[i]%mod;
 
	}
 
 
	for(i=0;i<T;++i)
	{
		scanf("%lu %u",&n[i],&G[i]);
	}
 
	for(j=0;j<T;++j)
	{
 
      if(countOnes(array[n[j]])==G[j])
    	  printf("\nCORRECT");
      else
    	  printf("\nINCORRECT");
 
	}
	return 0;
}
 
 int countOnes(unsigned long int n)
 {
	 unsigned long temp=n;
	 int count=0;
 
	 while(temp>0)
	 {
		 if(temp%2)
			 ++count;
		 temp=temp/2;
	 }
	 return count;
 }
<file_sep>/ERROR.cpp
#include <bits/stdc++.h>
#define NMAX 111111
using namespace std;
char input[NMAX];
int main(){
	int T;
	scanf("%d",&T);
	while(T>0){
		scanf("%s",input);
		int len=strlen(input);
		int flag=0;
		for(int i=0;i<len-2;++i){
			if((input[i]=='0'&&input[i+1]=='1'&&input[i+2]=='0')||(input[i]=='1'&&input[i+1]=='0'&&input[i+2]=='1'))
			{
				flag=1;
				break;
			}
		}
		if(flag) printf("Good\n");
		else printf("Bad\n");
		--T;
	}
	return 0;
}
<file_sep>/URBANDEV.cpp
#include <bits/stdc++.h>
#define NMAX 100002
using namespace std;
typedef pair<int,int> pii;
typedef pair<pair<int,int>,int> ppi;
vector<ppi> xlines[NMAX];
vector<ppi> ylines[NMAX];
bool eventCompare( ppi i, ppi j ){
  return (i.first.first == j.first.first? i.first.second < j.first.second: i.first.first < j.first.first);
}
int bitTree[NMAX<<3];
inline void add( int index, int val ){
  for(int i=index; i<(NMAX<<3); i+= (i&-i))
    bitTree[i] += val;
}
inline int get( int index ){
  int result = 0;
  for(int i=index; i > 0; i-= (i&-i))
    result += bitTree[i];
  return result;
}
int signals[NMAX];
long long int counter;
void solve(){
  memset(bitTree, 0, sizeof(bitTree));
  vector<ppi> events;
  for(int i=1;i<NMAX;++i){
    for(int j=0;j<xlines[i].size();++j){
      events.push_back(ppi(pii(xlines[i][j].first.first,1),i));
      events.push_back(ppi(pii(xlines[i][j].first.first,4),i));
      events.push_back(ppi(pii(xlines[i][j].first.first,6),i));
      events.push_back(ppi(pii(xlines[i][j].first.second,3),i));
    }
  }
  
  for(int i=1;i<NMAX;++i){
    for(int j=0;j<ylines[i].size();++j){
      events.push_back(ppi(pii(i,2),j));
      events.push_back(ppi(pii(i,5),j));
    }
  }
  sort(events.begin(), events.end(), eventCompare);
  for(int i=0;i<events.size();++i){
    int xval = events[i].first.first;
    int type = events[i].first.second;
    if( type == 3 || type == 4 ){
      int yval = events[i].second;
      add( yval, -1 );
    }
    else if( type == 1 || type == 6 ){
      add( events[i].second, +1 );
    }
    else if( type == 2 ){
      int j = events[i].second;
      int l = ylines[xval][j].first.first + 1;
      int r = ylines[xval][j].first.second - 1;
      int ptr = ylines[xval][j].second;
      if(l<=r){
	int res = get(r)-get(l-1);
	counter += res;
	signals[ptr] += res;
      }
    }
    else{
      int j = events[i].second;
      int l = ylines[xval][j].first.first;
      int r = ylines[xval][j].first.second;
      int ptr = ylines[xval][j].second;
      int res = get(r)-get(r-1);
      counter += res;
      signals[ptr] += res;
	
      res = get(l)-get(l-1);
      counter += res;
      signals[ptr] += res;      
    }    
  }
}
int main(){
  ios::sync_with_stdio(false);
  int N;
  cin >> N;
  for(int i=0;i<N;++i){
    int x1,y1,x2,y2;
    cin >> x1 >> y1 >> x2 >> y2;
    if( x1 == x2 )
      ylines[x1].push_back(ppi(pii(min(y1,y2),max(y1,y2)),i));
    else
      xlines[y1].push_back(ppi(pii(min(x1,x2),max(x1,x2)),i));
  }
  counter = 0;
  solve();
  long long int signalCount = counter;
  for(int i=1;i<NMAX;++i){
    swap( xlines[i], ylines[i] );
  }
  solve();
  cout << signalCount << endl;
  for(int i=0;i<N-1;++i) cout << signals[i] << " ";
  cout << signals[N-1] << endl;
  return 0;
}
<file_sep>/DISHOWN.cpp
#include <bits/stdc++.h>
#define NMAX 11111
using namespace std;
int par[NMAX],best[NMAX],sz[NMAX];
int N;
int find(int x){
  if( par[x] == -1) return x;
  else par[x]=find(par[x]);
}
int join(int x,int y){
  par[x]=y;
  best[y]=max(best[y],best[x]);
}
int main(){
  int T;
  scanf("%d",&T);
  while(T--){
    scanf("%d",&N);
    for(int i=1;i<=N;++i){
      par[i]=-1;
      sz[i]=1;
      scanf("%d",&best[i]);
    }
    int Q;
    scanf("%d",&Q);
    for(int i=0;i<Q;++i){
      int t;
      scanf("%d",&t);
      if(t==0){     
	int u,v;
	scanf("%d %d",&u,&v);
	int x,y;
	x=find(u);
	y=find(v);
	if(x==y) printf("Invalid query!\n");
	else if( best[x]<best[y] ) join(x,y);
	else if( best[y]<best[x] ) join(y,x);	
      }
      else{
	int u;
	scanf("%d",&u);
	printf("%d\n",find(u));
      }
      
    }
  }
  return 0;
}
<file_sep>/CHEFSQUA.cpp
#include <bits/stdc++.h>
#define NMAX 2222
#define x first
#define y second
using namespace std;
typedef pair<int,int> pi;
typedef long long int ll;
typedef pair<pi,pi> ppii;
pi a[NMAX];
set<pi> check;
inline ll dist(int x1,int y1,int x2,int y2){
  ll res = (x1-x2);
  res *= (x1-x2); res += (y1-y2)*(y1-y2);
  return res;
}
int main(){
  int n;
  scanf("%d",&n);
  for(int i=0;i<n;++i){
    scanf("%d %d",&a[i].x,&a[i].y);
    check.insert(a[i]);
  }
  assert(n==check.size());
  if(n==0){
    printf("%d\n",4);
    return 0;
  }
  else if(n==1){
    printf("%d\n",3);
    return 0;
  }
  int x1,x2,y1,y2;
  int best=0;
  ll a2;
  ppii p1,p2;
  pi t1,t2,t3,t4;
  int above,below;
  for(int i=0;i<n;++i){
    for(int j=i+1;j<n;++j){
      x1=a[i].x;x2=a[j].x;y1=a[i].y;y2=a[j].y;
      a2 = dist(x1,y1,x2,y2);
      t1=pi(x1+(y2-y1),y1+(x1-x2));
      t2=pi(x1-(y2-y1),y1-(x1-x2));
      t3=pi(x2+(y2-y1),y2+(x1-x2));
      t4=pi(x2-(y2-y1),y2-(x1-x2));
      if(dist(t1.x,t1.y,t3.x,t3.y)==a2){
	p1.x=t1; p1.y=t3; p2.x=t2; p2.y=t4;
      }
      else{
	assert(dist(t1.x,t1.y,t4.x,t4.y)==a2);
	p1.x=t1; p1.y=t4; p2.x=t2; p2.y=t3;
      }
      above=below=0;
      if(check.find(p1.x)!=check.end()) ++above;
      if(check.find(p1.y)!=check.end()) ++above;
      if(check.find(p2.x)!=check.end()) ++below;
      if(check.find(p2.y)!=check.end()) ++below;
      best=max(best,max(above,below)+2);
    }
  }
  printf("%d\n",4-best);
  return 0;
}
<file_sep>/TUX01.cpp
#include <bits/stdc++.h>
#define NMAX 1111111
#define L(x) (x<<1)
#define R(x) ((x<<1)+1)
using namespace std;
typedef long long int LL;
struct node{
	LL val,freq;
	node(LL v,LL f){
		val=v,freq=f;
	}
	node(){
		val=-1;
		freq=0;
	}
};
node tree[NMAX<<3];
LL input[NMAX];
node merge(const node &x,const node &y){
	if(x.val==-1 && y.val==-1)
		return node(-1,0);
	else if(x.val==-1)
		return node(y.val,y.freq);
	else if(y.val==-1)
		return node(x.val,x.freq);
	else{
		if(x.val==y.val) return node(x.val,x.freq+y.freq);
		else if(x.val<y.val) return node(x.val,x.freq);
		else return node(y.val,y.freq);
	}
}
void init(LL index,LL i,LL j){
	if(i==j){
		if(input[i-1]%2) tree[index]=node(-1,0);
		else tree[index]=node(input[i-1],1);
		return;
	}
	LL mid=(i+j)>>1;
	init(L(index),i,mid);
	init(R(index),mid+1,j);
	tree[index]=merge(tree[L(index)],tree[R(index)]);
}
node query(LL index,LL i,LL j,LL left,LL right){
	if(i==left && j==right)
		return tree[index];
	else if(i>right || j<left)
		return node(-1,0);
	LL mid=(i+j)>>1;
	if(right<=mid) return query(L(index),i,mid,left,right);
	else if(left>mid) return query(R(index),mid+1,j,left,right);
	else return merge(query(L(index),i,mid,left,mid),query(R(index),mid+1,j,mid+1,right));
}
void update(LL index,LL i,LL j,LL pos,LL val){
	if(i==j && i==pos){
		if(val%2) tree[index]=node(-1,0);
		else tree[index]=node(val,1);
		return;
	}
	LL mid=(i+j)>>1;
	if(pos<=mid) update(L(index),i,mid,pos,val);
	else update(R(index),mid+1,j,pos,val);
	tree[index]=merge(tree[L(index)],tree[R(index)]);
}
/*void prLLTree(LL index,LL i,LL j){
	if(i==j){
		prLLf("%d,%d - %lld %lld\n",i,j,tree[index].val,tree[index].freq);
		return;
	}
	LL mid=(i+j)>>1;
	prLLTree(L(index),i,mid);
	prLLTree(R(index),mid+1,j);
	prLLf("%d,%d - %lld %lld\n",i,j,tree[index].val,tree[index].freq);
}*/
void swap(LL &x,LL &y){
	LL temp=x;
	x=y;
	y=temp;
}
int main(){
	LL N,M;
	scanf("%lld %lld",&N,&M);
	for(LL i=0;i<N;++i) scanf("%lld",&input[i]);
	init(1,1,N);
	for(LL i=0;i<M;++i) {
		LL type,u,v;
		scanf("%lld %lld %lld",&type,&u,&v);
		node res;
		switch(type){
		case 1 :	res=query(1,1,N,u,v);
					if(res.val==-1) res.freq=0;
					printf("%lld %lld\n",res.val,res.freq);
					break;
		case 2 :	update(1,1,N,u,v);
					break;
		}
	}
	return 0;
}
<file_sep>/LCH15JAB.cpp
#include <bits/stdc++.h>
using namespace std;
int main(){
	ios::sync_with_stdio(false);
	int T;
	cin >> T;
	while(T--){
		string s;
		cin >> s;
		int f=0;
		if(s.size()%2) {
			cout << "NO" << endl;
			continue;
		}
		for(int i=0;i<26;++i){
			int cnt = 0;
			for(int j=0; j<s.size(); ++j)
				if(s[j]==i+'a') ++cnt;
			if(cnt == s.size()/2){
				cout << "YES" << endl;
				f=1;
				break;
			}
		}
		if(!f)
		cout << "NO" << endl;
	}
}
<file_sep>/ROTATION.cpp
#include <bits/stdc++.h>
#define NMAX 111111
using namespace std;
int A[NMAX];
int start,end;
int main(){
  int N,M;
  scanf("%d %d",&N, &M);
  start = 0;
  for(int i=0;i<N;++i) 
    scanf("%d",&A[i]);
  for(int i=0;i<M;++i){
    char buf[5];
    int x;
    scanf("%s %d",buf,&x);
    switch(buf[0]){
    case 'R' : printf( "%d\n", A[ ( start + x - 1 + N ) % N] );
      break;
    case 'C' : start = ( start + x ) % N;
      break;
    case 'A' : start = ( start - x + N ) % N;
      break;
    }
    //cout << start << "-- " << endl;
  }
  return 0;
}
<file_sep>/CAOS1.cpp
#include <cstdio>
#include <iostream>
using namespace std;
const int MAX=51;
char array[MAX][MAX];
int R,C;
void print()
{
	for(int i=0;i<R;++i)
		for(int j=0;j<C;++j)
			printf("\n%d,%d : %c",i,j,array[i][j]);
}
int find(int x,int y)
{
	int i,j;
	int up,down,left,right;
	up=down=left=right=0;
	i=x-1;
	while(i>=0)
	{
		if(array[i][y]=='#') break;
		++up;
		--i;
	}
	i=x+1;
	while(i<R)
	{
		if(array[i][y]=='#') break;
		++down;
		++i;
	}
	j=y-1;
	while(j>=0)
	{
		if(array[x][j]=='#') break;
		++left;
		--j;
	}
	j=y+1;
	while(j<C)
	{
		if(array[x][j]=='#') break;
		++right;
		++j;
	}
	return min(left,min(right,min(up,down)));
}
int solve()
{
	int count=0;
	for(int i=0;i<R;++i)
		for(int j=0;j<C;++j)
			if(array[i][j]=='^' && find(i,j)>=2) ++count;
	return count;
}
int main()
{
	int T;
	scanf("%d",&T);
	while(T>0)
	{
		scanf("%d %d",&R,&C);
		for(int i=0;i<R;++i)
			scanf("%s",array[i]);
		printf("%d\n",solve());
		--T;
	}
	return 0;
}
<file_sep>/CHEFRRUN.cpp
#include <bits/stdc++.h>
#define NMAX 111111
using namespace std;
vector<int> adj[NMAX];
stack<int> connectedVertices;
int disc[NMAX],low[NMAX],onstack[NMAX];
int result = 0;
int cdisc = 1;
void dfs( int u ){
  disc[u] = cdisc;
  low[u] = cdisc++;
  onstack[u] = 1;
  connectedVertices.push( u );
  for(int i=0;i<adj[u].size();++i){
    int v = adj[u][i];
    if( !disc[v] ){
      dfs( v );
      low[u] = min( low[u], low[v] );
    }
    else if( onstack[v] ){
      low[u] = min( low[u], disc[v] );
    }
  }
  if( disc[u] == low[u] ){
    if( connectedVertices.top() != u ) result++;
    while( connectedVertices.top() != u ){
      result++;
      onstack[ connectedVertices.top() ] = 0;
      connectedVertices.pop();
    }
    onstack[ connectedVertices.top() ]=0;
    connectedVertices.pop();
  }
}
int main(){
  ios::sync_with_stdio( false );
  int T;
  cin >> T;
  while( T-- ){
    int N;
    cin >> N;
    vector<int> A(N);
    for(int i=0;i<N;++i) cin >> A[i];
    
    connectedVertices = stack<int>();
    result = 0;
    cdisc = 0;
    for(int i=1;i<=N;++i) disc[i]=low[i]=onstack[i]=0, adj[i].clear();
    for(int i=0;i<N;++i){
      int nxt = ((i+A[i]+1)%N);
      if( nxt == i ) ++result;
      else adj[i+1].push_back( nxt + 1 );
    }
    for(int i=1;i<=N;++i){
      if( !disc[i] ) 
	dfs( i );
    }
    
    cout << result << endl;
  }
  return 0;
}
<file_sep>/IOPC1207.cpp
// author noob333
// H + Shift C + B + E + B + E
#include <bits/stdc++.h>
#define NMAX 100011
//#define DEBUG 1
using namespace std;
// Input macros
#define s(n)                        scanf("%d",&n)
#define sc(n)                       scanf("%c",&n)
#define sl(n)                       scanf("%lld",&n)
#define sf(n)                       scanf("%lf",&n)
#define ss(n)                       scanf("%s",n)
// Useful constants
#define INF                         (int)1e9
#define EPS                         1e-9
#define DINF                        2.0e7
// Useful hardware instructions
#define bitcount                    __builtin_popcount
#define gcd                         __gcd
// Useful container manipulation / traversal macros
#define REP(i,a,b)                  for(int i=a;i<b;i++)
#define RREP(i,a,b)                 for(int i=a;i>b;i--)
#define foreach(v, c)               for( typeof( (c).begin()) v = (c).begin();  v != (c).end(); ++v)
#define all(a)                      a.begin(), a.end()
#define in(a,b)                     ( (b).find(a) != (b).end())
#define pb                          push_back
#define fill(a,v)                    memset(a, v, sizeof a)
#define sz(a)                       ((int)(a.size()))
#define mp                          make_pair
#define fi                          first
#define se                          second
#define L(x)						(x<<1)
#define R(x)						((x<<1)+1)
// Some common useful functions
#define sq(a)                        ( (a)*(a) )
#define maX(a,b)                     ( (a) > (b) ? (a) : (b))
#define miN(a,b)                     ( (a) < (b) ? (a) : (b))
#define checkbit(n,b)                ( (n >> b) & 1)
#define setbit(n,b)                  ( n |= (1<<b) )
#define unsetbit(n,b)                ( n &= ~(1<<b) )
#define DREP(a)                      sort(all(a)); a.erase(unique(all(a)),a.end())
#define INDEX(arr,ind)               (lower_bound(all(arr),ind)-arr.begin())
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef set<int> si;
typedef map<string, int> msi;
#ifdef DEBUG
     #define debug(args...)            {dbg,args; cerr<<endl;}
#else
    #define debug(args...)              // Just strip off all debug tokens
#endif
struct debugger
{
    template<typename T> debugger& operator , (const T& v)
    {
        cerr<<v<<" ";
        return *this;
    }
} dbg;
template <typename T1, typename T2>
    inline std::ostream& operator << (std::ostream& os, const std::pair<T1, T2>& p)
    {
        return os << "(" << p.first << ", " << p.second << ")";
    }
    template<typename T>
    inline std::ostream &operator << (std::ostream & os,const std::vector<T>& v)
    {
        bool first = true;
        os << "[";
        for(unsigned int i = 0; i < v.size(); i++)
        {
            if(!first)
                os << ", ";
            os << v[i];
            first = false;
        }
        return os << "]";
    }
    template<typename T>
    inline std::ostream &operator << (std::ostream & os,const std::set<T>& v)
    {
        bool first = true;
        os << "[";
        for (typename std::set<T>::const_iterator ii = v.begin(); ii != v.end(); ++ii)
        {
            if(!first)
                os << ", ";
            os << *ii;
            first = false;
        }
        return os << "]";
    }
    template<typename T1, typename T2>
    inline std::ostream &operator << (std::ostream & os,const std::map<T1, T2>& v)
    {
        bool first = true;
        os << "[";
        for (typename std::map<T1, T2>::const_iterator ii = v.begin(); ii != v.end(); ++ii)
        {
            if(!first)
                os << ", ";
            os << *ii ;
            first = false;
        }
        return os << "]";
    }
    inline void inp(int &n) {
    	n = 0;
    	int ch = getchar();
    	int sign = 1;
    	while (ch < '0' || ch > '9') {
    		if (ch == '-') sign = -1;
    		ch = getchar();
    	}
    	while (ch >= '0' && ch <= '9')
    		n = (n << 3) + (n << 1) + ch - '0', ch = getchar();
    	n = n*sign;
    }
struct segNode{
	int lazy;
	int sum,len;
	segNode(int a=0,int b=0,int c=0){
		lazy=a;
		sum=b; len=c;
	}
};
struct segTree{
	segNode tree[NMAX<<2];
	void modify(int index,int val){
		if(val%2) tree[index].sum = tree[index].len-tree[index].sum;
		tree[index].lazy += val;
	}
	void push(int index,int i,int j){
		if(i!=j){
			if(tree[index].lazy){
				modify(L(index),tree[index].lazy);
				modify(R(index),tree[index].lazy);
				tree[index].lazy=0;
			}
		}
	}
	void build(int index,int i,int j){
		tree[index]=segNode(0,0,j-i+1);
		if(i==j) return;
		int mid=(i+j)>>1;
		build(L(index),i,mid);
		build(R(index),mid+1,j);
	}
	void update(int index,int i,int j,int st,int en){
		if(i==st && j==en){
			modify(index,1);
			return;
		}
		push(index,i,j);
		int mid = (i+j)>>1;
		if(en<=mid) update(L(index),i,mid,st,en);
		else if(st>mid) update(R(index),mid+1,j,st,en);
		else{
			update(L(index),i,mid,st,mid);
			update(R(index),mid+1,j,mid+1,en);
		}
		tree[index].sum = tree[L(index)].sum + tree[R(index)].sum;
	}
	int query(int index,int i,int j,int st,int en){
		if(i==st && j==en)	return tree[index].sum;
		push(index,i,j);
		int mid = (i+j)>>1;
		int x1,x2;
		x1=x2=0;
		if(en<=mid) x1=query(L(index),i,mid,st,en);
		else if(st>mid) x2=query(R(index),mid+1,j,st,en);
		else{
			x1=query(L(index),i,mid,st,mid);
			x2=query(R(index),mid+1,j,mid+1,en);
		}
		//tree[index].sum = tree[L(index)].sum + tree[R(index)].sum;
		return x1+x2;
	}
	void printTree(int index,int i,int j){
		if(i==j){
			printf("%d,%d - %d %d %d\n",i,j,tree[index].lazy,tree[index].sum,tree[index].len);
			return;
		}
		int mid=(i+j)>>1;
		printTree(L(index),i,mid);
		printTree(R(index),mid+1,j);
		printf("%d,%d - %d %d %d\n",i,j,tree[index].lazy,tree[index].sum,tree[index].len);
	}
}segTrees[3];
int N[3];
void init(){
	REP(i,0,3){
		//fill(segTrees[i].tree,0);
		segTrees[i].build(1,0,N[i]-1);
	}
}
void change(int ind,int u,int v){
	segTrees[ind].update(1,0,N[ind]-1,u,v);
	//segTrees[ind].printTree(1,0,N[ind]-1);
	//cout << endl;
}
ll ask(int x1,int y1,int z1,int x2,int y2,int z2){
	ll r1=segTrees[0].query(1,0,N[0]-1,x1,x2);
	ll r2=segTrees[1].query(1,0,N[1]-1,y1,y2);
	ll r3=segTrees[2].query(1,0,N[2]-1,z1,z2);
	ll g1=(x2-x1+1)-r1;
	ll g2=(y2-y1+1)-r2;
	ll g3=(z2-z1+1)-r3;
	//debug(r1,g1,r2,g2,r3,g3);
	return (r1*r2*r3+r1*g2*g3+g1*r2*g3+g1*g2*r3);
}
void solve(){
	int x1,x2,y1,y2,z1,z2;
	int Q;
	REP(i,0,3)
		inp(N[i]);
	init();
	inp(Q);
	REP(i,0,Q){
		int ty;
		inp(ty);
		if(ty==3){
			inp(x1); inp(y1); inp(z1);
			inp(x2); inp(y2); inp(z2);
			printf("%lld\n",ask(x1,y1,z1,x2,y2,z2));
		}
		else{
			inp(x1); inp(x2);
			change(ty,x1,x2);
		}
	}
}
int main(){
	//freopen("1.in","r",stdin);
	int T;
	inp(T);
	while(T--){
		solve();
	}
	//fclose(stdin);
	return 0;
}
<file_sep>/FORGETPW.cpp
#include <bits/stdc++.h>
#define NMAX 1111111
#define RMAX 256
using namespace std;
char rule[RMAX],input[NMAX],output[NMAX];
inline void init(){
  for(int i=0;i<RMAX;++i) rule[i]=i;
}
int main(){
  int T;
  scanf("%d",&T);
  while(T--){
    init();
    int rules;
    
    scanf("%d\n",&rules);
    for(int i=0;i<rules;++i) {
      char str[5];
      gets(str);
      //printf("\n---RUle%s\n",str);
      rule[int(str[0])]=str[2];
    }
    scanf("%s",input);
    //printf("%d %s\n",T,input);
    int flag=0;
    int ptr=0;
    int len=strlen(input);
    int i;
    assert(len>0);
    for(i=0;i<len;++i) input[i]=rule[input[i]];
    for(i=0;i<len;++i){
      if(input[i]=='.') break;
      if(flag || input[i]!='0' ) flag=1,output[ptr++]=input[i];
    }
    flag=ptr;
    for(;i<len;++i){
      if(input[i]!='0') flag=ptr+1;
      output[ptr++]=input[i];
    }
    for(i=ptr-1;i>=flag;--i) output[i]='\0',--ptr;
    if(output[ptr-1]=='.') output[i]='\0',--ptr;
    if(ptr==0) output[0]='0',++ptr;
    output[ptr]='\0';
    
    printf("%s\n",output);
  }
  return 0;
}
<file_sep>/PRPOTION.cpp
#include <bits/stdc++.h>
#define inf 1000000011
using namespace std;
int main(){
  int t;
  scanf("%d",&t);
  while(t--){
    int maxR,maxG,maxB,res;
    int R,G,B,M,tmp;
    maxR=maxG=maxB=0;
    scanf("%d %d %d %d",&R,&G,&B,&M);
    for(int i=0;i<R;++i){
      scanf("%d",&tmp);
      maxR=max(maxR,tmp);
    }
    for(int i=0;i<G;++i){
      scanf("%d",&tmp);
      maxG=max(maxG,tmp);
    }
    for(int i=0;i<B;++i){
      scanf("%d",&tmp);
      maxB=max(maxB,tmp);
    }
    res=max(maxR,max(maxB,maxG));
    for(int i=0;i<M;++i){
      if(maxR>=maxG && maxR>=maxB){
    	  maxR/=2;
      }
      else if(maxG>=maxR && maxG>=maxB){
    	  maxG/=2;
      }
      else{
    	  maxB/=2;
      }
      res = min(res,max(maxR,max(maxG,maxB)));
    }
    printf("%d\n",res);
  }
  return 0;
}
<file_sep>/CHEFCBA.cpp
#include <bits/stdc++.h>
using namespace std;
int main(){
	ios::sync_with_stdio( false );
	int a[4], flag = 0;
	for(int i=0;i<4;++i) cin >> a[i];
	
	sort(a, a+3);
	do {
    	double x = ((double)a[0])/a[1];
    	double y = ((double)a[2])/a[3];
    	if( x == y ){
    		flag = 1;
    		break;
    	}
    	
    }while ( next_permutation(a,a+3) );
    
    if(flag) cout << "Possible";
    else cout << "Impossible";
    
	return 0;
}
<file_sep>/COLOR.cpp
#include <bits/stdc++.h>
#define NMAX 111111
using namespace std;
int main(){
  ios::sync_with_stdio(false);
  int T;
  cin >> T;
  string rgb( "RGB" );
  while( T-- ){
    int N;
    cin >> N;
    string s;
    cin >> s;
    int minCost = NMAX;
    for(int i=0;i<3;++i){
      int cost = 0;
      for(int j=0;j<s.size();++j){
        if( s[j] != rgb[i] ) ++cost;
      }
      minCost = min( minCost, cost );
    }
    cout << minCost << endl;
  }
  return 0;
}
<file_sep>/QTREE6.cpp
#include <bits/stdc++.h>
#define NMAX 111111
#define L(x) ( x<<1 )
#define R(x) ( (x<<1 ) + 1)
#define pb push_back
#define sz size( )
#define CL(S,x) memset(S,x,sizeof(S))
#define FOR(i,x,y) for(i=x;i<=y;i++)
#define _FOR(i,x,y) for(i=x;i>=y;i--)
#define inf 999999999
using namespace std;
typedef long long int ll;
inline int read_int() {
  register char c = getchar_unlocked();
  while(c<'0' || c>'9') c = getchar_unlocked();
  int ret = 0;
  while(c>='0' && c<='9') {
    ret = (ret<<3)+(ret<<1) + c - 48;
    c = getchar_unlocked();
  }
  return ret;
}
struct node{
  int col;
  int pos[2];
};
struct node2{
  ll lazy[2];
  ll sum[2];
};
vector<int> adjList[NMAX];
int subtree[NMAX], parent[NMAX], color[NMAX];
int n1, Q;
struct hlChain{
  vector<node> tree;
  vector<node2> tree2;
  vector<int> subt,inp;
  int N, col;
  ll val;
  hlChain( vector<int> input ){
    N = input.sz;
    inp = input;
    subt = vector<int>(N+1);
    for(int i=0;i<N;++i) subt[i] = subtree[input[i]]; 
    tree = vector<node>(N<<2);
    tree2 = vector<node2>(N<<2);
    init(1,0,N-1);
    init2(1,0,N-1);
  }
  node merge(node x,node y,int mid){
    node z;
    z.col=0;
    z.pos[0] = (y.pos[0]==(mid+1))?min(mid+1,x.pos[0]):y.pos[0];
    z.pos[1] = (y.pos[1]==(mid+1))?min(mid+1,x.pos[1]):y.pos[1];
    return z;
  }
  void init(int idx,int i,int j){
    if(i==j) {
      tree[idx].col=0;
      tree[idx].pos[0]=i;
      tree[idx].pos[1]=inf;
      return;
    }
    int mid=(i+j)>>1;
    
    init(L(idx),i,mid);
    init(R(idx),mid+1,j);
  
    tree[idx] = merge( tree[L(idx)], tree[R(idx)], mid );
  }
  
  void update(int idx,int i,int j,int pt,int val){
    if(i==j && i==pt){
    tree[idx].col = val;
    tree[idx].pos[val]=i;
    tree[idx].pos[1^val]=inf;
    return;
    }
    int mid=(i+j)>>1;
    
    if(pt<=mid) update(L(idx),i,mid,pt,val);
    else update(R(idx),mid+1,j,pt,val);
    tree[idx] = merge( tree[L(idx)], tree[R(idx)], mid );
  }
  
  node query(int idx,int i,int j,int left,int right){
    if(i==left && j==right) return tree[idx];
    int mid=(i+j)>>1;
    
    if(right<=mid) return query(L(idx),i,mid,left,right);
    else if(left>mid) return query(R(idx),mid+1,j,left,right);
    else{
      node res1 = query(L(idx),i,mid,left,mid);
      node res2 = query(R(idx),mid+1,j,mid+1,right);
      return merge( res1, res2, mid);
    }
  }
  
  void propagate( int idx,int i,int j ){
    tree2[idx].sum[0] += (tree2[idx].lazy[0]*(j-i+1));
    tree2[idx].sum[1] += (tree2[idx].lazy[1]*(j-i+1));
    if(i!=j){
      tree2[L(idx)].lazy[0] += tree2[idx].lazy[0];
      tree2[L(idx)].lazy[1] += tree2[idx].lazy[1];
      tree2[R(idx)].lazy[0] += tree2[idx].lazy[0];
      tree2[R(idx)].lazy[1] += tree2[idx].lazy[1];
    }
    tree2[idx].lazy[0]=tree2[idx].lazy[1]=0;
  }
  void init2( int idx,int i,int j ){
    if(i==j) {
      tree2[idx].sum[0]=(ll)subt[i] - 1;
      tree2[idx].lazy[0]=tree2[idx].lazy[1]=tree2[idx].sum[1]=0;
      return;
    }
    int mid=(i+j)>>1;
    init2(L(idx),i,mid);
    init2(R(idx),mid+1,j);
    tree2[idx].sum[0]=tree2[L(idx)].sum[0] + tree2[R(idx)].sum[0];
    tree2[idx].sum[1]=tree2[L(idx)].sum[1] + tree2[R(idx)].sum[1];
    tree2[idx].lazy[0]=tree2[idx].lazy[1]=0;
  }
  
  void update2(int idx,int i,int j,int left,int right){
    propagate(idx,i,j);
    if( left<=i && j<=right ){
      tree2[idx].sum[col] += ( val * (j-i+1));
      if(i!=j){
	tree2[L(idx)].lazy[col] += val;
	tree2[R(idx)].lazy[col] += val;
      }
      return;
    }
    if(left>j || right<i) return;
    
    int mid= (i+j)>>1;
    update2(L(idx),i,mid,left,right);
    update2(R(idx),mid+1,j,left,right);
    
    tree2[idx].sum[0]=tree2[L(idx)].sum[0] + tree2[R(idx)].sum[0];
    tree2[idx].sum[1]=tree2[L(idx)].sum[1] + tree2[R(idx)].sum[1];
  }
  
  ll query2(int idx,int i,int j,int left,int right){
    propagate(idx,i,j);
    if( left<=i && j<=right ) return tree2[idx].sum[col];
    if(left>j || right<i) return 0;
    
    int mid= (i+j)>>1;
    ll res1 = query2(L(idx),i,mid,left,right);
    ll res2 = query2(R(idx),mid+1,j,left,right);
    
    tree2[idx].sum[0]=tree2[L(idx)].sum[0] + tree2[R(idx)].sum[0];
    tree2[idx].sum[1]=tree2[L(idx)].sum[1] + tree2[R(idx)].sum[1];
    return res1 + res2;
  }
  void printTree( int idx,int i,int j){
    if(i==j){
      cout<<i<<","<<j<<" "<<tree[idx].pos[0]<<" "<<tree[idx].pos[1]<<endl;
      return;
    }
    int mid=(i+j)>>1;
    printTree(L(idx),i,mid);
    printTree(R(idx),mid+1,j);
    cout<<i<<","<<j<<" "<<tree[idx].pos[0]<<" "<<tree[idx].pos[1]<<endl;
  }
  void printTree2( int idx,int i,int j){
    if(i==j){
      cout<<i<<","<<j<<" "<<tree2[idx].sum[0]<<" "<<tree2[idx].sum[1]<<"-->"<<tree2[idx].lazy[0]<<" "<<tree2[idx].lazy[1]<<endl;
      return;
    }
    int mid=(i+j)>>1;
    printTree2(L(idx),i,mid);
    printTree2(R(idx),mid+1,j);
    cout<<i<<","<<j<<" "<<tree2[idx].sum[0]<<" "<<tree2[idx].sum[1]<<"-->"<<tree2[idx].lazy[0]<<" "<<tree2[idx].lazy[1]<<endl;
  }
  node query(int left,int right){
    return query(1,0,N-1,left,right);
  }
  ll query2(int left,int right,int col_){
    col= col_;
    return query2(1,0,N-1,left,right);
  }
  void update(int point,int value){
    update(1,0,N-1,point,value);
  }
  
  void update2(int left,int right,int col_,ll val_){
    col=col_;
    val=val_;
    update2(1,0,N-1,left,right);
  }
};
vector<hlChain> chains;
vector< vector<int> > chainVal;
int chainPos[NMAX], chainId[NMAX], chainHead[NMAX];
int cnum;
int dfs( int u,int p ){
  subtree[u] = 1;
  parent[u] = p;
  color[u]=0;
  for(int i=0;i<adjList[u].sz;++i){
    int v=adjList[u][i];
    if( v!=p ) subtree[u] += dfs(v,u);
  }
  return subtree[u];
}
void hld(int u,int p){
  chainVal[cnum].pb(u);
  chainPos[u] = chainVal[cnum].sz-1;
  chainId[u] = cnum;
  if( chainPos[u] == 0 ) chainHead[cnum] = u;
  
  int most,idx;
  most = idx =-1;
  for(int i=0;i<adjList[u].sz;++i){
    int v=adjList[u][i];
    if( v!=p && subtree[v] > most ) most=subtree[v], idx=v;
  } 
  if( idx != -1 ) hld(idx,u);
  for(int i=0;i<adjList[u].sz;++i){
    int v=adjList[u][i];
    if( v!=p && v!=idx){
      ++cnum;
      chainVal.pb(vector<int>(0));
      hld(v,u);
    }
  }
}
int lowestWithSameCol( int u ){
  int x = u;
  int col = color[u];
  int pos = chainPos[u];
  int idx = chainId[u];
  node low;  
  while(1){
    low = chains[idx].query(0,pos);
    if(low.pos[col]!=0) return chains[idx].inp[low.pos[col]];
    x = parent[chainHead[idx]];
    if(x==-1 || color[x]!=col) return chainHead[idx];
    pos = chainPos[x];
    idx = chainId[x];
  }
}
ll ask( int u ){
  int top = lowestWithSameCol(u);
  int idx = chainId[top];
  int pos = chainPos[top];
  return chains[idx].query2(pos,pos,color[u]) + 1;
}
ll change1( int u ){
  int x = u;
  int oldCol = color[u];
  int newCol = 1^oldCol;
  int pos = chainPos[u];
  int idx = chainId[u];
  ll sub,add;
  node low;
  sub = -( chains[idx].query2(pos,pos,oldCol) + 1);
  add = chains[idx].query2(pos,pos,newCol)+1;
  x = parent[u];  
  if( x!=-1 && color[x] == oldCol ){
    pos = chainPos[x];
    idx = chainId[x];
    while( 1 ){
      low = chains[idx].query(0,pos);    
      chains[idx].update2(low.pos[oldCol],pos,oldCol,sub);
      if( low.pos[oldCol] !=0 ){
	x = chains[idx].inp[low.pos[oldCol]-1];
	idx = chainId[x], pos = chainPos[x];
	break;
      }
      x = parent[chainHead[idx]];
      if(x==-1) break;
      idx = chainId[x], pos = chainPos[x];     
      if(color[x]!=oldCol) break;
    }
  }
  if( x!=-1 ){
    pos = chainPos[x],idx=chainId[x];
    chains[idx].update2(pos,pos,oldCol,sub);
  }
  pos=chainPos[u], idx=chainId[u];
  //cout<< newCol << " ---< " <<endl;
  color[u] = 1^color[u];
  chains[idx].update( pos,newCol );
  //x = u;
  
  x = parent[u];  
  if( x!=-1 && color[x] == newCol ){
    pos = chainPos[x];
    idx = chainId[x];
    while( 1 ){      
      low = chains[idx].query(0,pos);    
      chains[idx].update2(low.pos[newCol],pos,newCol,add);
      if( low.pos[newCol] !=0 ){
	x = chains[idx].inp[low.pos[newCol]-1];
	idx = chainId[x], pos = chainPos[x];
	break;
      }
      x = parent[chainHead[idx]];
      if(x==-1) break;
      idx = chainId[x], pos = chainPos[x];     
      if(color[x]!=newCol) break;
    }
  }
  if( x!=-1 ){
    pos = chainPos[x], idx = chainId[x];
    chains[idx].update2(pos,pos,newCol,add);
  }
}  
void solve(){  
  cnum = 0;
  chainVal.pb(vector<int>(0));
  dfs(1,-1);
  hld(1,-1);
  for(int i=0;i<=cnum;++i){
    //for(int j=0;j<chainVal[i].sz;++j)
    // cout<<chainVal[i][j]<<" ";
    //cout<< endl;
    hlChain x(chainVal[i]);
    chains.pb(x);
  }
  
  Q = read_int();
  //scanf("%d",&Q);
  for(int i=0;i<Q;++i){
    int type,u;
    type =read_int();
    u = read_int();
    //scanf("%d %d",&type,&u);
    if(type == 0) {
      printf("%lld\n",ask(u));
    }
    else{
      change1(u);            
      //                  cout<<"---><>"<<endl;
      //                  chains[chainId[u]].printTree2(1,0,chains[chainId[u]].N-1);
    }
  }
  
}
int main(){
  n1 = read_int();
  for(int i=0;i<n1-1;++i){
    int u,v;
    u = read_int();
    v = read_int();
    adjList[u].pb(v);
    adjList[v].pb(u);
  }
  
  solve();
  return 0;
}
<file_sep>/FCBARCA.cpp
#include <stdio.h>
#include <vector>
#include <algorithm>
#define MOD 1000000007
using namespace std;
typedef long long int x64;
x64 array[1001][11];
void initialize()
{
	x64 runSq;
	for(int k=1;k<=10;++k)
		array[1][k]=k;
	for(int i=1;i<=10;++i)
	{
		runSq=i*i;
		for(int n=2;n<=1000;++n)
		{
			array[n][i]=(runSq-array[n-1][i])%MOD;
			if(array[n][i]<0)
				array[n][i]+=MOD;
			runSq=runSq*i%MOD;
		}
	}
}
int main()
{
	initialize();
	int T,N,K;
	scanf("%d",&T);
	while(T>0)
	{
		scanf("%d %d",&N,&K);
		printf("%lld\n",array[N-1][K]);
		--T;
	}
	return 0;
}
<file_sep>/ADIGIT.cpp
#include <bits/stdc++.h>
#define DIGITS 10
#define NMAX 111111
using namespace std;
int counter[DIGITS];
int dp[NMAX];
int main(){
	memset(counter,0,sizeof(counter));
	int N,M;
	scanf("%d %d\n",&N,&M);
	for(int i=0;i<N;++i){
		int a,res=0;
		char x;
		scanf("%c",&x);		
		a=x-'0';
		for(int j=0;j<DIGITS;++j) 
			res=res+(counter[j]*abs(a-j));
		dp[i]=res;
		counter[a]++;
	}
	for(int i=0;i<M;++i){
		int x;
		scanf("%d",&x);
		printf("%d\n",dp[x-1]);
	}
}
<file_sep>/PRIME1.cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll mulmod(ll a, ll b, ll mod)
{
    ll x = 0,y = a % mod;
    while (b > 0)
    {
        if (b % 2 == 1)
        {    
            x = (x + y) % mod;
        }
        y = (y * 2) % mod;
        b /= 2;
    }
    return x % mod;
}
ll modulo(ll base, ll exponent, ll mod)
{
    ll x = 1;
    ll y = base;
    while (exponent > 0)
    {
        if (exponent % 2 == 1)
            x = (x * y) % mod;
        y = (y * y) % mod;
        exponent = exponent / 2;
    }
    return x % mod;
}
 
/*
 * Miller-Rabin primality test, iteration signifies the accuracy
 */
bool Miller(ll p,int iteration)
{
    if (p < 2)
    {
        return false;
    }
    if (p != 2 && p % 2==0)
    {
        return false;
    }
    ll s = p - 1;
    while (s % 2 == 0)
    {
        s /= 2;
    }
    for (int i = 0; i < iteration; i++)
    {
        ll a = rand() % (p - 1) + 1, temp = s;
        ll mod = modulo(a, temp, p);
        while (temp != p - 1 && mod != 1 && mod != p - 1)
        {
            mod = mulmod(mod, mod, p);
            temp *= 2;
        }
        if (mod != p - 1 && temp % 2 == 0)
        {
            return false;
        }
    }
    return true;
}
inline ll ReadNext(){
register ll c = getchar();
ll x = 0;
for(;(c<48 || c>57);c = getchar());
for(;c>47 && c<58;c = getchar()) {x = (x<<1) + (x<<3) + c - 48;}
return x;
}
int main(){
  int T;
  //scanf("%d",&T);
  T=ReadNext();
  while(T--){
    ll m,n;
    //scanf("%lld %lld",&m,&n);
    m=ReadNext();
    n=ReadNext();
    for(ll k=m;k<=n;++k)
      if(Miller(k,10))
	printf("%lld\n",k);
    if(T) printf("\n");
  }
  
  return 0;
}
<file_sep>/WSTRING.cpp
#include <cstdio>
#include <cstring>
#include <vector>
#define REP26(i)	for(i=0;i<26;++i)
using namespace std;
const int MAX=10005;
struct seg
{
	vector<int> count;
	vector<int> cumFreq;
	int max;
	int cumMax;
};
vector<seg> segments;
void solve()
{
	vector<seg>::iterator itr;
	int prefix,suffix,best,k,total;
	if(segments.begin()!=segments.end())
	{
		REP26(k)
				segments[0].cumFreq[k]=segments[0].count[k];
		segments[0].cumMax=segments[0].max;
	}
	for(int k=0;k<segments.size();++k)
	{
		int i;
		if(k+1==segments.size())
			break;
		REP26(i)
		{
			segments[k+1].cumFreq[i]=segments[k].cumFreq[i]+segments[k+1].count[i];
			segments[k+1].cumMax=max(segments[k+1].cumMax,segments[k+1].cumFreq[i]);
		}
	}
	total=segments.size()-1;
	best=0;
	for(int i=0;i<segments.size();++i)
	{
		suffix=0;
		if(i+1>=segments.size()||i+2>=segments.size()||i+3>=segments.size())
			break;
		prefix=segments[i].cumMax;
		int j;
		REP26(j)
			suffix=max(suffix,segments[total].cumFreq[j]-segments[i+2].cumFreq[j]);
		if(!(prefix&&suffix&&segments[i+1].max&&segments[i+2].max))
			continue;
		best=max(best,prefix+segments[i+1].max+segments[i+2].max+suffix);
	}
	if(best)
		printf("%d\n",best+3);
	else
		printf("%d\n",0);
}
void printSeg()
{
	for(int i=0;i<segments.size();++i)
	{
		int j;
		printf("\n\n");
		REP26(j)
			printf(" %d",segments[i].count[j]);
		printf("\n");
		REP26(j)
			printf(" %d",segments[i].cumFreq[j]);
		printf("\n %d %d",segments[i].max,segments[i].cumMax);
	}
}
int main()
{
	seg dummy;
	dummy.cumFreq=vector<int>(26,0);
	dummy.count=vector<int>(26,0);
	dummy.cumMax=dummy.max=0;
	int T;
	scanf("%d",&T);
	while(T>0)
	{
		char str[MAX];
		int len,k;
		scanf("%s",str);
		len=strlen(str);
		segments.clear();
		segments.push_back(dummy);
		k=0;
		for(int i=0;i<len;++i)
		{
			if(str[i]=='#')
			{
				{
					++k;
					segments.push_back(dummy);
				}
			}
			else
			{
				++segments[k].count[str[i]-'a'];
				segments[k].max=max(segments[k].max,segments[k].count[str[i]-'a']);
			}
		}
		solve();
		--T;
	}
	return 0;
}
<file_sep>/CHEFBM.cpp
#include <bits/stdc++.h>
#define NMAX 111111
using namespace std;
typedef long long int LL;
typedef pair<LL,LL> pii;
vector<LL> modify[NMAX];
void solve1();
int main(){
/*	LL N,M,P;
	scanf("%lld %lld %lld",&N,&M,&P);
	for(LL i=0;i<P;++i){
		LL u,v;
		scanf("%lld %lld",&u,&v);
		modify[u].push_back(v);
	}
	for(LL i=1;i<=N;++i){
		if(M==1){
			printf("%lld\n",M+LL(modify[i].size()));
			continue;
		}
		else if(modify[i].size()==0){
			printf("%lld\n",M-1);
			continue;
		}
		else{
			LL flag=0;
			vector<pii> cnt;
			LL res=M-1;
			cnt.push_back(pii(-1,0));
			sort(modify[i].begin(),modify[i].end());
			LL sz=modify[i].size();
			LL ctr=0;
			modify[i].push_back(-1);
			for(LL j=0;j<sz;++j){
				++ctr;
				if(modify[i][j]!=modify[i][j+1]){
					cnt.push_back(pii(modify[i][j],ctr));
					ctr=0;
				}
			}
			cnt.push_back(pii(M+1,0));
			//for(int j=0;j<cnt.size();++j) printf("%lld,%lld ",cnt[j].first,cnt[j].second);
			//printf("\n");
			for(LL j=1;j<cnt.size()-1;++j){
				if(cnt[j-1].first+1!=cnt[j].first){
					if(cnt[j].first!=1) res+=cnt[j].second;
				}
				if(cnt[j].first==M){
					continue;
				}
				LL next=(cnt[j].first+1==cnt[j+1].first)?cnt[j+1].second:0;
				if(cnt[j].second>next+1){
					flag=1;
					break;
				}
				else res=res+(next-cnt[j].second);
			}
			if(flag) res=-1;
			printf("%lld\n",res);
		}
	}
*/
	solve1();
	return 0;
}
void solve1(){
	LL N,M,P;
		scanf("%lld %lld %lld",&N,&M,&P);
		for(LL i=0;i<P;++i){
			LL u,v;
			scanf("%lld %lld",&u,&v);
			modify[u].push_back(v);
		}
		for(LL i=1;i<=N;++i){
			if(M==1){
				printf("%d\n",0);
				continue;
			}
			else if(modify[i].size()==0){
				printf("%lld\n",M-1);
				continue;
			}
			else{
				LL flag=0;
				vector<pii> cnt;
				LL res=M-1;
				cnt.push_back(pii(-1,0));
				sort(modify[i].begin(),modify[i].end());
				LL sz=modify[i].size();
				LL ctr=0;
				modify[i].push_back(-1);
				for(LL j=0;j<sz;++j){
					++ctr;
					if(modify[i][j]!=modify[i][j+1]){
						cnt.push_back(pii(modify[i][j],ctr));
						ctr=0;
					}
				}
				cnt.push_back(pii(M+1,0));
				//for(int j=0;j<cnt.size();++j) printf("%lld,%lld ",cnt[j].first,cnt[j].second);
				//printf("\n");
				for(LL j=1;j<cnt.size()-1;++j){
					if(cnt[j-1].first+1!=cnt[j].first){
						if(cnt[j].first!=1) res+=cnt[j].second;
					}
					if(cnt[j].first==M){
						continue;
					}
					LL next=(cnt[j].first+1==cnt[j+1].first)?cnt[j+1].second:0;
					if(cnt[j].second>next+1){
						flag=1;
						break;
					}
					else res=res+(next-cnt[j].second);
				}
				if(flag) res=-1;
				printf("%lld\n",res);
			}
		}
}
<file_sep>/DIVQUERY.cpp
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <iostream>
#define NMAX 111111
using namespace std;
int tree[NMAX],input[NMAX],res[NMAX];
int N,Q;
struct Query{
	int pos,k;
	int index,count;
}qry[NMAX<<1];
void update(int idx,int val){
	for(int i=idx;i<NMAX;i+=(i&-i))
		tree[i]+=val;
}
int read(int idx){
	int sum=0;
	for(int i=idx;i>0;i-=(i&-i))
		sum+=tree[i];
	return sum;
}
bool comp(const Query &x,const Query &y){
	if(x.pos<y.pos) return true;
	return false;
}
int main(){
	scanf("%d %d",&N,&Q);
	input[0]=0;
	for(int i=1;i<=N;++i) scanf("%d",&input[i]);
	for(int i=0;i<(Q<<1);++i) {
		scanf("%d %d %d",&qry[i].pos,&qry[i+1].pos,&qry[i].k);
		qry[i].index=i/2;
		qry[i+1].index=i/2;
		qry[i+1].k=qry[i].k;
		--qry[i].pos;
		++i;
	}
	sort(qry,qry+(Q<<1),comp);
	//memset(tree,0,sizeof(tree));
	//memset(res,0,sizeof(res));
	int qptr=0;
	for(int i=0;i<=N;++i){
		for(int j=1;j*j<=input[i];++j)
			if(input[i]%j==0){
				++tree[j];
				if((input[i]!=j*j)) ++tree[input[i]/j]  ;
			}
		while( qptr<(Q<<1) && qry[qptr].pos==i ){
			res[qry[qptr].index]=tree[qry[qptr].k]-res[qry[qptr].index];
			++qptr;
		}
		if(qptr>=(Q<<1)) break;
	}
	for(int i=0;i<Q;++i) printf("%d\n",res[i]);
	return 0;
}
<file_sep>/APPROX.cpp
#include <stdio.h>
#define SIZE 1000002
char array[SIZE];
void compute(int N)
{
  int num=103993,rem=4687,div=33102;
  for(int i=0;i<N;++i)
 {
   rem=(rem*10);
   num=rem/div;
   array[i]=48+(num);
   rem=rem-(num*div);
 } 
}
int main()
{
  int T,N[2001],max=-1;
  
  scanf("%d",&T);
  
   for(int i=0;i<T;++i)
  {
    scanf("%d",&N[i]);
    if(N[i]>max)
     max=N[i];
  }
  
  compute(max);
  
   for(int i=0;i<T;++i)
  {
    if(N[i]==0)
     printf("3\n");
    else
    {
      char c=array[N[i]];
      array[N[i]]='\0';
      printf("3.%s \n",array);
      array[N[i]]=c;
    } 
  } 
  
  return 0;
}
<file_sep>/ALEXNUMB.cpp
#include <cstdio>
int main(){
	int T;
	scanf("%d",&T);
	while(T>0){
		long long int N,x;
		scanf("%lld",&N);
		for(int i=0;i<N;++i) scanf("%lld",&x);
		printf("%lld\n",(N*(N-1))>>1);
		--T;
	}
	return 0;
}
<file_sep>/SSS.cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long int LL;
LL pow(LL a, LL b, LL MOD) {
LL x = 1, y = a;
    while(b > 0) {
        if(b%2 == 1) {
            x=(x*y);
            if(x>MOD) x%=MOD;
        }
        y = (y*y);
        if(y>MOD) y%=MOD;
        b /= 2;
    }
    return x;
}
LL modInverse(LL a, LL m) {
    return pow(a,m-2,m);
}
int main(){
	LL T;
	scanf("%lld",&T);
	while(T--)	{
		LL n,p,res;
		scanf("%lld %lld",&n,&p);
		if(n>=p) res=0;
		else if(n==p-1) res=-1;
		else{
			res=1;
			for(int i=p-2;i>n;--i)	res=(res*modInverse(i,p)%p);
		}
		printf("%lld\n",res);
	}
	return 0;
}
<file_sep>/DIGITSEP.cpp
#include <bits/stdc++.h>
#define NMAX 300
#define MMAX 10
using namespace std;
typedef long long int ll;
int N,M,X,Y;
string s;
ll maxGcd;
ll _gcd(ll a, ll b) {
    return b == 0 ? a : _gcd(b, a % b);
}
void dfs(int idx, int m, int counter, ll currGcd){
  //cout << idx << " " << m << " " << endl;
  if(currGcd == 1) return;
  if(idx>=N){
    --counter;
    if(counter >= X && counter <= Y)
      maxGcd = max(maxGcd, currGcd);
    return;
  }
  if(counter>Y) return;
  ll currVal = 0;
  for(int i=0;i<m;++i){
    if(idx+i>=N) break;
    currVal *= 10;
    currVal += s[idx+i]-'0';
  }
  if(currGcd < 0) currGcd = currVal;
  else currGcd = _gcd(currGcd, currVal);
  if(currGcd == 1) return;
  for(int i=1;i<=M;++i){
    dfs(idx+m, i, counter+1, currGcd);
  }
}
void solve(){
  maxGcd = 1;
  for(int i=0;i<=M;++i)
    dfs(0,i,0,-1);
  cout << maxGcd << endl;
}
int main(){
  ios::sync_with_stdio(false);
  int T;
  cin >> T;
  while(T--){
    cin >> N;
    cin >> s;
    cin >> M >> X >> Y;
    solve();
  }
  return 0;
}
<file_sep>/PPTREE.cpp
// By noob.
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <climits>
#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <list>
#include <complex>
#pragma comment(linker, "/STACK:266777216")
using namespace std;
#define assert(f) { if(!(f)) { fprintf(stderr,"Assertion failed: "); fprintf(stderr,#f); fprintf(stderr,"\n"); exit(1); } }
typedef long long LL;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef pair<int,int> PII;
typedef vector<PII> VPII;
typedef vector<double> VD;
typedef pair<double,double> PDD;
const int inf=1000000000;
const LL INF=LL(inf)*inf;
const double eps=1e-9;
const double PI=2*acos(0.0);
#define bit(n) (1<<(n))
#define bit64(n) ((LL(1))<<(n))
#define pb push_back
#define sz size()
#define mp make_pair
#define cl clear()
#define all(a) (a).begin(),(a).end()
#define fill(ar,val) memset((ar),(val),sizeof (ar))
#define MIN(a,b) {if((a)>(b)) (a)=(b);}
#define MAX(a,b) {if((a)<(b)) (a)=(b);}
#define sqr(x) ((x)*(x))
#define X first
#define Y second
clock_t start=clock();
#define NMAX 111111
int N;
vector<VPII> Tree;
int cost[NMAX];
struct node{
	vector<node *>links;
	node(){
		links.resize(2,NULL);
	}
};
struct Trie{
	node *root;
	Trie(){
		root=new node();
	}
	void insert(int);
	int find(int);
};
void Trie::insert(int x){
	node *curr=root;
	//int lim=1;
	//while((lim<<1)<=x) lim=lim<<1;
	int lim=1<<30;
	for(;lim>0;lim=lim>>1){
		int d=(x&lim)==0?0:1;
		if(curr->links[d]==NULL)
			curr->links[d]=new node();
		curr=curr->links[d];
	}
}
int Trie::find(int x){
	node *curr=root;
	int lim=1<<30;
	int res=0;
	for(;lim>0;lim=lim>>1){
		int d=(x&lim)==0?0:1;
		if(curr->links[!d]!=NULL) res+=lim,curr=curr->links[!d];
		else curr=curr->links[d];
	}
	return res;
}
void dfs(int u,int p,int weight){
	cost[u]=cost[p]^weight;
	for(int i=0;i<Tree[u].size();++i){
		int v=Tree[u][i].X;
		if(v!=p){
			dfs(v,u,Tree[u][i].Y);
		}
	}
}
int main()
{
	int T;
	scanf("%d",&T);
	while(T>0){
		scanf("%d",&N);
		Tree.clear();
		Tree.resize(N+1,VPII(0));
		for(int i=0;i<N-1;++i){
			int u,v,w;
			scanf("%d %d %d",&u,&v,&w);
			Tree[u].pb(PII(v,w));
			Tree[v].pb(PII(u,w));
		}
		cost[1]=0;
		dfs(1,1,0);
		Trie *t=new Trie();
		for(int i=1;i<=N;++i){
			t->insert(cost[i]);
		}
		int best=INT_MIN;
		for(int i=1;i<=N;++i){
			best=max(best,t->find(cost[i]));
		}
		printf("%d\n",best);
		--T;
	}
	return 0;
}
<file_sep>/MAANDI.cpp
#include <cstdio>
#define gc getchar_unlocked
using namespace std;
void scanint(int &x)
{
    register int c = gc();
    x = 0;
    int neg = 0;
    for(;((c<48 || c>57) && c != '-');c = gc());
    if(c=='-') {neg=1;c=gc();}
    for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
    if(neg) x=-x;
}
int check(int num)
{
	int flag=0;
	while(num)
	{
		int rem=num%10;
		if(rem==4 || rem==7) {
			flag=1;
			break;
		}
		num=num/10;
	}
	return flag;
}
int overlucky(int x)
{
	int count=0;
	for(int i=1; i*i<=x; ++i)
	{
		int num=i;
		
		if(x%i==0){
			count+=check(i);
			if(i*i!=x)		count+=check(x/i);
		}
		
	}
	return count;
}
int main()
{
	int T;
	scanint(T);
	
	while(T>0)
	{
		int N;
		scanint(N);
		printf("%d\n",overlucky(N));		
		--T;
	}
	return 0;
}
<file_sep>/PRGIFT.cpp
#include <bits/stdc++.h>
using namespace std;
int main(){
	int T;
	scanf("%d",&T);
	for(int t=0;t<T;++t){
		int n,k;
		int evenCount=0;
		scanf("%d %d",&n,&k);
		for(int i=0;i<n;++i){
			int x;
			scanf("%d",&x);
			if(x%2==0) ++evenCount;
		}
		if(evenCount==n && k==0) printf("NO");
		else if(k<=evenCount) printf("YES");
		else printf("NO");
		if(t<T-1) printf("\n");
	}
	return 0;
}
<file_sep>/CSUB.cpp
#include <bits/stdc++.h>
using namespace std;
int main(){
  int T;
  scanf("%d",&T);
  while(T--){
    int N;
    int cnt=0;
    scanf("%d\n",&N);
    for(int i=0;i<N;++i){
      char c;
      scanf("%c",&c);
      if(c=='1') cnt++;
    }
    long long int res= (long long int)cnt;
    res = (res * (res-1))/2;
    res = res + cnt;
    printf("%lld\n",res);
  }
  return 0;
}
<file_sep>/XRQRS.cpp
// author noob333
// H + Shift C + B + E + B + E
#include <bits/stdc++.h>
#include <stdint.h>
#include <fcntl.h>
#include <unistd.h>
#define MAXVAL 500001
#define NMAX 500010
#define gc getchar_unlocked
#define DEBUG 1
using namespace std;
// Input macros
#define s(n)                        scanf("%d",&n)
#define sc(n)                       scanf("%c",&n)
#define sl(n)                       scanf("%lld",&n)
#define sf(n)                       scanf("%lf",&n)
#define ss(n)                       scanf("%s",n)
// Useful constants
#define INF                         (int)1e9
#define EPS                         1e-9
// Useful hardware instructions
#define bitcount                    __builtin_popcount
#define gcd                         __gcd
// Useful container manipulation / traversal macros
#define REP(i,a,b)                  for(int i=a;i<b;i++)
#define RREP(i,a,b)                 for(int i=a;i>b;i--)
#define foreach(v, c)               for( typeof( (c).begin()) v = (c).begin();  v != (c).end(); ++v)
#define all(a)                      a.begin(), a.end()
#define in(a,b)                     ( (b).find(a) != (b).end())
#define pb                          push_back
#define fill(a,v)                    memset(a, v, sizeof a)
#define sz(a)                       ((int)(a.size()))
#define mp                          make_pair
#define fi                          first
#define se                          second
// Some common useful functions
#define maX(a,b)                     ( (a) > (b) ? (a) : (b))
#define miN(a,b)                     ( (a) < (b) ? (a) : (b))
#define checkbit(n,b)                ( (n >> b) & 1)
#define DREP(a)                      sort(all(a)); a.erase(unique(all(a)),a.end())
#define INDEX(arr,ind)               (lower_bound(all(arr),ind)-arr.begin())
#define L(x)                         ( (x<<1) )
#define R(x)                         ( (x<<1)+1 )
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<ll> vl;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef set<int> si;
typedef map<string, int> msi;
#ifdef DEBUG
     #define debug(args...)            {dbg,args; cerr<<endl;}
#else
    #define debug(args...)              // Just strip off all debug tokens
#endif
struct debugger
{
    template<typename T> debugger& operator , (const T& v)
    {    
        cerr<<v<<" ";    
        return *this;    
    }
} dbg;
template <typename T1, typename T2>
    inline std::ostream& operator << (std::ostream& os, const std::pair<T1, T2>& p)
    {
        return os << "(" << p.first << ", " << p.second << ")";
    }
    template<typename T>
    inline std::ostream &operator << (std::ostream & os,const std::vector<T>& v)
    {
        bool first = true;
        os << "[";
        for(unsigned int i = 0; i < v.size(); i++)
        {
            if(!first)
                os << ", ";
            os << v[i];
            first = false;
        }
        return os << "]";
    }
    template<typename T>
    inline std::ostream &operator << (std::ostream & os,const std::set<T>& v)
    {
        bool first = true;
        os << "[";
        for (typename std::set<T>::const_iterator ii = v.begin(); ii != v.end(); ++ii)
        {
            if(!first)
                os << ", ";
            os << *ii;
            first = false;
        }
        return os << "]";
    }
template<typename T1, typename T2>
inline std::ostream &operator << (std::ostream & os,const std::map<T1, T2>& v)
{
  bool first = true;
  os << "[";
  for (typename std::map<T1, T2>::const_iterator ii = v.begin(); ii != v.end(); ++ii)
    {
      if(!first)
	os << ", ";
      os << *ii ;
      first = false;
    }
  return os << "]";
}
class FastInput {
	public:
		FastInput() {
			m_dataOffset = 0;
			m_dataSize = 0;
			m_v = 0x80000000;
		}
		uint32_t ReadNext() {
			if (m_dataOffset == m_dataSize) {
				int r = read(0, m_buffer, sizeof(m_buffer));
				if (r <= 0) return m_v;
				m_dataOffset = 0;
				m_dataSize = 0;
				int i = 0;
				if (m_buffer[0] < '0') {
					if (m_v != 0x80000000) {
						m_data[m_dataSize++] = m_v;
						m_v = 0x80000000;
					}
					for (; (i < r) && (m_buffer[i] < '0'); ++i);
				}
				for (; i < r;) {
					if (m_buffer[i] >= '0') {
						m_v = m_v * 10 + m_buffer[i] - 48;
						++i;
					} else {
						m_data[m_dataSize++] = m_v;
						m_v = 0x80000000;
						for (i = i + 1; (i < r) && (m_buffer[i] < '0'); ++i);
					}
				}
			}
			return m_data[m_dataOffset++];
		}
	public:
		uint8_t m_buffer[32768];
		uint32_t m_data[16384];
		size_t m_dataOffset, m_dataSize;
		uint32_t m_v;
};
class FastOutput {
	public:
		FastOutput() {
			m_dataOffset = 0;
		}
		~FastOutput() {
		}
		void Flush() {
			if (m_dataOffset) {
				if (write(1, m_data, m_dataOffset));
				m_dataOffset = 0;
			}
		}
		void PrintUint(uint32_t v, char d) {
			if (m_dataOffset + 11 > sizeof(m_data)) Flush();
			if (v < 100000) {
				if (v < 1000) {
					if (v < 10) {
						m_data[m_dataOffset + 0] = v + 48;
						m_dataOffset += 1;
					} else if (v < 100) {
						m_data[m_dataOffset + 1] = v - v / 10 * 10 + 48; v /= 10;
						m_data[m_dataOffset + 0] = v + 48;
						m_dataOffset += 2;
					} else {
						m_data[m_dataOffset + 2] = v - v / 10 * 10 + 48; v /= 10;
						m_data[m_dataOffset + 1] = v - v / 10 * 10 + 48; v /= 10;
						m_data[m_dataOffset + 0] = v + 48;
						m_dataOffset += 3;
					}
				} else {
					if (v < 10000) {
						m_data[m_dataOffset + 3] = v - v / 10 * 10 + 48; v /= 10;
 
						m_data[m_dataOffset + 2] = v - v / 10 * 10 + 48; v /= 10;
 
						m_data[m_dataOffset + 1] = v - v / 10 * 10 + 48; v /= 10;
 
						m_data[m_dataOffset + 0] = v + 48;
 
						m_dataOffset += 4;
 
					} else {
 
						m_data[m_dataOffset + 4] = v - v / 10 * 10 + 48; v /= 10;
 
						m_data[m_dataOffset + 3] = v - v / 10 * 10 + 48; v /= 10;
 
						m_data[m_dataOffset + 2] = v - v / 10 * 10 + 48; v /= 10;
 
						m_data[m_dataOffset + 1] = v - v / 10 * 10 + 48; v /= 10;
 
						m_data[m_dataOffset + 0] = v + 48;
 
						m_dataOffset += 5;
 
					}
 
				}
 
			} else {
 
				if (v < 100000000) {
 
					if (v < 1000000) {
 
						m_data[m_dataOffset + 5] = v - v / 10 * 10 + 48; v /= 10;
 
						m_data[m_dataOffset + 4] = v - v / 10 * 10 + 48; v /= 10;
 
						m_data[m_dataOffset + 3] = v - v / 10 * 10 + 48; v /= 10;
 
						m_data[m_dataOffset + 2] = v - v / 10 * 10 + 48; v /= 10;
 
						m_data[m_dataOffset + 1] = v - v / 10 * 10 + 48; v /= 10;
 
						m_data[m_dataOffset + 0] = v + 48;
 
						m_dataOffset += 6;
 
					} else if (v < 10000000) {
 
						m_data[m_dataOffset + 6] = v - v / 10 * 10 + 48; v /= 10;
 
						m_data[m_dataOffset + 5] = v - v / 10 * 10 + 48; v /= 10;
 
						m_data[m_dataOffset + 4] = v - v / 10 * 10 + 48; v /= 10;
 
						m_data[m_dataOffset + 3] = v - v / 10 * 10 + 48; v /= 10;
 
						m_data[m_dataOffset + 2] = v - v / 10 * 10 + 48; v /= 10;
 
						m_data[m_dataOffset + 1] = v - v / 10 * 10 + 48; v /= 10;
 
						m_data[m_dataOffset + 0] = v + 48;
 
						m_dataOffset += 7;
 
					} else {
 
						m_data[m_dataOffset + 7] = v - v / 10 * 10 + 48; v /= 10;
 
						m_data[m_dataOffset + 6] = v - v / 10 * 10 + 48; v /= 10;
 
						m_data[m_dataOffset + 5] = v - v / 10 * 10 + 48; v /= 10;
 
						m_data[m_dataOffset + 4] = v - v / 10 * 10 + 48; v /= 10;
 
						m_data[m_dataOffset + 3] = v - v / 10 * 10 + 48; v /= 10;
 
						m_data[m_dataOffset + 2] = v - v / 10 * 10 + 48; v /= 10;
 
						m_data[m_dataOffset + 1] = v - v / 10 * 10 + 48; v /= 10;
 
						m_data[m_dataOffset + 0] = v + 48;
 
						m_dataOffset += 8;
 
					}
 
				} else {
 
					if (v < 1000000000) {
 
						m_data[m_dataOffset + 8] = v - v / 10 * 10 + 48; v /= 10;
 
						m_data[m_dataOffset + 7] = v - v / 10 * 10 + 48; v /= 10;
 
						m_data[m_dataOffset + 6] = v - v / 10 * 10 + 48; v /= 10;
 
						m_data[m_dataOffset + 5] = v - v / 10 * 10 + 48; v /= 10;
 
						m_data[m_dataOffset + 4] = v - v / 10 * 10 + 48; v /= 10;
 
						m_data[m_dataOffset + 3] = v - v / 10 * 10 + 48; v /= 10;
 
						m_data[m_dataOffset + 2] = v - v / 10 * 10 + 48; v /= 10;
 
						m_data[m_dataOffset + 1] = v - v / 10 * 10 + 48; v /= 10;
 
						m_data[m_dataOffset + 0] = v + 48;
 
						m_dataOffset += 9;
 
					} else {
 
						m_data[m_dataOffset + 9] = v - v / 10 * 10 + 48; v /= 10;
 
						m_data[m_dataOffset + 8] = v - v / 10 * 10 + 48; v /= 10;
 
						m_data[m_dataOffset + 7] = v - v / 10 * 10 + 48; v /= 10;
 
						m_data[m_dataOffset + 6] = v - v / 10 * 10 + 48; v /= 10;
 
						m_data[m_dataOffset + 5] = v - v / 10 * 10 + 48; v /= 10;
 
						m_data[m_dataOffset + 4] = v - v / 10 * 10 + 48; v /= 10;
 
						m_data[m_dataOffset + 3] = v - v / 10 * 10 + 48; v /= 10;
 
						m_data[m_dataOffset + 2] = v - v / 10 * 10 + 48; v /= 10;
 
						m_data[m_dataOffset + 1] = v - v / 10 * 10 + 48; v /= 10;
 
						m_data[m_dataOffset + 0] = v + 48;
 
						m_dataOffset += 10;
 
					}
 
				}
 
			}
 
			m_data[m_dataOffset++] = d;
 
		}
 
		void PrintChar(char d) {
 
			if (m_dataOffset + 1 > sizeof(m_data)) Flush();
 
			m_data[m_dataOffset++] = d;
 
		}
 
		void ReplaceChar(int offset, char d) {
 
			m_data[m_dataOffset + offset] = d;
 
		}
 
 
 
	public:
 
		uint8_t m_data[32768];
 
		size_t m_dataOffset;
 
};
inline void scanint(int &x)
{
    register int c = gc();
    x = 0;
    int neg = 0;
    for(;((c<48 || c>57) && c != '-');c = gc());
    if(c=='-') {neg=1;c=gc();}
    for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
    if(neg) x=-x;
}
int input[NMAX];
int N,M;
struct trieNode{
  trieNode* next[2];
  int cnt;
  trieNode(){
    next[0] = next[1] = NULL;
    cnt = 0;
  }
};
void printTrie(trieNode *root,int val){
  if(root->next[0]==NULL && root->next[1]==NULL)
    cout << val << ",";
  if(root->next[0]) printTrie(root->next[0],val<<1);
  if(root->next[1]) printTrie(root->next[1],(val<<1)+1);
}
trieNode *trieVersions[NMAX];
trieNode* insert(trieNode* root,int x,int mask){
  int tmp = (x&mask)>0?1:0;
  trieNode* ptr = new trieNode();
  ptr->next[0] = root->next[0]; ptr->next[1] = root->next[1];
  ptr->cnt = root->cnt + 1;
  if(root->next[tmp]==NULL){
    trieNode* head = ptr;
    while(mask){
      ptr->next[tmp] = new trieNode();
      ptr = ptr->next[tmp];
      ptr->cnt += 1;
      mask >>= 1;
      tmp = (x&mask)>0?1:0;
    }
    return head;
  }
  ptr->next[tmp] = insert(root->next[tmp],x,mask>>1);
  return ptr;
}
// trieNode* insert(trieNode* root,int x){
//   // trieNode *ptr=(trieNode*)malloc(sizeof(trieNode));
//   trieNode *ptr = new trieNode();
//   trieNode *head = ptr;
//   ptr->next[0] = root->next[0]; ptr->next[1] = root->next[1];
//   ptr->cnt = root->cnt + 1;
//   int mask = 1<<19; int tmp = (mask&x)>0?1:0;
//   while(mask && root->next[tmp]!=NULL){
    
//   }
//   REP(i,0,20){    
//     int tmp = (mask&x)>0?1:0;
//     if(ptr->next[tmp]==NULL) ptr->next[tmp] = new trieNode();
//     ptr=ptr->next[tmp];
//     ptr->cnt += 1;
//     mask >>= 1;
//   }  
//   return head;
// }
ii getTrieMax(trieNode* st,trieNode* en,int x){
  //debug(x);
  int mask = 1<<19;
  int best = 0, val = 0;
  REP(i,0,20){
    int tmp = (mask&x)>0?1:0;
    //debug(st,en,tmp,mask);
    if(en->next[1^tmp] && !(st!=NULL && st->next[1^tmp]!=NULL && en->next[1^tmp]->cnt - st->next[1^tmp]->cnt==0)){
      best += mask;
      val += ((1^tmp)*mask);
      en=en->next[1^tmp]; if(st!=NULL) st=st->next[1^tmp];
    }
    else{
      val += (tmp*mask);
      en = en->next[tmp]; if(st!=NULL) st=st->next[tmp];
    }
    mask >>= 1;
  }
  return ii(best,val);
}
// inline void insert(trieNode* root,int x){
//   trieNode *ptr=root;
//   int mask = 1<<19;
//   ptr->cnt += 1;
//   REP(i,0,20){
//     int tmp = (mask&x)>0?1:0;
//     if(!ptr->next[tmp]) ptr->next[tmp]=(trieNode*)malloc(sizeof(trieNode));
//     ptr=ptr->next[tmp];
//     ptr->cnt += 1;
//     mask >>= 1;
//   }
// }
// inline void remove(trieNode* root,int x){
//   trieNode * ptr=root;
//   int mask = 1<<19;
//   REP(i,0,20){
//     int tmp = (mask&x)>0?1:0;
//     //debug(tmp,mask);
//     ptr->cnt -= 1;    
//     if(ptr->next[tmp]->cnt==1){
//       ptr->next[tmp]=NULL;
//       return;
//     }
//     ptr = ptr->next[tmp];
//     // ptr=ptr->next[tmp];
//     // ptr->cnt -= 1;
//     // if(ptr->cnt == 0 ){
//     //   delete ptr;
//     //   //ptr = NULL;
//     //   return;
//     // }     
//     mask >>= 1;
//   }
// }
// inline ii getTrieMax(trieNode *root,int x){
//   trieNode *ptr = root;
//   assert(ptr!=NULL);
//   int mask = 1<<19;
//   int best=0,val=0;
  
//   for(int i=0;i<20;++i){
//     int tmp = (mask&x)>0?1:0;
//     //debug(tmp,mask);
//     if(ptr->next[1^tmp]){
//       best += mask;
//       val += ((1^tmp)*mask);
//       ptr = ptr->next[1^tmp];
//     }
//     else{
//       val += (tmp*mask);
//       ptr = ptr->next[tmp];
//     }    
//     mask >>= 1;
//   }
//   return ii(best,val);
// }
// struct segNode{
//   trieNode* trie;
//   segNode(){
//     trie = (trieNode*)malloc(sizeof(trieNode));
//   }
// }xorTree[NMAX<<2];
// inline void build(int index,int i,int j){
//   xorTree[index]=segNode();
//   if(i==j) return;
//   int mid=(i+j)>>1;
//   build(L(index),i,mid);
//   build(R(index),mid+1,j);  
// }
// inline void update(int index,int i,int j,int pos,int val){  
//   if(input[pos]) remove(xorTree[index].trie,input[pos]);
//   insert(xorTree[index].trie,val);
//   if(i==j) return;  
//   int mid=(i+j)>>1;
//   if(pos<=mid) update(L(index),i,mid,pos,val);
//   else update(R(index),mid+1,j,pos,val);
// }
// inline ii query(int index,int i,int j,int st,int en,int val){
//   if(i==st && j==en){
//     return getTrieMax(xorTree[index].trie,val);
//   }
//   int mid=(i+j)>>1;
//   if(en<=mid) return query(L(index),i,mid,st,en,val);
//   else if(st>mid) return query(R(index),mid+1,j,st,en,val);
//   else{
//     ii r1,r2;
//     r1 = query(L(index),i,mid,st,mid,val);
//     r2 = query(R(index),mid+1,j,mid+1,en,val);
//     if(r1.fi>=r2.fi) return r1;
//     else return r2;
//   }
// }
// inline void printTree(int index,int i,int j){
//   if(i==j){
//     cout << i << "," << j << "---";
//     printTrie(xorTree[index].trie,0);
//     cout << endl;	
//     return;
//   }
//   int mid=(i+j)>>1;
//   printTree(L(index),i,mid);
//   printTree(R(index),mid+1,j);
//   cout << i << "," << j << "---";
//   printTrie(xorTree[index].trie,0);
//   cout << endl;	
// }
struct perNode{
  perNode *l,*r;
  int cnt;
  perNode(){
    l = r = NULL;
    cnt = 0;
  }
};
perNode* versions[NMAX];
inline perNode* buildPerNode(int i,int j){
  perNode *root = (perNode*) malloc(sizeof(perNode));
  if(i==j) return root;
  int mid=(i+j)>>1;
  root->l = buildPerNode(i,mid);
  root->r = buildPerNode(mid+1,j);
  return root;
}
inline perNode* updPerNode(perNode *root,int i,int j,int pos){
  perNode *tmp = (perNode*) malloc(sizeof(perNode));
  //perNode *tmp = root;
  tmp->l = root->l; tmp->r = root->r; tmp->cnt = root->cnt;
  tmp->cnt += 1;
  if(i==j) return tmp;
  int mid=(i+j)>>1;
  if(pos<=mid)
    tmp->l = updPerNode(root->l,i,mid,pos);
  else
    tmp->r = updPerNode(root->r,mid+1,j,pos);
  return tmp;
}
inline int queryPerNode(perNode *root,int i,int j,int st,int en){
  if(i==st && j==en) return root->cnt;
  int mid=(i+j)>>1;
  if(en<=mid) return queryPerNode(root->l,i,mid,st,en);
  else if(st>mid) return queryPerNode(root->r,mid+1,j,st,en);
  else return queryPerNode(root->l,i,mid,st,mid) + queryPerNode(root->r,mid+1,j,mid+1,en);
}
inline int askLessThan(int st,int en,int x){
  return queryPerNode(versions[en],1,MAXVAL,1,x)-queryPerNode(versions[st-1],1,MAXVAL,1,x);
}
inline int findKth(perNode *st,perNode *en,int i,int j,int k){
  if(i==j) return i;
  int small = en->l->cnt-st->l->cnt;
  int mid = (i+j)>>1;
  if(k<=small) return findKth(st->l,en->l,i,mid,k);
  else return findKth(st->r,en->r,mid+1,j,k-small);  
}
 
inline void addOperation(int x){
  N++;
  //update(1,1,M,N,x);
  trieVersions[N] = insert(trieVersions[N-1],x,1<<19);
  versions[N] = updPerNode(versions[N-1],1,MAXVAL,x);
  input[N] = x;
  // REP(i,1,N+1){
  //   printTrie(trieVersions[i],0);
  //   cout << endl;
  // }
}
inline void removeOperation(int k){
  N -= k;  
}
inline int maxXorOperation(int l,int r,int x){
  ii res = getTrieMax(trieVersions[l-1],trieVersions[r],x);
  //if(x^input[l]>res.fi) return input[l];
  return res.se;
}
inline int kThOperation(int l,int r,int x){
  return findKth(versions[l-1],versions[r],1,MAXVAL,x);
}
FastInput fi;
FastOutput fo;
int main(){
  //ios::sync_with_stdio(false);
  int type,u,v,k;
  //cin >> M;
  //scanint(M);
  M=fi.ReadNext();
  //build(1,1,M);
  versions[0] = buildPerNode(1,MAXVAL);
  trieVersions[0] = new trieNode();
  N = 0;
  REP(i,0,M){
    //cin >> type;
    //scanint(type);
    type=fi.ReadNext();
    if(type == 0){
      //cin >> k;
      //scanint(k);
      k=fi.ReadNext();
      addOperation(k);
    }
    else if(type == 1){
      //cin >> u >> v >> k;
      //scanint(u); scanint(v); scanint(k);
      u=fi.ReadNext(); v=fi.ReadNext(); k=fi.ReadNext();
      // cout << maxXorOperation(u,v,k) << endl;
      //printf("%d\n",maxXorOperation(u,v,k));
      fo.PrintUint(maxXorOperation(u,v,k),'\n');
    }
    else if(type == 2){
      //cin >> k;
      //scanint(k);
      k=fi.ReadNext();
      removeOperation(k);
    }
    else if(type == 3){
      //cin >> u >> v >> k;
      //scanint(u); scanint(v); scanint(k);
      u=fi.ReadNext(); v=fi.ReadNext(); k=fi.ReadNext();
      //cout << askLessThan(u,v,k) << endl;
      //printf("%d\n",askLessThan(u,v,k));
      fo.PrintUint(askLessThan(u,v,k),'\n');
    }
    else{
      //cin >> u >> v >> k;
      //scanint(u); scanint(v); scanint(k);
      u=fi.ReadNext(); v=fi.ReadNext(); k=fi.ReadNext();
      //cout << kThOperation(u,v,k) << endl;
      //printf("%d\n",kThOperation(u,v,k));
      fo.PrintUint(kThOperation(u,v,k),'\n');
    }    
  }
  fo.Flush();
  return 0;
}
<file_sep>/FLIPCOIN.cpp
#include <bits/stdc++.h>
#define NMAX 111111
#define L(x) (x<<1)
#define R(x) ((x<<1)+1)
using namespace std;
int tree[NMAX<<2][2];
void update(int index,int i,int j,int left,int right){
  //printf("%d %d\n",i,j);
  if(tree[index][1]){
    tree[index][0]=(tree[index][1]%2==0?tree[index][0]:(j-i+1)-tree[index][0]);
    if(i!=j) tree[L(index)][1]+=tree[index][1],tree[R(index)][1]+=tree[index][1];
    tree[index][1]=0;
  }
  if(i>right || j<left) return;
  if(i>=left && j<=right) {   
    tree[index][0]=(j-i+1)-tree[index][0];
    if(i!=j) ++tree[L(index)][1],++tree[R(index)][1];
    return;
  }
  if(i!=j){
  int mid=(i+j)>>1;
  update(L(index),i,mid,left,right);
  update(R(index),mid+1,j,left,right);
  tree[index][0]=tree[L(index)][0]+tree[R(index)][0];
  }
}
int query(int index,int i,int j,int left,int right){
  if(tree[index][1]){
    tree[index][0]=(tree[index][1]%2==0?tree[index][0]:(j-i+1)-tree[index][0]);
    if(i!=j) tree[L(index)][1]+=tree[index][1],tree[R(index)][1]+=tree[index][1];
    tree[index][1]=0;
  }
  if(i>right || j<left) return 0;
  if(i>=left && j<=right) return tree[index][0];
  
  if(i!=j){
  int mid=(i+j)>>1;
  int t1=query(L(index),i,mid,left,right);
  int t2=query(R(index),mid+1,j,left,right);
  tree[index][0]=tree[L(index)][0]+tree[R(index)][0];
  return t1+t2;  
  }
  
}
void printTree(int index,int i,int j){
  if(i==j) {
    printf("%d %d - %d,%d \n",i,j,tree[index][0],tree[index][1]);
    return;
  }
  int mid=(i+j)>>1;
  printTree(L(index),i,mid);
  printTree(R(index),mid+1,j);
  printf("%d %d - %d,%d \n",i,j,tree[index][0],tree[index][1]);
}
int main(){
  int N,Q;
  memset(tree,0,sizeof(tree));
  scanf("%d %d",&N,&Q);
  for(int i=0;i<Q;++i){
    int type,u,v;
    scanf("%d %d %d",&type,&u,&v);
    ++u,++v;
    //printf("u=%d,v=%d\n",u,v);
    if(type==0) update(1,1,N,u,v);
    else printf("%d\n",query(1,1,N,u,v));
    //printf("\nPRINTING TREE ----> \n");
    //printTree(1,1,N);
  }
  return 0;
}
<file_sep>/STRPALIN.cpp
#include <bits/stdc++.h>
using namespace std;
int main(){
  ios::sync_with_stdio( false );
  
  int T;
  cin >> T;
  while( T-- ){
    string a,b;
    cin >> a >> b;
    vector<int> flag(26);
    int f=0;
    for(int i=0;i<a.size();++i) flag[a[i]-'a']=1;
    for(int i=0;i<b.size();++i) 
      if(flag[b[i]-'a']==1){
	f=1;
	break;
      }
    if(f) cout << "Yes" << endl;
    else cout << "No" << endl;
    
  }
  return 0;
}
<file_sep>/CHEFFED.cpp
#include <bits/stdc++.h>
using namespace std;
int maxSx = 81;
int maxSSx = 16;
int digitSum( int x ){
	int sum = 0;
	while( x > 0 ) sum += x%10, x/=10;
	return sum;
}
int main(){
	ios::sync_with_stdio(false);
	int N, cnt = 0;
	cin >> N;
	
	for(int i=1;i<=maxSx;++i){
		for(int j=1;j<=maxSSx;++j){
			int x = N - i - j;
			if( x < 0 ) continue;
			int sx = digitSum( x );
			int ssx = digitSum( sx );
			if( sx == i && ssx == j ) ++cnt;
		}
	}
	cout << cnt << endl;
	
	return 0;
}
<file_sep>/PREDICT.cpp
#include <cstdio>
const int MAX=10000;
typedef unsigned long long x64;
int main()
{
	x64 T;
	scanf("%llu",&T);
	while(T>0)
	{
		double 	p,res;
		scanf("%lf",&p);
		p=(p>0.5?p:1-p);
		res=(MAX+(MAX*2*(1-p)))*p;
		printf("%f\n",res);
		--T;
	}
	return 0;
}
<file_sep>/MIXTURES.cpp
#include <bits/stdc++.h>
#define NMAX 111
#define INF 9999999
using namespace std;
int mix[NMAX][NMAX];
int color[NMAX][NMAX];
int input[NMAX];
int N;
void init(){
  for(int i=0;i<N;++i){
    color[i][i]=input[i];
    for(int j=i+1;j<N;++j)
      color[i][j]=(color[i][j-1]+input[j])%100;
  }
}
void solve(){
    for(int i=0;i<N;++i) mix[i][i]=0;
    for(int sz=2;sz<=N;++sz){
      for(int i=0;i<N;++i){
	int j=i+sz-1;
	if(j>=N) break;
	mix[i][j]=INF;
        for(int k=i;k<j;++k)
	  mix[i][j]=min(mix[i][j],mix[i][k]+mix[k+1][j]+color[i][k]*color[k+1][j]);
      }
    }
    printf("%d\n",mix[0][N-1]);
}
int main(){
  //int T;
  //scanf("%d",&T);
  while(scanf("%d",&N)>0){
    //scanf("%d",&N);
    for(int i=0;i<N;++i) scanf("%d",&input[i]);
    init();
    solve();
  }
  return 0;
}
<file_sep>/COINS.cpp
#include <map>
#include <algorithm>
#include <iostream>
#include <stdio.h>
typedef unsigned long long ull;
using namespace std;
map<ull,ull> bytelandCoins;
void preCompute()
{
	for(int i=0;i<12;++i)
		bytelandCoins.insert(pair<ull,ull>(i,i));
}
ull solve(ull x)
{
	ull ans;
	if(bytelandCoins.find(x)!=bytelandCoins.end())
	{
		ans=bytelandCoins[x];
		return ans;
	}
	ans= solve(x>>1)+solve(x>>2)+solve(x/3);
	ans= ans>x? ans:x;
	bytelandCoins.insert(pair<ull,ull>(x,ans));
	return ans;
}
int main()
{
	ull num,N[10];
	int i=0;
	preCompute();
	while(scanf("%llu",&num)!=EOF)
	{
		N[i]=solve(num);
		++i;
	}
	for(int j=0;j<i;++j)
	{
		printf("%llu\n",N[j]);
	}
	return 0;
}
<file_sep>/FRIEMEET.cpp
#include <bits/stdc++.h>
#define NMAX 555555
using namespace std;
typedef pair<int,int> pii;
typedef long long int ull;
ull computeGcd(ull a, ull b)
{
    if (a == 0)
        return b;
    return computeGcd(b%a, a);
}
ull trigger;
int N,M;
int cost[NMAX], friendly[NMAX], subtree[NMAX];
vector<pii> adj[NMAX];
int dfs( int u, int par, int edgeCost ){
  cost[u] = edgeCost;
  subtree[u] = 0;
  if( friendly[u] ) subtree[u] = 1;
  for(int i=0;i<adj[u].size();++i){
    int next = adj[u][i].first, val = adj[u][i].second;
    if( next != par )
      subtree[u] += dfs( next, u, val );
  }
  
  return subtree[u];
}
ull solve(){
  ull result = 0;
  dfs( 1, -1, 0 );
  for(int i=2;i<=N;++i){
    ull inSubtree = subtree[i];
    ull outOfSubtree = M - subtree[i];
    ull edgeInPaths = cost[i];
    edgeInPaths *= inSubtree;
    edgeInPaths *= outOfSubtree;
    result += edgeInPaths;
    if( result > trigger ) assert(false);
  }
  ull allPairs = ((ull)M)*M;
  result *= 2;
  ull gcd = computeGcd( result, allPairs );
  result /= gcd;
  allPairs /= gcd;
  cout << result << " " << allPairs << endl;
  //cout << result/gcd << " "  << allPairs/gcd << endl;
}
void resetVectors(){
  for(int i=1; i<=N; ++i)
    cost[i] = 0, friendly[i] = 0, subtree[i] = 0, adj[i].clear();  
}
int main(){
  ios::sync_with_stdio(false);
  trigger = 1;
  for(int i=0;i<18;++i) trigger *= 10;
  int T;
  cin >> T;
  while( T-- ){  
    cin >> N >> M;    
    resetVectors();
    for(int i=0;i<N-1;++i){
      int u,v,w;
      cin >> u >> v >> w;
      
      adj[u].push_back(pii(v,w));
      adj[v].push_back(pii(u,w));
    }
    for(int i=0;i<M;++i){
      int x;
      cin >> x;
      friendly[x] = 1;
    }
    
    solve();
  }
  return 0;
}
<file_sep>/RRSTONE.cpp
#include <bits/stdc++.h>
#define NMAX 111111
using namespace std;
typedef long long int LL;
LL input[NMAX];
int main(){
	LL N,K,best;
	scanf("%lld %lld",&N,&K);
	for(int i=0;i<N;++i){
		scanf("%lld",&input[i]);
		if(i>0) best=max(best,input[i]);
		else best=input[i];
	}
	if(K>0){
		LL val;
		for(int i=0;i<N;++i){
			input[i]=best-input[i];
			if(i>0) val=max(val,input[i]);
			else val=input[i];
		}
		if(K%2==0){
			for(int i=0;i<N;++i) input[i]=val-input[i];
		}
	}
	for(int i=0;i<N;++i) printf("%lld ",input[i]);
	return 0;
}
<file_sep>/TMSLT.cpp
#include <bits/stdc++.h>
#define NMAX 3333333
#define MOD 1000000
using namespace std;
typedef long long int LL;
int strengths[MOD];
LL readLL()
{
   LL cc = getc(stdin);
   for (;cc < '0' || cc > '9';)  cc = getc(stdin);
   LL ret = 0;
   for (;cc >= '0' && cc <= '9';)
   {
      ret = ret * 10 + cc - '0';
      cc = getc(stdin);
   }
  return ret;
}
int main(){
	LL T;
	//scanf("%lld",&T);
	T=readLL();
	while(T--){
		LL N,a,b,c,d,prev,maxval;
		//scanf("%lld %lld %lld %lld %lld",&N,&a,&b,&c,&d);
		N=readLL();
		a=readLL();
		b=readLL();
		c=readLL();
		d=readLL();
		memset(strengths,0,sizeof(strengths));
		maxval=prev=d;
		strengths[prev]=1;
		for(LL i=1;i<N;++i){
			LL curr;
			curr=(a*prev*prev)+(b*prev)+c;
			if(curr>=MOD) curr=curr%MOD;
			strengths[curr]+=1;
			maxval=max(maxval,curr);
			prev=curr;
		}
		LL l,r;
		l=r=0;
		int flag=0;
		for(LL i=0;i<=maxval;++i){
			if(strengths[i]){
				for(LL j=0;j<strengths[i];++j){
					if(flag==0){
						l+=i;
						flag=1;
					}
					else{
						r+=i;
						flag=0;
					}
				}
			}
		}
		printf("%lld\n",abs(l-r));
	}
	return 0;
}
<file_sep>/SREENI.cpp
#include <bits/stdc++.h>
using namespace std;
int main(){
	//freopen("1.in","r",stdin);
	int T;
	scanf("%d",&T);
	while(T--){
	string s1,s2;
	vector<int> pos;
	int flag=0;
	cin>>s1>>s2;
	if(s1.length()!=s2.length()){
		printf("NO\n");
		return 0;
	}
	for(int i=0;i<s2.length();++i)
		if(s2[i]==s1[0]) pos.push_back(i);
	for(int k=0;k<pos.size();++k){
		int i,j=pos[k];
		for(i=0;i<s1.length();++i,j=(j+1)%s2.size())
			if(s1[i]!=s2[j]) break;
		if(i==s1.length()){
			flag=1;
			break;
		}
	}
	if(flag) printf("YES\n");
	else printf("NO\n");
	}
	return 0;
}
<file_sep>/LEBALONS.cpp
#include <bits/stdc++.h>
#define NMAX 44
typedef double ld;
using namespace std;
int C[NMAX];
ld P[NMAX];
int flag[NMAX];
ld dp[NMAX][NMAX];
ld F[NMAX][NMAX];
int N,M;
vector<ld> group[NMAX];
void init(){
	for(int i=0;i<NMAX;++i)
		for(int j=0;j<NMAX;++j)
			dp[i][j]=0.0;
	dp[0][0]=1.0;
	for(int i=1;i<NMAX;++i){
		dp[i][0]=1.0;
		for(int j=1;j<=i;++j)
			dp[i][j]=dp[i-1][j]+dp[i-1][j-1];
	}
}
ld pow2(int x){
	if(x==0) return 1.0;
	else if(x&1) return 2.0*pow2(x-1);
	else{
		ld t=pow2(x/2);
		return t*t;
	}
}
vector<ld> k_products_1(vector<ld> a, int n){
	vector<ld> newer,older;
    older=vector<ld>(n+1);
    int d, i;
    older[0] = 1.0;
    for(d = 1; d <= n; ++d){
        newer = vector<ld>(n+1);
        newer[0] = a[d-1]*older[0];
        for(i = 1; i <= d; ++i){
            newer[i] = older[i-1] + a[d-1]*older[i];
        }
        older = newer;
    }
    return older;
}
void solve1();
int main(){
	solve1();
	/*init();
	int T;
	scanf("%d",&T);
	while(T--){
		memset(flag,0,sizeof(flag));
		for(int i=0;i<NMAX;++i) group[i].clear();
		int groups=0;
		ld res=0.0;
		scanf("%d %d",&N,&M);
		for(int i=0;i<N;++i){
			scanf("%d %lf",&C[i],&P[i]);
			if(flag[C[i]]==0){
				++groups;
				flag[C[i]]=groups;
			}
			group[flag[C[i]]].push_back(P[i]);
		}
			ld tot=0.0;
			ld sum=0.0;
			vector<ld> powers(groups);
			for(int i=0;i<groups;++i){
				powers[i]=pow2(group[i+1].size())-1;
				//printf("%lf ",powers[i]);
			}
			//printf("\n");
			vector<ld> res2=k_products_1(powers,groups);
			//for(int i=0;i<res.size();++i) printf("%lf\n",res[i]);
			for(int i=M;i<=groups;++i) tot+=res2[groups-i];
			for(int i=1;i<=groups;++i){
				vector<ld> other_powers;
				vector<ld> res3;
				for(int j=1;j<=groups;++j){
					if(j!=i) other_powers.push_back(pow2(group[i].size())-1);
				}
				res3=k_products_1(other_powers,groups-1);
				double x,y;
				x=y=0.0;
				for(int j=0;j<group[i].size();++j) x+=group[i][j];
				for(int j=max(0,M-1);j<=groups-1;++j) y+=res3[groups-1-j];
				sum+=(x*y*(pow2(group[i].size()-1))/tot);
			}
		//	printf("%0.9Lf %0.9Lf",tot,2.0*tot);
			//printf("%lf\n",tot);
			ld rem=pow2(N-M);
//			tot+=dp[groups][M]*rem;
			if(M==0){
				for(int j=0;j<N;++j) sum+=((rem-1)*(P[j]/tot));
			}
			else{
				for(int j=0;j<N;++j) sum+=(dp[groups-1][M-1]*rem*(P[j]/tot));
			}
			res=sum;
			printf("%0.9lf\n",res);
	}*/
	return 0;
}
void solve1(){
	init();
		int T;
		scanf("%d",&T);
		while(T--){
			memset(flag,0,sizeof(flag));
			for(int i=0;i<NMAX;++i) group[i].clear();
			int groups=0;
			ld res=0.0;
			scanf("%d %d",&N,&M);
			for(int i=0;i<N;++i){
				scanf("%d %lf",&C[i],&P[i]);
				if(flag[C[i]]==0){
					++groups;
					flag[C[i]]=groups;
				}
				group[flag[C[i]]].push_back(P[i]);
			}
				ld tot=0.0;
				ld sum=0.0;
				vector<ld> powers(groups);
				for(int i=0;i<groups;++i){
					powers[i]=pow2(group[i+1].size())-1;
					//printf("%lf ",powers[i]);
				}
				//printf("\n");
				vector<ld> res2=k_products_1(powers,groups);
				//for(int i=0;i<res.size();++i) printf("%lf\n",res[i]);
				for(int i=M;i<=groups;++i) tot+=res2[groups-i];
				for(int i=1;i<=groups;++i){
					vector<ld> other_powers;
					vector<ld> res3;
					for(int j=1;j<=groups;++j){
						if(j!=i) other_powers.push_back(pow2(group[j].size())-1);
					}
					res3=k_products_1(other_powers,groups-1);
					double x,y;
					x=y=0.0;
					for(int j=0;j<group[i].size();++j) x+=group[i][j];
					for(int j=max(0,M-1);j<=groups-1;++j) y+=res3[groups-1-j];
					sum+=(x*y*(pow2(group[i].size()-1))/tot);
				}
			/*//	printf("%0.9Lf %0.9Lf",tot,2.0*tot);
				//printf("%lf\n",tot);
				ld rem=pow2(N-M);
	//			tot+=dp[groups][M]*rem;
				if(M==0){
					for(int j=0;j<N;++j) sum+=((rem-1)*(P[j]/tot));
				}
				else{
					for(int j=0;j<N;++j) sum+=(dp[groups-1][M-1]*rem*(P[j]/tot));
				}
	*/
				res=sum;
				printf("%0.9lf\n",res);
		}
}
<file_sep>/CLETAB.cpp
#include <bits/stdc++.h>
#define NMAX 222
#define MMAX 444
using namespace std;
int N,M;
int pages[MMAX];
set<int> buffer;
set<int>::iterator bufferItr;
void solve(){
  int currPage = 0;
  int pageFaults = 0;
  buffer.clear();
  while( currPage < M ){
    if( buffer.find( pages[currPage] ) == buffer.end() ){
      ++pageFaults;
      if( buffer.size() < N ) buffer.insert( pages[currPage] );
      else{
	int mxPage,mxDist;
	mxPage = mxDist = -1;
	for( bufferItr = buffer.begin(); bufferItr != buffer.end(); ++ bufferItr ){
	  int page = *bufferItr;
	  int dist = MMAX + NMAX;
	  for( int i = currPage + 1; i < M; ++i )
	    if( pages[i] == page )
	      dist = min( dist, i );
	  if( mxPage == -1 || dist > mxDist) mxPage = page, mxDist = dist;
	}
	buffer.erase( mxPage );
	buffer.insert( pages[currPage] );
      }
    }
    ++currPage;
  }
  printf("%d\n", pageFaults );
}
int main(){
  int T;
  scanf("%d",&T);
  while(T--){
    scanf("%d %d",&N,&M);
    for(int i=0;i<M;++i) scanf("%d",&pages[i]);
    solve();
  }
  return 0;
}
<file_sep>/CSS2.cpp
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pi;
typedef long long int ll;
typedef pair<ll,pi> pp;
map<ll,pi> dict;
int main(){
  int n,m;
  scanf("%d %d",&n,&m);
  int id,attr,val,pri;
  for(int i=0;i<n;++i){
    scanf("%d %d %d %d",&id,&attr,&val,&pri);
    ll key=(ll(id)*1000000)+ll(attr);
    if(dict.find(key)==dict.end())
      dict.insert(pp(key,pi(val,pri)));
    else
      dict[key]=dict[key].second>pri?dict[key]:pi(val,pri);
  }
  for(int i=0;i<m;++i){
    scanf("%d %d",&id,&attr);
    ll key=(ll(id)*1000000)+ll(attr);
    printf("%d\n",dict[key].first);
  }
  return 0;
}
<file_sep>/CHEFSPL.cpp
#include <bits/stdc++.h>
using namespace std;
int main(){
	ios::sync_with_stdio(false);
	int D;
	cin >> D;
	while( D-- ){
		string s;
		cin >> s;
		int sz=s.size();
		if(sz == 1) cout << "NO" << endl;
		else if(sz&1){
			int i=0, cnt=0, j=sz/2 + 1;	
			while( i <= sz/2 && cnt < 2 ){
				if( s[i] != s[j] ) cnt++, ++i;
				else ++i, ++j;
			}
			if( cnt < 2 ) cout << "YES" << endl;
			else{
				reverse(s.begin(),s.end());
	
				i=0, cnt=0, j=sz/2 + 1;	
				while( i <= sz/2 && cnt < 2 ){
					if( s[i] != s[j] ) cnt++, ++i;
					else ++i, ++j;
				}
	
				if( cnt < 2 ) cout << "YES" << endl;
				else cout << "NO" << endl;
			}
		}
		else{
			int flag = 0;
			for(int i=0,j=sz/2;j<sz;++i,++j)
				if(s[i] != s[j]){
					flag=1;
					break;
				}
			if( flag ) cout << "NO" << endl;
			else cout << "YES" << endl;
		}
		
	}
	
	return 0;
}
<file_sep>/CRAWA.cpp
#include <bits/stdc++.h>
using namespace std;
int main(){
	int T;
	scanf("%d",&T);
	for(int t=0;t<T;++t){
		int x,y,flag=0;
		scanf("%d %d",&x,&y);
		if(x==0){
			if(y==0) printf("YES\n");
			else flag=1;
		}
		else if(x==1){
			if(y==1 || y==2) printf("YES\n");
			else flag=1;
		}
		else if(x>0){
			if((x+1)&1) flag=1;
			else{
				int d=(x-1)/2;
				if(y>=(-d*2)&&y<=((d+1)*2)) printf("YES\n");
				else flag=1;
			}
		}
		else{
			int tmp=-x;
			if(tmp&1) flag=1;
			else{
				if(y>=(-tmp) && y<=tmp) printf("YES\n");
				else flag=1;
			}
		}
		if(flag){
			if(y>0){
				if(y&1) printf("NO\n");
				else{
					if(x>=(-y)&&x<=(y-1)) printf("YES\n");
					else printf("NO\n");
				}
			}
			else{
				int tmp=(-y);
				if(tmp&1) printf("NO\n");
				else{
					if(x>=(-tmp)&&x<=(tmp+1)) printf("YES\n");
					else printf("NO\n");
				}
			}
		}
	}
	return 0;
}
<file_sep>/FIBQ.cpp
#include <bits/stdc++.h>
#define NMAX 111111
#define MOD 1000000007
#define MOD2INV 500000004
#define L(x) (x<<1)
#define R(x) ((x<<1)|1)
using namespace std;
typedef long long int ll;
template <typename T>
inline T fpow( T base, int exp ){
  T res = 1;
  while( exp ){
    if( exp & 1 ) res= (res*base)%MOD;
    base=(base*base)%MOD;
    exp >>= 1;
  }
  return res;
}
struct ComplexNumber {
  ll real, img;
  ComplexNumber( ll x=0, ll y=0 ){
    real = x, img = y;
  }
  ComplexNumber operator+(const ComplexNumber& x){
    return ComplexNumber( real+x.real, img+x.img );
  }
  ComplexNumber operator-(const ComplexNumber& x){
    return ComplexNumber( real-x.real, img-x.img );
  }
  ComplexNumber operator%(const ll& mod){
    return ComplexNumber( real%mod, img%mod );
  }
  ComplexNumber operator*(const ComplexNumber& x){
    return ComplexNumber( real*x.real + 5*img*x.img, real*x.img + img*x.real );
  }  
  ComplexNumber operator=(const ComplexNumber& x){
    real = x.real, img = x.img;
  }
  ll getIm(){ return img; }
  friend ostream &operator<<( ostream &output, const ComplexNumber &D )
  { 
    output << D.real << " + " << D.img << "i";
    return output;            
  }
};
ComplexNumber phiPower( int n ){
  return fpow( ComplexNumber(1,1), n );
}
int input[NMAX];
ComplexNumber tree[NMAX<<3];
void printTree( int idx, int i, int j ){
  cout << i << "," << j << " " << tree[idx] << endl;
  if(i==j) return;
  int mid=(i+j)>>1;
  printTree(L(idx),i,mid);
  printTree(R(idx),mid+1,j);
}
ll revmod( int n ){
  return fpow( (ll)MOD2INV, n );
}
void init( int idx, int i, int j ){  
  if( i==j ){
    tree[idx] = phiPower( input[i] );
    tree[idx] = tree[idx] * revmod(input[i]), tree[idx] = tree[idx] % MOD;
    tree[idx] = tree[idx] + ComplexNumber(1,0), tree[idx] = tree[idx]%MOD;
    //cout << i << "," << j << " " << tree[idx] << endl;
    return;
  }
  int mid=(i+j)>>1;
  init( L(idx), i, mid );
  init( R(idx), mid + 1, j );
  tree[idx] = tree[L(idx)]*tree[R(idx)];
  tree[idx] = tree[idx]%MOD;
}
ComplexNumber query( int idx, int i, int j, int lt, int rt ){
  if( i==lt && j==rt ) return tree[idx];
  int mid=(i+j)>>1;
  if( rt <= mid ) return query( L(idx), i, mid, lt, rt );
  else if ( lt > mid ) return query( R(idx), mid + 1, j, lt, rt );
  else{
    ComplexNumber res = query( L(idx), i, mid, lt, mid )*query( R(idx), mid + 1, j, mid + 1, rt );
    res =res%MOD;
    return res;
  }
}
void update( int idx, int i, int j, int pos, int val ){
  if( i == j && i == pos ){
    tree[idx] = phiPower( val );
    tree[idx] = tree[idx] * revmod(val), tree[idx] = tree[idx] % MOD;
    tree[idx] = tree[idx] + ComplexNumber(1,0), tree[idx] = tree[idx]%MOD;
    return;
  }
  
  int mid=(i+j)>>1;
  if( pos <= mid ) update(L(idx), i, mid, pos, val);
  else update( R(idx), mid+1, j, pos, val );
  
  tree[idx] = tree[L(idx)]*tree[R(idx)];
  tree[idx] = tree[idx]%MOD;  
}
int main(){  
  ios::sync_with_stdio(false);
  
  //cout << phiPower(1) << "\t" << phiPower(2) << "\t" << phiPower(3) << endl;
  //cout << revmod[0] << endl << revmod[1] << endl << (phiPower(2) * revmod[2])%MOD << endl << (phiPower(3)*revmod[3])%MOD << endl;
  
  int N,Q;
  cin >> N >> Q;
  
  for(int i=1;i<=N;++i)
    cin >> input[i];
    
  init(1,1,N);
  //printTree(1,1,N);
  for(int i=0;i<Q;++i){
    string type;
    int x,y;
    cin >> type >> x >> y;
    
    if( type[0] == 'Q' ){
      ll res = query( 1, 1, N, x, y ).getIm();            
      res = (res * 2) % MOD;      
      cout << res << endl;
    }
    else{
      update( 1, 1, N, x, y );
    }
  }
  
  return 0;
}
<file_sep>/BINTREE.cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long int LL;
inline LL find_depth(LL x){
	LL res=0;
	while(x>1) x=x>>1,res++;
	return res;
}
inline LL lca(LL x,LL y){
	LL res=0;
	while(x!=y){
		if(find_depth(x)<find_depth(y)) y=y>>1;
		else x=x>>1;
		++res;
	}
	return res;
}
int main()
{	
	int N;
	scanf("%d",&N);
	while(N--){
		int i,j;
		scanf("%d %d",&i,&j);
		printf("%lld\n",lca(i,j));
	}
	
	return 0;
}
<file_sep>/RESERVOI.cpp
#include <bits/stdc++.h>
#define NMAX 1111
using namespace std;
string str[NMAX];
int N,M;
int main(){
  ios::sync_with_stdio(false);
  int T;
  cin >> T;
  while(T--){
    cin >> N >> M;
    for(int i=0;i<N;++i) cin >> str[i];
    int flag = 0;
    for(int i=0;i<N;++i){
      if(str[i][0] == 'W' || str[i][M-1] == 'W'){
	flag = 1;
	break;
      }
    }
    for(int i=0;i<M;++i){
      if(str[N-1][i] == 'W'){
	flag = 1;
	break;
      }
    }
    
    for(int i=0;i<N;++i){
      for(int j=0;j<M;++j){
	
	if(str[i][j] == 'W'){
	  if(j>0 && str[i][j-1]=='A'){
	    flag = 1;
	    break;
	  }
	  else if(j<M-1 && str[i][j+1]=='A'){
	    flag = 1;
	    break;
	  }
	  else if(i<N-1 && str[i+1][j]=='A'){
	    flag = 1;
	    break;
	  }
	}
	
	if(str[i][j] == 'A'){
	  if(i>0 && str[i-1][j]=='B'){
	    flag = 1;
	    break;
	  }
	}
	
      }
      if(flag == 1) break;
    }
    
    if(flag == 1) cout << "no" << endl;
    else cout << "yes" << endl;
    
  }
  return 0;
}
<file_sep>/BINTOUR.cpp
#include <bits/stdc++.h>
#define NMAX (1<<19)
typedef long long int LL;
const LL MOD=1000000009;
using namespace std;
vector<LL> f;
LL pow(LL a, LL b)
{
    LL x=1,y=a;
    while(b > 0)
    {
        if(b%2 == 1)
        {
            x=(x*y);
            if(x>MOD) x%=MOD;
        }
        y = (y*y);
        if(y>MOD) y%=MOD;
        b /= 2;
    }
    return x;
}
LL InverseEuler(LL n)
{
    return pow(n,MOD-2);
}
LL C(LL n, LL r)
{
    return (f[n]*((InverseEuler(f[r]) * InverseEuler(f[n-r])) % MOD)) % MOD;
}
int main(){
	int K,N;
	scanf("%d",&K);
	N=1<<K;
    f=vector<LL>(N+1,1);
    for (int i=2; i<=N;i++)
        f[i]= (f[i-1]*i) % MOD;
	/*vector<LL> fact(N+1,0),ifact(N+1,0);
	fact[0]=fact[1]=1;
	ifact[0]=ifact[1]=1;
	for(int i=2;i<N+1;++i){
		fact[i]=(fact[i-1]*LL(i)) % MOD;
	//	ifact[i]=((-(MOD / i) * ifact[MOD % i]) % MOD) + MOD;
		ifact[i]=(modInverse(i)*ifact[i-1])%MOD;
	}
	*/
	int L=N>>1;
	for(int i=1;i<L;++i) printf("%d\n",0);
	for(int i=L;i<N;++i){
	/*	LL n=fact[i-1];
		LL d=(ifact[L-1]*ifact[i-L])%MOD;
		LL res=(n*d)%MOD;
		res=(res*fact[L])%MOD;
		res=(res*fact[L])%MOD;
		*/
		LL res=C(i-1,L-1);
		res=(((res*f[L])%MOD)*f[L])%MOD;
		res=(res*2)%MOD;
		printf("%lld\n",res);
	}
	printf("%lld",f[N]);
	return 0;
}
<file_sep>/FLAGS.cpp
#include <bits/stdc++.h>
#define NMAX 11111
using namespace std;
typedef long long int ll;
int main(){
  int T;
  scanf("%d",&T);
  while(T--){
    ll N;
    scanf("%lld",&N);
    if(N==1) printf("0\n");
    else if(N==2) printf("4\n");
    else if(N==3) printf("42\n");
    else{
      ll res = N*(N-1)*2 + (5*N*(N-1)*(N-2)) + (2*N*(N-1)*(N-2)*(N-3));
      printf("%lld\n",res);
    }
  }
  return 0;
}
<file_sep>/FIRESC.cpp
#include <stdio.h>
#include <iostream>
#define MOD 1000000007
struct node
{
	int rank,elements;
	node *parent;
};
node *nodes[100001];
void MakeSet(node *x)
{
	x->parent=x;
	x->rank=0;
	x->elements=1;
}
node * Find(node *x)
{
	if(x->parent!=x)
		x->parent=Find(x->parent);
	return x->parent;
}
void Link(node *x,node *y)
{
	if(x->rank > y->rank)
	{
		y->parent=x;
		x->elements+=y->elements;
	}
	else
	{
		x->parent=y;
		y->elements+=x->elements;
		if(x->rank==y->rank)
			y->rank+=1;
	}
}
void Union(node *x,node *y)
{
	Link(Find(x),Find(y));
}
void CreateDisjointSets(int &groups,unsigned long &leaders)
{
	int N,M,count=0;
	unsigned long long ways=1;
	scanf("%d %d",&N,&M);
	for(int i=1;i<=N;++i)
	{
		node *newNode=new node();
		nodes[i]=(newNode);
		MakeSet(newNode);
	}
	for(int j=0;j<M;++j)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		if(Find(nodes[u])!=Find(nodes[v]))
		{
			Union(nodes[u],nodes[v]);
		}
	}
	for(int i=1;i<=N;++i)
	{
		if(nodes[i]->parent==nodes[i])
		{
			++count;
			ways=ways*nodes[i]->elements;
			if(ways>MOD)
				ways=ways%MOD;
		}
	}
	groups=count;
	leaders=ways;
}
int main()
{
	int T,ans[5];
	unsigned long leader[5];
	scanf("%d",&T);
	for(int i=0;i<T;++i)
	{
		CreateDisjointSets(ans[i],leader[i]);
		printf("%d %lu\n",ans[i],leader[i]);
	}
}
<file_sep>/LEPAINT.cpp
#include <bits/stdc++.h>
#define NMAX 55
#define CMAX 111
using namespace std;
typedef double ld;
int query[NMAX];
ld prob[NMAX][CMAX];
int n,c,k;
void solve(){
  ld ci = ld(1)/c;
  ld res=0.0;
  ld exp=0.0;    
  for(int i=0;i<k+1;++i)
    for(int j=0;j<c;++j)
      prob[i][j]=0.0;
  prob[0][1]=1.0;
  
  for(int i=0;i<k+1;++i){
    for(int j=0;j<c;++j){
      if(prob[i][j]>0.0){
	prob[i+1][j] += (prob[i][j]/2.0);
	for(int col=0;col<c;++col){
	  int newCol = (col*j)%c;
	  prob[i+1][newCol] += ((ci)*(prob[i][j]/2.0));
	}
      }
      //cout<<prob[i][j]<<" ";
    }
    //cout<<endl;
  }
  for(int i=0;i<n;++i){
    int indx=query[i];
    exp=0.0;
    for(int j=0;j<c;++j) exp += (ld(j)*prob[indx][j]);
    res += exp;
    //cout<< query[i]<<" "<<exp << endl;
  }
  printf("%.9lf\n",res);
}
int main(){
  int T;
  scanf("%d",&T);
  while(T--){
    memset(query,0,sizeof(query));
    scanf("%d %d %d",&n,&c,&k);
    for(int i=0;i<k;++i){
      int l,r;
      scanf("%d %d",&l,&r);
      --l,--r;
      for(int j=l;j<=r;++j) query[j] += 1;      
    }
    solve();
  }
  return 0;
}
<file_sep>/PERMSUFF.cpp
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
int main(){
  int T;
  scanf("%d",&T);
  while(T--){
    int N,M;
    scanf("%d %d",&N,&M);
    vector<int> input(N),flag(N,0);
    vector<pii> intervals;
    for(int i=0;i<N;++i) scanf("%d",&input[i]);
    for(int i=0;i<M;++i){
      int u,v;
      scanf("%d %d",&u,&v);
      intervals.push_back(pii(u,v));
    }
    sort(intervals.begin(),intervals.end());
    stack<pii> s;
    s.push(intervals[0]);
    for(int i=1;i<M;++i){
      pii t = s.top();
      if( intervals[i].first > t.second )
	s.push(intervals[i]);
      else if( intervals[i].second > t.second ){
	t.second=intervals[i].second;
	s.pop();
	s.push(t);
      }
    }
    int poss=1;
    while(!s.empty()){
      pii curr = s.top();
      s.pop();
      for(int i=curr.first;i<=curr.second;++i){
	if( input[i-1]>curr.second || input[i-1]<curr.first ){
	  poss=0;
	  break;
	}
	flag[i-1]=1;
      }
    }
    if(!poss) printf("Impossible\n");
    else{
      
      for(int i=0;i<N;++i)
	if(flag[i]==0 && input[i]!=i+1){
	  poss=0;
	  break;
	}
      if(poss) printf("Possible\n");
      else printf("Impossible\n");
    }
  }
  return 0;
}
<file_sep>/TOURISTS.cpp
// author noob333
// H + Shift C + B + E + B + E
#include <bits/stdc++.h>
#define NMAX 100002
#define EMAX 200002
#define gc getchar_unlocked
#define DEBUG 1
using namespace std;
// Input macros
#define s(n)                        scanf("%d",&n)
#define sc(n)                       scanf("%c",&n)
#define sl(n)                       scanf("%lld",&n)
#define sf(n)                       scanf("%lf",&n)
#define ss(n)                       scanf("%s",n)
// Useful constants
#define INF                         (int)1e9
#define EPS                         1e-9
// Useful hardware instructions
#define bitcount                    __builtin_popcount
#define gcd                         __gcd
// Useful container manipulation / traversal macros
#define REP(i,a,b)                  for(int i=a;i<b;i++)
#define RREP(i,a,b)                 for(int i=a;i>b;i--)
#define foreach(v, c)               for( typeof( (c).begin()) v = (c).begin();  v != (c).end(); ++v)
#define all(a)                      a.begin(), a.end()
#define in(a,b)                     ( (b).find(a) != (b).end())
#define pb                          push_back
#define fill(a,v)                    memset(a, v, sizeof a)
#define sz(a)                       ((int)(a.size()))
#define mp                          make_pair
#define fi                          first
#define se                          second
// Some common useful functions
#define maX(a,b)                     ( (a) > (b) ? (a) : (b))
#define miN(a,b)                     ( (a) < (b) ? (a) : (b))
#define checkbit(n,b)                ( (n >> b) & 1)
#define DREP(a)                      sort(all(a)); a.erase(unique(all(a)),a.end())
#define INDEX(arr,ind)               (lower_bound(all(arr),ind)-arr.begin())
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<ll> vl;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef set<int> si;
typedef map<string, int> msi;
#ifdef DEBUG
     #define debug(args...)            {dbg,args; cerr<<endl;}
#else
    #define debug(args...)              // Just strip off all debug tokens
#endif
struct debugger
{
    template<typename T> debugger& operator , (const T& v)
    {    
        cerr<<v<<" ";    
        return *this;    
    }
} dbg;
template <typename T1, typename T2>
    inline std::ostream& operator << (std::ostream& os, const std::pair<T1, T2>& p)
    {
        return os << "(" << p.first << ", " << p.second << ")";
    }
    template<typename T>
    inline std::ostream &operator << (std::ostream & os,const std::vector<T>& v)
    {
        bool first = true;
        os << "[";
        for(unsigned int i = 0; i < v.size(); i++)
        {
            if(!first)
                os << ", ";
            os << v[i];
            first = false;
        }
        return os << "]";
    }
    template<typename T>
    inline std::ostream &operator << (std::ostream & os,const std::set<T>& v)
    {
        bool first = true;
        os << "[";
        for (typename std::set<T>::const_iterator ii = v.begin(); ii != v.end(); ++ii)
        {
            if(!first)
                os << ", ";
            os << *ii;
            first = false;
        }
        return os << "]";
    }
template<typename T1, typename T2>
inline std::ostream &operator << (std::ostream & os,const std::map<T1, T2>& v)
{
  bool first = true;
  os << "[";
  for (typename std::map<T1, T2>::const_iterator ii = v.begin(); ii != v.end(); ++ii)
    {
      if(!first)
	os << ", ";
      os << *ii ;
      first = false;
    }
  return os << "]";
}
void scanint(int &x)
{
    register int c = gc();
    x = 0;
    for(;(c<48 || c>57);c = gc());
    for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
}
int nodeDegree[NMAX], visited[NMAX];
vector<int> adjacencyList[NMAX];
int edgeStart[EMAX], edgeEnd[EMAX], direction[EMAX];
int nodeLastIndex[NMAX];
void eulerTour(int u){
  while(nodeLastIndex[u]<adjacencyList[u].size()){
    int idx=adjacencyList[u][nodeLastIndex[u]++];
    if(direction[idx] == 0){
      int st = edgeStart[idx], en = edgeEnd[idx];
      if(st == u){
	direction[idx] = +1;
	eulerTour(en);
      }
      else{
	direction[idx] = -1;
	eulerTour(st);
      }
    }
  }
}
void dfs(int u){
  visited[u] = 1;
  for(int i=0;i<adjacencyList[u].size();++i){
    int idx = adjacencyList[u][i];
    int st = edgeStart[idx], en = edgeEnd[idx];
    if(st == u){
      if(!visited[en]) dfs(en);
    }
    else{
      if(!visited[st]) dfs(st);
    }
  }    
}
int main(){
  //ios::sync_with_stdio(false);
  int N, E;
  //cin >> N >> E;
  //scanf("%d %d",&N,&E);
  scanint(N);
  scanint(E);
  for(int i=0;i<E;++i){
    int u,v;
    //cin >> u >> v;
    //scanf("%d %d",&u,&v);
    scanint(u);
    scanint(v);
    edgeStart[i] = u;
    edgeEnd[i] = v;
    adjacencyList[u].pb(i);
    adjacencyList[v].pb(i);
    nodeDegree[u]++;
    nodeDegree[v]++;
  }
  dfs(1);
  for(int i=1;i<=N;++i){
    if(!visited[i] || nodeDegree[i]%2){
      //cout << "NO" << endl;
      printf("NO\n");
      return 0;
    }
  }
  eulerTour(1);
  //cout << "YES" << endl;
  printf("YES\n");
  for(int i=0;i<E;++i){
    if(direction[i] == -1)
      printf("%d %d\n",edgeEnd[i], edgeStart[i]);
    else
      printf("%d %d\n",edgeStart[i], edgeEnd[i]);
  }
  
  return 0;
}
<file_sep>/REIGN.cpp
#include <iostream>
#include <cstdio>
#include <climits>
#define NMAX 111111
using namespace std;
typedef long long int LL;
int N,K;
int input[NMAX];
LL forward[NMAX],backward[NMAX];
int main(){
	int T;
	scanf("%d",&T);
	while(T>0){
	scanf("%d %d",&N,&K);
	for(int i=0;i<N;++i) scanf("%d",&input[i]);
	LL sumF,sumB;
	LL bestF,bestB;
	sumF=sumB=0;
	bestF=bestB=LLONG_MIN;
	for(int i=0,j=N-1;i<N && j>=0;++i,--j){
		sumF+=input[i];
		sumB+=input[j];
		bestF=max(bestF,sumF);
		bestB=max(bestB,sumB);
		if(sumF<0) sumF=0;
		if(sumB<0) sumB=0;
		forward[i]=bestF;
		backward[j]=bestB;
	}
	LL bestSplit=LLONG_MIN;
	for(int i=0;i<N-K-1;++i)	bestSplit=max(bestSplit,forward[i]+backward[i+K+1]);
	printf("%lld\n",bestSplit);
	--T;
	}
	return 0;
}
<file_sep>/DELISH.cpp
#include <cstdio>
#include <vector>
#include <climits>
using namespace std;
typedef long long int x64;
vector<x64> input;
inline x64 absolute(x64 x)
{
	if(x>0) return x;
	else return (-x);
}
void solve()
{
	vector<x64>	leftMax,leftMin,rightMax,rightMin;
	int len=input.size();
	leftMax=vector<x64>(len,0);
	leftMin=vector<x64>(len,0);
	rightMax=vector<x64>(len,0);
	rightMin=vector<x64>(len,0);
	/*leftMax[0]=input[0];
	leftMin[0]=input[0];
	rightMax[len-1]=input[len-1];
	rightMin[len-1]=input[len-1];*/
	x64 maxResult=LLONG_MIN;
	x64 maxSum=0;
	x64 minResult=LLONG_MAX;
	x64 minSum=0;
	for(int i=0;i<len;++i)
	{
		maxSum+=input[i];
		if(maxSum>maxResult)	maxResult=maxSum;
		if(maxSum<0)		maxSum=0;
		leftMax[i]=maxResult;
		minSum+=input[i];
		if(minSum<minResult)	minResult=minSum;
		if(minSum>0)	minSum=0;
		leftMin[i]=minResult;
	}
	maxResult=LLONG_MIN;
	maxSum=0;
	minResult=LLONG_MAX;
	minSum=0;
	for(int i=len-1;i>=0;--i)
	{
		maxSum+=input[i];
		if(maxSum>maxResult)	maxResult=maxSum;
		if(maxSum<0)		maxSum=0;
		rightMax[i]=maxResult;
		minSum+=input[i];
		if(minSum<minResult)	minResult=minSum;
		if(minSum>0)	minSum=0;
		rightMin[i]=minResult;
	}
	x64 result=LLONG_MIN;
	for(int i=0;i<len-1;++i)
	{
		x64 leftHigh,leftLow,rightHigh,rightLow;
		leftHigh=leftMax[i];
		leftLow=leftMin[i];
		rightHigh=rightMax[i+1];
		rightLow=rightMin[i+1];
		result=max(result,max(absolute(rightHigh-leftLow),absolute(leftHigh-rightLow)));
	}
	printf("%lld\n",result);
}
int main()
{
	int T;
	scanf("%d",&T);
	while(T>0)
	{
		int N;
		scanf("%d",&N);
		input=vector<x64>(N,0);
		for(int i=0;i<N;++i)
			scanf("%lld",&input[i]);
		solve();
		--T;
	}
	return 0;
}
<file_sep>/FENWITER.cpp
#include <bits/stdc++.h>
using namespace std;
int main(){
  ios::sync_with_stdio( false );
  int T;
  cin >> T;
  while( T-- ){
      string L1,L2,L3;
      long long int N;
      cin >> L1 >> L2 >> L3 >> N;
      long long int result = 0;
      for(int i=0;i<L1.size();++i)
    	  result += (L1[i] == '1' ? 1:0);
      for(int i=0;i<L3.size();++i)
    	  result += (L3[i] == '1' ? 1:0);
      for(int i=0;i<L2.size();++i)
    	  result += (L2[i] == '1' ? N:0);
      if( result == 0 ){
    	  cout << result << endl;
		  continue;
      }
      //cout << "init:" << result << endl;
      int check=L3.size()-1;
      while( check >=0 ){
    	  if( L3[check] == '0' ) break;
    	  -- result, -- check;
      }
      if( check >= 0 ){
    	  cout << result + 1 << endl;
    	  continue;
      }
      check = L2.size()-1;
      long long int tmp = 0;
      while( check >=0 ){
    	  if( L2[check] == '0' ) break;
    	  ++ tmp, -- check;
      }
      if( check >= 0 ){
    	  result -= tmp;
    	  cout << result + 1 << endl;
    	  continue;
      }
      result -= (N*tmp);
      check = L1.size()-1;
      while( check >=0 ){
    	  if( L1[check] == '0' ) break;
    	  -- result, -- check;
      }
      cout << result + 1 << endl;
  }
  return 0;
}
<file_sep>/KINGCON.cpp
#include <stdio.h>
#include <vector>
using namespace std;
typedef vector<int> VI;
typedef vector<VI> VVI;
class Graph
{
	VVI adjList;
	int missile;
	vector<int> lowValues,dfsValues,visited,parent,articulation;
	int articulationPoints;
	int root,rootCount;
	int counter;
public:
	void CreateList(int,int,int);
	void CountArticulationPoints(int);
	long long int GetCost();
};
long long int Graph::GetCost()
{
	return ((long long int)missile)*articulationPoints;
}
void Graph::CreateList(int Vertices,int Edges,int val)
{
	int N1,N2;
	adjList=VVI(Vertices,VI());
	missile=val;
	lowValues.resize(Vertices,0);
	dfsValues.resize(Vertices,0);
	visited.resize(Vertices,0);
	parent.resize(Vertices,0);
	articulation.resize(Vertices,0);
	for(int i=0;i<Edges;++i)
	{
		scanf("%d %d",&N1,&N2);
		adjList[N1].push_back(N2);
		adjList[N2].push_back(N1);
	}
	articulationPoints=counter=root=rootCount=0;
	CountArticulationPoints(root);
	for(int i=0;i<Vertices;++i)
	{
		articulationPoints+=articulation[i];
	}
}
void Graph::CountArticulationPoints(int v)
{
	visited[v]=1;
	lowValues[v]=dfsValues[v]=counter++;
	for(VI::iterator itr=adjList[v].begin();itr!=adjList[v].end();++itr)
	{
		int val=(*itr);
		if(!visited[val])
		{
			parent[val]=v;
			if(v==root)
				++rootCount;
			CountArticulationPoints(val);
			if(lowValues[val]>=dfsValues[v])
			{
				if(v==root)
				{
					if(rootCount>1)
					{
						articulation[v]=1;
					}
				}
				else
				{
					articulation[v]=1;
				}
			}
			lowValues[v]=min(lowValues[v],lowValues[val]);
		}
		else if(parent[v]!=val)
		{
			lowValues[v]=min(lowValues[v],dfsValues[val]);
		}
	}
}
int main()
{
	int N,E,m,T;
	scanf("%d",&T);
	while(T>0)
	{
		Graph g;
		scanf("%d %d %d",&N,&E,&m);
		g.CreateList(N,E,m);
		printf("%lld\n",g.GetCost());
		--T;
	}
	return 0;
}
<file_sep>/CHBLLNS.cpp
#include <bits/stdc++.h>
using namespace	std;
int main(){
  ios::sync_with_stdio(	false );
  int T;
  cin >> T;
  while( T-- ){
    long long int R,G,B,K, res = 0;
    cin >> R >> G >> B >> K;
    res += min( K-1, R );
    res	+= min( K-1, G );
    res	+= min( K-1, B );
    cout << res + 1 << endl;
  }
  return 0;
}
