akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<cstdio>
using namespace std;
int main(){
    int a,b;
    for(;;){
        int dp[20][20] = {{0}};
        scanf("%d%d",&b,&a);
        if(a == 0 && b == 0)break;
        int n;
        scanf("%d",&n);
        int y,x;
        int check[20][20] = {{0}};
        for(int i = 0;i < n; i++){
            scanf("%d%d",&y,&x);
            check[y][x] = 1;
        }
        dp[1][0] = 1;
        for(int i = 1;i <= b; i++){
            for(int j = 1;j <= a; j++){
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
                if(check[i][j] != 0)dp[i][j] = 0;
            }
        }
        printf("%d\n",dp[b][a]);
    }
        return 0;
}

Measured memory_bytes: 1188
#include<stdio.h>

int main(){
  int n,a,b,i,min=1000,sum=0;
  scanf("%d",&n);
  for(i=1;i<n;i++){
    a=i;
    b=n-i;
    sum=0;
    while(a||b){
      sum+=a%10;
      sum+=b%10;
      a/=10;
      b/=10;
    }
    if(min>sum)
      min=sum;
  }
  printf("%d\n",min);
}

Measured memory_bytes: 128
#include <iostream>
#include <string>
using namespace std;

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

    string S;
    int* ans=new int[4];
    for(int i=0;i<4;i++){
        ans[i]=0;
    }
    for(int i=0;i<N;i++){
        cin>>S;
        if(S=="AC"){ans[0]++;};
        if(S=="WA"){ans[1]++;};
        if(S=="TLE"){ans[2]++;};
        if(S=="RE"){ans[3]++;};

    }

    cout<<"AC x "<<ans[0]<<endl;
    cout<<"WA x "<<ans[1]<<endl;
    cout<<"TLE x "<<ans[2]<<endl;
    cout<<"RE x "<<ans[3]<<endl;

    return 0;
}

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

using namespace std;

int main()
{
    int n,m;
    bool flag=true;
    cin>>n>>m;
    char x[n][n],z[m][m];
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            cin>>x[i][j];

    for(int i=0; i<m; i++)
        for(int j=0; j<m; j++)
        {
            cin>>z[i][j];
        }

    for(int i=0; i<n; i++)
    {
        for(int j=0; j<n; j++)
        {

                flag=true;
            for(int w=i,k=0; w<m+i; k++,w++)
            {
                for(int q=j,k2=0; q<m+j; k2++,q++)
                {
                    if(x[w][q]!=z[k][k2])
                        flag=false;


                }
            }
            if(flag)
                return cout<<"Yes", 0;
        }
    }



    cout<<"No";
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	vi a(n + 1);
	for(auto &x: a){
		cin >> x;
	}
	vi b(n);
	for(auto &x: b){
		cin >> x;
	}
	ll res = 0, rem = 0;
	for(int i = 0; i < n; i ++){
		if(rem >= a[i]){
			rem = b[i];
			res += a[i];
		}
		else{
			rem += b[i];
			if(rem >= a[i]){
				rem -= a[i];
				res += a[i];
			}
			else{
				res += rem;
				rem = 0;
			}
		}
	}
	if(rem >= a[n]){
		res += a[n];
	}
	else{
		res += rem;
	}
	cout << res;
	return 0;
}

Measured memory_bytes: 1024
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

typedef long long ll;

int main(){
  ll N; cin >> N;
  vector<pair<ll,ll>> BA(N);
  for(ll i = 0; i < N; i++){cin >> BA[i].second  >> BA[i].first;}
  
  sort(BA.begin(),BA.end());
   ll sum = 0;
  bool flag = true;
  for(ll i = 0; i < N; i++){
    sum += BA[i].second;
    if(sum > BA[i].first){ flag = false; break;}}
  
  if( !flag){ cout << "No" << endl;}
else{ cout << "Yes" << endl;}
  return 0;}

Measured memory_bytes: 3328
import sys

stdin = sys.stdin

ns = lambda: stdin.readline()
ni = lambda: int(ns())
na = lambda: list(map(int,stdin.readline().split()))

MOD = 10**9+7

class Comb:
    def __init__(self, size):
        self.fact = [0 for i in range(size + 1)]
        self.inv_fact = [0 for i in range(size + 1)]
        self.factrical(size)

    def nCr(self, n,r):
        ret = self.fact[n]
        ret *= self.inv_fact[n-r]
        ret %= MOD
        ret *= self.inv_fact[r]
        ret %= MOD
        return ret

    def factrical(self, N):
        self.fact[0] = 1
        self.inv_fact[0] = 1
        for i in range(1,N+1):
            self.fact[i] = i * self.fact[i-1] % MOD
            self.inv_fact[i] = self.inv(self.fact[i]) % MOD

    def inv(self, a):
        return pow(a, MOD-2, MOD)

N = ni()
a = na()
c = [-1 for i in range (N)]
index = [-1,-1]

for i, x in enumerate(a):
    if (c[x-1]!=-1):
        index[0] = c[x-1]
        index[1] = i
        break

    c[x-1] = i

co = Comb(N+1)
for i in range(1, N+2):
    ans = co.nCr(N+1,i)
    if ((N-index[1]) + (index[0])>=i-1 ):
        ans -= co.nCr((N-index[1]) + (index[0]),i-1) 
        
    print (ans%MOD)     
            



Measured memory_bytes: 20456
#include <stdio.h>
#include <limits.h>

int main(void){

    int N;
    int M;
    scanf("%d",&N);
    scanf("%d",&M);
    
    long long int A[M];
    long long int B[M];
    
    for(int i=0;i<M;i++){
        scanf("%lld",&A[i]);
        scanf("%lld",&B[i]);
        A[i]--;
        B[i]--;
    }
    
    long long int parent [N];
    long long int size[N];
   
    for (int i=0;i<N;i++){
        parent[i]=i;
        size[i]=1;
    }
   
    long long int key;
    long long int keyone;
    long long int keytwo;
    long long int keythree;
    for(int j=0;j<M;j++){
        
        key = B[j];
        
        while( key !=  parent[key] ){
        key = parent[key];
        }
    
        keyone = A[j];
        
        while(keyone != parent[keyone]){
            keyone = parent[keyone];
        }
        
        parent[key]= keyone;
        
        keytwo = B[j];
        while(keyone != keytwo){
            keythree = keytwo;
             keytwo = parent[keytwo];
            parent[keythree] = keyone;
        }
        
        
        
        
}
    
    
    
    
    long long int answer = -1;
    
    for(int k=0;k<N;k++){
        if(parent[k]==k){
            answer++;
        }
    }

    printf("%lld",answer);
    
    
    
    
    return 0;
}



Measured memory_bytes: 4820
#! -*- coding: utf-8 -*-

import numpy as np

n = int(raw_input())
p = np.zeros([n,2],dtype=int)
for i in range(n):
    p[i] = map(int,raw_input().split())

#print p

s = np.zeros([n])

for i in range(n):
    katamuki = np.zeros([n])
    for j in range(n):
        if not i == j:
            vec = np.array([p[j][0]-p[i][0],p[j][1]-p[i][1]])
            xvec = np.array([1,0])
            katamuki[j] = np.arccos((np.dot(xvec,vec))/(np.linalg.norm(vec)))
        if p[j][1]-p[i][1] < 0:
            katamuki[j] = 2*np.pi - katamuki[j]
    #print katamuki
    katamuki = np.sort(katamuki)
    for j in range(n-1):
        if j == 0:
            kakudo = katamuki[1]+(2*np.pi-katamuki[n-1])
        else:
            kakudo = katamuki[j+1]-katamuki[j]
        if kakudo > np.pi:
            s[i] = kakudo-np.pi

#print s
ans = s / (2*np.pi)
#print ans
for line in ans:
    print line


Measured memory_bytes: 16388
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <map>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i=0;i < (int)(n);i++)
struct edge{int from,to;
            ll cost;};
edge es[2002];
ll d[1002];
bool neg[1001];
int V,E;
const ll INF = (1LL << 61);

void find_negative_loop(int s){
    for (int i=0;i < V;i++) d[i] = INF;
    d[s] = 0;
    for (int i=0;i < V;i++){
        for (int j = 0;j < E;j++){
            edge e =es[j];
            if ( d[e.from] != INF && d[e.to] >  d[e.from] + e.cost){
                d[e.to] = d[e.from] + e.cost;
                if (i == V-1 ) return;
            }
        }
    }
    return;
}
void f(){
    for (int i=0;i < V;i++){
        for (int j = 0;j < E;j++){
            edge e = es[j];
            if (d[e.from] != INF && d[e.to] >  d[e.from] + e.cost){
                d[e.to] = d[e.from] + e.cost;
                neg[e.to] = true;
            }
            if (neg[e.from] == true) neg[e.to] = true;
        }
    }
}
int main(){
    cin >> V >> E;
    rep(i,E){
        int x,y;
        ll z;
        cin >> x >> y >> z;
        es[i] = {x-1,y-1,-z};
    }
    find_negative_loop(0);
    rep(i,V) neg[i] = false;
    f();
    if (neg[V-1]){
        cout << "inf" << endl;
    }
    else cout << -d[V-1] << endl;
   
    
    return 0;    
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#ifdef ENABLE_DEBUG_OUTPUT
#define DEBUG_LOG(s) cout << s << endl;
#else
#define DEBUG_LOG(s) void();
#endif

int main(){
    int n, m, q;
    cin >> n >> m >> q;

    vector<vector<int>> sum(n + 1, vector<int>(n + 1, 0));
    for (auto i = 0; i < m; i++) {
        int l, r; cin >> l >> r; sum[l][r]++;
    }

    for (auto i = 1; i <= n; i++) {
        for (auto j = 1; j <= n; j++) {
            sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
        }
    }

    for (auto i = 0; i < q; i++) {
        int l, r; cin >> l >> r;
        cout << sum[r][r] - sum[l - 1][r] << endl;
    }

    return 0;
}

Measured memory_bytes: 1920
import  java.util.HashMap;
import java.util.Scanner;
public class Main{

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		HashMap<Integer,Integer> hm = new HashMap<Integer,Integer>();
		
		int n = sc.nextInt();
		int p = 1000000007;
		
		for(int i= 0 ; i < n ;i++) {
			int a = sc.nextInt();
			if(!hm.containsKey(a)) {
				hm.put(a, 1);
			}
			else {
				hm.put(a, hm.get(a)+ 1);
			}
		}
		int tmp = -1;
		long ans = 1;
		
		for(int num : hm.keySet()) {
			if(num != 0 && hm.get(num)== 2) {
				ans = (ans * 2) % p;
			}
			else if(n % 2 == 1 && hm.get(0) == 1) {
				continue;
			}
			else {
				ans = 0;
				break;
			}
		}
		System.out.println(ans);
		

	}

}


Measured memory_bytes: 64116
#include<iostream>
using namespace std;
int main()
{
	int a;
	cin>>a;
	if(a==19 || a==29 || a==39 || a==49 || a==59 || a==69 || a==79 || a==89 || a>=90)
	{
		cout<<"Yes"<<endl;
	}
	else
	{
		cout<<"No"<<endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,a[100];
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	int v,j;
	for(int i=0;i<n;i++){
		v=a[i];
		j=i-1;
		while(j>=0&&a[j]>v){
			a[j+1]=a[j];
			j--;
		}
		a[j+1]=v;
		cout<<a[0];
		for(int k=1;k<n;k++){
			cout<<" "<<a[k];
		}
		cout<<endl;
	}
	return 0;
}



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

void printVec(vector<int> vec) {
  for (size_t i = 0; i < vec.size(); i++) {
    if (i == vec.size() - 1) {
      cout << vec[i] << endl;
    } else {
      cout << vec[i] << " ";
    }
  }
}

int main() {
  int N, cnt = 0;
  cin >> N;
  vector<int> A(N);
  for (size_t i = 0; i < N; i++) {
    cin >> A.at(i);
  }

  for (size_t i = 0; i < N; i++) {
    for (size_t j = N - 1; i < j; j--) {
      if (A[j - 1] > A[j]) {
        auto tmp = A[j];
        A[j] = A[j - 1];
        A[j - 1] = tmp;
        cnt += 1;
      }
    }
  }

  printVec(A);
  cout << cnt << endl;
}


Measured memory_bytes: 3152
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, x, y) for (int i = x; i < y; i++)
#define FORN(i, x, y) for (int i = x; i <= y; i++)
#define DEC(i, x, y) for (int i = x; i >= y; i--)
#define scan1(X) scanf("%d", &X)
#define scan2(X, Y) scanf("%d%d", &X, &Y)
#define scan3(X, Y, Z) scanf("%d%d%d", &X, &Y, &Z)
#define scan4(X, Y, Z, W) scanf("%d%d%d%d", &X, &Y, &Z, &W)
#define scanl1(X) scanf("%lld", &X);
#define scanl2(X, Y) scanf("%lld%lld", &X, &Y)
#define scanl3(X, Y, Z) scanf("%lld%lld%lld", &X, &Y, &Z)
#define scanl4(X, Y, Z, W) scanf("%lld%lld%lld%lld", &X, &Y, &Z, &W)
#define print1(X) printf("%d\n", X);
#define print2(X, Y) printf("%d %d\n", X, Y);
#define print3(X, Y, Z) printf("%d %d %d\n", X, Y, Z);
#define print4(X, Y, Z, W) printf("%d %d %d %d\n", X, Y, Z, W);
#define printl1(X) printf("%lld\n", X);
#define printl2(X, Y) printf("%lld %lld\n", X, Y);
#define printl3(X, Y, Z) printf("%lld %lld %lld\n", X, Y, Z);
#define printl4(X, Y, Z, W) printf("%lld %lld %lld %lld\n", X, Y, Z, W);
#define max3(X, Y, Z) max(X, max(Y, Z))
#define max4(X, Y, Z, W) max(max(X, Y), max(Z, W))
#define min3(X, Y, Z) min(X, min(Y, Z))
#define min4(X, Y, Z, W) min(min(X, Y), min(Z, W))
#define popcount(X) __builtin_popcount(X)
#define all(x) x.begin(), x.end()
#define size(X) (int)X.size()
#define mp make_pair
#define pb push_back
#define fr first
#define sc second
#define lc(x) 2 * x
#define rc(x) 2 * x + 1
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
typedef pair<ld, ld> pldld;
const long long l_inf = numeric_limits<long long>::max();
const long long l_ninf = numeric_limits<long long>::min();
const int inf = numeric_limits<int>::max();
const int ninf = numeric_limits<int>::min();
const double pi = 1.00 * acos(-1.00);
const double eps = 1e-8;
void cio(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
ll gcd(ll a, ll b){
    if (b == 0)
        return a;
    return gcd(b, a % b);
}
ll lcm(ll a, ll b) { return (a * (b / gcd(a, b))); }
int sq( int x ) {return x * x;}
////////////////////////////////////////////////////////////////////Header
const ll mod =  1e9 + 7;

ll pow_ ( ll x, ll n ) {
    ll ret = 1;
    while ( n ) {
        if ( n & 1 ) {
            ret = (ret * x ) % mod;
        }
        n >>= 1;
        x = (x * x) % mod;
    }
    return ret;
}

ll sub ( ll x, ll y ) {
    ll r = ( x - y ) % mod;
    if ( r < 0 ) return r + mod;
    return r;
}

ll add ( ll x, ll y ) {
    return ( x + y ) % mod;
}

int main () {
    int N;
    cin>>N;
    ll ans = add(sub(pow_(10, N), add(pow_(9, N), pow_(9, N))), pow_(8, N));
    cout<<ans<<endl;
}

Measured memory_bytes: 3620
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n, k;
    cin >> n >> k;
    double sum[n + 1];
    sum[0] = 0;
    for (int i = 1; i <= n; i++)
    {
        int faces;
        cin >> faces;
        sum[i] = sum[i - 1] + (double)(faces + 1) / 2;
    }
    double ans = -1;
    for (int i = 1; i <= (n - k + 1); i++)
    {
        ans = max(ans, sum[i + k - 1] - sum[i - 1]);
    }
    cout << setprecision(10) << ans << endl;
    return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(i,m,n) for(int i=(int)(m); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define REPL(i,m,n) for(ll i=(ll)(m); i<(ll)(n); i++)
#define repl(i,n) REP(i,0,n)
#define all(v) v.begin(), v.end()
const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 1e9+7;



int main(){
  ll N;
  cin >> N;

  ll r = (ll)sqrt(N);

  ll ans;
  while ( ( N % r ) != 0 ) {
    r--;
    if(r==1){
      ans = N-1; // (1, 1) -> (1, N)
      cout << ans << endl;
      return 0;
    }
  }
  ans = (r - 1) + ((N/r) - 1);
  // cout << r << endl;

  cout << ans << endl;

  return 0;
}


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

using namespace std;
typedef long long ll;
typedef long double ld;
typedef tuple<int, int> duo;

#define TT template<typename T>
#define ET(T) typename T::value_type
TT inline T sq(T x){return x*x;}
TT inline T In(){T x;cin>>x;return x;}
TT inline int ubnd(T&v,ET(T) x){return upper_bound(begin(v),end(v),x)-begin(v);}
TT inline int lbnd(T&v,ET(T) x){return lower_bound(begin(v),end(v),x)-begin(v);}
TT inline void sort(T&v){sort(begin(v),end(v));}
TT inline void revs(T&v){reverse(begin(v),end(v));}
TT inline void uniq(T&v){sort(v);v.erase(unique(begin(v),end(v)),end(v));}
TT inline void inpt(T&v,int n,function<ET(T)()>f=In<ET(T)>){for(v.reserve(n);n--;v.emplace_back(f()));}
TT inline void show(T&v,string d=" ",string e="\n"){int i=0;for(auto&x:v)i++&&(cout<<d),cout<<x;cout<<e;}
#undef TT
#undef ET

inline void fast_io(){ios::sync_with_stdio(0); cin.tie(0);}
inline int in(){int x;scanf("%d",&x);return x;}
inline string instr(){string x;cin>>x;return x;}
inline ll pow_mod(ll a, ll k, ll m){ll r=1;for(;k>0;a=a*a%m,k>>=1)if(k&1)r=r*a%m;return r;}
inline ll mod_inv(ll a, ll p){return pow_mod(a,p-2,p);}

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

char field[10000][8];
int main()
{
  int n;
  while (n = in()){
    int height[8] = {};
    memset(field, '.', sizeof(field));
    for (int i = 0; i < 10000; i++) field[i][0] = '0', field[i][6] = 0;
    for (int i = 0; i < n; i++){
      int d, p, q;
      cin >> d >> p >> q;
      if (d == 1){
        int h = 0;
        for (int j = 0; j < p; j++) h = max(h, height[q + j]);
        for (int j = 0; j < p; j++) field[h][q + j] = '#';
        for (int j = 0; j < p; j++) height[q + j] = h + 1;
        field[h][0] += p;
      }
      else {
        int h = height[q];
        for (int j = 0; j < p; j++){
          field[h + j][q] = '#';
          field[h + j][0]++;
        }
        height[q] += p;
      }
      bool line_delete = false;
      for (int i = 0; i < 5000; i++){
        if (field[i][0] == '0') break;
        if (field[i][0] != '5') continue;
        memmove(field[i], field[i + 1], 40000);
        i--;
        line_delete = true;
      }
      if (!line_delete) continue;
      for (int i = 1; i <= 5; i++){
        int h = height[i];
        while (h >= 0 && field[h][i] != '#') h--;
        height[i] = h + 1;
      }
    }
    int tot = 0;
    for (int i = 0; i < 5000; i++) tot += field[i][0] - '0';
    cout << tot << "\n";
  }
  return (0);
}

// priority_queue queue deque front top push pop map set stringstream max_element min_element insert count find get tie make_tuple

Measured memory_bytes: 1328
#include <iostream>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;

int main(void) {
  ios::sync_with_stdio(false);
  string S, T;
  cin >> S >> T;

  int N = S.size();
  rep(i, N) {
    string newS = S.back() + S.substr(0, N-1);
    if(newS == T) {
      cout << "Yes" << endl;
      return 0;
    }
    S = newS;
  }
  cout << "No" << endl;
  return 0;
}

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

int main()
{
	string s;
	cin >> s;
	sort(s.begin(),s.end());
	int cnt = 0;
	for(int i = 0;i<s.size()-1;i++)
	{if(s[i]!=s[i+1])cnt++;}
	if(cnt==3||(cnt==1&&s.front()=='N'&&s.back()=='S')||(cnt==1&&s.front()=='E'&&s.back()=='W'))
	{cout<<"Yes"<<endl;}
	else 
		cout<<"No"<<endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(){
    long long n, k;
    cin >> n >> k;
    long long ans = 0;
    long long sum = 0; // 累積和
    for(int i = 1; i <= n+1; i++){
        if(i >= k){
            ans = (ans + i * n -2 * sum + 1) % 1000000007;
        }
        sum = (sum + i) % 1000000007;
    }
    cout << ans;
    return 0;
}

Measured memory_bytes: 3644
import java.util.Scanner;
    
    public class Main {
    	public static void main(String[] args){
    		Scanner sc = new Scanner(System.in);
    		// 整数の入力
    		int a = sc.nextInt();
    		
    		if(a%10==3) {
    			System.out.println("bon");
    		}else if(a%10==0||a%10==1||a%10==6||a%10==8) {
    			System.out.println("pon");
    		}else {
    			System.out.println("hon");
    		}
    		
    	}
    }

Measured memory_bytes: 35604
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define ll long long
#define rep(i,l,r)for(ll i=(l);i<(r);i++)
#define repp(i,l,r,k)for(ll i=(l);i<(r);i+=(k))
#define INF ((1LL<<62)-(1LL<<31))
#define max(p,q)((p)>(q)?(p):(q))
#define min(p,q)((p)<(q)?(p):(q))
#define bit(n,m)(((n)>>(m))&1)
int upll(const void*a, const void*b){return*(ll*)a<*(ll*)b?-1:*(ll*)a>*(ll*)b?1:0;}
int downll(const void*a, const void*b){return*(ll*)a<*(ll*)b?1:*(ll*)a>*(ll*)b?-1:0;}
void sortup(ll*a,int n){qsort(a,n,sizeof(ll),upll);}
void sortdown(ll*a,int n){qsort(a,n,sizeof(ll),downll);}
ll pom(ll a,ll n,int m){ll x=1;for(a%=m;n;n/=2)n&1?x=x*a%m:0,a=a*a%m;return x;}
ll po(ll a,int n){ll x=1;while(n--)x*=a;return x;}
//#define MOD 998244353
#define MOD 1000000007
#define invp(a,p)pom(a,p-2,p)

//行列累乗
void matpom(ll*mat,int size,ll n,int m){
	ll*temp=(ll*)malloc(size*size*sizeof(ll));
	ll*ans=(ll*)malloc(size*size*sizeof(ll));

	rep(i,0,size)rep(j,0,size)ans[i*size+j]=i==j;
	while(n){
		if(n%2){
			rep(i,0,size*size)temp[i]=0;
			rep(i,0,size)rep(j,0,size)rep(k,0,size)temp[i*size+j]=(temp[i*size+j]+ans[i*size+k]*mat[k*size+j])%m;
			rep(i,0,size*size)ans[i]=temp[i];
		}
		rep(i,0,size*size)temp[i]=0;
		rep(i,0,size)rep(j,0,size)rep(k,0,size)temp[i*size+j]=(temp[i*size+j]+mat[i*size+k]*mat[k*size+j])%m;
		rep(i,0,size*size)mat[i]=temp[i];
		n/=2;
	}
	rep(i,0,size*size)mat[i]=ans[i];

	free(temp);
	free(ans);
}

ll a[16];
ll L,A,B,M;
char s[20];
int main(){
	ll ans=0;
	scanf("%lld%lld%lld%lld",&L,&A,&B,&M);
	ll l=sprintf(s,"%lld",A);
	ll r=sprintf(s,"%lld",A+(L-1)*B);
	rep(k,l,r+1){
		ll x,y,n;
		//初項xと項数nを求める
		if(k==l)x=A;
		else{
			x=po(10,k-1)/B*B+(A%B);
			if(x<po(10,k-1))x+=B;
			if(x>=po(10,k))continue;
		}
		
		if(k==r)y=A+(L-1)*B;
		else{
			y=po(10,k)/B*B+(A%B);
			if(y>=po(10,k))y-=B;
		}
		
//		printf("%lld %20lld %20lld\n",k,x,y);
		
		n=(y-x)/B+1;
		rep(i,0,16)a[i]=0;
		a[3]=a[6]=a[10]=a[11]=a[15]=1;	
		a[0]=a[5]=pom(10,k,M);
		matpom(a,4,n-1,M);
		ll base=(a[0]+a[2]+a[3])%M;
		ll diff=(a[4]+a[6]+a[7])%M;
		ans=(ans*pom(pom(10,n,M),k,M)+base*(x%M)+diff*(B%M))%M;
	}
	printf("%lld",ans);
}

Measured memory_bytes: 128
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstring>
#include <sstream>
#include <cassert>
using namespace std;
static const double EPS = 1e-5;
typedef long long ll;
typedef pair<int,int> PI;
typedef vector<int> vi;
#define rep(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
#define mp make_pair
#define pb push_back
#define f first
#define s second

set<string> ans;
vi in;
vi selected;

void dfs(int k,int pos){
  //cout<<"dfs "<<k<<" "<<pos<<endl;
  if(k==0){
    sort(ALL(selected));
    do{
      string str;
      rep(i,selected.size()){
        stringstream ss;
        ss<<selected[i];
        str+=ss.str();
      }
      ans.insert(str);
    }while(next_permutation(ALL(selected)));
    sort(ALL(selected));
    reverse(ALL(selected));
  }else{
    for(int i=pos;i<in.size();i++){
      selected[k-1]=in[i];
      dfs(k-1,i+1);
    }
  }
}

main(){
  int n,k;
  while(cin>>n>>k,k|n){
    in.clear();
    ans.clear();
    selected.clear();
    selected.resize(k);
    rep(i,n){
      int t;
      cin>>t;
      in.pb(t);
    }
    sort(ALL(in));

    
    dfs(k,0);
    cout<<ans.size()<<endl;
  }
}

Measured memory_bytes: 1060
#include <iostream>
#include <cstring>
using namespace std;
int n,dmax;
int m[300];
bool visited[300], isVisit[300], isGoal;
void dfs(int p){
  if(visited[p])return ;
  visited[p] = true;
  isVisit[p] = true;
  if(p == n+1){
    isGoal = true;
    return;
  }
  for(int i = 1; i <= dmax && p+i <= n+1; i++){
    int np = p+i;
    np = np + m[np];
    if(np > n + 1)np = n + 1;
    if(np < 0) np = 0;  
    dfs(np);
  }
}
void solve(){
  memset(isVisit, 0, sizeof(isVisit));
  isVisit[0] = true;
  for(int i = 0 ; i <= n; i++){
    if(!isVisit[i])continue;
    isGoal = false;
    memset(visited, 0, sizeof(visited));
    dfs(i);
    if(!isGoal)break;    
  }
  cout << (isGoal?"OK":"NG") << endl;
}
int main(){
  while( cin >> dmax, dmax ){
    cin >> n;
    m[0] = 0;
    int i;
    for(i = 1 ; i < n+1 ;i++){
      cin >> m[i];
    }
    m[i] = 0;
    solve();
  }
  return 0;
}

Measured memory_bytes: 1152
from collections import *
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    k = int(input())
    dist = [-1] * k
    q = deque()
    q.append([1, 1])
    while q:
        d, u = q.popleft()
        if dist[u] != -1: continue
        dist[u] = d
        if u == 0:
            print(d)
            break
        v = (u + 1) % k
        if dist[v] == -1: q.append([d + 1, v])
        v = (u * 10) % k
        if dist[v] == -1: q.appendleft([d, v])

main()


Measured memory_bytes: 11500
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <stack>

using namespace std;

typedef struct _TAG_POSITION {
	int x;
	int y;
} POSITION;

int main(){
	int W, H;
	stack<POSITION> S;
	POSITION p;
	while(cin >> W >> H, W || H){
		char board[H+2][W+2];
		int ret = 0;
		for(int i = 0; i < H+2; i++){
			for(int j = 0; j < W+2; j++){
				(((i == 0) || (i == H + 1)) || ((j == 0) || (j == W + 1))) && (board[i][j] = '#');
				(0 < i && i < H + 1) && (0 < j && j < W + 1) && cin >> board[i][j];
				if(board[i][j] == '@') { S.push({i,j}); ret++; }
			}
		}

		while(!S.empty()){
			p = S.top();
			S.pop();
			if(board[p.x + 1][p.y] == '.') { board[p.x + 1][p.y] = '@'; ret++; S.push({p.x + 1,p.y}); }
			if(board[p.x - 1][p.y] == '.') { board[p.x - 1][p.y] = '@'; ret++; S.push({p.x - 1,p.y}); }
			if(board[p.x][p.y + 1] == '.') { board[p.x][p.y + 1] = '@'; ret++; S.push({p.x,p.y + 1}); }
			if(board[p.x][p.y - 1] == '.') { board[p.x][p.y - 1] = '@'; ret++; S.push({p.x,p.y - 1}); }
		}
		cout << ret << "\n";
	}
	return 0;
}

Measured memory_bytes: 1196
package main
import (
	"bufio"
	"fmt"
	"os"
)
var r = bufio.NewReader(os.Stdin)
func main() {
	var w, h int
	fmt.Fscan(r, &w, &h)
    
    // ↓ここを変える
	fmt.Printf("%d %d\n", w * h, 2 * w + 2 * h)
}


Measured memory_bytes: 1172
#include <vector>
#include <iostream>
#include <cmath>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <fstream>
#include <unistd.h>
#include <string>
#include <numeric>
#include <queue>
#include <deque>
#include <sstream>
#include <iomanip>
#include <set>
#include <stack>
#include <cassert>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<vvl> vvvl;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
typedef vector<vvb> vvvb;
typedef vector<vvvb> vvvvb;
typedef vector<string> vs;
typedef vector<vector<string>> vvs;
typedef vector<char> vc;
typedef vector<vector<char>> vvc;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<vvd> vvvd;
typedef pair<int, int> P;
typedef pair<ll, ll> PL;
typedef vector<P> vp;
typedef vector<PL> vpl;
typedef vector<vector<P>> vvp;
typedef vector<vector<PL>> vvpl;
const int INF = 1001001001;
const ll LINF = 1e17;
const double pi = 3.1415926535897932;
const string endstr = "\n";
#define FOR(i, a, b) for(ll i = (a); i < b; i++)
#define RFOR(i, a, b) for(ll i = (a); i > b; i--)
#define REP(i, n) for(ll i = 0; i < n; i++)
#define RREP(i, n) for(ll i = n-1; i > -1; i--)
#define FORMAP(it, m) for(auto it = m.begin(); it != m.end(); it++)
#define ff first
#define ss second
#define pb push_back
#define epb emplace_back

template <typename T>
T gcd(T a, T b) {
    return (a == 0) ? b : gcd(b%a, a);
}
template <typename T>
T lcm(T a, T b) {
    return a / gcd(a, b) * b;
}

bool p_comp_fs(const PL p1, const PL p2){ return p1.first < p2.first;};
bool p_comp_fg(const PL p1, const PL p2){ return p1.first > p2.first;};
bool p_comp_ss(const PL p1, const PL p2){ return p1.second < p2.second;};
bool p_comp_sg(const PL p1, const PL p2){ return p1.second > p2.second;};
template <typename T>
vector<T> uniquen(vector<T> vec){
    vec.erase(unique(vec.begin(), vec.end()), vec.end());
    return vec;
}


int main(){
    ll x, y; cin >> x >> y;
    ll m = (x+y)%2;
    if(m%2 == 0){
        if(x == y) cout << "Brown" << endl;
        else cout << "Alice" << endl;
    }
    else{
        if(abs(x-y) <= 1) cout << "Brown" << endl;
        else cout << "Alice" << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(void){
int a,b;
  cin>>a;
  cin>>b;
  if(a==b){
      cout<<"a == b";
  }
  else if(a>b){
      cout<<"a > b";
  }
  else if(b>a){
      cout<<"a < b";
  }
  cout<<endl;
}


Measured memory_bytes: 3068
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
//
struct edge{
	int from;int to;int cost;
	bool operator<(const edge&R)const{
		return cost<R.cost;
	}
};
struct kruskal{
	//
	int v,e;
	vector<int> par,ran;
	//
	kruskal(int n,int m){
		v=n;e=m;
		init(v);
	}
	//
	void init(int n){
		par.resize(n);
		ran.resize(n);
		for(int i=0;i<n;i++){
			par[i]=i;
			ran[i]=0;
		}
	}
	//
	int find(int x){
		if(par[x]==x){
			return x;
		}else{
			return par[x]=find(par[x]);
		}
	}
	//
	void unite(int x,int y){
		x=find(x);
		y=find(y);
		if(x==y){
			return ;
		}
		if(ran[x]<ran[y]){
			par[x]=y;
		}else{
			par[y]=x;
			if(ran[x]==ran[y]){
				ran[x]++;
			}
		}
	}
	//
	bool same(int x,int y){
		return find(x)==find(y);
	}
	//
	int cul(vector<edge> es){
		sort(es.begin(),es.end());
	    int res=0;
		for(int i=0;i<e;i++){
			edge &e=es[i];
			if(!same(e.from,e.to)){
				unite(e.from,e.to);
				res+=e.cost;
			}
		}
		return res;
	}
	//
};
//
int main(){
	int V,E;
	cin>>V>>E;
	vector<edge> G;
	for(int i=0;i<E;i++){
		int s,t,cost;
		cin>>s>>t>>cost;
		G.push_back((edge){s,t,cost});
	}
	kruskal k(V,E);
	cout<<k.cul(G)<<endl;
	return 0;
}


Measured memory_bytes: 5460
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<utility>
#include<algorithm>
#include<cstdio>
#include<iomanip>
#include<queue>
#include<stack>
#include<bitset>

#define ll int64_t
#define Rep(i, n) for (ll i = 0; i < n; i++)

using namespace std;

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

    ll N, K;
    cin >> N >> K;
    vector<ll> a(N);
    Rep (i, N) {
        cin >> a[i];
    }
    vector<ll> all;
    Rep (i, N) {
        ll now = 0;
        for (ll j = i; j < N; j++) {
            now += a[j];
            all.push_back(now);
        }
    }

    // cout << all.size() << endl;

    vector<bool> use(N*(N+1)/2, true), tmp(N*(N+1)/2, true);
    ll ans = 0;
    ll s = all.size();
    for (ll i = 50; i >= 0; i--) {
        // cout << "i=" << i << endl;
        Rep (j, s) tmp[j] = true;
        ll cnt = 0;
        Rep (j, s) {
            if ((all[j] & ((ll)1 << i)) && use[j]) {
                cnt++;
                // cout << all[j] << endl;
            } else {
                tmp[j] = false;
            }
        }

        // cout << i << " " << cnt << endl;
        if (cnt >= K) {
            ans += (ll)1 << i;
            Rep (j, s) {
                use[j] = tmp[j];
            }
        }
    }

    cout << ans << endl;

    
}

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

int main(){
  int x;
  cin>>x;
  if(x==1)cout<<0<<endl;
  if(x==0)cout<<1<<endl;
  return 0;
}

Measured memory_bytes: 3616
//
//  main.cpp
//  CP-C++
//
//  Created by ALOK KUMAR THAKUR on 05/05/20.
//  Copyright © 2020 ALOK KUMAR THAKUR. All rights reserved.
//

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define tc() ll T;cin>>T;while(T--)
#define pb push_back

struct cmp {
    bool operator() (const ll& a, const ll& b){
        return a < b;
    }
};

int main() {
    
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    
    /*-----------------Code Begins Here------------------*/
    
    string s; cin>>s;
    if(s == "SSS") cout<<0;
    else if(s == "RSS" || s == "SRS" || s == "SSR" || s == "RSR") cout<<1;
    else if(s == "RRS" || s == "SRR") cout<<2;
    else cout<<3;
    
    /*------------------Code Ends Here-------------------*/
    
    return 0;
}


Measured memory_bytes: 3648
#define __LOCAL_DEBUG__
#include<bits/stdc++.h>
using namespace std;
#ifdef __LOCAL_DEBUG__
# define _debug(x) { cerr << "\033[94m" << __func__ << " " << #x << ": " << (x) << "\n\033[0m"; }
#else
# define _debug(...) {((void) 0);}
#endif
#define REP(i, n) for (int i = (0); i < (n); i++)
#define REPP(i, a, b) for (int i = (a); i < (b); i++)
#define EACH(x, arr) for (auto& x : arr) 
#define ITR(i, c) for (__typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define CLR(x, v) memset(x, v, sizeof (x))
#define ALL(x) x.begin(), x.end()
#define SZ(x) (int) x.size()
template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; }
template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; }
using LL = long long;
using PII = pair<int, int>;
using VI = vector<int>;
using VVI = vector<VI>;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const int MAXN = 2e5 + 10;
int n, m, c;
void MAIN() {
    cin >> n >> m >> c;
    VI B(m);
    VVI A(n, VI(m));
    REP(i, m) cin >> B[i];
    REP(i, n) REP(j, m) cin >> A[i][j];
    int res = 0;
    REP(i, n) {
        int sum = 0;
        REP(j, m) sum += B[j] * A[i][j];
        sum += c;
        res += sum > 0;
    }
    cout << res << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int TC = 1;
    // cin >> TC;
    REP(tc, TC) {
    // while (cin >> n, n) {
        // cout << "Case " << tc + 1 << ": ";
        MAIN();
    }
    return 0;
}


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

#define all(x) (x).begin(), (x).end()

typedef long long ll;
typedef array<int, 3> tri;
typedef long double ld;

template <class T> istream& operator>>(istream& I, vector<T>& v) {for (T &e: v) I >> e; return I;}
template <class T> ostream& operator<<(ostream &O, const vector<T>& v) {for (const T &e: v) O << e << ' '; return O;}



const ll A = 911382323, B = 972663749;
void _main() {
        int n; cin >> n;
        string s; cin >> s;
        vector<ll> H(n);
        H[0] = s[0];
        for (int i = 1; i < n; i++)
                H[i] = (s[i] + H[i - 1] * A) % B;

        vector<ll> P(n);
        P[0] = 1;
        for (int i = 1; i < n; i++)
                P[i] = (P[i - 1] * A) % B;


        auto ss_hsh = [&] (int i, int j) -> ll {
                if (i == 0) return H[j];
                return ((H[j] - H[i - 1] * P[j - i + 1]) % B + B) % B;
        };

        auto valid = [&](int k) -> bool {
                map<ll, int> where;
                for (int i = 0; i < n; i++) {
                        int j = i + k - 1;
                        if (j > n) break;
                        ll hash = ss_hsh(i, j);
                        if (!where.count(hash)) where[hash] = i;
                        else if (where[hash] + k - 1 < i) return 1;
                }
                return 0;
        };



        int l = 0, r = n / 2, ans = 0;
        while (l <= r) {
                int mid = (l + r) / 2;
                if (valid(mid)) l = mid + 1, ans = mid;
                else r = mid - 1;
        }

        cout << ans;
}



signed main() {
        ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//        freopen("input.txt", "r", stdin);
        int _t = 1;
//        cin >> _t;
        while (_t--) _main();
        return 0;
}

Measured memory_bytes: 4044
/*  
    Talkin' to myself and feelin' old
    Sometimes I'd like to quit, nothin' ever seems to fit
    Hangin' around, nothin' to do but frown
    Rainy days and Mondays always get me down
    _________________________
    _________________________
    912 Hours of Solitude
    Quarantine_Day : 38
*/

#include<bits/stdc++.h>

using namespace std;

typedef long long int       ll;
typedef vector<int>         vi;
typedef vector<ll>          vl;
typedef pair<int, int>      pii;
typedef pair<ll, ll>		pll;

#define pb(n)           push_back(n)
#define GSORT(v)        sort(v.begin(), v.end(), greater<int>())
#define SORT(v)         sort(v.begin(), v.end());
#define REV(v)          reverse(v.begin(), v.end());
#define db(a)           cout<<#a<<" = "<<a<<endl;
#define FIN             freopen("in.txt","r",stdin);
#define FOUT            freopen("out.txt","w",stdout);
#define REP(i,n)        for(int i = (int)(0); i < (int)(n); i++)
#define FOR(i, a, b)    for(int i = (int)a; i <= (int)b; i++)    

#define MAX 50005

int n, k;
int go(int i, int sum){
    if(i > n) return sum;

    int a = go(i + 1, sum * 2);
    int b = go(i + 1, sum + k);

    return min(a, b);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin>>n>>k;
    cout<<go(1, 1)<<"\n";
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using str = string;
using ll = long long;
#define REP(i,n) for(int i=0; i<int(n); i++)
#define RREP(i,n) for(int i=int(n)-1; i>=0; i--)
#define FOR(i,f,t) for(int i=int(f); i<=int(t); i++)
#define RFOR(i,f,t) for(int i=int(f); i>=int(t); i--)
#define ALL(vec) (vec).begin(),(vec).end()
#define ASORT(vec) sort(ALL(vec))
#define DSORT(vec) sort(ALL(vec), greater<int>());
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))
#define YES(ans) if(ans) cout<<"YES"<<endl; else cout<<"NO"<<endl;
#define Yes(ans) if(ans) cout<<"Yes"<<endl; else cout<<"No"<<endl;
#define yes(ans) if(ans) cout<<"yes"<<endl; else cout<<"no"<<endl;

const int MAX = 3000;
const int MOD = 1000000007;

ll fac[MAX], finv[MAX], inv[MAX];

void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

ll COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}


int main() {
    COMinit();
    int s, t;
    ll ans=0;
    cin >> s;
    REP(i, s/3) {
        t = s - 3*(i+1);
        ans = (ans + COM(t+i, i))%MOD;
    }
    cout << ans << endl;
}


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

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
//conversion
//------------------------------------------
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}

typedef long long LL;
const LL mod=1000000007;
#define MAX 10000
#define NIL -1
const double PI  = acos(-1.0);
const int INF = 1e9 + 7;
//-------------------------------------------


int N,M;

vector< pair<int, int> > p;

int cnt,temp;

int main(){

    cin.tie(0);
    ios::sync_with_stdio(false);

    cin >> N >> M;

    REP(j,M){
        int x,y;
        cin >> x >> y;

        p.push_back(pair<int, int>(x, y));

    }

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


/*    for (int i = 0; i < M; i++) {
      printf("(%d,%d) ", p[i].first, p[i].second);
    }
*/
    temp = p[0].second;

    REP(i, M){

        if( i >= 1){

            if( p[i].first <=  p[i-1].second){

                if( temp > p[i].second){
                    temp = p[i].second;
                }
            }
            //dump(temp);

            if( p[i].first >=  temp){
                //dump(p[i].first);
                //dump(p[i].second);
                cnt++;
                temp = p[i].second;
            }

        }

    }

    cout << cnt + 1<< endl;








    return 0;
}


Measured memory_bytes: 1400
#include <bits/stdc++.h>
#define ll long long
#define endl '\n'
using namespace std;
const ll mod = (ll)1e9+7;
const int INF = 0x3f3f3f3f;

int a[100001];

int mpow(int b, int e)
{
    int ret=1;
    for(int i=0; i<e; i++)
    {
        ret=ret*b%mod;
    }
    return ret;
}

int divisors[1001];

void dostuff(int n)
{
    while(n%2==0)
    {
        n/=2;
        divisors[2]++;
    }
    for(int i=3; i<=sqrt(n); i+=2)
    {
        while(n%i==0)
        {
            n/=i;
            divisors[i]++;
        }
    }
    if(n>2) divisors[n]++;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll n, ans=1;
    cin >> n;
    for(int i=2; i<=n; i++) dostuff(i);
    for(int i=2; i<=1000; i++)
    {
        ans = (ans*(divisors[i]+1))%mod;
    }
    cout << ans;
}


Measured memory_bytes: 256
def framod(n, mod=10**9+7, a=1):
    for i in range(1,n+1):
        a=a * i % mod
    return a


def power(n, r, mod=10**9+7):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod


def comb(n, k, mod=10**9+7):
    a=framod(n, mod)
    b=framod(k, mod)
    c=framod(n-k, mod)
    return (a * power(b, mod-2, mod) * power(c, mod-2, mod)) % mod


N, K = map(int, input().split())
R = N - K
mod = 10**9 + 7

ans = [0]*K
if R == 0:
  ans[0] = 1
elif R == 1:
  ans[0] = 2
  if K >= 2:
    ans[1] = (K-1) % mod
elif R == 2:
  ans[0] = 3
  if K >= 2:
    ans[1] = (3*K - 3) % mod
    if K >= 3:
      ans[2] = (K-1)*(K-2)//2 % mod
else:
  ans[0] = R + 1
  if K >= 2:
    if R > K:
      for i in range(2, K+1):
        ans[i-1] = comb(K-1, i-1)*(comb(R-1, i-2)+2*comb(R-1, i-1)+comb(R-1, i)) % mod
    else:
      for i in range(2, R):
        ans[i-1] = comb(K-1, i-1)*(comb(R-1, i-2)+2*comb(R-1, i-1)+comb(R-1, i)) % mod
      
      ans[R-1] = comb(K-1, R-1)*(comb(R-1, R-2)+2*comb(R-1, R-1)) % mod
      if R <= K-1:
        ans[R] = comb(K-1, R)*comb(R-1, R-1) % mod

for a in ans:
  print(a)

Measured memory_bytes: 3444
#include <iostream>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n,x,t; cin>>n>>x>>t;
    int count;
    if(n%x==0) count=n/x;
    else count=n/x +1;
    count*=t;
    cout<<count<<endl;
	return 0;
}




Measured memory_bytes: 3132
#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s,t;
    cin>>s>>t;
    int flag=0;
    if(s.size()!=t.size()-1)
    cout<<"No";
    else
    {
        for(int i=0;i<s.size();i++)
        {
            if(s[i]!=t[i])
            {
                flag=1;
                break;
            }
        }
        if(flag==1)
        cout<<"No";
        else
        {
            cout<<"Yes";
        }
        
    }
}

Measured memory_bytes: 3628
#lines = <<'EOS'
#9
#0 1 4
#1 2 3
#2 -1 -1
#3 -1 -1
#4 5 8
#5 6 7
#6 -1 -1
#7 -1 -1
#8 -1 -1
#EOS

lines = $stdin.read
array = lines.split("\n")

N = array[0].to_i
Node = Struct.new(:parent, :left, :right)

nodes = Array.new(N) { Node.new }

for i in 1...(array.size)
  carray = array[i].split(" ")
  id    = carray[0].to_i
  left  = carray[1].to_i
  right = carray[2].to_i

  # puts "id #{id}, left #{left}, right #{right}"

  # set parents for each children
  nodes[left].parent  = id if left  != -1
  nodes[right].parent = id if right != -1

  # set left/right nodes
  nodes[id].left  = left if left != -1
  nodes[id].right = right if right != -1
end

def pre_parse(id, nodes)
  return if id.nil?
  print " #{id}"
  pre_parse(nodes[id].left, nodes)
  pre_parse(nodes[id].right, nodes)
end

def in_parse(id, nodes)
  return if id.nil?
  in_parse(nodes[id].left, nodes)
  print " #{id}"
  in_parse(nodes[id].right, nodes)
end

def post_parse(id, nodes)
  return if id.nil?
  post_parse(nodes[id].left, nodes)
  post_parse(nodes[id].right, nodes)
  print " #{id}"
end

root = 0
for i in 0...nodes.size
  root = i if nodes[i].parent.nil?
end

puts "Preorder"
pre_parse(root, nodes)
puts ""

puts "Inorder"
in_parse(root, nodes)
puts ""

puts "Postorder"
post_parse(root, nodes)
puts ""

Measured memory_bytes: 8712
#include<cstdio>
#include<algorithm>
using namespace std;
int n,maxn;
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		int x;
		scanf("%d",&x);
		if(x<maxn){
			puts("No");
			return 0;
		}
		else if(x>maxn)
			maxn=x-1;
	}
	puts("Yes");
	return 0;
}

Measured memory_bytes: 128
N,X = map(int,input().split())
x = list(map(int,input().split())) + [X]
x.sort()
def gcd(x,y):
    if y==0:
        return x
    else:
        return gcd(y,x%y)
ans = x[1]-x[0]
for i in range(N):
    b = x[i+1]-x[i]
    ans = gcd(max(ans,b),min(ans,b))
print(ans)

Measured memory_bytes: 14252
#include<iostream>
using namespace std;

void call(int n){

    for(int i=1; i<=n; i++){
        int x=i;
        if(x%3 == 0){
            cout << " " << i;
            continue;
        }
        do{
            if(x%10 == 3){
                cout << " " << i;
                break;
            }
        }while(x /= 10);
    }
    cout << endl;
}

int main(){
    int n;
    cin >> n;
    call(n);
    return 0;
}

Measured memory_bytes: 1164
import sys
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip() # ignore trailing spaces

n,m = na()
a = [0]*40
for i in range(n):
  for j in na()[1:]:
    a[j] += 1

print(a.count(n))

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define bit(n) (1LL<<(n))
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
using namespace std;
typedef long long ll;
typedef pair<int, int> P;

const int MAX = 510000;
const int MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}



int main(){
    int n, k;
    cin >> n >> k;
    COMinit();
    int r = n-k;
    for(int i=1; i<=k; i++){
        ll ans = COM(r+1, i) * COM(k-1, i-1) % MOD;
        cout << ans << endl;
    }
}

Measured memory_bytes: 12160
#include<iostream>
using namespace std;

int main() {
  int ABC[3];
  scanf("%d %d %d", &ABC[0], &ABC[1], &ABC[2]);

  int sum = 0;
  int maxval = 0;
  for (int i = 0; i < 3; ++i) {
    sum += ABC[i];
    if (ABC[i] > maxval) maxval = ABC[i];
  }

  printf("%d\n", sum - maxval + 10 * maxval);
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s,p,t1,t2,l;
    cin>>s;
    p=s;
    int n=s.length(),flag=0,c=0,d=0;
    int t=(n-1)/2,k=(n+3)/2;
    reverse(p.begin(),p.end());
    if(s==p){
        t1=s.substr(0,t);
        l=t1;
        reverse(t1.begin(),t1.end());
        //cout<<t1<<endl<<l;
        if(t1==l){
            t2=s.substr(k-1,n);
            string l1=t2;
            reverse(t2.begin(),t2.end());
            //cout<<t2<<endl<<l1;
            if(t2==l1)
            {
                flag=1;
            }
        }
    }
    if(flag==1)
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;
}


Measured memory_bytes: 256