akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <cmath>
#include <iostream>
#include <cstdlib>
#include <string>
#include <iomanip>
#include <ctime>
#include <set>
#include <sstream>
#include <map>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
int a[5][105],x[105],y[105],i,n,j;int ans=0,t;
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
    cin>>n;
	for(j=1;j<=n;j++)
	{
		cin>>a[1][j];
		x[j]=x[j-1]+a[1][j];
	}
	for(j=1;j<=n;j++)
	{
		cin>>a[2][j];
	}
	y[n+1]=0;
	for(j=n;j>=1;j--)
	{
		y[j]=y[j+1]+a[2][j];
	}
	for(i=1;i<=n;i++)
	{
		t=x[i]+y[i];
		if(t>ans)ans=t;
	}
	printf("%d\n",ans);
    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T,class U> using P = pair<T,U>;
template<class T> using vec = vector<T>;
template<class T> using vvec = vector<vec<T>>;


int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N,U,V;
    cin >> N >> U >> V;
    U--; V--;
    vvec<int> g(N);
    for(int i=0;i<N-1;i++){
        int a,b;
        cin >> a >> b;
        a--; b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    vec<int> distU(N,0),distV(N,0);
    auto dfs = [&](auto& self,int cur,int par,vec<int>& dist)-> void{
        for(auto& e:g[cur]) if(e!=par){
            dist[e] = dist[cur]+1;
            self(self,e,cur,dist);
        }
    }; 

    int inf = 1e9;
    int ans = 0,ans2 = inf;
    dfs(dfs,V,-1,distV);
    dfs(dfs,U,-1,distU);
    for(int i=0;i<N;i++){
        if(distU[i]<distV[i]){
            ans = max(ans,distV[i]-1);
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 9216
#include <stdio.h>

#define MAX 40

int main()
{
	int j, i, num;
	double height;
	int class[6] = {};


	scanf( "%d", &num );
	for ( i = 0 ; i < num ; i++ ) {
		scanf("%lf", &height );	
		if ( height < 165.0 ) {
			class[0]++;
		} else if ( height >= 165.0 && height < 170.0 ) {
			class[1]++;
		} else if ( height >= 170.0 && height < 175.0 ) {
			class[2]++;
		} else if ( height >= 175.0 && height < 180.0 ) {
			class[3]++;
		} else if ( height >= 180.0 && height < 185.0 ) {
			class[4]++;
		} else if ( height >= 185.0 ) {
			class[5]++;
		}
	}


	for ( i = 0 ; i < sizeof( class ) / sizeof( int ) ; i++ ) {
		printf( "%d:", i+1 );
		for ( j = 0 ; j < class[i] ; j++ ) {
			printf( "*" );
		}
		printf( "\n" );	
	}

	return 0;
}



Measured memory_bytes: 2036
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pii pair<int, int>
#define pli pair<ll, int>
#define pil pair<int, ll>
#define pll pair<ll, ll>
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep3(i, l, n) for (int i = l; i < (n); ++i)
#define sz(v) (int)v.size()
#define endl '\n'
const int inf = 1000000007;
const ll INF = 1e18;
int mod = 998244353;
// int mod = 1000000007;
const double eps = 1e-8;
#define abs(x) (x >= 0 ? x : -(x))
#define lb(v, x) (int)(lower_bound(all(v), x) - v.begin())
#define ub(v, x) (int)(upper_bound(all(v), x) - v.begin())
template<typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { if (a < b) { a = b; return 1; } return 0; }
ll gcd(ll a, ll b) { if (b == 0) return a; return gcd(b, a % b); }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
template<typename T, typename U> T pow_(T a, U b) { return b ? pow_(a * a, b / 2) * (b % 2 ? a : 1) : 1; }
ll modpow(ll a, ll b, ll _mod) { return b ? modpow(a * a % _mod, b / 2, _mod) * (b % 2 ? a : 1) % _mod : 1; }
template<class T, class U> ostream& operator << (ostream& os, const pair<T, U>& p) { os << p.F << " " << p.S; return os; }
template<class T> ostream& operator << (ostream& os, const vector<T>& vec) { rep(i, sz(vec)) { if (i) os << " "; os << vec[i]; } return os; }
template<class T> ostream& operator << (ostream& os, const set<T>& s) { for (auto si : s) os << si << " "; return os; }
template<typename T> inline istream& operator >> (istream& is, vector<T>& v) { rep(j, sz(v)) is >> v[j]; return is; }
template<class T, class T2> inline void add(T &a, T2 b) { (a += (b % mod + mod)) %= mod; }
template<class T> void operator += (vector<T>& v, vector<T> v2) { rep(i, sz(v2)) v.eb(v2[i]); }

void solve();

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout << fixed << setprecision(12);
    int T;
    T = 1;
    while (T--) solve();
}

void solve() {
    ll n;
    cin >> n;
    int x, m;
    cin >> x >> m;
    
    set<ll> s;
    vector<ll> v, v2;
    
    ll x2 = x;
    rep(i, m) {
        s.emplace(x2);
        (x2 *= x2) %= m;
        if (s.count(x2)) {
            rep(j, m) {
                v2.eb(x2); // ループ部分だけ
                (x2 *= x2) %= m;
                if (x2 == v2[0]) break;
            }
            x2 = x;
            rep(j, m) {
                if (x2 == v2[0]) break;
                v.eb(x2);
                (x2 *= x2) %= m;
            }
            break;
        }
    }
    // cerr << v << endl << v2 << endl;
    
    ll ans = 0;
    rep(i, sz(v)) {
        ans += v[i];
        --n;
        if (n == 0) break;
    }
    // cerr << n << " " << ans << endl;
    ans += n / sz(v2) * accumulate(all(v2), 0LL);
    n %= sz(v2);
    rep(i, n) ans += v2[i];
    cout << ans << endl;
}




Measured memory_bytes: 6200
#include<iostream>
#include<queue>
#include<map>
#include<set>
 
using namespace std;
 
#define rep(i, n) for (int i = 0; i < int(n); ++i)
 
bool used[6000][2001];
vector<pair<short, short> > edge[6000];
 
int main() {
  while (true) {
    rep (i, 6000) edge[i].clear();
    rep (i, 6000) rep (j, 2001) used[i][j] = false;
    int n, m, cap;
    string src, dest;
    cin >> n >> m >> cap;
    cap *= 10;
    if (n == 0) break;
    cin >> src >> dest;
    map<string, int> mp;
    rep (i, n) {
      string c1, c2;
      int d;
      cin >> c1 >> c2 >> d;
      short nc1, nc2;
      if (mp.count(c1)) {
	nc1 = mp[c1];
      } else {
	nc1 = mp.size();
	mp[c1] = nc1;
      }
      if (mp.count(c2)) {
	nc2 = mp[c2];
      } else {
	nc2 = mp.size();
	mp[c2] = nc2;
      }
      edge[nc1].push_back(make_pair(nc2, d));
      edge[nc2].push_back(make_pair(nc1, d));
    }
    set<int> st;
    rep (i, m) {
      string s;
      cin >> s;
      st.insert(mp[s]);
    }
    priority_queue<pair<int, pair<short, short> >,vector<pair<int, pair<short, short> > >, greater<pair<int, pair<short, short> > > > que;
    que.push(make_pair(0, make_pair(mp[src], cap)));
    int res = 1e9;
    while (!que.empty()) {
      pair<int, pair<short, short> > now = que.top();
      que.pop();
      int cost = now.first;
      short pos = now.second.first;
      short f = now.second.second;
      if (used[pos][f]) continue;
      used[pos][f] = true;
      if (mp[dest] == pos) {
	res = cost;
	break;
      }
      rep (i, edge[pos].size()) {
	int nc = cost + edge[pos][i].second;
	short np = edge[pos][i].first;
	short nf = f - edge[pos][i].second;
	if (nf < 0) continue;
	if (st.count(np)) nf = cap;
	if (used[np][nf]) continue;
	que.push(make_pair(nc, make_pair(np, nf)));
      }
    }
    if (res == 1e9) cout << -1 << endl;
    else cout << res << endl;
  }
}

Measured memory_bytes: 31008
#include <stdio.h>
#include <memory.h>
typedef struct{
	int num;
	int cnt;
}data;
int main(void){
	data q[100]={0};
	int a[1000][100]={0};
	int n,m,i,j;
	while(scanf("%d %d",&n,&m),n+m){
		memset(a,0,sizeof(a));
		memset(q,0,sizeof(q));
		for(i=0;i<n;i++){
			for(j=0;j<m;j++){
				scanf("%d",&a[i][j]);
			}
		}
		for(j=0;j<m;j++){
			q[j].num=j+1;
			for(i=0;i<n;i++){
				q[j].cnt+=a[i][j];
			}
		}
		for(i=0;i<m-1;i++){
			for(j=m-1;j>i;j--){
				if(q[j-1].cnt<q[j].cnt){
					data t=q[j-1];
					q[j-1]=q[j];
					q[j]=t;
				}
			}
		}
		for(i=0;i<m-1;i++){
			printf("%d ",q[i].num);
		}
		printf("%d\n",q[m-1].num);
	}
	return 0;
}

Measured memory_bytes: 1000
import sys
import math  # noqa
import bisect  # noqa
import queue  # noqa


def input():
    return sys.stdin.readline().rstrip()


def main():
    W, N = map(int, input().split())
    weight = []
    value = []
    for _ in range(N):
        A, B = map(int, input().split())
        weight.append(A)
        value.append(B)

    INF = 1000000007
    MAX_N = 1005
    MAX_W = 10005
    dp = [[INF for _ in range(MAX_W)] for _ in range(MAX_N)]
    for i in range(MAX_N):
        dp[i][0] = 0

    for i in range(N):
        for j in range(W + 1):
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
            w = j + weight[i]
            if w >= W:
                w = W
            dp[i + 1][w] = min(dp[i + 1][w], dp[i + 1][j] + value[i])

    print(dp[N][W])


if __name__ == '__main__':
    main()


Measured memory_bytes: 126168
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
using namespace std;
#define REP(i,m,n) for(int i=(int)m ; i < (int) n ; ++i )
#define rep(i,n) REP(i,0,n)
typedef long long ll;
typedef pair<int,int> pint;
typedef pair<ll,int> pli;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;
int dx[4]={1,0,-1,0} , dy[4]={0,1,0,-1} ;
struct SegmentTree{
   private:
       int n;
       vector<ll> node;
   public:
       SegmentTree(int sz,ll init){
           n=1;
           while(n<sz)n*=2;
           node.resize(2*n-1,init);
       }
       void update(int k,ll x){
           k+=n-1;
           node[k]=x;
           while(k>0){
               k=(k-1)/2;
               node[k]=min(node[2*k+1],node[2*k+2]);
           }
       }
       //[a,b)でのminを返す
       ll get(int a,int b,int k=0,int l=0,int r=-1){
           if(r<0)r=n;
           if(r<=a||b<=l)return longinf;
           if(a<=l&&r<=b)return node[k];
           ll xl=get(a,b,2*k+1,l,(l+r)/2);
           ll xr=get(a,b,2*k+2,(l+r)/2,r);
           return min(xl,xr);
       }
   };
int main(){
   int n;
   cin>>n;
   int p[n];
   SegmentTree odd(n,inf),even(n,inf);
   rep(i,n){
       int x;cin>>x;
       p[x]=i;
       if(i%2)odd.update(i, x);
       else even.update(i, x);
   }
   priority_queue<pair<int,pint>,vector<pair<int,pint>>,greater<pair<int,pint>>> q;
   int mi=even.get(0,n);
   q.push({mi,{0,n}});
   vector<int> ans;
   while(q.size()){
       int l=q.top().second.first;
       int r=q.top().second.second;
       int ret=q.top().first;
       q.pop();
       if(r<=l)continue;
       ans.push_back(ret);
       ret=p[ret];
       int nex;
       if(ret%2)nex=even.get(ret+1,r);
       else nex=odd.get(ret+1,r);
       ans.push_back(nex);
       nex=p[nex];
       if(l%2){
           if(l<ret)q.push({odd.get(l,ret),{l,ret}});
           if(ret<nex)q.push({even.get(ret+1,nex),{ret+1,nex}});
           if(nex<r)q.push({odd.get(nex+1,r),{nex+1,r}});
       }
       else{
           if(l<ret)q.push({even.get(l,ret),{l,ret}});
           if(ret<nex)q.push({odd.get(ret+1,nex),{ret+1,nex}});
           if(nex<r)q.push({even.get(nex+1,r),{nex+1,r}});
       }
   }
   rep(i,n)cout<<ans[i]<<" ";
   cout<<endl;
   return 0;
}

Measured memory_bytes: 11916
#include<stdio.h>

int main(){
  int N;
  scanf("%d", &N);
  
  int p[N];
  for(int i = 0; i < N; i++) scanf("%d", p + i);
  
  int count = 0;
  for(int i = 1; i < N; i++){
    if(p[i - 1] == i){
      p[i] ^= p[i - 1];
      p[i - 1] ^= p[i];
      p[i] ^= p[i - 1];
      count++;
    }
  }
  if(p[N - 1] == N) count++;
  
  printf("%d\n", count);
  
  return 0;
}


Measured memory_bytes: 512
#include<cstdio>
using namespace std;
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    if(n == m){
        printf("-1\n");
        return 0;
    }
    for(int i = n; i < 1000000000; i += n){
        if(i % m != 0){
            printf("%d\n", i);
            return 0;
        }
    }
    printf("-1\n");
    return 0;
}

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

bool prime(LL N){
	if ( N == 1) return false;
	for( LL i = 2; i * i <= N; ++i){
		if(N % i == 0) return false;
	}
	return true;
}

int main(){
	int X;cin >> X;
	LL ans = 0;
	for(LL i = X;i <= 1000000; i++){
		if(prime(i)) {
			ans = i;
			break;
		}
	}
	cout << ans << endl;	


}














Measured memory_bytes: 3612
#include<iostream>
#include<functional>
#include<queue>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
#define pb push_back
#define all(c) c.begin(),c.end()
#define uni(c) c.erase(unique(all(c)),c.end())
using namespace std;
typedef pair<int,int > P;
int main(){
	int n;
	vector<vector<int> > c(8,vector<int>(8));
	while(cin>>n){
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				cin>>c[i][j];
			}
		}
		priority_queue<P,vector<P>,greater<P> > que;
		int v=0;
		for(int i=0;i<n;i++){
			v=v*10+i;
		}
		int ans=0;
		map<int,bool> u;
		que.push(P(0,v));
		int m=1;
		for(int i=0;i<n;i++){
			m*=10;
		}
		while(!que.empty()){
			P p=que.top();
			que.pop();
			int now=p.second,np=p.first;;
			if(u[now]){
				continue;
			}
			u[now]=1;
			ans=max(ans,np);
			for(int i=1;i<m;i*=10)
			for(int j=i*10;j<m;j*=10){
				int a=(now/i)%10,b=(now/j)%10;
				int nn=now-a*i-b*j+a*j+b*i;
				if(u[nn]){
					continue;
				}
				que.push(P(np+c[a][b],nn));
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}

Measured memory_bytes: 6120
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
#define fr second.first
#define to second.second
#define co first
const int INF=INT_MAX;
typedef pair<int,int> P;
typedef pair<int,P> Edge;
long long edmonds(vector<Edge> edges,int v,int st) {
  
  vector<P> mins(v,P(INF,-1));
  for(int i=0;i<(int)edges.size();i++) {
    Edge edge=edges[i];
    mins[edge.to]=min(mins[edge.to],P(edge.co,edge.fr));
  }
  mins[st]=P(-1,-1);
   
  vector<int> gr(v,0);
  vector<bool> tfc(v,false),f(v,false);
  int cnt=0; 
 
  for(int i=0;i<v;i++){
    if(f[i]) continue;
    vector<int> ch;
    int cu=i;
    for(;cu!=-1&&!f[cu];){ 
      f[cu]=true;
      ch.push_back(cu);
      cu=mins[cu].second;
    }
    if(cu!=-1){
      bool tfc2=false;
      for(int j=0;j<(int)ch.size();j++) {
    gr[ch[j]]=cnt;
    if(ch[j]==cu){
      tfc[cnt]=true;
      tfc2=true;
    }
    if(!tfc2) cnt++;
      }
      if(tfc2) cnt++;
    }
    else for(int j=0;j<(int)ch.size();j++,cnt++) gr[ch[j]]=cnt;
  }
 
  if(cnt==v){
    long long ans=1;
    for(int i=0;i<v;i++) ans+=mins[i].co;
    return ans;
  }
 
  long long res=0;
  for(int i=0;i<v;i++) if(i!=st&&tfc[gr[i]]) res+=mins[i].co;
     
  vector<Edge> nedges;
  for(int i=0;i<(int)edges.size();i++) {
    Edge edge=edges[i];
    int fto=edge.to,gfr=gr[edge.fr],gto=gr[edge.to];
    if(gfr==gto) continue;
    else if(tfc[gto]) nedges.push_back(make_pair(edge.co-mins[fto].co,P(gfr,gto)));
    else nedges.push_back(make_pair(edge.co,P(gfr,gto)));
  }
 
  return res+edmonds(nedges,cnt,gr[st]);
 
}
 
int main(){
  int v,e,r;
  cin>>v>>e>>r;
  vector<Edge> es;
  for(int i=0,s,t,w;i<e&&cin>>s>>t>>w;i++) es.push_back(make_pair(w,P(s,t)));
  cout<<edmonds(es,v,r)<<endl;
  return 0;
}


Measured memory_bytes: 3644
#include <bits/stdc++.h>
#define FOR(i, m, n) for (int i = m; i < (n); i++)
#define RFOR(i, m, n) for (int i = (m - 1); i >= 0; i--)
#define REP(i, n) FOR(i, 0, n)
#define RREP(i, n) RFOR(i, n, 0)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;

ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }

int main() {
  int r, g, b;
  cin >> r >> g >> b;
  int sum = 100 * r + 10 * g + b;
  cout << (sum % 4 == 0 ? "YES" : "NO") << endl;
  return 0;
}

Measured memory_bytes: 256
MEMO_LENGTH = 200000

N, X, M = gets.split.map &:to_i
a = X
ans = 0
if N < MEMO_LENGTH
  N.times{
    ans += a
    a = a.pow(2, M)
  }
  p ans
  exit
end

memo = []
MEMO_LENGTH.times{
  ans += a
  memo << a
  a = a.pow(2, M)
}
last = memo[-1]
memo.pop
idx = memo.rindex(last)
# p [last, idx]
period = MEMO_LENGTH - 1 - idx
period_arr = memo[idx+1..-1] + [memo[idx]]
period_sum = period_arr.sum
div, mod = (N - MEMO_LENGTH).divmod(period)
# p [div,mod, period_arr]
ans += period_sum * div + period_arr.take(mod).sum
p ans

Measured memory_bytes: 17052
#include<bits/stdc++.h>
using namespace std;
const int mn=1e3+10;
int dis[mn][mn];
bool ad[mn][mn];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){
        dis[i][j]=min(min(i,n+1-i),min(j,n+1-j));
    }
    memset(ad,1,sizeof(ad));
    int ans=0;
    for(int i=0;i<n*n;i++){
        deque<int>q;
        int x;
        cin>>x,x--;
        int a=x/n+1,b=x%n+1;
        ans+=dis[a][b]-1;
        ad[a][b]=0;
        q.push_back((a-1)*n+(b-1));
        while(q.size()){
            x=q.front();
            q.pop_front();
            a=x/n+1,b=x%n+1;
            int pro=dis[a][b]+ad[a][b];
            if(pro<dis[a+1][b]){
                dis[a+1][b]=pro;
                if(ad[a][b])q.push_back(a*n+(b-1));
                else q.push_front(a*n+(b-1));
            }
            if(pro<dis[a-1][b]){
                dis[a-1][b]=pro;
                if(ad[a][b])q.push_back((a-2)*n+(b-1));
                else q.push_front((a-2)*n+(b-1));
            }
            if(pro<dis[a][b+1]){
                dis[a][b+1]=pro;
                if(ad[a][b])q.push_back((a-1)*n+b);
                else q.push_front((a-1)*n+b);
            }
            if(pro<dis[a][b-1]){
                dis[a][b-1]=pro;
                if(ad[a][b])q.push_back((a-1)*n+(b-2));
                else q.push_front((a-1)*n+(b-2));
            }
        }
    }
    printf("%d",ans);
}

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

int main(){
  string p,s;
  cin>>p>>s;
  p=p+p;
  bool flag=false;
  for(int i=0;i<(int)p.size()-(int)s.size()+1;i++){
    
    // pのi文字目から連続したs.size() 文字を抜き出す
    string t=p.substr(i, s.size() );
    
    if( t == s ){
      flag=true;
      break;
    }
  }
  if(flag){
    cout<<"Yes"<<endl;
  }else{
    cout<<"No"<<endl;
  }
  return 0;
}




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

// Template Headers {{{
using pii = pair<int, int>; using vpii = vector<pii>;
using vi = vector<int>; using vvi = vector<vi>;
using ll = long long; using vll = vector<long long>;
template <class T> istream &operator>>(istream &, vector<T> &);
template <class T> ostream &operator<<(ostream &, const vector<T> &);
template <class T, class U> istream &operator>>(istream &, pair<T, U> &);
template <class T, class U> ostream &operator<<(ostream &, const pair<T, U> &);
constexpr int INF = 0x3f3f3f3f; constexpr ll BINF = 0x3f3f3f3f3f3f3f3fLL;
// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// }}}

int solve() {
	int n; cin >> n;
	vector<pair<ll, ll>> a(n); cin >> a;
	vector<pair<ll, ll>> pqcan;
	pqcan.emplace_back(INF, INF);
	for (int i=0;i<n;i++) for (int j=0;j<n;j++) {
		ll pi = a[j].first - a[i].first;
		ll qi = a[j].second - a[i].second;
		if (pi == 0 && qi == 0) continue;
		pqcan.emplace_back(pi, qi);
	}
	ll ans = BINF;
	for (auto pq : pqcan) {
		ll p, q; tie(p, q) = pq;
		multiset<pair<ll, ll>> ms;
		for (auto z : a) ms.insert(z);
		ll now = 0;
		while (!ms.empty()) {
			now++;
			ll u, v;
			tie(u, v) = *ms.begin(); ms.erase(ms.begin());
			multiset<pair<ll, ll>>::iterator it;
			while ((it = ms.find({u + p, v + q})) != ms.end()) {
				u += p; v += q;
				ms.erase(it);
			}
		}
		ans = min(ans, now);
	}
	cout << ans << endl;
	return 0;
}

// Template Main {{{
int main() {
	ios::sync_with_stdio(0);
	// precompute();
	// int t; cin >> t; for (int i=1;i<=t;i++)
	solve();
	// cout << (solve() ? "YES" : "NO") << endl;
	return 0;
}

template <class T> istream &operator>>(istream &is, vector<T> &v) {
	for (auto it=v.begin();it!=v.end();++it) is >> *it;
	return is;
}

template <class T> ostream &operator<<(ostream &os, const vector<T> &v) {
	for (auto it=v.begin();it!=v.end();) os << *it, os << " \n"[++it==v.end()];
	return os;
}

template <class T, class U> istream &operator>>(istream &is, pair<T, U> &p) {
	return is >> p.first >> p.second;
}

template <class T, class U> ostream &operator<<(ostream &os, const pair<T, U> &p) {
	return os << p.first << ' ' << p.second;
}
// }}}

// vim: fdm=marker


Measured memory_bytes: 512
#include <cstdio>
#include <string>
#include <algorithm>
#include <iostream>
using namespace std;
#define DEBUG(X) cerr<<__LINE__<<" "<<#X<<": "<<X<<endl;
int main() {
  string s1, s2, s3;
  cin >> s1 >> s2 >> s3;
  transform (s1.begin (), s1.end (), s1.begin (), ::toupper);
  transform (s2.begin (), s2.end (), s2.begin (), ::toupper);
  transform (s3.begin (), s3.end (), s3.begin (), ::toupper);
  cout << s1[0] << s2[0] << s3[0] << endl;
}

Measured memory_bytes: 256
h, w = map(int, input().split())
a = [list(input()) for i in range(h)]
a = [['#' for i in range(w)]] + a + [['#' for i in range(w)]]
for i in range(h+2):
    a[i] = ['#']+ a[i] +['#']
    print(''.join(a[i]))

Measured memory_bytes: 3060
#include <iostream>

using namespace std;

#define ll long long

int main(){
    int n;
    cin >> n;
    ll sum = 0;
    for (int i = 1; i <= n; i++){

        if (i % 3 != 0 && i % 5 != 0) {
            sum += i;
        }
    }
    cout << sum << "\n";
}

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

#define ll long long
#define ss second
#define ff first
#define pb push_back

using namespace std;

const int N = 1e6 + 69;

int n, answer, m, x, y;
int fix[N], ANS[N];

vector<int> gr[N];

void dfs(int x){

        fix[x] = 1;
        for(int  i = 0; i <gr[x].size(); i++){
                int to = gr[x][i];
                if(fix[to]){
                        ANS[x] = max(ANS[x],ANS[to]+1);
                        continue;
                }
                dfs(to);
                ANS[x] = max(ANS[x],ANS[to]+1);
        }

        answer = max(answer, ANS[x]);
}

int main(){

        ios :: sync_with_stdio(0);

        cin >> n >> m;


        for(int i = 0;i < m; i++){
                cin >> x >> y;
                gr[x].pb(y);
        }

        for(int  i = 1; i <= n; i++){
                if(fix[i]) continue;
                dfs(i);
        }

        cout << answer << endl;
}


Measured memory_bytes: 32000
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N;
  cin >> N;
  if (65 <= N && N <= 90){
    cout << 1 << endl;
  } else if (97 <= N && N <= 122){
    cout << 2 << endl;
  } else {
    cout << 0 << endl;
  }
}


Measured memory_bytes: 3088
#include<stdio.h>
int main(void){
  int array[100000],n,k,i,j;
  long long int sum,max;

  while(scanf("%d %d",&n,&k) && n && k){
    for(i=0;i<n;i++) scanf("%d",&array[i]);
    sum=0;
    for(i=0;i<k;i++) sum+=array[i];
    max=sum;
    for(i=k;i<n;i++){
      sum+=array[i]-array[i-k];
      if(max<sum) max=sum;
    }
    printf("%lld\n",max);
  }
  return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i,n) for(long long i = 0; i < (n); ++i)
#define ll long long
#define P pair<ll,ll>
#define all(v) (v).begin(),(v).end()

const ll mod = 1e9+7;
const ll INF = 1e18;
const double pi = acos(-1.0);

int main(void)
{
    ll n, ans=0;
    cin >> n;
    vector<ll> a(n+1), b(n);
    rep(i,n+1) cin >> a[i];
    rep(i,n) cin >> b[i];
    rep(i,n){
        if(a[i] >= b[i]) ans += b[i];
        else{
            ans += min(b[i], a[i]+a[i+1]);
            a[i+1] = max(0LL, a[i+1]-b[i]+a[i]);
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 4784
#include <cstdio>
#include <algorithm>
typedef long long ll;
const int maxn = 200000*32*3;
const ll inf = 1ll<<60;
int l[maxn], r[maxn], ls[maxn], rs[maxn];
ll val[maxn];
int cnt = 0;
int newnode(int L, int R, ll def = -inf)
{
	int i = cnt++;
	val[i] = def;
	l[i] = L, r[i] = R;
	ls[i] = rs[i] = -1;
	return i;
}

ll query(int i, int L, int R)
{
	if (l[i] == L && r[i] == R) return val[i];
	int mid = (l[i]+r[i])/2;
	ll ans = -inf;
	if (L <= mid && ls[i] != -1) ans = std::max(ans, query(ls[i], L, std::min(R, mid)));
	if (R > mid && rs[i] != -1) ans = std::max(ans, query(rs[i], std::max(L, mid+1), R));
	return ans;
}

void modify(int i, int a, ll b)
{
	if (l[i] == r[i])
	{
		val[i] = std::max(val[i], b);
		return;
	}
	int mid = (l[i]+r[i])/2;
	if (a <= mid) modify(ls[i]=(ls[i]==-1?newnode(l[i], mid):ls[i]), a, b);
	if (a > mid) modify(rs[i]=(rs[i]==-1?newnode(mid+1, r[i]):rs[i]), a, b);
	val[i] = std::max(ls[i]==-1?-inf:val[ls[i]], rs[i]==-1?-inf:val[rs[i]]);
}

struct Point { int x, y; }p[200005];
bool operator< (Point a, Point b) { return a.x < b.x; }
int main()
{
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) scanf("%d%d", &p[i].x, &p[i].y);
	std::sort(p, p+n);
	int a = newnode(1, 1000000005);
	int b = newnode(1, 1000000005);
	ll ans = -inf;
	for (int i = 0; i < n; i++)
	{
		ans = std::max(ans, p[i].x+p[i].y+query(a, 1, p[i].y));
		ans = std::max(ans, p[i].x-p[i].y+query(b, p[i].y, 1000000005));
		modify(a, p[i].y, -p[i].x-p[i].y);
		modify(b, p[i].y, -p[i].x+p[i].y);
	}
	printf("%lld\n", ans);
}


Measured memory_bytes: 129176
#include<iostream>
#include<vector>
#include<set>
#include<unordered_set>
#include<list>
#include<stack>
#include<queue>
#include<map>
#include<unordered_map>
#include<algorithm>
#include<cmath>
#include<tuple>
#include<iomanip>
#include<climits>
#define ll long long int
#define mod 1000000007
#define pi acos(-1)
using namespace std;

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  ll a, b, k;
  cin>>a>>b>>k;
  ll t1 , t2;
  if(a>=k)
  {
    cout<<a-k<<" "<<b;
  }
  else
  {
    if(k-a>b)
      cout<<0<<" "<<0;
    else
      cout<<0<<" "<<b-k+a;
  }
  
  return 0;
}

Measured memory_bytes: 256
from sys import stdin, setrecursionlimit


def main():
    mod = 10 ** 9 + 7
    input = stdin.buffer.readline
    n, k = map(int, input().split())
    ans = 0
    for i in range(k, n + 2):
        ans += (n - i + 1) * i + 1
    print(ans % mod)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()


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

int H, W;
vector<vector<int>> tfmat(10, vector<int> (10));

int const INF = 1 << 30;

int main(void){
    // Your code here!
    cin >> H >> W;
    for (int i=0; i<10; i++) for (int j=0; j<10; j++) cin >> tfmat[i][j];
    
    vector<vector<int>> grid(H, vector<int> (W));
    for (int i=0; i<H; i++) for (int j=0; j<W; j++) cin >> grid[i][j];
    

    for (int k=0; k<10; k++){
        for (int i=0; i<10; i++){
            for (int j=0; j<10; j++){
                tfmat[i][j] = min(tfmat[i][j], tfmat[i][k] + tfmat[k][j]);
            }
        }
    }
    
    int ans = 0;
    for (int i=0; i<H; i++){
        for (int j=0; j<W; j++){
            if (grid[i][j] != -1){
                ans += tfmat[grid[i][j]][1];
            }
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 3744
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
ll n;
ll INF = (1LL<<34);
P t[100];
ll dp[100][100];

P on(P x,P y){
  return P(x.first,y.second);
}

ll cost(P x,P y){
  return x.first*x.second*y.first*y.second;
}

int compute(int a,int b){
  ll A,B;
  if(dp[a][b]!=-1)return dp[a][b];
  if(a==b)return 0;
  if(a+1==b)return cost(t[a],t[b]);
  if(a+2==b){
    A  = cost(t[a],t[a+1]);
    A += cost( on(t[a],t[a+1])  ,t[b]);
    B  = cost(t[b-1],t[b]);
    B += cost(t[a], on(t[b-1],t[b]) );
    return (A<B?A:B);
  }

  ll res=INF;
  ll sum;
  P X,Y;
  for(int i=a;i<b;i++){
    X=on(t[a],t[i]);
    Y=on(t[i+1],t[b]);
    
    sum=cost(X,Y);
    sum = compute(a,i)+ sum +compute(i+1,b) ;
    res=(sum<res?sum:res);

  }
  dp[a][b]=res;
  return res;
}

int main(){

  while(cin>>n&&n){
    for(int i=0;i<n;i++)cin>>t[i].first>>t[i].second;
    for(int i=0;i<100;i++)for(int j=0;j<100;j++)dp[i][j]=-1;
    cout<<compute(0,n-1)<<endl;
  }
  return 0;
}

Measured memory_bytes: 1244
#include <iostream>
#include <vector>
#include <queue>

using std::cin;
using std::cout;
using std::endl;
using std::vector;
using std::queue;

int main(void) {
	int w,h;
	cin >> w >> h;

	char c;
	while ( w != 0 || h != 0 ) {
		vector< vector<int> > area(h+2, vector<int>(w+2));
		queue<int> checkx,checky;
		
		for (int i = 0; i < h+2; i++) {
			for (int j = 0; j < w+2; j++) {
				if (i==0||i==h+1||j==0||j==w+1) {
					area[i][j] = -1;
				}
				else {
					cin >> c;
					if ( c == 'W' ) {
						area[i][j] = 1;
					}
					else if ( c == 'B' ) {
						area[i][j] = 2;
					}
					else {
						area[i][j] = 0;
						checky.push(i);
						checkx.push(j);
					}
				}
			}
		}

		int count_b = 0;
		int count_w = 0;
		int count = 0;
		int mode = 0;
		int xn,yn;
		queue<int> sx,sy;
		while (!checkx.empty()) {
			xn = checkx.front();
			yn = checky.front();
			checkx.pop();
			checky.pop();
			count = 0;
			mode = 0;
			if (area[yn][xn] == 0) {
				count++;
				sx.push(xn);
				sy.push(yn);
				while (!sx.empty()) {
					xn = sx.front();
					yn = sy.front();
					area[yn][xn] = -1;
					sx.pop();
					sy.pop();
					if (area[yn+1][xn] == 0) {
						sx.push(xn);
						sy.push(yn+1);
						area[yn+1][xn] = -1;
						count++;
					}
					if (area[yn-1][xn] == 0) {
						sx.push(xn);
						sy.push(yn-1);
						area[yn-1][xn] = -1;
						count++;
					}
					if (area[yn][xn+1] == 0) {
						sx.push(xn+1);
						sy.push(yn);
						area[yn][xn+1] = -1;
						count++;
					}
					if (area[yn][xn-1] == 0) {
						sx.push(xn-1);
						sy.push(yn);
						area[yn][xn-1] = -1;
						count++;
					}
					if (area[yn+1][xn] > 0) {
						if (mode == 0) {
							mode = area[yn+1][xn];
						}
						else if (mode != area[yn+1][xn]) {
							mode = -1;
						}
					}
					if (area[yn-1][xn] > 0) {
						if (mode == 0) {
							mode = area[yn-1][xn];
						}
						else if (mode != area[yn-1][xn]) {
							mode = -1;
						}
					}
					if (area[yn][xn+1] > 0) {
						if (mode == 0) {
							mode = area[yn][xn+1];
						}
						else if (mode != area[yn][xn+1]) {
							mode = -1;
						}
					}
					if (area[yn][xn-1] > 0) {
						if (mode == 0) {
							mode = area[yn][xn-1];
						}
						else if (mode != area[yn][xn-1]) {
							mode = -1;
						}
					}
				}
				if (mode > 0) {
					if (mode == 1) {
						count_w += count;
					}
					else {
						count_b += count;
					}
				}
			}
		}
		cout << count_b << " " << count_w << endl;

		cin >> w >> h;
	}

	return 0;
}

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

int main() {
  ll X,Y,Z;
  cin >> X >> Y >> Z;
 
  cout << Z  << " "<< X <<" "<< Y << endl;
  
  return 0;
}

Measured memory_bytes: 3564
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>

const int s=1001;

using namespace std;

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

	int min = 1001;
	int ans=0;
	int N,X; cin >> N >> X;
	vector<int> m;

	for(int i=0;i<N;i++){
		int tmp;
		cin >> tmp;
		m.push_back(tmp);
		X -= m[i];
		ans++;
		if(min > m[i]) min = m[i];
	}
	ans += X/min;
	cout << ans << "\n";

	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int main(void)
{
   int a, b, c;
   
   scanf("%d %d %d", &a, &b, &c);

   if(a < b)
   {
       if(b < c) printf("Yes\n");
       if(c < b) printf("No\n");
   }
   else printf("No\n");

    return 0;
}

Measured memory_bytes: 580
#include <stdio.h>
int main(void){
    int S,h,m,s;
    scanf("%d", &S);
    h=S/3600;
    m=(S-h*3600)/60;
    s=S-(h*3600+m*60);
    printf("%d:%d:%d\n",h,m,s);
    return 0;
}



Measured memory_bytes: 2100
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<vector>
#include<map>
using  namespace std;
const int maxn=1e4+50;
int main()
{
	int n,x,a[maxn],ans=1,sum=0;
	scanf("%d%d",&n,&x);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)
	{
		sum+=a[i];
		if(sum<=x)ans++; 
	}
	printf("%d\n",ans);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include<vector>
using namespace std;
#define rep(i, n)        for(int i=0; i<(int)(n); ++i)
int main() {
  int a,b,c;
  cin>>a>>b;
  c=(a+b)/2;
  if(c*2==a+b)cout<<c;
  else cout<<c+1;
}


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

#define all(v) v.begin(), v.end()
#define V vector
#define P pair
typedef long long ll;
const int INT_INF = 1e9;
const ll INF = 1LL << 30;

int main() {
    V<int> v(3);
    for(int i = 0; i < 3; i++) cin >> v[i];
    sort(all(v));

    int x = v[2] - v[0];
    int y = v[2] - v[1];
    int a = 0, b = 0;
    if(x > 1){
        a = x / 2;
        x %= 2;
    }
    if(y > 1){
        b = y / 2;
        y %= 2;
    }
    int cnt = 0;
    if(x == 1 && y == 1) cnt++;
    else if(x == 1 || y == 1) cnt += 2;
    cout << cnt + a + b << endl;
}


Measured memory_bytes: 256
#include <cstdio>

int search(int A[], int n, int key) {
    int i = 0;
    A[n] = key;
    while (A[i] != key) {
        i++;
    }

    return i != n;
}

int main() {
    int i, n, A[100001], q, key, sum = 0;
    scanf("%d", &n);
    for (i = 0; i < n; ++i) {
        scanf("%d", &A[i]);
    }

    scanf("%d", &q);
    for (i = 0; i < q; ++i) {
        scanf("%d", &key);
        if (search(A, n, key)) {
            sum++;
        }
    }

    printf("%d\n", sum);

    return 0;
}



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

using namespace std;
typedef long long ll;
typedef string str;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector <pii> vpii;
typedef vector <pll> vpll;
typedef map <str,int> mapsi;
typedef map <str,int> :: iterator mapsitr;
typedef map <int , int> mint;
typedef map <ll , ll> mll;
typedef set <int> si;
typedef set <ll> sll;
typedef si :: iterator sitr;
typedef si :: reverse_iterator rsitr;
typedef sll :: iterator sltr;
typedef sll :: reverse_iterator rsltr;
#define mset multiset

typedef mset <int> msi;
typedef mset <ll> msll;
typedef msi :: iterator msitr;
typedef msi :: reverse_iterator msritr;
typedef msll :: iterator msltr;
typedef msll :: reverse_iterator mslritr;

#define mp make_pair
#define pb push_back
#define pob pop_back
#define pf push_front
#define pof pop_front
#define fi first
#define se second
#define fs first.second
#define ss second.second
#define ff first.first
#define sf second.first
#define newl '\n'

char to_upper (char x){
    if( 97 <= int(x) && int(x) <= 126)return char(x-32);
    else if( 65 <= int(x) && int(x) <= 90)return x;
}
char to_lower (char x){
    if( 97 <= int(x) && int(x) <= 126)return x;
    else if( 65 <= int(x) && int(x) <= 90)return char(x+32);
}
int numerize (char x){
    if(48 <= int(x) && int(x) <= 57)return int(x-'0');
    else if( 97 <= int(x) && int(x) <= 126)return int(x-96);
    else if( 65 <= int(x) && int(x) <= 90)return int(x-64);
}
bool isect (int l1, int r1, int l2, int r2){
    pii p1,p2;
    p1 = mp(l1,r1); p2 = mp(l2,r2);
    if(p1>p2)swap(p1,p2);
    if(p2.fi <= p1.se)return true;
    else return false;
}
ll fexp (ll num1, ll num2, ll MOD){
    if(num2==0)return 1;
    else if(num2==1)return num1;
    else{
        ll temp = fexp (num1,num2/2,MOD); ll res = ((temp%MOD) * (temp%MOD))%MOD;
        if(num2%2==1) res = ((res%MOD)*(num1%MOD))%MOD; return res;
    }
}
ll invmod (ll num, ll MOD){return fexp (num,MOD-2,MOD);}
ll gcd (ll num1, ll num2){
    if(num1 < num2) swap(num1,num2); ll num3 = num1 % num2 ;
    while(num3 > 0){ num1 = num2; num2 = num3; num3 = num1 % num2;}
    return num2;
}
ll lcm (ll num1 , ll num2){return (ll) (num1/gcd(num1,num2))*num2;}


// end of Template
str s;
int main(){

//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin>>s;
    cout<<"ABC"<<s<<newl;

}


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

typedef pair<int,int> pi;
typedef vector<int> vi;
 
#define FOR(i,a,b) for(int i = (a); i < (b); ++i)
#define pb push_back

template<typename T> void max_self(T &a, T b) { a = max(a,b); return;}
template<typename T> void min_self(T &a, T b) { a = min(a,b); return;}
 
const int nax = 1e5 + 5;
const int mod = 1e9 + 7;

int modExpo(int a,int b,int c){
	if(b == 0) return 1;
	int answer = 1;
	while(b){
		if(b & 1) answer = ((answer % c) * (a % c)) % c;
		a = ((a % c) * (a % c)) % c;
		b /= 2; 
	}
	
	return answer;
}

signed main(){
	
	std::ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	int t = 1;
	//cin >> t;
	while(t--){
		int a;
		cin >> a;
		
		cout << a + a * a + a * a * a << "\n";
	}
    
    return 0;
}


Measured memory_bytes: 3620
#include<bits/stdc++.h>
using namespace std;
using ll = long long; 
using ull = unsigned long long;
using V = vector<int>;
using VV = vector<vector<int>>;
using VVV = vector<vector<vector<int>>>;
using VL = vector<ll>;
using VVL = vector<vector<ll>>;
using VVVL = vector<vector<vector<ll>>>;
template<class T> using pq = priority_queue<T>;
template<class T> using P = pair<T, T>;
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define REP(i,k,n) for(int i=(k);i<(n);i++)
#define all(a) (a).begin(),(a).end()
#define output(x,y) cout << fixed << setprecision(y) << x << endl;
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; }
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
// const ll MOD = 1e9 + 7;
const ll MOD = 998244353;
ll upper = MOD + MOD;
ll under = -upper;
ll UPPER = MOD * MOD;
ll UNDER = -UPPER;
const long double pi = 3.141592653589793;
ll fac[210000];
ll finv[210000];
ll inv[210000];
void modinv(int max) {
	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 comb(int n, int r) {
	if (n < r) return 0;
	if (n < 0 || r < 0) return 0;
	return fac[n] * (finv[r] * finv[n - r] % MOD) % MOD;
}
ll modpow(ll a, ll b, ll M) {
	ll res = 1;
	for (; b > 0; b >>= 1) {
		if (b & 1) res = (res * a) % M;
		a = a * a % M;
	}
	return res;
}
int main() { // 問題文はしっかり読め!!!
	modinv(202020);
	int n, m, k;
	cin >> n >> m >> k;
	ll ans = 0;
	rep(i, k + 1) {
		ll tmp = comb(n - 1, i) * m;
		tmp %= MOD;
		tmp *= modpow(m - 1, n - i - 1, MOD);
		tmp %= MOD;
		ans += tmp;
		ans %= MOD;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 8392
N, M  = map(int, input().split())
li = []
for i in range(M):
    li.append(list(map(int, input().split())))

li2 = [-1 for i in range(5)]
flag = 0
for i in range(M):
    if li2[li[i][0]] == -1 or li2[li[i][0]] == li[i][1]:
        li2[li[i][0]] = li[i][1]
    else:
        flag = 1
        break
if li2[1] == 0 and N != 1:
    flag = 1
if flag == 1:
    print(-1)
else:
    if N == 1 and M == 0:
        print(0)
    else:
        for i in range(1, N+1):
            if i == 1:
                if li2[i] == -1:
                    print(1, end="")
                else:
                    print(li2[i], end="")
            else:
                if li2[i] == -1:
                    print(0, end="")
                else:
                    print(li2[i], end="")

Measured memory_bytes: 38488
#include <iostream>
#include <string>



int main() {
  std::string in;
  std::cin >> in;

  int a = std::stoi(in);

  switch (a%10) {
    case 3:
      std::cout << "bon" << std::endl;
      break;
    case 0:
    case 1:
    case 6:
    case 8:
      std::cout << "pon" << std::endl;
      break;
    default:
      std::cout << "hon" << std::endl;
      break;
  }

  return 0;

}


Measured memory_bytes: 3044
import java.util.*;

public class Main {
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
		int h = sc.nextInt();
		int w = sc.nextInt();
		int n = sc.nextInt();
		int[][] field = new int[h][w];
		int[] arr = new int[n];
		for (int i = 0; i < n; i++) {
		    arr[i] = sc.nextInt();
		}
		int hh = 0;
		int ww = 0;
		for (int i = 0; i < n; i++) {
		    for (int j = 0; j < arr[i]; j++) {
		        field[hh][ww] = i + 1;
		        if(hh % 2 == 0) {
		            if (ww == w - 1) {
		                hh++;
		            } else {
		                ww++;
		            }
		        } else {
		            if (ww == 0) {
		                hh++;
		            } else {
		                ww--;
		            }
		        }
		    }
		}
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < h; i++) {
		    for (int j = 0; j < w; j++) {
		        if (j != 0) {
		            sb.append(" ");
		        }
		        sb.append(field[i][j]);
		    }
		    sb.append("\n");
		}
	    System.out.print(sb);
   }
}




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

int main()
{
	int n, k;

	cin >> n >> k;

	vector<pair<long long, int> > d(n);

	for (int i = 0; i < n; i++)
		cin >> d[i].second >> d[i].first;

	sort(d.begin(), d.end(), greater<pair<long long, int>>());

	vector<int> tc(n, 0);
	vector<long long> v(k, 0);
	vector<long long> w;
	long long m = 0;
	int u = 0;

	for (int i = 0; i < k; i++) {
		m += d[i].first;

		if (tc[d[i].second - 1] == 0)
			u++;
		else
			w.push_back(d[i].first);

		tc[d[i].second - 1]++;
	}

	v[u - 1] = m;

	int p = k;

	while (w.size() > 0) {

		while (p < n && tc[d[p].second - 1] > 0)
			p++;

		if (p == n)
			break;

		v[u] = v[u - 1] + d[p].first - w.back();
		tc[d[p].second - 1] = 1;
		w.pop_back();
		u++;
	}

	long long mx = 0;

	for (int i = 0; i < k; i++) {
		if(v[i] > 0)
			mx = max(mx, v[i] + (long long)(i + 1) * (long long)(i + 1));
	}

	cout << mx << endl;

	return 0;
}

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

int main(){
    int n,x;
    char ch;
    cin>>n;
    int a[4][13]={};
    for(int i=1;i<=n;i++){
        cin>>ch>>x;
        if(ch=='S'){
            for(int j=1;j<=13;j++){
                if(x==j){
                    a[0][x-1]=1;
                }
            }
        }
        if(ch=='H'){
            for(int j=1;j<=13;j++){
                if(x==j){
                    a[1][x-1]=1;
                }
            }
        }
        if(ch=='C'){
            for(int j=1;j<=13;j++){
                if(x==j){
                    a[2][x-1]=1;
                }
            }
        }
        if(ch=='D'){
            for(int j=1;j<=13;j++){
                if(x==j){
                    a[3][x-1]=1;
                }
            }
        }
    }
    for(int k=0;k<4;k++){
        for(int l=0;l<13;l++){
            if((a[k][l]==0)&&(k==0)){
                cout<<'S'<<' '<<l+1<<endl;
            }
            if((a[k][l]==0)&&(k==1)){
                cout<<'H'<<' '<<l+1<<endl;
            }
            if((a[k][l]==0)&&(k==2)){
                cout<<'C'<<' '<<l+1<<endl;
            }
            if((a[k][l]==0)&&(k==3)){
                cout<<'D'<<' '<<l+1<<endl;
            }
        } 
    }
}


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

using namespace std;
 
int main()
{
    int n, num, w;
    pair<int, int> p[20];  
 
    cin >> n;
    for (int i = 0; i < n; i++) {
	cin >> num >> w;
	p[i] = make_pair(-w, num);
    }
    sort(p, p+n);
    cout << p[0].second << ' ' << (-1) * p[0].first << endl;
    return 0;
}

Measured memory_bytes: 3092
use std::io;


fn main() {
    let (n, m, c) = {
        let i = read::<isize>();
        (i[0], i[1], i[2])
    };
    let bm = read::<isize>();
    let mut an = Vec::new();
    for _ in 0..n {
        an.push(read::<isize>());
    }

    let mut cnt = 0;
    for i in 0..n as usize {
        let mut sum = c;
        for j in 0..m as usize {
            sum += an[i][j] * bm[j];
        }
        if sum > 0 { cnt += 1; }
    }

    println!("{}", cnt);
}


#[allow(dead_code)]
fn read<T>() -> Vec<T>
where T:
std::str::FromStr,
T::Err: std::fmt::Debug {

    let mut buf = String::new();
    io::stdin().read_line(&mut buf).unwrap();
    buf.split_whitespace()
        .map(|s| s.trim().parse().unwrap())
        .collect()
}

#[allow(dead_code)]
fn read_one<T>() -> T
where T:
std::str::FromStr,
T::Err: std::fmt::Debug {

    let mut buf = String::new();
    io::stdin().read_line(&mut buf).unwrap();
    buf.trim().parse().unwrap()
}

Measured memory_bytes: 4352
#include<bits/stdc++.h>
using namespace std;
 
#define DEBUG
#ifdef DEBUG
#define debug(...) __f(#__VA_ARGS__, __VA_ARGS__)
	template <typename Arg1>
	void __f(const char* name, Arg1&& arg1)
	{
		cerr << name << " = " << arg1 << endl;
	}
	template <typename Arg1, typename... Args>
	void __f(const char* names, Arg1&& arg1, Args&&... args)
	{
		const char* comma = strchr(names + 1, ','); cerr.write(names, comma - names) << " = " << arg1 << " || ";
		__f(comma+1, args...);
	}
#else
#define debug(...)
#endif
 
template <class Ch, class Tr, class Container>
basic_ostream <Ch, Tr> & operator << (basic_ostream <Ch, Tr> & os, Container const& x) {
    os << "{ ";
    for(auto& y : x) os << y << " ; ";
    return os << "}";
}
 
template <class X, class Y>
ostream & operator << (ostream & os, pair <X, Y> const& p) {
	return os << "[ " << p.first << ", " << p.second << "]" ;
}
 
#define FAST_IO std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long int
#define pb push_back
#define mp make_pair
#define ld long double
#define sz(a) (ll)(a).size()
#define endl "\n"
 
// priority_queue<ll, vector<ll>, less<ll>>pq;     // Max Heap
// priority_queue<ll, vector<ll>, greater<ll>>pq;

const int MAXN = 5e5 + 5;

ll n, q, a[MAXN], nx[MAXN];
vector<ll>adj[MAXN], segtree[2 * MAXN];

void build()
{
	for(int i=n-1;i>0;i--)
	{
		ll p=0, q=0;
		while(p<segtree[2*i].size() && q<segtree[2*i+1].size())
		{
			if(segtree[2*i][p] < segtree[2*i+1][q]) segtree[i].pb(segtree[2*i][p++]);
			else segtree[i].pb(segtree[2*i+1][q++]);
		}
		while(p < segtree[2*i].size()) segtree[i].pb(segtree[2*i][p++]);
		while(q < segtree[2*i+1].size()) segtree[i].pb(segtree[2*i+1][q++]);
	}
}
ll query(ll l,ll r,ll x)
{
	ll ans = 0;
	for(l+=n-1,r+=n ; l<r ; l/=2,r/=2)
	{
		if(l%2)
		{		
			ans+=upper_bound(segtree[l].begin(),segtree[l].end(),x)-segtree[l].begin();
			l++;
		}	
		if(r%2)
		{	
			r--;
			ans+=upper_bound(segtree[r].begin(),segtree[r].end(),x)-segtree[r].begin();
		}		
	}
	return ans;
}

int main()
{
	FAST_IO;
 
 	cin >> n >> q;
 	for(int i=0;i<n;i++) cin >> a[i];
 	for(int i=n-1;i>=0;i--)
 	{
 		if(!sz(adj[a[i]])) nx[i] = n;
 		else nx[i] = adj[a[i]].back();
 		adj[a[i]].pb(i);
 	}
 	for(int i=0;i<n;i++) segtree[n + i].pb(nx[i]);
 	build();
 	while(q--)
 	{
 		ll l, r;
 		cin >> l >> r;
 		cout << r - l + 1 - query(l, r, r - 1) << endl;
 	}
    return 0;
}

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

using namespace std;

#define ll  long long
#define X   first
#define Y   second

const int   N   = 2e5 + 1;

typedef pair<int,int>   ii;

vector<ii>  g[N];

int h[N];
ll  f[N];
ll  l[N], r[N];

ll  dfs(int u,int p,ll  v)  {
    if (h[u])   {
        if (h[u] % 2 == h[p] % 2)   {
            ll  cur = abs(v - f[u]);
            if (cur & 1)    return  -1;
            if (cur == 0)   return  -1;
            l[u] = max(l[u],cur / 2);
            r[u] = min(r[u],cur / 2);
            if (l[u] > r[u])
                l[u] = -1,
                r[u] = -2;
            return  cur / 2;
        }
        return  0 - (v != f[u]);
    }
    l[u] = 1;
    r[u] = 1e9;
    h[u] = h[p] + 1;
    f[u] = v;
    for(ii  e : g[u])   if (e.X != p)   {
        int x = e.X;
        int s = e.Y;
        ll  y = dfs(x,u,v + s * (h[u] & 1 ? -1 : 1));
        if (y <  0) return  -1;
        if (y >= s) return  -1;
        l[u] = max(l[u],s - r[x]);
        r[u] = min(r[u],s - l[x]);
    }
    if (l[u] > r[u])
        l[u] = -1,
        r[u] = -2;
    return  l[u];
}

int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n, m;   cin >> n >> m;

    while (m--) {
        int x, y, s;    cin >> x >> y >> s;
        g[x].push_back({y,s});
        g[y].push_back({x,s});
    }

    if (dfs(1,0,0) < 0)
        return  0 * puts("0");

    cout << r[1] - l[1] + 1;
}

Measured memory_bytes: 20608