akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sstream>
#include <iostream>
#include <math.h>
#include <time.h>
#include <unistd.h>
#include <algorithm>
#include <map>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <set>
#include <string>
 
#ifndef ONLINE_JUDGE
	#define DEBUG(x) cout << '>' << #x << ':' << x << endl;
#else
	#define DEBUG(x) do {} while(0);
#endif
 
#define pb push_back
#define mp make_pair
#define ALL(x) (x).begin(), (x).end()
#define PER(i, N) for(int (i) = (N)-1; (i) >= 0; (i)--)
#define REP(i, N) for(int (i) = 0; (i) < (int)(N); (i)++)
 
using namespace std;
typedef long long ll;
inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; }

template <typename T, typename U> std::istream&operator>>(std::istream&i, pair<T,U>&p) {i >> p.x >> p.y; return i;}
template<typename T>std::istream&operator>>(std::istream&i,vector<T>&t) {for(auto&v:t){i>>v;}return i;}
template <typename T, typename U> std::ostream&operator<<(std::ostream&o, const pair<T,U>&p) {o << p.x << ' ' << p.y; return o;}
template<typename T>std::ostream&operator<<(std::ostream&o,const vector<T>&t) {if(t.empty())o<<'\n';for(size_t i=0;i<t.size();++i){o<<t[i]<<" \n"[i == t.size()-1];}return o;}
template<typename T> using minheap = priority_queue<T, vector<T>, greater<T>>;
template<typename T> using maxheap = priority_queue<T, vector<T>, less<T>>;
template<typename T> T gcd(T a,T b) { if (a<b) swap(a,b); return b?gcd(b,a%b):a; }

ll n,k;

bool sim(ll num, ll d) {
//	cout << num << " " << d <<endl;
	if(num < d) {
		return num==1;
	}
	if(num % d == 0) {
		return sim(num/d, d);
	} else {
		return sim(num%d, d);
	}
}

void solve(istream& cin, ostream& cout) {
	cin >> n;
	if(n == 2) {
		cout << 1 << endl;
		return;
	}
	set<ll> ks;
	ks.insert(n-1);
	ks.insert(n);
	for(ll d = 2; d*d <= n; d++) {
		if((n-1)%d == 0) {
			ks.insert(d);
			ks.insert((n-1)/d);
		}
		if(n % d == 0) {
			if(sim(n, d)) {
				ks.insert(d);
			}
			if(sim(n, n/d)) {
				ks.insert(n/d);
			}
		}
	}
	cout << ks.size() << endl;
}


int main() {
    ios_base::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	solve(cin, cout);
	/*
	{
		istringstream instr("2\n2\n14");
		solve(instr, cout);
	}
 */
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int C,R,ans;
int sen[10][10000];
int solve(int i){
	int res=0;
	int tmp[10][10000]={};
	for(int j=0;j<C;j++){
		if(i>>j&1)
			for(int k=0;k<R;k++)tmp[j][k]++;
	}
	for(int j=0;j<R;j++){
		int a=0;
		for(int k=0;k<C;k++){
			a+=(sen[k][j]+tmp[k][j])%2;
		}
		res+=min(a,C-a);
	}
	return C*R-res;
}
int main()
{
	while(true){
		cin>>C>>R;
		if(!C&&!R)break;
		for(int i=0;i<C;i++)for(int j=0;j<R;j++)cin>>sen[i][j];
		for(int i=0;i<1<<C;i++)ans=max(ans,solve(i));
		cout<<ans<<endl;
		ans=0;
	}
    return 0;
}

Measured memory_bytes: 1944
//#include"cpp_kyopro.h"
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <stdlib.h>
using namespace std;
int main()
{
	int n,i,sum=0; cin >> n;
	int  w[n];
        int su[n]; 
	//sum[0] = 0;
	for (i = 0; i < n; i++) {
		cin >> w[i];
		su[0] = w[0];
		su[i] = su[i - 1] + w[i];
//cout<<su[i]<<endl;
	}
	int a = su[n-1] / 2;
//cout<<a<<endl;
	int b;
	i = 0;
	while(abs(a-su[i])>abs(a-su[i+1])) {
		b = i;
		i++;

		
	}
	cout << abs(su[n-1]-su[i] -su[i ])<<endl;
	//cout << p + r + q - max <<endl;
       return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define INF 1e9
using namespace std;

#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(a)  (a).begin(),(a).end()
#define endl "\n"

template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
typedef long long ll;

void solve() {
    int n;
    cin >> n;
    vector<int> v(n);
    REP(i,n) cin >> v[i];

    auto partition = [&] (int p,int r) {
        auto x = v[r];
        auto i = p-1;
        FOR(j,p,r) {
            if (v[j] <= x) {
                i++;
                iter_swap(v.begin()+i,v.begin()+j);
            }
        }
        iter_swap(v.begin()+i+1,v.begin()+r);
        return i+1;
    };

    auto i = partition(0,n-1);


    REP(j,n) {
        if (j != 0) cout << " ";
        if (i == j)cout << "[";
        cout << v[j];
        if (i == j)cout << "]";
    }
    cout << endl;
}

int main() {
    solve();
    return 0;
}


Measured memory_bytes: 3108
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;

int main()
{
    ll N, K;
    cin >> N >> K;
    ll xi;
    vector<ll> X;
    for(int i=0;i<N;i++){
        cin >> xi;
        X.push_back(xi);
    }
    int i1 = distance(X.begin(), lower_bound(X.begin(), X.end(), 0));
    if(i1==0){
        cout<<X[K-1]<<endl;
        return 0;
    }
    ll res = numeric_limits<ll>::max();
    for(int i=0; i<K; i++){
        auto imax = i1-1-i+K-1;
        auto imin = i1-1-i;
        if(imax >= N) continue;
        if(imin < 0) continue;
        auto v = 2 * (abs(X[imin])+abs(X[imax]));
        v -= max(abs(X[imin]), abs(X[imax]));
        res = min(res, v);
    }
    if(i1-K>=0){
        auto imin = i1-K;
        auto v = abs(X[imin]);
        res = min(res, v);
    }
    cout<<res<<endl;

    return 0;
}

Measured memory_bytes: 1400
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define bit(n) (1<<(n))
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<bool> vb;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1;} return 0;}
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1;} return 0;}
int const INF = 1001001001;

const long double PI = acos(-1);

int main()
{
cin.tie(0);
ios::sync_with_stdio(false);

double R; cin >> R;
cout << fixed << setprecision(5)<<2 * PI * R << endl;

return 0;
}

Measured memory_bytes: 3796
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;
int ans;
int H, W, K;
vector<string> c;
// vector<pair<vector<int>, vector<int>>> ans;

void dfs(int x, int y, vector<int> &h, vector<int> &w){
    if (h.size() == x + 1 && w.size() == y + 1)
    {
        // for (int i = 0; i < h.size(); i++)
        // {
        //     cerr << h[i] << " ";
        // }
        // cerr << endl;
        // for (int i = 0; i < w.size(); i++)
        // {
        //     cerr << w[i] << " ";
        // }
        // cerr << endl;
        
        int temp = 0;
        for (int i = 0; i < H; i++)
        {
            if (find(h.begin(), h.end(), i) != h.end()) {
                continue;
            }
            for (int j = 0; j < W; j++)
            {
                if (find(w.begin(), w.end(), j) != w.end()) {
                    continue;
                }
                if (c[i][j] == '#')
                {
                    temp++;
                }
                
            } 
        }
        if (temp == K)
        {
            ans++;
            // ans.push_back(make_pair(h, w));
        }
        return;
    }
    if(w.back() == -1){
    if (h.size() < x + 1)
    {
        for (int i = h.back() + 1; i < H; i++)
        {
            h.push_back(i);
            dfs(x, y, h, w);
            h.pop_back();       
        }
    }
    }
    
    if (w.size() < y + 1)
    {
        for (int i = w.back() + 1; i < W; i++)
        {
            w.push_back(i);
            dfs(x, y, h, w);
            w.pop_back();
        }
        
    }
}

int main() {
    cin >> H >> W >> K;
    c.resize(H);
    for (int i = 0; i < H; i++)
    {
        cin >> c[i];
    }
    
    vector<int> h, w;
    h.push_back(-1);
    w.push_back(-1);
    for (int i = 0; i <= H; i++)
    {
        for (int j = 0; j <= W; j++)
        {
            dfs(i, j, h, w);
        }
        
    }
    cout << ans << endl;

  return 0;
}


Measured memory_bytes: 3640
def Heian():
    g = input().split()

    x = int(g[0])
    y = int(g[1])

    #= int(input().strip())

    M=int(input())
    a = []
    for i in range(M):
        a.append(list(map(int, input().split())))

    #Process Vert and Horiz
    Vert=[[True for i2 in range(x+1)]for i1 in range(y+1)]
    Horiz=[[True for i2 in range(x+1)]for i1 in range(y+1)]


    for i in range(x+1):
        Vert[0][i]=False
    for i in range(y+1):
        Horiz[i][0]=False

    for i in range(M):
        x1=a[i][0]
        x2=a[i][2]
        y1=a[i][1]
        y2=a[i][3]
        if x1==x2:
            Vert[max(y1,y2)][x1]=False
        if y1==y2:
            Horiz[y1][max(x1,x2)]=False

    Txy=[[0 for i2 in range(x+1)]for i1 in range(y+1)]
    for i in range(x+1):
        for j in range(y+1):
            if Vert[j][i]==False and Horiz[j][i]==False:
                if i==0 and j==0:
                    Txy[i][j]=1
                else:
                    Txy[j][i]=0
            elif Vert[j][i]==False:
                if i==0:
                    Txy[j][i]=0
                else:
                    Txy[j][i]=Txy[j][i-1]
            elif Horiz[j][i]==False:
                if j==0:
                    Txy[j][i]=0
                else:
                    Txy[j][i]=Txy[j-1][i]
            else:
                Txy[j][i]=Txy[j-1][i]+Txy[j][i-1]

    if Txy[y][x]==0:
        print("Miserable Hokusai!")
    else:
        print(Txy[y][x])


N = int(input())

for i in range(N):
    Heian()

Measured memory_bytes: 7780
#include <bits/stdc++.h>
using namespace std;
 
struct edge {int /*from,*/to,cost;};
typedef long long ll;
typedef pair<int,int> P;
typedef pair<pair<int,int>,int> PP;
typedef vector<int> VI;
typedef vector<long long int> VL;
typedef vector<edge> VE;
static const int MOD = 1000000007;
//static const int INF = 2147483647;
//static const long long INF = 9223372000000000000;
//static const long long INF = 9223372000000000000/2;
//static const int INF = 1000010000;
//int dx4[4] = {0,1,0,-1}, dy4[4] = {-1,0,1,0};
//int dx5[5] = {-1,0,0,0,1}, dy5[5] = {0,-1,0,1,0};
//int dx8[8] = {-1,0,1,1,1,0,-1,-1}, dy8[8] = {1,1,1,0,-1,-1,-1,0};
//int dx9[9] = {-1,0,1,1,1,0,-1,-1,0}, dy9[9] = {1,1,1,0,-1,-1,-1,0,0};
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define np next_permutation
#define pq priority_queue
#define SZ(a) int((a).size())
#define LEN(a) int((a).length())
#define MAX(a,b,c) max((a),max((b),(c)))
#define MIN(a,b,c) min((a),min((b),(c)))
#define SORT(c) sort((c).begin(),(c).end())
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define REP1(i,x) for(int i=1;i<=(int)(x);i++)
#define RREP(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define RREP1(i,x) for(int i=((int)(x));i>0;i--)
//#define int ll

signed main(){
    string o,e;
    cin >> o >> e;
    int len = LEN(o) + LEN(e);
    REP(i,len){
        if(i%2) printf("%c",e[i/2]);
        else printf("%c",o[i/2]);
    }
    return 0;
}

Measured memory_bytes: 384
# -*- coding: utf-8 -*-

n = int(input())

p = []
for i in range(n):
    yen = int(input())
    p.append(yen)

p_max_half = max(p)/2
p_max_index = p.index(max(p))

p_sum = sum(p)

print(int(p_sum-p_max_half))


Measured memory_bytes: 2940
#include "bits/stdc++.h"
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;

typedef long long ll;

int main() {
    int N;
    cin >> N;
    vector<string> s(N);
    vector<int> t(N);
    rep(i, N) cin >> s[i] >> t[i];
    string X;
    cin >> X;
    int ans = -1;
    rep(i, N) {
        if (s[i] == X) {
            ans = 0;
            continue;
        }
        if (ans < 0) continue;
        ans += t[i];
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
using ll = long long;

int main() {
  int N;
  std::cin >> N;
  int res{0};
  for (int i = 0; i < N; i++) {
    int l, r;
    std::cin >> l >> r;
    res += r - l + 1;
  }
  std::cout << res << std::endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define r(i,n) for(int i=0;i<n;i++)
#define INF 100000000
int dp[20001][256];
 main(){
  int n,m;
  while(cin>>n>>m,n){
    int b[m];int a[n+1];
    r(i,m)cin>>b[i];
    r(i,n)cin>>a[i+1];
    r(i,n+1)r(j,256)dp[i][j]=INF;
    dp[0][128]=1;
    r(i,n)r(j,256)
        if(dp[i][j]!=INF)r(k,m){
          int p=j+b[k];
          if(p>255)p=255;
          if(p<0)p=0;
          dp[i+1][p]=min(dp[i+1][p],dp[i][j]+(a[i+1]-p)*(a[i+1]-p));
        }
    int p=100000000;
    r(i,256)if(dp[n][i]!=INF)
      p=min(p,dp[n][i]);
    cout<<p-1<<endl;
  }
}

Measured memory_bytes: 23048
N = int(input())
S = input()

if N % 2 == 1:
  print("No")
  exit()
  
T_len = int(N / 2)
T1 = S[:T_len]
T2 = S[T_len:]

if T1 == T2:
  print("Yes")
else:
  print("No")

Measured memory_bytes: 9164
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>


using namespace std;

const int INF = 10000000;

// ツ各ツ可伉づェツタツイツδ仰＋ツスツタツーツトツ地ツ点ツづ個つサツづェツつシツづェツづ個甘板づ個仰猟猟」
int d[21][21][21][21];
vector<string> field;
pair<int,int> sp;
vector<pair<int,int> > dartys;
int w,h;

int bfs(int sy,int sx){
	queue<pair<int,int> > *prv = new queue<pair<int,int> >();
	queue<pair<int,int> > *nxt = new queue<pair<int,int> >();

	bool passed[21][21];
	for(int i = 0; i < 21; i++)
		fill(passed[i],passed[i]+21,false);

	prv->push(make_pair(sy,sx));

	int dy[] = {-1,0,0,1};
	int dx[] = {0,-1,1,0};

	int dist = 0;

	int cnt = 0;
	while(prv->size()){
		while(prv->size()){
			pair<int,int> cp = prv->front();prv->pop();
			if(passed[cp.first][cp.second])
				continue;
			passed[cp.first][cp.second]=true;
			d[sy][sx][cp.first][cp.second] = dist;

			if(field[cp.first][cp.second] == '*'){
				cnt++;
			}

			for(int i = 0; i < 4; i++){
				pair<int,int> np = cp;
				np.first += dy[i];
				np.second += dx[i];
				if(np.first >= 0 && np.second >= 0 && np.first < h && np.second < w){
					if(!passed[np.first][np.second] && field[np.first][np.second] != 'x'){
						nxt->push(np);
					}
				}
			}
		}
		dist++;
		swap(prv,nxt);
	}
	delete prv,nxt;
	return cnt;
}

int dfs(int s,pair<int,int> prv){
	if(s == (1 << (int)(dartys.size()))-1){
		return 0;
	}

	int minCost = INF;
	for(int i = 0; i < dartys.size(); i++){
		if(!((1 & (s >> i)) == 1) && d[prv.first][prv.second][dartys[i].first][dartys[i].second] != INF){
			minCost = min(minCost,dfs(s | (1 << i),make_pair(dartys[i].first,dartys[i].second))
				+ d[prv.first][prv.second][dartys[i].first][dartys[i].second]);
		}
	}
	return minCost;
}

int main(){

	while(cin >> w >> h && !(w == 0 && h == 0)){
		for(int i = 0; i < 21; i++){
			for(int j = 0; j < 21; j++){
				for(int k = 0; k < 21; k++){
					fill(d[i][j][k],d[i][j][k]+21,INF);
				}
			}
		}
		field.clear();
		dartys.clear();
		for(int i = 0; i < h; i++){
			string str;
			cin >> str;
			field.push_back(str);
			for(int j = 0; j < str.size(); j++){
				if(str[j] == 'o'){
					sp.first = i;
					sp.second = j;
				}
				else if(str[j] == '*'){
					dartys.push_back(make_pair(i,j));
				}
			}
		}

		if(dartys.size()==0){
			cout << 0 << endl;
			continue;
		}

		// ツ各ツ湘ェツ渉環つゥツづァツ深ツつウツ優ツ静ヲツ探ツ催オツづ、ツつサツづェツつシツづェツづ個湘ェツ渉環づ鳴づ個仰猟猟」ツづーツ仰づ淞づつィツつュ
		if(bfs(sp.first,sp.second) != dartys.size()){
			cout << -1 << endl;
			continue;
		}
//		bool fff = false;
		for(int i = 0; i < dartys.size(); i++){
			bfs(dartys[i].first,dartys[i].second);
		}

		// ツ渉嘉アツセツーツδ仰スツマツδ督姪「ツ妥ィツづーツ嘉ーツつュ
		cout << dfs(0,make_pair(sp.first,sp.second)) << endl;
	}

	return 0;
}

Measured memory_bytes: 3172
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {	
	int t=1;
//	cin >> t;
	while (t--) {
	   string s;
	   cin>>s;
	   long long temp=0;
	   for(int i=0;i<s.length();i++)
	   {
	   	 temp+=s[i]-'0';
	   	 
	   }
	   if(temp%9==0)
	   cout<<"Yes";
	   else
	   cout<<"No";
	   
       
}
	    
	} 
	
	

Measured memory_bytes: 3628
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define sc(x) scanf("%d",&x);
int main(){
    int n; sc(n)
    int A[n];
    for (int i = 0; i < n; i++) sc(A[i])
    ll sum = 0, cnt = 0, ans = 1e15;
    for (int i = 0; i < n; i++) sum += A[i];
    for (int i = 0; i < n - 1; i++){
        cnt += A[i];
        if (ans > abs(sum - 2 * cnt)) ans = abs(sum - 2 * cnt);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1024
def ncr(n,r,mod):
    cnt=1
    for i in range(n-r+1,n+1):
        cnt*=i
        cnt%=mod
    for i in range(1,r+1):
        cnt*=pow(i,mod-2,mod)
        cnt%=mod
    return cnt
mod=10**9+7
x,y=map(int,input().split())
if (x+y)%3!=0:
    print(0)
    exit()
mini=min(x,y)
if (x+y)//3>mini:
    print(0)
    exit()
n=(x+y)//3
dif=abs(x-y)
if dif%2==0:
    r=dif//2
    center=n//2
    print(ncr(n,center+r,mod))
else:
    r=(dif-1)//2
    center=n//2
    print(ncr(n,center-r,mod))

Measured memory_bytes: 3188
#! /usr/bin/python
# -*- coding: utf-8 -*-
import itertools

N, M = map(int, raw_input().split())
c = []
for i in xrange(N):
    c.append(map(float, raw_input().split()))

d = [[0]*N for i in range(N)]
for i in xrange(N):
    for j in xrange(i+1, N):
        L2 = (c[i][0]-c[j][0])**2
        a2 = (c[i][1]-c[j][1])**2
        b2 = (c[i][2]-c[j][2])**2
        d[i][j] = d[j][i] = L2+a2+b2
mdis = 0
for com in list(itertools.combinations(range(N), M)):
    dis = 0
    for i, j in list(itertools.combinations(com, 2)):
        dis += d[i][j]
    if mdis < dis: mdis=dis
print mdis

Measured memory_bytes: 33056
import java.util.Arrays;
import java.util.Scanner;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    double n=sc.nextLong(),a=sc.nextLong(),b=sc.nextLong(),c=sc.nextLong(),d=sc.nextLong(),e=sc.nextLong(),min=n,res=0;
    double[] in=new double[6];
    in[0]=n;
    in[1]=a;
    in[2]=b;
    in[3]=c;
    in[4]=d;
    in[5]=e;
    Arrays.sort(in);
    System.out.println((long)Math.ceil(n/in[0])+4);
  }
}


Measured memory_bytes: 23892
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#define rep(i, n) for(int i = 0; i<n; i++)

using namespace std;

class UnionFind{
    public:
        int *group;
        UnionFind(int n) {
            group = new int[n];
            rep(i,n) group[i] = i;
        };

        int find(int x) {
            int parent = group[x];
            if (parent == x) return x;
            return group[x] = find(parent);
        };

        void unite(int a, int b) {
            int pa = find(a);
            int pb = find(b);
            group[pb] = pa;
        };
};


int main(void) {
    int n, m;
    cin >> n >> m;
    int p[n+1];
    rep(i, n) cin >> p[i+1];

    UnionFind uf = UnionFind(n+1);
    rep(i, m) {
        int x, y;
        cin >> x >> y;
        uf.unite(x, y);
    }
    rep(i, n+1) uf.find(i);

    int c = 0;
    rep(i, n+1) {
        if (not i) i++;
        if (uf.find(i) == uf.find(p[i])) c++;
    }

    cout << c << endl;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;

int main()
{
	string a, b;
	int x;
	int zh(string s);
	
	cin >> a >> b;
	
	x = zh(a+b);
	  
	if (int(sqrt(x))==sqrt(x))		
	   cout << "Yes" << endl;
	else
	   cout << "No" << endl;
 
	return 0;
}

int zh(string s)
{
	int tmp=0;
	
	for (int i=0; i<s.size(); i++)
	   tmp = tmp*10+(s[i]-'0');
	   
	return tmp;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
	while (true) {
		int N;
		cin >> N;

		if (N == 0) {
			break;
		}

		vector<vector<int>> M(N);
		vector<int> size(N);
		
		for (int i = 0; i < N; i++) {
			cin >> size[i];

			for (int j = 0; j < size[i]; j++) {
				int temp;
				cin >> temp;
				M[i].push_back(temp);
			}
		}

		int k;
		cin >> k;

		vector<int> K;

		for (int i = 0; i < k; i++) {
			int temp;
			cin >> temp;
			K.push_back(temp);
		}

		int ans = -1;

		for (int i = 0; i < N; i++) {
			bool ok = true;

			for (int j = 0; j < k; j++) {
				bool flag = false;
				for (int x = 0; x < size[i]; x++) {
					if (K[j] == M[i][x]) {
						flag = true;
						break;
					}
				}

				if (flag == false) {
					ok = false;
					break;
				}
			}

			if (ok == true) {
				if (ans != -1) {
					ans = -1;
					break;
				}
				else {
					ans = i + 1;
				}
			}
		}

		cout << ans << endl;
	}

	return 0;
}

Measured memory_bytes: 3128
#include <bits/stdc++.h>
#include <assert.h>

using namespace std;

int main()
{
	int x, a, b;
	cin >> x >> a >> b;
	if (abs(x - a) > abs(x - b))
		cout << "B" << endl;
	else
		cout << "A" << endl;

	return 0;
}


Measured memory_bytes: 256
/*

    author : s@if

*/

#include<bits/stdc++.h>
using namespace std;

#define 		NIL 			-1
#define		 	fi	 		    first
#define 		sec 			second
#define 		MAX 			INT_MAX
#define			INF 			99999999
#define 		ll 			    long long
#define 		PI 			    acos(-1.0)
#define			MOD 			1000000007
#define 		PLL 			pair<ll,ll>
#define 		PII			    pair<int,int>
#define 		ull 			unsigned long long
#define 		For(i,a,b) 		for(int i=a;i<=(int)b;i++)


inline int in() {int x; scanf("%d", &x); return x; }
bool Check(int N , int pos)	{	return (bool) (N & (1<<pos));}
int Set(int N, int pos) {	return N = N | (1<<pos);}

int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};
int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};
int hr[]={-2,-2,-1,+1,+2,+2,-1,+1};
int hc[]={+1,-1,+2,+2,-1,+1,-2,-2};
int dx[]={+1,-1,+0,+0};
int dy[]={+0,+0,+1,-1};

const int MAXN = (int)1e5+9;

int main()
{
/*	freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);  */

    int i,j,k,l,m,n,p,q,x,y,u,v,r,tc,t;

    cin>>m>>n;
    
    if(n==1)
    {
        cout<<0<<endl;
        return 0;
    }

    vector<int>vv;

    p = m;

    for(i=1; i<=100; i++)
    {
        vv.push_back(m);
        m+=p-1;
    }

    for(i=0; i<vv.size();i++)
    {
        if(vv[i]>=n)
            break;
    }

    cout<<i+1<<endl;

  //  main();

    return 0;
}

// read the question correctly (is y a vowel? what are the exact constraints?)
// look out for SPECIAL CASES (n=1?) and overflow (ll vs int?)


Measured memory_bytes: 256
# ABC133D - Rain Flows into Dams
def main():
    # X_0 = sum(A) - 2 * sum(A[1::2]), X_i = 2Ai - X_{i-1}
    N, *A = map(int, open(0).read().split())
    X = [0] * N
    cur = sum(A) - 2 * sum(A[1::2])
    X[0] = cur
    for i, a in enumerate(A[:-1], 1):
        X[i] = a * 2 - cur
        cur = X[i]
    print(" ".join(map(str, X)))


if __name__ == "__main__":
    main()

Measured memory_bytes: 19212
#include<bits/stdc++.h>
#define rep(i,n) for (long long i = 0; i < (n); ++i)
//g++ -std=c++11 

using namespace std;

long long N;

// (head, tail) -> count
map<pair<long long, long long>, long long> memo;

int main(){
	cin >> N;
	rep(i, N+1) {
		string S = to_string(i);
		long long head = S[0] - '0';
		long long tail = S[S.size() - 1] - '0';
		if(head != 0 && tail != 0) {
			memo[make_pair(head, tail)]++;
		}
	}

	long long ans = 0;
	for(long long head = 1; head < 10; head++) {
		for(long long tail = 1; tail < 10; tail++) {
			ans += memo[make_pair(head, tail)] * memo[make_pair(tail, head)];
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 3676
#include <bits/stdc++.h>
#define rep(i, n) for(ll i = 0; i < n; i++)
#define repr(i, n) for(ll i = n; i >= 0; i--)
#define reprr(i, m, n) for (ll i = m; i < n; i++)
#define inf 2e9
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;


int main()
{
    ll N; cin >> N;
    ll M = 1e9+7;
    vector<ll> dp[4][4][4];
    // A -> 0, G -> 1, C -> 2, T -> 3

    rep(i, 4) rep(j, 4) rep(k, 4) {
        dp[i][j][k].resize(N+1, 0);
        if ((i == 0 && j == 1 && k == 2) || 
            (i == 0 && j == 2 && k == 1) || 
            (i == 1 && j == 0 && k == 2)) dp[i][j][k][3] = 0;
        else dp[i][j][k][3] = 1;
    }

    reprr(n, 3, N) rep(i, 4) rep(j, 4) rep(k, 4) rep(m, 4) {
        if (j == 0 && k == 2 && m == 1) continue;
        else if (
            ((j == 0 && k == 1) ||
            (i == 0 && k == 1) ||
            (j == 1 && k == 0) ||
            (i == 0 && j == 1)
            ) && m == 2
        ) continue;
        dp[j][k][m][n+1] = (dp[j][k][m][n+1] + dp[i][j][k][n]) % M;
    }

    ll cnt = 0;
    rep(i, 4) rep(j, 4) rep(k, 4) cnt = (cnt + dp[i][j][k][N]) % M;
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=2e5+500;
int p[N],siz[N],n,m;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)siz[i]=1;p[1]=1;
    for(int i=1,x,y;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        if(p[x])p[y]=1;
        if(siz[x]==1)p[x]=0;
        ++siz[y],--siz[x];    
    }
    int ans=0;
    for(int i=1;i<=n;i++)if(p[i])++ans;
    cout<<ans<<endl;
}

Measured memory_bytes: 4432
n = int(input())
h = [int(x) for x in input().split(' ')]

i = 1
lc = []
c = 0

while i < len(h):
    if h[i-1] >= h[i]:
        c += 1
    else:
        lc.append(c)
        c = 0
    i += 1
lc.append(c)
print(max(lc))

Measured memory_bytes: 14224
#define watch5(a,b,c,d,e) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d << " | "<<#e<<": "<<e<<endl;
#define watch4(a,b,c,d) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl;
#define watch3(a,b,c) cerr <<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<endl;
#define printclock cerr<<"Time : "<<1000*(ld)clock()/(ld)CLOCKS_PER_SEC<<"ms\n";
#define sharingan cerr << "\n-------------------------------------------\n\n";
#define watch2(a,b) cerr <<#a<<": "<<a<<" | "<<#b<<": "<<b<< endl;
#define Yup ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define watch(a) cerr <<#a<<": "<<a<<endl;
#define __gcd(a, b) __algo_gcd(a, b)
#define PI 3.14159265358979323846
#define mod 1000000007
#include "bits/stdc++.h"
using namespace std;
#define int long long

int32_t main(){
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    int x = a*c;
    int y = a*d;
    int z = b*c;
    int o = b*d;
    cout << max(max(x,y), max(z, o));
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define endl "\n"
#define pb push_back
#define f(i,n) for(i=0;i<n;i++)
#define F(i,a,b) for(i=a;a<=b;i++)
#define arr(a,n) for( i=0;i<n;i++)cin>>a[i];
#define fi first
#define se second
#define mp make_pair
#define mod 1000000007
#define YES cout<<"YES"<<endl;
#define Yes cout<<"Yes"<<endl;
#define NO cout<<"NO"<<endl;
#define No cout<<"No"<<endl;
#define yes cout<<"yes"<<endl;
#define no cout<<"no"<<endl;
#define vi vector<ll>
#define ed end()
#define bg begin()
#define sz size()
#define ln length()
#define s() sort(a,a+n);
#define sr() sort(a,a+n,greater<ll>());
#define v()  sort(v.begin(),v.end());
#define vr() sort(v.begin(),v.end(),greater<ll>());
#define mod 1000000007
#define fast() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
ll gcd(ll a, ll b){if(!b)return a;return gcd(b, a % b);}
ll power(ll x,ll y,ll p){ll res=1;x%=p;while(y>0){if(y&1)res=(res*x)%p;y=y>>1;x=(x*x)%p;}return res;}
int main() {
    /*#ifndef ONLINE_JUDGE
        // for getting input from input.txt
        freopen("input.txt", "r", stdin);
        // for writing output to output.txt
        freopen("output.txt", "w", stdout);
    #endif*/
        /* 
        Ofcourse it's Hard.
        It's supposed to be Hard.
        If it's easy everyone would do it.
        HARD IS WHAT MAKES IT GREAT

        YESTERDAY U SAID TOMORROW

        SLOWLY BECOMING THE PERSON I 
        SHOULD HAVE BEEN A LONG TIME AGO

        SAME TASK CAN'T BE FOUND DIFFICULT TWICE

        BTBHWSITW

        SPRH TU KAB P

        CP IS ALL ABOUT THINKING 
        YOU HAVE MUCH MORE POTENTIAL THAN U THINK

        AJIT SHIDDAT 10

        UR DAILY ROUTINE 


        */

fast();
//ll t;cin>>t;while(t--)
{
    ll n,m,s=0;
    cin>>n>>m;
    ll a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        s+=a[i];
        
    }
    sort(a,a+n,greater<ll>());
    double d=s/double(4*m);
    if(a[m-1]<d)
        No
    else
        Yes

    
}
return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <math.h>
#include <iomanip>
#include <limits>
#include <list>
#include <queue>
#include <tuple>
#include <map>
using namespace std;
#define MOD (long long int)(1e9+7)
#define ll long long int
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define reps(i,n) for(int i=1; i<=(int)(n); i++)
#define REP(i,n) for(int i=n-1; i>=0; i--)
#define REPS(i,n) for(int i=n; i>0; i--)
#define ALL(x) (x).begin(),(x).end()
#define INF (int)(1123456789)
#define LINF (long long int)(112345678901234567)

ll modpow(ll x, ll n) {
    if(n==0){
        return 1;
    }else if(n%2==0){
        ll h = modpow(x,n/2);
        return h * h % MOD;
    } else {
        return x * modpow(x,n-1) % MOD;
    }
}

int main() {
  int N; cin >> N;
  vector<int> W;
  rep(i,N){
    int w; cin >> w;
    W.push_back(w);
  }
  int up = 0;
  int down = 0;
  rep(i,N){
    up += W[i];
  }
  int sum = up;
  REPS(i,N-1){
    up -= W[i];
    down += W[i];
    sum = min(sum, abs(up-down));
  }

  cout << sum << endl;

  return 0;
}


Measured memory_bytes: 256
/*--iを++1で書き換えると？*/
#include <iostream>
using namespace std;
 
int main() {
    int n,flag,tmp, count;
    cin >> n;
    int A[n];
    for (int i = 0; i < n; ++i)
    {
        cin >> A[i];
    }
    flag = 1;
    count = 0;
    while(flag){
        flag = 0;
        for (int i = 1; i < n; ++i)
        {
            if (A[n-i] < A[n-i-1])
            {
                tmp = A[n-i];
                A[n-i] = A[n-i-1];
                A[n-i-1] = tmp;
                count +=1;
                flag = 1;
            }
        }
    }
    for (int i = 0; i < n; ++i)
    {
        cout  << A[i];
        if(i < n-1) cout << " ";
    }
    cout << endl;
    cout << count << endl;
    return 0;
}

Measured memory_bytes: 1160
# include "bits/stdc++.h"
using namespace std;
using LL = long long;
using ULL = unsigned long long;
const double PI = acos(-1);
template<class T>constexpr T INF() { return ::std::numeric_limits<T>::max(); }
template<class T>constexpr T HINF() { return INF<T>() / 2; }
template <typename T_char>T_char TL(T_char cX) { return tolower(cX); };
template <typename T_char>T_char TU(T_char cX) { return toupper(cX); };
const int vy[] = { -1, -1, -1, 0, 1, 1, 1, 0 }, vx[] = { -1, 0, 1, 1, 1, 0, -1, -1 };
const int dx[4] = { -1,0,1,0 }, dy[4] = { 0,-1,0,1 };
const char dir[4] = { 'u','l','d','r' };
int popcnt(unsigned long long n) { int cnt = 0; for (int i = 0; i < 64; i++)if ((n >> i) & 1)cnt++; return cnt; }
int d_sum(LL n) { int ret = 0; while (n > 0) { ret += n % 10; n /= 10; }return ret; }
int d_cnt(LL n) { int ret = 0; while (n > 0) { ret++; n /= 10; }return ret; }
LL gcd(LL a, LL b) { if (b == 0)return a; return gcd(b, a%b); };
LL lcm(LL a, LL b) { LL g = gcd(a, b); return a / g*b; };
# define ALL(qpqpq)           (qpqpq).begin(),(qpqpq).end()
# define UNIQUE(wpwpw)        (wpwpw).erase(unique(ALL((wpwpw))),(wpwpw).end())
# define LOWER(epepe)         transform(ALL((epepe)),(epepe).begin(),TL<char>)
# define UPPER(rprpr)         transform(ALL((rprpr)),(rprpr).begin(),TU<char>)
# define FOR(i,tptpt,ypypy)   for(LL i=(tptpt);i<(ypypy);i++)
# define REP(i,upupu)         FOR(i,0,upupu)
# define INIT                 std::ios::sync_with_stdio(false);std::cin.tie(0)
# pragma warning(disable:4996)

int n, m;
int a[101010];
int b[101010];
vector<pair<LL, LL>> c;
const int mod = 1e9 + 7;

class Segment_Tree {
private:
	int n;
	vector<LL> date;
	LL Rec(int a, int b, int k, int l, int r) {
		if (r <= a || b <= l) return 0;
		if (a <= l&&r <= b) return date[k];
		int m = (l + r) / 2;
		return (Rec(a, b, k * 2 + 1, l, m) + Rec(a, b, k * 2 + 2, m, r)) % mod;
	}
public:
	Segment_Tree(int n_) {
		n = 1;
		while (n<n_) n *= 2;
		date = vector<LL>(2 * n - 1,0);
	}
	void Update(int k, int x) {
		k += n - 1;
		(date[k] += x) %= mod;
		while (k>0) {
			k = (k - 1) / 2;
			date[k] = (date[k * 2 + 1] + date[k * 2 + 2]) % mod;
		}
	}
	LL Query(int a, int b) {
		return Rec(a, b, 0, 0, n);
	}
	LL Open(int k) {
		return date[k + n - 1];
	}
};

bool calc(pair<LL, LL> p, pair<LL, LL> q) {
	if (p.first == q.first)return p.second > q.second;
	return p < q;
}

int main() {
	cin >> n >> m;
	REP(i, n)cin >> a[i];
	REP(i, m)cin >> b[i];
	REP(i, n) {
		int it = lower_bound(b, b + m, a[i]) - b;
		if (it == 0 || it == m)continue;
		c.emplace_back(make_pair(b[it] - a[i], a[i] - b[it - 1]));
	}
	sort(ALL(c));
	UNIQUE(c);
	sort(ALL(c), calc);
	vector<LL> d;
	int N = c.size(), id = 1;
	REP(i, N)d.emplace_back(c[i].second);
	sort(ALL(d));
	UNIQUE(d);
	map<LL, LL>mp;
	REP(i, d.size()) {
		if (mp.find(d[i]) == mp.end()) {
			mp[d[i]] = id;
			id++;
		}
	}
	REP(i, N)c[i].second = mp[c[i].second];
	Segment_Tree seg(N+1);
	seg.Update(0, 1);
	LL ans = 1;
	REP(i, N) {
		LL t = seg.Query(0,c[i].second);
		seg.Update(c[i].second, t);
		ans += t;
		ans %= mod;
	}
	cout << ans%mod << endl;
}

Measured memory_bytes: 11248
// abc149_c
#include <bits/stdc++.h>
#ifdef LOCAL
#include "../cxx-prettyprint/prettyprint.hpp"
#endif
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;

#define REP(i, n) for (int (i) = 0 ; (i) < (int)(n) ; ++(i))
#define REPN(i, m, n) for (int (i) = m ; (i) < (int)(n) ; ++(i))
#define REP_REV(i, n) for (int (i) = (int)(n) - 1 ; (i) >= 0 ; --(i))
#define REPN_REV(i, m, n) for (int (i) = (int)(n) - 1 ; (i) >= m ; --(i))
#define ALL(x) x.begin(), x.end()

#define INF ((1 << 29)-1)
#define MOD (1000000007)

#define print2D(h, w, arr) REP(i, h) { REP(j, w) cout << arr[i][j] << " "; cout << endl; }
#define print_line(vec, n) {for(int i=0;i<(n-1);i++) cout << (vec)[i] << " "; cout << (vec)[(n)-1] << endl;}
template<class T> void print(const T& x){cout << x << endl;}
template<class T, class... A> void print(const T& first, const A&... rest) { cout << first << " "; print(rest...); }
struct PreMain {PreMain(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(20);}} premain;

#define MAX_N 200000

bool is_prime[MAX_N];

void seive(void) {
    REP(n, MAX_N) is_prime[n] = true;
    is_prime[0] = is_prime[1] = false;
    REPN(n, 2, MAX_N){
        if (!is_prime[n]) continue;

        for (int i = 2; n * i <= MAX_N;i++) {
            is_prime[n * i] = false;
        }
    }
}

int main() {
#ifdef LOCAL
    ifstream in("../arg.txt"); cin.rdbuf(in.rdbuf());
#endif

    int X;
    cin >> X;

    seive();

    while (true){
        if (is_prime[X]){
            print(X);
            return 0;
        }
        X++;
    }

    return 0;
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 lll;
const int N=105;
int n,a,b,i,j,fa[N],md[N],mdd;
pair<int,lll>ans;
vector<int>e[N];
void getfa(int x){for(int y:e[x])if(y!=fa[x])fa[y]=x,getfa(y);}
void dfs(int x,int fa,int d){
	mdd=max(mdd,d);md[d]=max(md[d],int(e[x].size()-(fa>0)));
	for(int y:e[x])if(y!=fa)dfs(y,x,d+1);
}
int main(){
	scanf("%d",&n);
	for(i=1;i<n;++i)scanf("%d%d",&a,&b),e[a].push_back(b),e[b].push_back(a);
	getfa(1);ans.first=N;
	for(i=1;i<=n;++i){
		mdd=0;memset(md,0,sizeof md);
		dfs(i,0,1);
		lll v=1;for(j=1;j<mdd;++j)v*=md[j];ans=min(ans,make_pair(mdd,v));
	}
	for(i=2;i<=n;++i){
		mdd=0;memset(md,0,sizeof md);
		dfs(i,fa[i],1);dfs(fa[i],i,1);
		lll v=2;for(j=1;j<mdd;++j)v*=md[j];ans=min(ans,make_pair(mdd,v));
	}
	printf("%d %lld\n",ans.first,ll(ans.second));
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <map>

using ll = long long;

using namespace std;

int main() {
    int n;
    cin >> n;
    map<string, int> m;
    int best = 0;
    for (int i=0; i<n; i++) {
        string s; cin >> s;
        m[s]++;
        best = max(best, m[s]);
    }
    for (auto &p:m)
        if (p.second == best) cout << p.first << '\n';
    return 0;
}

Measured memory_bytes: 25216
// oh, the less I know the better
// corner cases // int vs ll // cin vs scanf // clear structures // statement // doublesz
#include <bits/stdc++.h>
#define endl '\n'
#define fst first
#define snd second
#define pb push_back
#define sz(x) int(x.size())
#define REP(i,n) for(int i = 0; i < int(n); ++i)
#define trace(x) cout << #x << " = " << x << endl
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
const int N = 2e5+20, MOD = 1e9+7;

template<typename T, T mod>
struct Tint{
	T val;
	Tint(): val(0){}
	Tint(long long x){ x %= mod; if(x < 0) x += mod; val = x; }
	// basic operations
	Tint& operator += (Tint oth){ val += oth.val; if(val >= mod) val -= mod; return *this; }
	Tint& operator -= (Tint oth){ val -= oth.val; if(val < 0) val += mod; return *this; }
	Tint& operator *= (Tint oth){ val = (long long)(val) * oth.val % mod; return *this; }
	Tint operator + (Tint oth) const{ return Tint(*this) += oth; }
	Tint operator - (Tint oth) const{ return Tint(*this) -= oth; }
	Tint operator * (Tint oth) const{ return Tint(*this) *= oth; }
};

using Mint = Tint<int,MOD>;

Mint fact[N], ifact[N];

Mint bpow(Mint x, ll p){
	Mint ans;
	for(ans = 1; p; p >>= 1, x = x*x)
		if(p&1) ans = ans * x;
	return ans;
}

void build(){
	fact[0] = ifact[0] = 1;
	for(int i = 1; i < N; ++i){
		fact[i] = fact[i-1] * i;
		ifact[i] = bpow(fact[i],MOD-2);
	}
}

Mint comb(ll n, ll k){ return fact[n] * ifact[k] * ifact[n-k]; }
Mint ways(ll x, ll y){ return comb(x+y,x); }

int main(){

	fastio;
	build();
	int h,w,n;
	cin >> h >> w >> n;
	vector<ii> pts(n);
	for(int i = 0; i < n; ++i){
		cin >> pts[i].fst >> pts[i].snd;
		pts[i].fst--; pts[i].snd--;
	}
	pts.pb(ii(h-1,w-1));
	sort(pts.begin(),pts.end());

	vector<Mint> dp(sz(pts),1);
	for(int i = 0; i < sz(dp); ++i){
		dp[i] = ways(pts[i].fst,pts[i].snd);
		for(int j = 0; j < i; ++j){
			if(pts[j].fst <= pts[i].fst && pts[j].snd <= pts[i].snd){
				dp[i] -= ways(pts[i].fst-pts[j].fst, pts[i].snd-pts[j].snd) * dp[j];
			}
		}
	}

	cout << dp.back().val << endl;

	return 0;
}


Measured memory_bytes: 5240
#include<iostream>

using namespace std;

int func(int a, int x){
  return a+(a*x/100);
}

int main(void){

  int x,y,s;
  while(cin >> x >> y >> s, x|y|s){

    int ans=0;
    
    for(int i=1;i<1000;i++){
      for(int j=1;j<1000;j++){
	if(func(i,x)+func(j,x)==s){
	  ans = max(ans, func(i,y) + func(j,y));
	}
      }
    }
    cout << ans << endl;
  }
  
  return 0;
}

Measured memory_bytes: 3104
#include <bits/stdc++.h>
using namespace std;


void solve(long long x){
    cout << !x << endl;
}

// Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    long long x;
    scanf("%lld",&x);
    solve(x);
    return 0;
}


Measured memory_bytes: 3688
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long int a,b,c,k;
    cin>>a>>b>>c>>k;
    long long int sum=0;
    if(a>=k)
    {
        sum=k;
        cout<<sum<<endl;
    }
    else
    {
        sum=sum+a;
        k=k-a;
        if(b>=k)
        {
            sum=sum+0;
            cout<<sum<<endl;
        }
        else
        {
            sum=sum+0;
            k=k-b;
            if(c>=k)
            {
                sum=sum-k;
                cout<<sum<<endl;
            }
            else
            {
                sum=sum-c;
                cout<<sum<<endl;
            }
        }
    }
}

Measured memory_bytes: 3636
#include <iostream>
#include <cmath>
#include <vector>
#include <string>
#include <map>
#include <algorithm>
#include <tuple>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <cstdio>
#include <numeric>
#define REP(i, n) for(LL i = 0;i < n;i++)
#define REPR(i, n) for(LL i = n;i >= 0;i--)
#define FOR(i, m, n) for(LL i = m;i < n;i++)
#define FORR(i, m, n) for(LL i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define pb(a) push_back(a)
#define all(x) (x).begin(),(x).end()
#define INF (LL)1e15
#define MOD 1000000007
using namespace std;
typedef long long LL;
typedef pair<int, int> P;
typedef pair<LL, LL> LP;
typedef pair<int, P> PP;
typedef pair<LL, LP> LPP;
int dy[]={0, 0, 1, -1, 0};
int dx[]={1, -1, 0, 0, 0};

/*************** using variables ***************/
int n;
vector<LL> t;
/**********************************************/

LL euclidean(LL a, LL b){
    if(a < b) swap(a, b);
    LL r = a % b;
    while(r != 0){
        a = b;
        b = r;
        r = a % b;
    }

    return b;
}

LL gcd(LL a, LL b){
    return euclidean(a, b);
}

LL lcm(LL a, LL b){
    LL g = gcd(a, b);
    return a / g * b;
}

int main(){
    cin >> n;
    t.resize(n+5);
    REP(i, n) cin >> t[i];

    LL ans = 1LL;
    REP(i, n){
        ans = lcm(ans, t[i]);
    }

    cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>

using namespace std;

#define INF (1 << 30)
#define EPS 1e-10
#define MOD 1000000007

#define rep(i, n) FOR(i, 0, n)
#define FOR(i, x, n) for (int i = (x); i < (n); ++i)
#define all(v) (v).begin(), (v).end()

using ll = long long;

template<class T> void chmax(T& a, T b){ if (a < b) { a = b; } }
template<class T> void chmin(T& a, T b){ if (a > b) { a = b; } }

int a[200000], b[200000];

int main() {
    int n, c, d;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> a[i] >> b[i];
    }
    sort(a, a + n);
    sort(b, b + n);
    if (n % 2) {
        c = a[n / 2];
        d = b[n / 2];
    }
    else {
        c = a[n / 2 - 1] + a[n / 2];
        d = b[n / 2 - 1] + b[n / 2];
    }
    cout << d - c + 1 << endl;

    return 0;
}

Measured memory_bytes: 5036
#include<iostream>
using namespace std;
#define int long long

signed main(){
	int n;
	cin >> n;
	int x[n],y[n],h[n];
	int cx,cy,high,cnt=0;
	int ansX,ansY,ansH;

	for(int i=0;i<n;i++){
		cin>>x[i]>>y[i]>>h[i];
		if(h[i]!=0){
			ansX=x[i];ansY=y[i];ansH=h[i];
		}
	}
	for(int cx=0;cx<101;cx++){
		for(int cy=0;cy<101;cy++){
			cnt = 0;
			for(int i=0;i<n;i++){
				high = ansH + abs(ansX-cx)+abs(ansY-cy);
				high = max(0LL,high);
				if(h[i]==max(0LL,high-abs(x[i]-cx)-abs(y[i]-cy)))cnt++;
			}
			if(cnt==n){
				ansX=cx;ansY=cy;ansH=high;
				break;
			}
		}
	}
	cout<<ansX<<" "<<ansY<<" "<<ansH<<endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;

int main(){
	string s,aux;
	int k;
	cin >> k >> s;
	if(s.size() <= k){
		cout << s << endl;
	}else{
		for(int i = 0; i<k; i++){
			aux.push_back(s[i]);
		}
		
		cout << aux << "..." << endl;;
		
	}
   return 0; 
}



Measured memory_bytes: 3644
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define FOR(i, s, n) for (int i = (s); i < (n); i++)
#define RFOR(i, s, n) for (int i = (n) - 1; i >= (s); i--)
#define REP(i, n) FOR(i, 0, n)
#define RREP(i, n) RFOR(i, 0, n)
#define ALL(a) a.begin(), a.end()
const long long MOD = 1e9+7, INF = 1e18;
template<class T>inline bool CHMAX(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T>inline bool CHMIN(T&a,T b){if(a>b){a=b;return true;}return false;}

int dp[200020][2];

signed main(){
	string s;
	cin>>s;
	int N = s.size();
	REP(i,200020)REP(j,2)dp[i][j]=0;
	dp[1][0]=1;
	dp[2][1]=1;
	FOR(i,1,s.size()){
		REP(j,2){
			if(i-j-1<0)continue;
			if(dp[i][j]==INF)continue;
			string t = s.substr(i-j-1,j+1);
			if(t.size()!=j+1)continue;
			if(s.substr(i,1)!=t)CHMAX(dp[i+1][0],1+dp[i][j]);
			if(i+1!=s.size()&&s.substr(i,2)!=t)CHMAX(dp[i+2][1],1+dp[i][j]);
		}
	}
	cout<<max(dp[s.size()][0],dp[s.size()][1])<<endl;
}


Measured memory_bytes: 3716
#include <iostream>
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define F first
#define S second
#define fo(i,a,b)  for(int i = a; i < b; i++)

using ll = long long;
using ld = long double;
using ul = unsigned long long;
using ii = pair<int, int>;
#define Mosta     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ReadFile            freopen("input.in","r",stdin)
#define WriteFile           freopen("output.txt","w",stdout)
const ll mod7 = 1000000007,mod = 1000000000,OO = 0x3f3f3f3f;
const ld EPS = 1e-7;
double Pi=acos(-1);
const ld rad=Pi/180.0;
ll power(ll x, ll y, ll p)
{
    ll res = 1;
    while (y > 0)
    {
        if (y & 1)
            res = (res*x) % p;
        y = y>>1;
        x = (x*x) % p;
    }
    return res;
}
ll nCr (ll n,ll m)
{
        return(m == 0)?1:n*nCr(n-1,m-1)/m;
}
/*****************************************************/

int main()
{
    int n;
    vector<pair<int , int>> vec;
    cin >> n;

    for(int i = 1; i <= n; ++i){
        int x;
        cin >> x;
        vec.push_back(make_pair(x, i));
    }

    sort(vec.begin() , vec.end());

    for(int i = 0; i < n; ++i)
        cout << vec[i].second << " ";

    return 0;
}


Measured memory_bytes: 1780
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n;
	while(cin>>n,n){
		bool l = false,r = false,now = true;
		int cnt = 0;
		for(int i = 0;i < n;i++){
			string f;
			cin>>f;
			if(f[0] == 'l')l = !l;
			if(f[0] == 'r')r = !r;
			if(l==r && r==now){
				now = !now;
				cnt++;
			}
			//cout<<"#"<<l<<" "<<r<<" "<<now<<endl;
		}
		cout<<cnt<<endl;
	}
}

Measured memory_bytes: 1200
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <numeric>
#include <utility>
#include <string>
#include <bitset>

using namespace std;

int main() {
	int d, g;
	cin >> d >> g;
	g /= 100;

	vector<int> p(d, 0), c(d, 0);
	for (int i = 0; i < d; i++) {
		cin >> p[i] >> c[i];
		c[i] /= 100;
	}

	int ans = 1e9;
	int limit = 1 << d;
	for (int i = 0; i < limit; i++) {
		vector<bool> completes(d, false);
		int rest = g;
		int n_solve = 0;

		for (int j = 0; j < d; j++) {
			if ((i >> j) & 1) {
				completes[j] = true;
				rest -= p[j] * (j + 1) + c[j];
				n_solve += p[j];
			}
		}

		for (int k = d - 1; k >= 0; k--) {
			if (rest <= 0) {
				break;
			} else if (completes[k]) {
				continue;
			}

			int tmp = min(p[k] - 1, (rest + k) / (k + 1));
			n_solve += tmp;
			rest -= tmp * (k + 1);
		}

		if (rest <= 0) {
			ans = min(ans, n_solve);
		}
	}

	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include <vector>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include <cstdio>
#include <queue>
#include<stack>

using namespace std;

int main() {
	int n;
	long long x;
	cin >> n;
	int * a = new int[n];
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}

	long long s = 0;
	for (int j = 0; j < n; j++)
		s += a[j]-1;
	cout << s;
	return 0;
}


Measured memory_bytes: 384