akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <string>
#include <sstream>
#include <set>
#include <map>
#include <iostream>
#include <utility>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <unordered_set>
#include <unordered_map>
#include <limits.h>
#include <cstring>
#include <tuple>
#include <cassert>
#include <numeric>
using namespace std;
// type alias
typedef long long LL;
typedef vector < int > VI;
typedef unordered_map < int, int > MAPII;
typedef unordered_set < int > SETI;
typedef pair< int , int > II;
typedef tuple< int, int, int > III;
// repetition
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)
#define REPE(i,n)  for(int i=0;i<=(n);++i)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  for(int i=0;i<(n);++i)
#define FORR(x,arr) for(auto& x:arr)
#define SZ(a) int((a).size())
// DP
#define MINUS(dp) memset(dp, -1, sizeof(dp))
#define ZERO(dp) memset(dp, 0, sizeof(dp))
// minmax
#define SMAX(a,b) a = max(a,b)
#define SMIN(a,b) a = min(a,b)
// debug cerr
#define TRACE true
#define dump(x) if(TRACE) { cerr << #x << " = " << (x) << endl; }
#define dump2(x,y) if(TRACE) { cerr << #x << " = " << (x) << ", " << #y << " = " << (y) << endl; }
#define dump3(x,y,z) if(TRACE) { cerr << #x << " = " << (x) << ", " << #y << " = " << (y) << ", " << #z << " = " << (z) << endl; }
#define dump4(x,y,z,a) if(TRACE) { cerr << #x << " = " << (x) << ", " << #y << " = " << (y) << ", " << #z << " = " << (z) << ", " << #a << " = " << (a) << endl; }
#define dumpAR(ar) if(TRACE) { FORR(x,(ar)) { cerr << x << ','; } cerr << endl; }

/*
 
 7/29/2018
 
 22:55-23:10, 24:25-
 
 */

// $ g++ -std=c++14 -Wall -O2 -D_GLIBCXX_DEBUG x.cpp && ./a.out
const int MAX_N=2000+1;
int N;
LL Z,W;
LL A[MAX_N];
LL memo[MAX_N][2];

LL f(int s, int p) {
  LL &res=memo[s][p];
  if(res>=0) return res;
  int s2=s==0?W:A[s-1];
  res=abs(A[N-1]-s2);
  FOR(i,s,N-1) {
    if(p==0) SMAX(res,f(i+1,p^1));
    else SMIN(res,f(i+1,p^1));
  }
  return res;
}
void solve() {
  MINUS(memo);
  LL res=f(0,0);
  cout<<res<<endl;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  
  cin>>N>>Z>>W;
  REP(i,N) cin>>A[i];
  solve();
  return 0;
}


Measured memory_bytes: 512
#include "bits/stdc++.h"

using namespace std;

#define print(s) cout << (s) << endl;
#define sp(x) cout<<setprecision(x);
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n) 
#define all(a) (a).begin(), (a).end()
#define inf 10000000
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    string a,b,c;cin>>a>>b>>c;
    if(a[a.size()-1]==b[0]&&b[b.size()-1]==c[0]){
        cout<<"YES"<<endl;
    }else{
        cout<<"NO"<<endl;
    }
return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main()
{
	long a, b, tmp, x, r;
	
	scanf("%ld %ld", &a, &b);
	
	x = a * b;
	if(a<b){
	tmp = a;
	a = b;
	b = tmp;
	}
	r = a % b;
	while(r!=0){
	a = b;
	b = r;
	r = a % b;
	}
	
	printf("%ld\n", x/b);
	
return 0;
}

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

//template
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(a);i>(b);i--)
#define ALL(v) (v).begin(),(v).end()
typedef long long int ll; const int inf = 0x3fffffff; const ll INF = 0x3fffffffffffffff;
template<class T> inline bool chmax(T& a,T b){ if(a<b){a=b;return 1;}return 0; }
template<class T> inline bool chmin(T& a,T b){ if(a>b){a=b;return 1;}return 0; }
//template end



int main(){
    int n; scanf("%d",&n); bool f=0; int ans=0;
    rep(i,0,50001)if(1LL*i*108/100==n)f=1,ans=i;
    if(f)printf("%d\n",ans); else printf(":(\n");
    return 0;
}

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

const int MAXN = 100010;
typedef long long LL;
int n, A[MAXN], rk[MAXN]; LL ansl[MAXN];
int main() {
	std::ios_base::sync_with_stdio(false), std::cin.tie(0);
	std::cin >> n;
	for (int i = 1; i <= n; ++i) std::cin >> A[i], rk[i] = i;
	std::sort(rk + 1, rk + 1 + n, [] (int a, int b) {
		return A[a] == A[b] ? a < b : A[a] > A[b];
	});
	int cur = 1, mx = n + 1;
	while (cur <= n) {
		int tv = A[rk[cur]];
		while (cur <= n && A[rk[cur]] == tv)
			mx = std::min(mx, rk[cur++]);
		ansl[mx] += (LL) (tv - A[rk[cur]]) * (cur - 1);
	}
	for (int i = 1; i <= n; ++i) std::cout << ansl[i] << '\n';
	return 0;
}


Measured memory_bytes: 2688
#include <algorithm>
#include <array>
#include <cmath>
#include <iostream>
#include <vector>
using namespace std;

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

  int64_t N;

  cin >> N;

  int64_t x = 1;
  while (x <= N) {
    x *= 2;
  }
  cout << x / 2;

  return 0;
}


Measured memory_bytes: 3576
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long int n,k,i;
     cin>>n>>k;
    map<long long int,long long int>m;
    while(k--)
    {
        long long int d;
        cin>>d;
        long long int  a[d];
        for(i=0;i<d;i++)
            cin>>a[i];
        for(i=0;i<d;i++)
        {
            m[a[i]]++;
        }
    }
    long long int c=0;
    for( i=1;i<=n;i++)
        if(m[i]==0)
            c++;
    cout<<c;
    return 0;
}


Measured memory_bytes: 3632
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from collections import deque

N,*A = map(int,read().split())

B = deque()
reverse = False
for x in A:
    if reverse:
        B.appendleft(x)
    else:
        B.append(x)
    reverse = not reverse

B = list(B)
if reverse:
    B = B[::-1]

print(' '.join(map(str,B)))

Measured memory_bytes: 30664
n,k,q = list(map(int, input().split()))
a = [k-q for i in range(n)]

for i in range(q):
  b = int(input())
  a[b-1] += 1
  
for i in range(n):
  if a[i] > 0:
    print("Yes")
  else:
    print("No")

Measured memory_bytes: 7920
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll max(ll a,ll b)
{
    return((a>b)?a:b);
}
int main()
{
    int n,W,i,j;
    cin>>n>>W;
    int w[n],v[n];
    for(i=0;i<n;i++)
    {
        cin>>w[i]>>v[i];
    }
    ll dp[n+1][W+1];
    for(i=0;i<=n;i++)
    {
        for(j=0;j<=W;j++)
        {
            if((i==0)||(j==0))
            {
                dp[i][j]=0;
            }
            else if(j<w[i-1])
            {
                dp[i][j]=dp[i-1][j];
            }
            else
            {
                dp[i][j]=max(dp[i-1][j],v[i-1]+dp[i-1][j-w[i-1]]);
            }
        }
    }
    cout<<dp[n][W];
}


Measured memory_bytes: 79104
s = input()

for _ in range(10**5//5):
  if s.endswith('dream') or s.endswith('erase'):
    s = s[:-5]
  if s.endswith('eraser'):
    s = s[:-6]
  if s.endswith('dreamer'):
    s = s[:-7]
    
print('YES') if s == '' else print('NO')
  

Measured memory_bytes: 3188
#include <bits/stdc++.h>  
using namespace std;  
typedef unsigned long long ll; 
typedef long double ld;
const double eps = 1e-10;
const int INF = 0x3f3f3f3f;  
const int N = 100000 + 5;
map<string,int> mp;

int main()
{
	int n;
	cin >> n;
	string s;
	int cnt = 0;
	for(int i = 1; i <= n; i++){
		cin >> s;
		if(mp[s] == 1);
		else{
			cnt++;
			mp[s] = 1;
		}
	}
	cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 19228
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <map>
#include <time.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;

int main(){

	int N;
	scanf("%d",&N);

	char table[N+1][N+1];
	for(int row = 1; row <= N; row++){
		scanf("%s",table[row]);
	}

	int count;

	for(int row = 1; row <= N; row++){
		count = 0;
		for(int col = 0; col < N; col++){
			if(table[row][col] == 'o')count++;
			if(count == N-1){
				for(int i = 0; i < 1000; i++){
					printf("%d\n",row);
				}
				return 0;
				break;
			}
		}
	}

	srand((unsigned int)time(NULL));

	int number = rand()%N+1;

	for(int loop = 1; loop <= 1000; loop++){

		printf("%d\n",number);fflush(stdout);
		number = rand()%N+1;
	}

	return 0;
}

Measured memory_bytes: 3388
#include<stdio.h>

int main(void){

    int n,m,l;
    scanf("%d %d %d", &n, &m, &l);
    int a[n][m],b[m][l];
    long long int c[n][l];
    int i,j;

    for(i=0;i<n;i++){
        for(j=0;j<l;j++){
            c[i][j]=0;
        }
    }


    for(i=0;i<n;i++){
        for(j=0;j<m;j++){
            scanf("%d", &a[i][j]);
           // printf("%d",a[i][j]);
        }
    }

    for(i=0;i<m;i++){
        for(j=0;j<l;j++){
            scanf("%d", &b[i][j]);
            //printf("%d",b[i][j]);
        }
    }
/*
   // printf("========\n");
     //       printf("%d",b[0][1]);

printf("========\n");
//printf("m=%d\n",m);
for(i=0;i<n;i++){
        for(j=0;j<m;j++){
  //          printf("j=%d\n",j);
            if(j==m-1){
            printf("%d",a[i][j]);
            }else{
            printf("%d ",a[i][j]);
            }
    //        printf(" #%d# ",j);
        }
        printf("\n");
    }
  

for(i=0;i<m;i++){
        for(j=0;j<l;j++){
            if(j==l-1){
            printf("%d",b[i][j]);
            }else{
            printf("%d ",b[i][j]);
            }
        }
        printf("\n");
    }
*/

//printf("\n\n\n\n\n\n\n");

    int k=0;
    for(i=0;i<n;i++){
        for(j=0;j<l;j++){
            for(k=0;k<m;k++){ //kも０からはじまる！！
                c[i][j]+=a[i][k]*b[k][j];
            }
            if(j==l-1){
            printf("%lld",c[i][j]);
            }else{
            printf("%lld ",c[i][j]);
            }
        }
        printf("\n");
    }

    return 0;
}


Measured memory_bytes: 2112
#include <iostream>

int main(){
 int* x=new int[5];
 int ans=0;
 for(int i=0;i<5;i++){
  std::cin>>x[i];
  if(x[i]==0){
   ans=i+1;
  }
 }

 std::cout<<ans<<std::endl;

 
 return 0;
}

Measured memory_bytes: 3628
#include <iostream>
#include <stdio.h>
#define _USE_MATH_DEFINES
#include <math.h>
#include <set>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
#include <limits>
#include <bitset>
#include <stack>
#include <queue>
#include <ctype.h>

typedef long long int lli;
#define rep(i,s,N) for(int i=s;i<N;i++)
#define MOD 1000000007
#define more(a,b) (((a)>(b))?(a):(b))
#define less(a,b) (((a)<(b))?(a):(b))

using namespace std;
int N, M;

lli GCD(lli a, lli b)
{
	lli x = more(a, b);
	lli y = less(a, b);
	lli r = x % y;
	while (r > 0) {
		x = y;
		y = r;
		r = x % y;
	}
	return y;
}

int solver(vector<lli> &a)
{
	while (a[0] % 2 == 0) {
		rep(i, 0, N) {
			if (a[i] % 2 == 0)a[i] /= 2;
			else return 0;
		}
		M /= 2;
	}
	rep(i, 1, N)if (a[i] % 2 == 0)return 0;
	lli lcm = 1;
	rep(i, 0, N) {
		lli g = GCD(lcm, a[i]);
		lcm = lcm / g * a[i];
	}
	return (M / lcm + 1) / 2;
}

int main(void)
{
	cin >> N >> M;
	vector<lli> a(N); 
	rep(i, 0, N) {
		cin >> a[i];
		a[i] /= 2;
	}

	cout << solver(a) << endl;


	return 0;
}


Measured memory_bytes: 1024
import sys

N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
A = [0] + A
town = 1
visited = [0]*(N+1)

for i in range(1, K+1):
    town = A[town]
    if visited[town] == 0:
        visited[town] = i
    else:
        loop = i - visited[town]
        place = (K - visited[town]) % loop + visited[town]
        print(visited.index(place))
        sys.exit()
print(town)

Measured memory_bytes: 32312
#include <iostream>
#include <fstream>
#include <set>
#include <map>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <functional>
#include <algorithm>
#include <climits>
#include <cmath>
#include <iomanip>
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 2000000000000000000
#define int long long
typedef pair<int, int> P;
int A[3], D;
int choice[3] = {2, 3, 5};
map<int, int> d;
void dijkstra(int N) {
    priority_queue<P, vector<P>, greater<P>> que;
    d[N] = 0;
    que.push(P(0, N));
    while (!que.empty()) {
        P p = que.top(); que.pop();
        int v = p.second;
        if (d[v] < p.first) continue;
        if(v <= 1) continue; 
        //cout << v << " " << d[v] << endl;
        vector<P> v2;
        rep(i, 3) {
            int moveL = v % choice[i];
            int moveR = (choice[i] - v % choice[i]) % choice[i];
            int cost1 = A[i] + moveL * D;
            int cost2 = (v - ((v - moveL) / choice[i])) * D;
            int cost3 = A[i] + moveR * D;
            int cost4 = (v - ((v + moveR) / choice[i])) * D;
            double a = (v - ((v - moveL) / choice[i])), b = D;
            if(a * b >= INF2) cost2 = cost4 = INF2;
            v2.push_back({(v - moveL) / choice[i], min(cost1, cost2)});
            v2.push_back({(v + moveR) / choice[i], min(cost3, cost4)});
        }
        for(auto& e: v2) {
            if(d.find(e.first) == d.end()) d[e.first] = INF2;
            //cout << "*" << e.first << " " << d[e.first] << " " << d[v] << " " << e.second << endl;
            if (d[e.first] > d[v] + e.second) {
                d[e.first] = d[v] + e.second;
                que.push(P(d[e.first], e.first));
            }
        }
    }
}

signed main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int T; cin >> T;
    while(T--) {
        int N;
        cin >> N >> A[0] >> A[1] >> A[2] >> D;
        d.clear();
        dijkstra(N);
        cout << d[1] + D << endl;
    }

    return 0;
}


Measured memory_bytes: 4436
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
#include <cstdlib>
struct E {
    int mp;
    int bamboos;
};
struct S {
    std::vector<E>::iterator a, b, c;
};
struct C {
    bool operator()(const S &x, const S &y) const {
        return x.a->mp + x.b->mp + x.c->mp > y.a->mp + y.b->mp + y.c->mp;
    }
};
int calc_mp(int target, int bamboos, std::vector<int> &lengths) {
    if (bamboos == 0) {
        return INT_MAX / 3;
    }
    int mp = -10;
    int n = lengths.size();
    for (int i = 0; i < n; i++) {
        if (bamboos & (1 << i)) {
            mp += 10;
            target -= lengths[i];
        }
    }
    mp += std::abs(target);
    return mp;
}
int main() {
    int n, a, b, c;
    std::cin >> n >> a >> b >> c;
    std::vector<int> l(n);
    for (auto &li: l) std::cin >> li;
    int m = 1 << n;
    std::vector<E> ae(m), be(m), ce(m);
    for (int i = 0; i < m; i++) {
        ae[i].bamboos = i;
        be[i].bamboos = i;
        ce[i].bamboos = i;
        ae[i].mp = calc_mp(a, i, l);
        be[i].mp = calc_mp(b, i, l);
        ce[i].mp = calc_mp(c, i, l);
    }
    std::sort(ae.begin(), ae.end(), [](const E &x, const E &y){ return x.mp < y.mp; });
    std::sort(be.begin(), be.end(), [](const E &x, const E &y){ return x.mp < y.mp; });
    std::sort(ce.begin(), ce.end(), [](const E &x, const E &y){ return x.mp < y.mp; });
    std::priority_queue<S, std::vector<S>, C> q;
    q.push({ ae.begin(), be.begin(), ce.begin() });
    for (;;) {
        S s = q.top();
        q.pop();
        if ((s.a->bamboos & s.b->bamboos) == 0 &&
            (s.a->bamboos & s.c->bamboos) == 0 &&
            (s.b->bamboos & s.c->bamboos) == 0) {
            std::cout << (s.a->mp + s.b->mp + s.c->mp);
            break;
        }
        q.push({ s.a + 1, s.b, s.c });
        q.push({ s.a, s.b + 1, s.c });
        q.push({ s.a, s.b, s.c + 1 });
    }
}

Measured memory_bytes: 256
fun main(args : Array<String>) {
    val n = readLine()!!.toInt()
    val aa = readLine()!!.split(" ").map { it.toInt() }

    println(aa.fold(aa[0], { acc, a -> gcd(acc, a)}))
}

fun gcd(a : Int, b : Int) : Int {
    return if (a % b == 0) b else gcd(b, a % b)
}


Measured memory_bytes: 54016
#include<stdio.h>
int a[6],hantei[4],flag,i;
int main(void){
    for(i = 0;i < 6;i++){
        scanf("%d",&a[i]);
    }
    for(i = 0;i < 6;i++){
        switch (a[i]){
            case 1:
            hantei[0] += 1;
            break;
            case 2:
            hantei[1] += 1;
            break;
            case 3:
            hantei[2] += 1;
            break;
            case 4:
            hantei[3] += 1;
            break;

        }
    }
    flag = 0;
    for(i = 0;i < 4;i++){
        if(hantei[i] >= 3){
            flag =1;
        }
    }
    if(flag == 0){
        printf("YES");
    }else{
        printf("NO");
    }
    return 0;
}

    

Measured memory_bytes: 128
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <map>
#include <stack>
#include <queue>
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main()
{
    int n;
    scanf("%d", &n);
    vector<int> a(n);
    for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
    map<int, int> dic;
    int num = 0;
    for (int i = 0; i < n; ++i)
    {
        for (int k = 0; k < 8; k++)
        {
            if (a[i] >= 400 * k && a[i] < 400 * (k + 1))
            {
                ++dic[k];
            }
        }
        if (a[i] >= 3200) ++num;
    }
    int minval = dic.size() > 0 ? dic.size() : 1;
    int maxval = dic.size() + num;
    printf("%d %d\n", minval, maxval);
    return 0;
}


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

int main()
{
  int N;
  cin >> N;
  
  int X = N * 100 / 108;
  if(X * 108 / 100 == N)
  {
    cout << X << endl;
  }
  else if((X + 1) * 108 / 100 == N)
  {
    cout << X + 1 << endl;
  }
  else
  {
    cout << ":(" << endl;
  }
}

Measured memory_bytes: 3516
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<list>
#include<set>
#include<string>
#include<iomanip>
#include<math.h>
#include<bitset>
#include<functional>
#include<map>
using namespace std;
typedef long long ll;
#define lscan(x) scanf("%I64d",&x);
#define lprint(x) printf("%I64d",x);
ll gcd(ll a, ll b) {
	int c = a % b;
	while (c != 0) {
		a = b;
		b = c;
		c = a % b;
	}
	return b;
}
long long extGCD(long long a, long long b, long long &x, long long &y) {
	if (b == 0) {
		x = 1;
		y = 0;
		return a;
	}
	long long d = extGCD(b, a%b, y, x);
	y -= a / b * x;
	return d;
}
struct UnionFind {
	vector<int> par;

	UnionFind(int N) : par(N) {
		for (int i = 0; i < N; i++) par[i] = i;
	}

	int root(int x) {
		if (par[x] == x) return x;
		return par[x] = root(par[x]);
	}

	void unite(int x, int y) {
		int rx = root(x);
		int ry = root(y);
		if (rx == ry) return;
		par[rx] = ry;
	}

	bool same(int x, int y) {
		int rx = root(x);
		int ry = root(y);
		return rx == ry;
	}
};

ll M = 1000000007;

vector<ll> fac(1000001); //n!(mod M)
vector<ll> ifac(1000001); //k!^{M-2} (mod M)

ll mpow(ll x, ll n) {
	ll ans = 1;
	while (n != 0) {
		if (n & 1) ans = ans * x % M;
		x = x * x % M;
		n = n >> 1;
	}
	return ans;
}
ll mpow2(ll x, ll n, ll mod) {
	ll ans = 1;
	while (n != 0) {
		if (n & 1) ans = ans * x % mod;
		x = x * x % mod;
		n = n >> 1;
	}
	return ans;
}
void setcomb() {
	fac[0] = 1;
	ifac[0] = 1;
	for (ll i = 0; i < 1000000; i++) {
		fac[i + 1] = fac[i] * (i + 1) % M; // n!(mod M)
	}
	ifac[1000000] = mpow(fac[1000000], M - 2);
	for (ll i = 1000000; i > 0; i--) {
		ifac[i - 1] = ifac[i] * i%M;
	}
}
ll comb(ll a, ll b) {
	if (a == 0 && b == 0)return 1;
	if (a < b || a < 0)return 0;
	ll tmp = ifac[a - b] * ifac[b] % M;
	return tmp * fac[a] % M;
}
ll perm(ll a, ll b) {
	if (a == 0 && b == 0)return 1;
	if (a < b || a < 0)return 0;
	return fac[a] * ifac[a - b] % M;
}
long long modinv(long long a) {
	long long b = M, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= M;
	if (u < 0) u += M;
	return u;
}

vector<vector<ll>> li(222222);
int main() {
	ll x,i,j;
  cin>>x;
  for(i=x;;i++){
    int flag=1;
    for(j=2;j*j<=i;j++){
      if(i%j==0){
        flag--;
        break;
      }
    }
    if(flag){
      cout<<i<<endl;
      break;
    }
  }
}


Measured memory_bytes: 21120
using System;
using System.Collections.Generic;
using System.Collections;
using System.Collections.Specialized;
using System.Linq;
using System.Text;
using System.IO;
using System.Reflection;
using static System.Math;
using System.Numerics;
static class Program{
	const int mod=(int)1e9+7;
	const double eps=1e-11;
	static void Main(){
		Sc sc=new Sc();
		var s=sc.Ia;
		var a=sc.Ia;
		var b=sc.Ia;
		var c=sc.Ia;
		Array.Sort(a,(u,v)=>v.CompareTo(u));
		Array.Sort(b,(u,v)=>v.CompareTo(u));
		Array.Sort(c,(u,v)=>v.CompareTo(u));
		long p=0;
		for(int i = 0;i<s[0];i++) {
			p+=a[i];
		}
		for(int i = 0;i<s[1];i++) {
			p+=b[i];
		}
		int r=s[0]-1,g=s[1]-1;
		long ans=p;
		for(int i = 0;i<s[4];i++) {
			if(g<0&&r<0){
				break;
			}
			else if(g<0||(r>=0&&a[r]<=b[g])){
				p-=a[r];
				r--;
			}
			else if(r<0||a[r]>=b[g]){
				p-=b[g];
				g--;
			}
			p+=c[i];
			ans=Max(ans,p);
		}
		Console.WriteLine(ans);
	}
}
public class Sc{
	public int I{get{return int.Parse(Console.ReadLine());}}
	public long L{get{return long.Parse(Console.ReadLine());}}
	public double D{get{return double.Parse(Console.ReadLine());}}
	public string S{get{return Console.ReadLine();}}
	public int[] Ia{get{return Array.ConvertAll(Console.ReadLine().Split(),int.Parse);}}
	public long[] La{get{return Array.ConvertAll(Console.ReadLine().Split(),long.Parse);}}
	public double[] Da{get{return Array.ConvertAll(Console.ReadLine().Split(),double.Parse);}}
	public string[] Sa{get{return Console.ReadLine().Split();}}
	public object[] Oa{get{return Console.ReadLine().Split();}}
	public int[] Ia2{get{return Array.ConvertAll(("0 "+Console.ReadLine()+" 0").Split(),int.Parse);}}
	public int[] Ia3(int a){return Array.ConvertAll((a.ToString()+" "+Console.ReadLine()).Split(),int.Parse);}
	public int[] Ia3(bool a,int b,bool c,int d){return Array.ConvertAll(((a?b.ToString()+" ":"")+Console.ReadLine()+(c?" "+d.ToString():"")).Split(),int.Parse);}
	public long[] La2{get{return Array.ConvertAll(("0 "+Console.ReadLine()+" 0").Split(),long.Parse);}}
	public long[] La3(int a){return Array.ConvertAll((a.ToString()+" "+Console.ReadLine()).Split(),long.Parse);}
	public long[] La3(bool a,int b,bool c,int d){return Array.ConvertAll(((a?b.ToString()+" ":"")+Console.ReadLine()+(c?" "+d.ToString():"")).Split(),long.Parse);}
	public double[] Da2{get{return Array.ConvertAll(("0 "+Console.ReadLine()+" 0").Split(),double.Parse);}}
	public double[] Da3(int a){return Array.ConvertAll((a.ToString()+" "+Console.ReadLine()).Split(),double.Parse);}
	public double[] Da3(bool a,int b,bool c,int d){return Array.ConvertAll(((a?b.ToString()+" ":"")+Console.ReadLine()+(c?" "+d.ToString():"")).Split(),double.Parse);}
	public T[] Arr<T>(int n,Func<T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f();}return a;}
	public T[] Arr<T>(int n,Func<int,T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f(i);}return a;}
	public T[] Arr<T>(int n,Func<string[],T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f(Console.ReadLine().Split());}return a;}
	public T[] Arr<T>(int n,Func<int,string[],T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f(i,Console.ReadLine().Split());}return a;}
}

Measured memory_bytes: 37320
#include<bits/stdc++.h>
using namespace std;
int main(void){
    int n,m;
    cin>>n;
    int*D=new int[n];
    for(int i=0;i<n;i++){
        cin>>D[i];
    }
    sort(D,D+n);
    cin>>m;
    int*T=new int[m];
    for(int i=0;i<m;i++){
        cin>>T[i];
    }
    sort(T,T+m);
    int Tnum=0;
    for(int i=0;i<n;i++){
        if(D[i] == T[Tnum]){
            Tnum++;
            if(Tnum==m){
                cout<<"YES"<<endl;
                return 0;
            }
        }
    }
    cout<<"NO"<<endl;
    return 0;
}

Measured memory_bytes: 1792
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {

	static List<List<edge>> graph;

	static int[] d;

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(br.readLine());

		graph = new ArrayList<>();

		d = new int[n];

		for (int i = 0; i < n; i++) {
			String[] node_edge = br.readLine().split(" ");

			int k = Integer.parseInt(node_edge[1]);
			List<edge> node_edges = new ArrayList<>();
			for (int j = 0; j < k; j++) {
				node_edges.add(
						new edge(i, Integer.parseInt(node_edge[2 + j * 2]), Integer.parseInt(node_edge[3 + j * 2])));
			}
			graph.add(node_edges);
		}
		/*
		 * for(int i=0; i<graph.size(); i++){ for(edge e: graph.get(i)){
		 * System.out.println(e.from+""+e.to+""+e.cost); } }
		 */
		bell(0);

		for (int i = 0; i < d.length; i++) {
			System.out.println(i + " " + d[i]);
		}
	}

	static void bell(int sx) {

		Arrays.fill(d, Integer.MAX_VALUE / 2);
		d[sx] = 0;

		while (true) {
			boolean judge = true;
			for (int i = 0; i < graph.size(); i++) {

				List<edge> e = graph.get(i);

				for (edge now_edge : e) {

					int v = now_edge.to;
					int u = now_edge.from;
					int c = now_edge.cost;

					if (d[v] > d[u] + c) {
						d[v] = d[u] + c;

						/*
						 * System.out.println("from"+u+""+"to"+v + ""+"??????"+
						 * d[v]);
						 */
						judge = false;
					}

				}

			}
			if (judge) {
				break;
			}
		}

	}

	static class edge {

		int to;

		int from;

		int cost;

		public edge(int from, int to, int cost) {
			this.from = from;
			this.to = to;
			this.cost = cost;
		}
	}

}

Measured memory_bytes: 80156
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstring>
#include <math.h>
#define rep(i,n) for (int i = 1; i <= n; ++i)
using namespace std;
typedef long long ll;

int main() {
  int w,a,b,ans=0;
  cin >> w >> a >> b;

  if (a > b) swap(a, b);

  ans = b-(a+w) > 0 ? b-(a+w) : 0;

  cout << ans  <<endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<set>

using namespace std;

int main(){
	string s;
	cin>>s;
	set<char> sud,sap;
	for(char c:s){
		if(c=='N' or c=='S'){
			sud.insert(c);
		}
		else sap.insert(c);
	}
	if((sud.size()==0 or sud.size()==2) and (sap.size()==0 or sap.size()==2)){
		cout<<"Yes"<<endl;
	}
	else cout<<"No"<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <math.h>
#include <vector>
#include <algorithm>
#include <iomanip>


using namespace std;

int main(){
    string S;
    cin>>S;
    int N=S.size();
    int flag=0;
    if(S[0]!='A')flag=1;
    int count=0;
    for(int i=2;i<N-1;i++){
      if(S[i]=='C')count++;
    }
    if(count!=1)flag=2;
    count=0;
    for(int i=0;i<N;i++){
      if(S[i]<'a')count++;
    }
    if(count!=2)flag=3;
    if(flag==0)cout<<"AC"<<endl;
    else cout<<"WA"<<endl;
    // cout<<flag<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
 
int H, W;

int main(void){
	
	scanf("%d %d", &H, &W);
	vector<vector<char>> a(110, vector<char>(110, '#'));
	for(int i = 1; i <= H; ++i){
	    string temp; cin >> temp;
	    for(int j = 0; j < temp.size(); ++j){
	        a[i][j + 1] = temp[j];
	    }
	}
	
	for(int i = 0; i <= H + 1; ++i){
	    for(int j = 0; j <= W + 1; ++j){
	        printf("%c", a[i][j]);
	    }
	    printf("\n");
	}
	
    return 0;
}

Measured memory_bytes: 256
#include <iostream>

int main(){
    int x;
    std::cin >> x;

    int sum, count;
    sum = 0;
    count = 0;
    
    while(1){
        sum = sum + x;
        count = count + 1;
        if(sum % 360 == 0){
            break;
        }
    }
    std::cout << count << std::endl;
}

Measured memory_bytes: 3632
N, M, X, Y = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
minB = min(B)
maxA = max(A)
for i in range(X, Y+1):
  if maxA < i and minB >= i and X < i and i <= Y:
    print("No War")
    exit()
print("War")

Measured memory_bytes: 38256
object Main {

  import java.util.Scanner

  def main(args: Array[String]): Unit = {
    val sc = new Scanner(System.in)
    val writer = new java.io.PrintWriter(System.out)
    writer.println(solve(sc))
    writer.flush()
  }

  def solve(sc: Scanner): String = {
    val (n, m) = (sc.nextInt(), sc.nextInt())
    val gates = (1 to m).map(_ => (sc.nextInt(), sc.nextInt()))
    debug(n, m, gates)

    val leftMax = gates.map { case (l, _) => l }.max
    val rightMin = gates.map { case (_, r) => r }.min
    (if (leftMax > rightMin) 0 else rightMin - leftMax + 1).toString
  }

  private def debug(x: Any): Unit = {
    if (System.getenv("LOCAL_DEBUG") != null) println(x)
  }
}


Measured memory_bytes: 75496
#include <iostream>
#include <algorithm>
#include <iomanip>

int main()
{
    int n;
    std::cin >> n;

    double a[55];
    for (int i = 0; i < n; ++i)
    {
        std::cin >> a[i];
    }

    std::sort(a, a + n);
    double cur = a[0];
    for (int i = 1; i < n; ++i)
    {
        cur = (cur + a[i]) / 2;
    }

    std::cout << std::setprecision(10) << cur;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
typedef complex<double> pt;
typedef pair<pt,pt> L;
typedef vector<P> poly;
const double EPS = 1e-9;

int n;
double x[50005],r[50005];
int main(){
	while(1){
		cin >> n ; if(!n) return 0;
		rep(i,n) scanf("%lf%lf",&x[i],&r[i]);
		double lb = 0,ub = 300000.0;
		rep(w,100){
			double mid = (lb+ub)/2;
			vector<pair<double,int> >event;
			rep(i,n){
				if(r[i]*2 < mid) continue;
				event.pb(mp(x[i]-sqrt(r[i]*r[i]-mid*mid/4.0),1));
				event.pb(mp(x[i]+sqrt(r[i]*r[i]-mid*mid/4.0),-1));
			}
			sort(event.begin(),event.end());
			double pre;
			int cur = 0;
			bool ok = 0;
			for(int i=0;i<event.size();i++){
				cur += event[i].sc;
				if(cur == 1 && event[i].sc == 1){
					pre = event[i].fi;
				}
				else if(cur == 0){
				    //cout << event[i].fi << " " << pre << endl;
					if(event[i].fi-pre >= mid){
						ok = 1;
					}
				}
			}
			if(ok) lb = mid;
			else ub = mid;
		}
		printf("%.12f\n",lb);
	}
}

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

int main()
{
	while(true){
	    int W, H;
	    int mod=100000;
	    cin >> W >> H;
	    if(W+H==0) break;
	    int dpu1[110][110], dpu2[110][110], dpr1[110][110], dpr2[110][110]; 
	    for(int h=0; h<H; h++){
	        for(int w=0; w<W; w++){
	            dpu1[w][h]=0;
	            dpu2[w][h]=0;
	            dpr1[w][h]=0;
	            dpr2[w][h]=0;
	        }
	    }
	    
	    for(int w=1; w<W; w++){
	        dpu1[w][0]=1;
	    }
	    for(int h=1; h<H; h++){
	        dpr1[0][h]=1;
	    }
	    
	    for(int h=1; h<H; h++){
	        for(int w=1; w<W; w++){
	            dpu1[w][h]=(dpr2[w-1][h]+dpu1[w-1][h])%mod;
	            dpu2[w][h]=dpu1[w][h-1]%mod;
	            dpr1[w][h]=(dpu2[w][h-1]+dpr1[w][h-1])%mod;
	            dpr2[w][h]=dpr1[w-1][h]%mod;
	        }
	    }
	    cout << (dpu1[W-1][H-1]+dpu2[W-1][H-1]+dpr1[W-1][H-1]+dpr2[W-1][H-1])%mod << "\n";
	    
	}
		
	return 0;
}


Measured memory_bytes: 3276
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

//　呼び出し
func main() {
	// 共通
	sc := NewScanner()

	// *** NextInt
	a := sc.NextInt()
	sc.NextInt()
	sc.NextInt()
	sc.NextInt()
	e := sc.NextInt()
	k := sc.NextInt()

	if abs(a-e) > k {
		fmt.Println(":(")
	} else {
		fmt.Println("Yay!")
	}
}

// ======================= 以下ライブラリ ========================

func abs(i int) int {
	if i < 0 {
		return -i
	}
	return i
}

// *** int
func (s *Scanner) NextInt() int {
	v, _ := strconv.Atoi(s.Next())
	return v
}

// *** int64
func (s *Scanner) NextInt64() int64 {
	v, _ := strconv.ParseInt(s.Next(), 10, 64)
	return v
}

// **** float
func (s *Scanner) NextFloat() float64 {
	v, _ := strconv.ParseFloat(s.Next(), 64)
	return v
}

// *** []int 一行読み取って
func (s *Scanner) NextIntArray() []int {
	s.pre()
	start := s.p
	result := []int{}
	for ; s.p < len(s.buf)+1; s.p++ {
		if s.p == len(s.buf) || s.buf[s.p] == ' ' {
			v, _ := strconv.ParseInt(string(s.buf[start:s.p]), 10, 0)
			result = append(result, int(v))
			start = s.p + 1
		}
	}

	return result
}

// *** string 一行読み読み取って
func (s *Scanner) NextLine() string {
	s.pre()
	start := s.p
	s.p = len(s.buf)
	return string(s.buf[start:])
}


// ====================以下共通部分==================================
type Scanner struct {
	r   *bufio.Reader
	buf []byte
	p   int
}

func NewScanner() *Scanner {
	rdr := bufio.NewReaderSize(os.Stdin, 1000)
	return &Scanner{r: rdr}
}

func (s *Scanner) Next() string {
	s.pre()
	start := s.p
	for ; s.p < len(s.buf); s.p++ {
		if s.buf[s.p] == ' ' {
			break
		}
	}
	result := string(s.buf[start:s.p])
	s.p++
	return result
}

func (s *Scanner) pre() {
	if s.p >= len(s.buf) {
		s.readLine()
		s.p = 0
	}
}

func (s *Scanner) readLine() {
	s.buf = make([]byte, 0)
	for {
		l, p, e := s.r.ReadLine()
		if e != nil {
			panic(e)
		}
		s.buf = append(s.buf, l...)
		if !p {
			break
		}
	}
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < int(n); i++)
#define rep1(i,n) for (int i = 1; i <= int(n); i++)
#define repR(i,n) for (int i = int(n)-1; i >= 0; i--)
#define rep1R(i,n) for (int i = int(n); i >= 1; i--)
#define all(x) (x).begin(), (x).end()
#define show(x) #x " = " << x
using ll = long long;

int main() {
    ll N; cin >> N;
    cout << N*(N-1)/2 << endl;
}


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

vector<int> a;

bool rec(int i, int s){
    if(i==0){
        if(s==0) return true;
        else return false;
    }
    return rec(i-1,s) || rec(i-1,s-a[i-1]);
}

int main() {
    int n, q;
    cin >> n;
    a.resize(n);
    for(int i=0;i<n;i++){
        cin >> a[i];
    }
    cin >> q;
    for(; q>0; q--){
        int m;
        cin >> m;
        cout << (rec(n,m) ? "yes" : "no") << endl;
    }
    return 0;
}


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

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

    vector<string> s;
    for(int i = 0; i < h; i++){
        string ts;
        cin >> ts;

        bool flg = true;
        for(int j = 0; j < w; j++){
            if(ts[j]=='#'){flg = false;}
        }
        if(!flg){s.push_back(ts);}
    }

    for(int i = 0; i < w; i++){
        bool flg = true;
        for(int j = 0; j < s.size(); j++){
            if(s[j][i]=='#'){
                flg = false;
            }
        }
        if(flg){
            for(int j = 0; j < s.size(); j++){
                s[j][i] = 'a';
            }
        }

    }
    for(int i = 0; i < s.size(); i++){
        for(int j = 0; j < w; j++){
            if(s[i][j] == 'a'){;}
            else{cout << s[i][j];}
        }
        cout << endl;
    }

    return 0;
}


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

int main(){
    int n,x,i=3;
    cin >> n;
    while(n>=i){
        x=i;
        if(i%3==0){
            cout << ' ' << i;
        } else if(i%10==3){
            cout << ' ' << i;
        } else {
            while(x!=0){
                x/=10;
                if(x%10==3){
                cout << ' ' << i;
                break;
                }
            }            
        }
        i++;
    }
    cout << endl;
}


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

int main() {
  std::string s;
  cin >> s;
  for(int i = 0; i <= s.size(); i++){
    if(i == s.size()){
      cout << endl;
    }
    else if((i + 1) % 2 != 0){
      cout << s.at(i);
    }
  }
}


Measured memory_bytes: 512
import java.util.Scanner;

public class Main {
    public void main(Scanner sc) {
        int n = sc.nextInt();
        int c[] = new int[n - 1];
        int s[] = new int[n - 1];
        int f[] = new int[n - 1];

        for (int i = 0; i < n - 1; i++) {
            c[i] = sc.nextInt();
            s[i] = sc.nextInt();
            f[i] = sc.nextInt();
        }

        for (int i = 0; i < n; i++) {
            int time = 0;
            for (int j = i; j < n - 1; j++) {
                if (time < s[j]) {
                    time = s[j];
                } else if (time % f[j] != 0) {
                    time += f[j] - (time % f[j]);
                }
                time += c[j];
            }
            System.out.println(time);
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        new Main().main(sc);
        sc.close();
    }
}


Measured memory_bytes: 25836
n = int(input())
l = list(map(int, input().split()))
l.sort()
cnt = 0
for i in range(n-2):
    for j in range(i, n-1):
        for k in range(j, n):
            if l[i] != l[j] and l[i] != l[k] and l[j] != l[k]:
                if l[i] + l[j] > l[k]:
                    cnt += 1
print(cnt)

Measured memory_bytes: 9120
#include<iostream>
using namespace std;
int n,x,ans=0;
int main() {
	while (cin>>n>>x)
	{
		if (n == 0) { break; }
		for (int i = 1; i < n+1; i++)	{
			for (int j = 1; j < n+1; j++) {
				for (int k = 1; k < n+1; k++)	{
					if (i+j+k==x&&i<j&&j<k)
					{
						ans++;

					}
				}
			}

		}
		cout << ans << endl;
		ans = 0;
	}

	return 0;
}


Measured memory_bytes: 1160
#include <bits/stdc++.h>
#define N 105
using namespace std;
int n,x,ans,a[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>x;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++){
        if(x>=a[i]){
            x-=a[i];
            ans++;
        }
    }
    if(x&&n==ans) ans--;
    cout<<ans;
    return 0;
}


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

int main(){
  int n;
  while(cin >> n, n){
    vector< vector<int> > V(31);
    int f, d;
    for(int i = 0; i < n; ++i){
      cin >> f;
      for(int j = 0; j < f; ++j){
	cin >> d;
	V[d].push_back(i);
      }
    }
    bool M[n][n];
    for(int i = 0; i < n; ++i){
      fill(M[i],M[i]+n,false);
      M[i][i] = true;
    }
    bool g = false;
    for(int i = 0; i < 31; ++i){
      bool t[n];
      fill(t,t+n,false);
      for(int j = 0; j < (int)V[i].size(); ++j){
	for(int k = 0; k < n; ++k){
	  t[k] |= M[V[i][j]][k];
	}
      }
      g = true;
      for(int j = 0; j < n; ++j)
	g &= t[j];
      if(g){
	cout << i << endl;
	break;
      }else{
	for(int j = 0; j < (int)V[i].size(); ++j){
	  for(int k = 0; k < n; ++k){
	    M[V[i][j]][k] = t[k];
	  }
	}
      }
    }
    if(!g) cout << -1 << endl;
  }
  return 0;
}

Measured memory_bytes: 3076
n,m=map(int, raw_input().split())
x=map(int, raw_input().split())
y=map(int, raw_input().split())

x1=[]
x_sum=0
for i in range(n):
	x_sum+=( (n-i-1)-i )*x[i]

y_sum=0
for i in range(m):
	y_sum+=( (m-i-1)-i )*y[i]


print x_sum*y_sum%(10**9+7)

Measured memory_bytes: 15780
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<string>
#include<unordered_map>
#include<string.h>
#include<math.h>
using namespace std;
using ll = long long;
int main(){
    int N;
    int x[10], y[10];
    cin >> N;
    for(int i = 0;i <N;i++){
        cin >> x[i] >> y[i];
    }
    double sum = 0;
    for(int i = 0;i < N;i++){
        for(int j = 0;j < N;j++){
            sum += sqrt((x[i] - x[j])*(x[i] - x[j])+(y[i] - y[j])*(y[i] - y[j]));
        }
    }
    
    printf("%.16f", sum / N);
}


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

typedef long long ll;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second

typedef pair<int,int> pi;

int main()
{
    int n,l;
    while(cin >>n >>l,n)
    {
        vector<pi> ant(n);
        rep(i,n)
        {
            char c;
            int p;
            scanf(" %c %d", &c, &p);

            if(c=='L') ant[i]=pi(-1,p);
            else ant[i]=pi(1,p);
        }

        int t=0;
        int last=-1;

        while(1)
        {
            int alive=n;
            rep(i,n) if(ant[i].se==0 || ant[i].se==l) --alive;

            if(alive==0) break;
            else if(alive==1)
            {
                rep(i,n) if(0<ant[i].se && ant[i].se<l) last=i+1;
            }
            else if(alive==2)
            {
                rep(i,n) if(ant[i].se==1) last=i+1;
            }

            // printf(" t= %d, last= %d\n", t,last);
            // rep(i,n) printf("  %d : pos %d, %c\n", i,ant[i].se,(ant[i].fi==-1)?'L':'R');

            int nf[100];
            fill(nf,nf+100,-1);
            rep(i,n)
            {
                int nx=ant[i].se+ant[i].fi;

                if(nx==0 || nx==l) ant[i]=pi(0,nx);
                else
                {
                    ant[i].se+=ant[i].fi;
                    if(nf[ant[i].se]==-1) nf[ant[i].se]=i;
                    else
                    {
                        int idx=nf[ant[i].se];
                        ant[i].fi = -ant[i].fi;
                        ant[idx].fi = -ant[idx].fi;
                        // printf(" swap %d, %d\n", idx,i);

                    }
                }
            }

            ++t;
        }

        printf("%d %d\n", t, last);
    }
    return 0;
}

Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> lpair;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;
#define rep(i,m,n) for(ll i = (m); i < (n); i++)
#define rrep(i,m,n) for(ll i = (m); i >= (n); i--)
#define print(x) cout << (x) << endl;
#define print2(x,y) cout << (x) << " " << (y) << endl;
#define printa(x,n) for(ll i = 0; i < n; i++){ cout << (x[i]) << " ";} cout<<endl;
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N,M;
    cin >> N >> M;
    ll L[100010], R[100010];
    rep(i,0,M){
        cin >> L[i] >> R[i];
    }
    ll sum[100010] = {};
    rep(i,0,M){
        sum[L[i]]++;
        sum[R[i]+1]--;
    }
    rep(i,0,N+1) sum[i+1] += sum[i];
    ll ans = 0;
    rep(i,0,N+1){
        if(sum[i] == M) ans++;
    }
    print(ans);
    
}

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

using namespace std;

int H, W, A, B;
map<int, int> startColumn;
multiset<int> horizontalDistanceSet;

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

  cin >> H >> W;
  for(int i = 0; i < W; ++i) {
    startColumn[i] = i;
    horizontalDistanceSet.insert(0);
  }
  
  for(int i = 0; i < H; ++i) {
    cin >> A >> B;
    int leftWall = A - 1;
    int rightWall = B;

    int rightmostStartColumn = -1;
    auto it = startColumn.lower_bound(leftWall);
    while(it != startColumn.end() && it->first <= rightWall) {
      int currentSquare = it->first;
      int startColumnToReachCurrentSquare = it->second;

      rightmostStartColumn = max(rightmostStartColumn, startColumnToReachCurrentSquare);

      int horizontalDistance = currentSquare - startColumnToReachCurrentSquare;
      horizontalDistanceSet.erase(horizontalDistanceSet.find(horizontalDistance));
      startColumn.erase(it++); // don't really get this...
    }

    if(rightmostStartColumn > -1 && rightWall < W) {
      int horizontalDistance = rightWall - rightmostStartColumn;
      horizontalDistanceSet.insert(horizontalDistance);
      startColumn[rightWall] = rightmostStartColumn;
    }

    int ans = -1;
    int verticalDistance = i + 1;
    if(horizontalDistanceSet.size()) {
      int horizontalDistance = *(horizontalDistanceSet.begin());
      ans = horizontalDistance + verticalDistance;
    }
    cout << ans << "\n";
  }
  return 0;
}

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
#define REP(i, n) for(int i=0; i<n; i++)
#define REPi(i, a, b) for(int i=int(a); i<int(b); i++)
#define MEMS(a,b) memset(a,b,sizeof(a))
#define mp make_pair
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; }
const ll MOD = 1e9+7;

int main(){
    ll N;
    cin >> N;
    vector<ll> A(N);
    REP(i,N){
        cin >> A[i];
    }

    vector<ll> ans(N, 0);

    for(int b = 0; b < 62; b++){
        int nbit = 0;
        REP(i,N){
            int bit = (A[i] >> b) & 1;
            if(bit) nbit++;
        }

        REP(i,N){
            int bit = (A[i] >> b) & 1;
            if((nbit % 2 == 0 && bit) || (nbit % 2 == 1 && !bit)){
                ans[i] += (1LL << b);
            }
        }

    }

    REP(i,N){
        printf("%lld ", ans[i]);
    }
    cout << endl;
    return 0;
}


Measured memory_bytes: 6300
N = int(input())
A = [int(_) for _ in input().split()] 

X = []
x0 = sum(A) - sum(A[1::2]) * 2
X.append(x0)

for aa in A:
    x0 = (aa - x0 // 2 ) * 2
    X.append(x0)
X.pop()

for xx in X:
    print(xx,  end=" ")


Measured memory_bytes: 65508
import sys
n=int(input())
a=list(map(int,input().split()))
if n==1:
    print(1)
    sys.exit()
k=1
s=a[0]
lst=[0]*n
for i in range(n):
    while s^a[k]==s+a[k]:
        s+=a[k]
        k+=1
        if k==n:
            for j in range(i,n):
                lst[j]=n-j
            break
    else:
        lst[i]=k-i
        s=s^a[i]
        continue
    break
print(sum(lst))

Measured memory_bytes: 77900
#include <stdio.h>
#include <iostream>
#include <string>
#include <vector> 
#include <algorithm>
#include <typeinfo>
#include <cmath>
#include <numeric>
using namespace std;

int getGCD(int a, int b){
    if(b == 0) return a;
    return getGCD(b, a%b);
}
int main()
{
    int N;
    long long max_sum;
    std::cin >> N;
    std::vector<long long> A(N);
    for (int i = 0; i < N; ++i) std::cin >> A[i];
    
    int minus_cnt = 0;
    for (int i = 0; i < N; ++i)
    {
        if(A[i] < 0){
            A[i] = -A[i];
            // std::cout << A[i] << "\n";
            minus_cnt = minus_cnt + 1;
            }
    }
    
    if(minus_cnt%2 == 0){
        max_sum = accumulate(A.begin(), A.end(), 0LL);
    }else{
        std::vector<long long>::iterator iter = std::min_element(A.begin(), A.end());
        int index = std::distance(A.begin(), iter);
        A[index] = -A[index];
        max_sum = accumulate(A.begin(), A.end(), 0LL);
    }
    std::cout << max_sum << "\n";
}

Measured memory_bytes: 1024
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#define LL long long
using namespace std;
const LL mod=1e9+7;
LL n,r=2,t1=10,num1=1,pre[15],ans=0;
LL t2=10,num2=1,cnt=1;
LL pow(LL a,LL b)
{
	LL ans=1;
	while(b)
	{
		if(b&1) ans=ans*a%mod;
		a=a*a%mod;b>>=1;
	}
	return ans;
}
void check(LL len)
{
	if(len<num1) return;
	LL num=n/len,tot=9*pow(10,len-1)%mod;
	(ans+=(tot-num+1)%mod)%=mod;
	//printf("%lld %lld %lld\n",len,tot,num);
}
LL down(LL a,LL b) {return a%b==0?a/b-1:a/b;}
LL up(LL a,LL b) {return a/b+1;}
int main()
{
	scanf("%lld",&n);
	pre[0]=1;for(LL i=1;i<=8;i++) pre[i]=pre[i-1]*10;
	if(n>9)
	{
		for(LL i=1;;i++)
		{
			if(i==t1)
			{
				t1*=10,num1++;
				if(num1*pre[num1-1]*9>=n) break;
			}
			while(cnt<n)
			{
				if(cnt+num2>n) break;
				cnt+=num2;
				r++;if(r==t2) t2*=10,num2++;
			}
			if(cnt==n) (ans+=1)%=mod;
			cnt-=num1;
			//printf("%lld %lld %lld %lld\n",i,r,cnt,ans);
		}
	}
	//printf("1:%lld %lld %lld\n",t1,num1,ans);
	for(LL i=1;i*i<=n;i++)
	{
		if(n%i==0)
		{
			check(i);
			if(i*i!=n) check(n/i);
		}
	}
	//printf("2:%lld\n",ans);
	for(LL i=num1;i<=n/2;i++)
	{
		LL R=down(n,i),L=up(n,i+1);
		if(L<=R) (ans+=(R-L+1))%=mod;
		//printf("%lld %lld\n",i,ans);
	}
	printf("%lld",(ans+mod)%mod);
}

Measured memory_bytes: 256