akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int MN = 1e5 + 5, LN = 17, MOD = 1e9 + 7, INF = 0x3f3f3f3f, BSZ = 320;
string s;
int N, ret[MN];

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    cin >> s;
    N = s.length();
    for (int i = 0; i < N; ) {
        int cur = i;
        int l = 0, r = 0;
        int left = 0, right = 0;
        while (s[cur] == 'R') {
            cur++;
            left++;
        }
        l = cur - 1;
        r = cur;
        while (s[cur] == 'L') {
            cur++;
            right++;
        }
        ret[l] = (left + 1) / 2 + right / 2;
        ret[r] = (left) / 2 + (right + 1) / 2;
        i = cur;
    }
    for (int i = 0; i < N; i++) cout << ret[i] << " ";
    return 0;
}


Measured memory_bytes: 1104
def LIS(L):
    from bisect import bisect
    seq=[L[0]]
    for i in L:
        pos=bisect(seq,i)
        if (seq[-1] < i):
            seq.append(i)
        elif(i not in seq):
            seq[pos]=i
    return len(seq)
n = int(input())
L = []
for i in range(n):
    L.append(int(input()))
print(LIS(L))


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

int main(){
	string s; cin >> s;
	rep(i,s.size()){
		cout << 'x' ;
	}
	cout << endl;
}

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

int main() {
	int n;
	cin >> n;
	vector<long> a(n);
	for (long& i : a) cin >> i;
	vector<long> b = a;
	long ans1 = 0;
	if (b.front() <= 0) {
		ans1 += 1 - b.front();
		b.front() = 1;
	}
	for (int i = 1; i < n; ++i) {
		b[i] += b[i - 1];
		if (i % 2) {
			if (b[i] >= 0) {
				ans1 += b[i] + 1;
				b[i] = -1;
			}
		}
		else {
			if (b[i] <= 0) {
				ans1 += 1 - b[i];
				b[i] = 1;
			}
		}
	}
	b = a;
	long ans2 = 0;
	if (b.front() >= 0) {
		ans2 += b.front() + 1;
		b.front() = -1;
	}
	for (int i = 1; i < n; ++i) {
		b[i] += b[i - 1];
		if (i % 2) {
			if (b[i] <= 0) {
				ans2 += 1 - b[i];
				b[i] = 1;
			}
		}
		else {
			if (b[i] >= 0) {
				ans2 += b[i] + 1;
				b[i] = -1;
			}
		}
	}
	cout << min(ans1, ans2);
}

Measured memory_bytes: 1792
#include <cstdio>
#include <algorithm>
#include <functional>
using namespace std;

const int MAXN = 100005;

int N;
int a[MAXN];

int main() {
	scanf("%d", &N);
	for (int i = 1; i <= N; i++)
		scanf("%d", a + i);

	sort(a + 1, a + N + 1, greater <int> ());	
	
	int k = 1;
	for (int i = 1; i <= N; i++) 
		if (a[i + 1] < i + 1) { 
			k = i;
			break;
		}
	
	int cnt = 0;
	for (int i = 1; i <= N; i++)
		cnt += a[i] >= k;	
		
	puts((a[k] - k) % 2 || (cnt - k) % 2 ? "First" : "Second");

	return 0;
}

Measured memory_bytes: 512
# -*- coding: <encoding name> -*-
import sys

#def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def LI(): return list(map(int,input().split()))
def TI(): return tuple(map(int,input().split()))
def RN(N): return [input().strip() for i in range(N)]


def main():
    S = input()
    T = input()
    Tl = T[:-1]

    if Tl == S:
        print("Yes")
    else:
        print("No")


if __name__ == "__main__":
	main()

Measured memory_bytes: 9136
#include <iostream>
#include <cstring>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <math.h>
#include <string>
#include <map>
#include <cstdlib>
#include <stdio.h>
using namespace std;

typedef long long ll;
ll mod=1000000007;

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

    int table[2*N+1][2*N+1];
    for(int i=0; i<2*N+1; i++){
        for(int j=0; j<2*N+1; j++){
            table[i][j]=1;
        }
    }

    for(ll i=2; i<=2*N; i++){
        for(ll j=1; j<min(i, 2*N+1); j++){
            table[i][j]=table[i-1][j-1]+table[i-1][j];
            table[i][j]%=mod;
        }
    }

    for(ll i=1; i<=K; i++){//K
        ll tmp=i;
        ll tmp2=i-1;
        if(N-K+1<i){
            cout << 0 << endl;
            continue;
        }
        if(N-K+1/2<tmp) tmp=N-K+1-i;
        if(K-i<0){
            cout << 0 << endl;
            continue;
        }else{
            if((K-1)/2<i-1) tmp2=K-1-i+1;
        }
        ll ans=table[N-K+1][tmp]%mod*table[K-1][tmp2];
        cout << ans%mod << endl;
    }
    
    return 0;
}

Measured memory_bytes: 62720
//# pragma GCC optimize ("O2")
#include<iostream>
#include<algorithm>
#include<bitset>
#include<climits>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<deque>
#include<climits>
#include<list>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<vector>
#include<iomanip>
#include<sstream>
#define out(i,a,now) for(int i=a.be[now],to=a.v[i];i;i=a.ne[i],to=a.v[i])
#define fo(i,a,b) for(i=a;i<=b;i++)
#define max(a,b) (a>b?a:b)
#define min(a,b) (a>b?b:a)
#define mp(a,b) make_pair(a,b)
#define qk(x) memset(x,0,sizeof(x))
#define RG register
#define gs(x) (tr[tr[x].f].son[1]==x)
#define lb(x) (x&(-x))
#define mid ((l+r)>>1)
#ifdef Mogician
#endif
using namespace std;
typedef long long LL;
typedef double DB;
template <class T> void cmax(T &a,T b)
{
    a=max(a,b);
}
template <class T> void cmin(T &a,T b)
{
    a=min(a,b);
}
template <class T> void swp(T &a,T &b)
{
	T temp=a; a=b; b=temp;
}
const LL maxn=110000;
LL a[maxn],n,ans,res;
int main()
{
	scanf("%lld",&n);
	LL i;
	fo(i,1,n)
	{
		scanf("%lld",&a[i]);
		ans+=(LL)abs(a[i]-a[i-1]);
	}
	ans+=(LL)abs(a[n]);
//	ans++;
	fo(i,1,n)
	{
		LL x=min(a[i-1],a[i+1]),y=max(a[i-1],a[i+1]);
		res=ans;
		if (a[i]>=x && a[i]<=y) printf("%lld\n",res);
		else if (a[i]>=y) printf("%lld\n",res-2*(a[i]-y));
		else printf("%lld\n",res-2*(x-a[i]));
	}
	return 0;
}

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

int main() {
  int n;
  cin >> n;
  for(int i = 1;i <= n;i++){
    if(i%3 == 0){
      cout << " " << i;
    }
    else{
      string s = to_string(i);
      for(int j = 0;j < s.size();j++){
        if(s[j] == '3'){
          cout << " " << i;
          break;
        }
      }
    }
  }
  cout << "" << endl;
}



Measured memory_bytes: 3288
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
#define pb push_back
#define mp make_pair
#define eps 1e-9
#define INF 2000000000
#define LLINF 100000000000000000ll
#define sz(x) ((int)(x).size())
#define fi first
#define sec second
#define all(x) (x).begin(),(x).end()
#define sq(x) ((x)*(x))
#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define repn(i,a,n) for(int (i)=(a);(i)<(int)(n);(i)++)
#define EQ(a,b) (abs((a)-(b))<eps)
template<class T> void chmin(T& a,const T& b){if(a>b)a=b;}
template<class T> void chmax(T& a,const T& b){if(a<b)a=b;}
int H,W;
string s[305];
int A[605][305][305];
int B[605][305][305];
const int g = 300;
const int MAX = g*2;
int getA(int k,int a,int b,int c){ // [a,b]
	if(a>b)return 0;
	if(b<0)return 0;
	a = max(a,0);
	b = min(b,W-1);
	if(a==0)return A[k][b][c];
	return A[k][b][c]-A[k][a-1][c];
}
int getB(int k,int a,int b,int c){ // [a,b]
	if(a>b)return 0;
	if(b<0)return 0;
	a = max(a,0);
	b = min(b,W-1);
	if(a==0)return B[k][b][c];
	return B[k][b][c]-B[k][a-1][c];
}
int main(){
	cin >> H >> W;
	for(int i=0;i<H;i++)cin >> s[i];
	for(int i=0;i<H;i++){
		for(int j=0;j<W;j++){
			if(s[i][j]=='#'){
				for(int k=1;k<W;k++){
					if(i-k>=0&&j+k<W&&s[i-k][j+k]=='#')A[i+j][j][k]=1;
					if(i+k<H&&j+k<W&&s[i+k][j+k]=='#')B[i-j+g][j][k]=1;
				}
			}
		}
	}
	for(int i=0;i<=MAX;i++){
		for(int j=0;j<W;j++){
			for(int k=1;k<W;k++){
				A[i][j+1][k]+=A[i][j][k];
				B[i][j+1][k]+=B[i][j][k];
			}
		}
	}
	ll ans = 0ll;
	for(int i=0;i<H;i++){
		for(int j=0;j<W;j++){
			if(s[i][j]=='#'){
				for(int k=0;k<=MAX;k++){
					int p = abs(i+j-k);
					int l,r;
					if( p>0 && ((p&1)==0) ){
						int hp = (p>>1);
						if(k<i+j){
							l = j-p;
							r = j-hp-1;
							ans += getA(k,l,r,hp);
							/*if(getA(k,l,r,hp)){
								printf("A1: %d %d %d %d %d %d %d\n",i,j,k,l,r,p,getA(k,l,r,hp));
							}*/
						}else{
							l = j+1;
							r = j+hp;
							ans += getA(k,l,r,hp);
							/*if(getA(k,l,r,hp)){
								printf("A2: %d %d %d %d %d %d %d\n",i,j,k,l,r,p,getA(k,l,r,hp));
							}*/
						}
					}
					p = abs(i-j+g-k);
					if( p>0 && ((p&1)==0) ){
						int hp = (p>>1);
						if(k>i-j+g){
							l = j-p+1;
							r = j-hp;
							ans += getB(k,l,r,hp);
							/*if(getB(k,l,r,hp)){
								printf("B1: %d %d %d %d %d %d %d\n",i,j,k,l,r,p,getB(k,l,r,hp));
							}*/
						}else{
							l = j;
							r = j+hp-1;
							ans += getB(k,l,r,hp);
							/*if(getB(k,l,r,hp)){
								printf("B2: %d %d %d %d %d %d %d\n",i,j,k,l,r,p,getB(k,l,r,hp));
							}*/
						}
					}
				}
			}
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 438784
#include <bits/stdc++.h>
using namespace std;
int main() { 
    long a,b;

    cin >> a >> b;

    if(a >b ){
    	cout << "a > b" << endl;
    }else if(b > a){
    	cout << "a < b" << endl;
    }
    else{
    	cout << "a == b" << endl;
    }
    
    
    return 0;
}




Measured memory_bytes: 3084
#include<stdio.h>

int main(void){
  int h,w;
  int i,j;
  
  while(1){
    scanf("%d",&h);
    scanf("%d",&w);

    if(h==0 && w==0){
      break;
    }

    for(i=0;i<h;i++){
      for(j=0;j<w;j++){
        printf("#");
      }
      putchar('\n');
    }
    putchar('\n');
  }

  return 0;
}

Measured memory_bytes: 576
import itertools
n,m = map(int,input().split())
ab = []
count = 0
for i in range(m):
  ab.append(set(map(int,input().split())))
ns = [i for i in range(1,n+1)]
ptn = [i for i in list(itertools.permutations(ns)) if i[0]==1]
for i in ptn:
  first = i[0]
  for s in range(1,n):
    if {first,i[s]} not in ab:
      break
    first=i[s]
  else:
    count +=1
print(count)

Measured memory_bytes: 8052
#include <bits/stdc++.h>
#define ll long long
#define vi vector<int>
#define e "\n"
#define MaRiaMa { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); }
#define fix(n) cout << fixed << setprecision(n);
using namespace std;
int main()
{
	MaRiaMa;
	set<int> p;
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int x;
		cin >> x;
		p.emplace(x);
	}
	cout << p.size();
}

Measured memory_bytes: 3644
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4.2")
#pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define PB push_back
#define all(x) x.begin(),x.end()
#define vi vector<ll>
#define ii pair<ll,ll>
#define vii vector<ii>
#define vb vector<bool>
#define vvi vector<vector<ll> >
#define vvii vector<vii>
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define read(x) long long x;cin>>x;
#define FOR(a,b,c,d) for(int a=b;a<=c;a+=d)
#define MP make_pair
#define F first
#define AS assign
#define S second
#define debug(x) cout<<(#x)<<": "<<(x)<<"\n"
#define SZ(x) x.size()
#define mod 1000000007
#define lg2(x) 63-(__builtin_ctzll(x))
#define RZ resize
#define IN insert
#define X real()
#define Y imag()
#define FBO find_by_order
#define OFK order_of_key
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>indexed_set;
typedef unsigned long long ull;
typedef long double d64;
typedef complex<d64>P;
ll modpow(int a,int b,int m){
    if(!b)return 1%m;
    ll u=modpow(a,b/2,m);
    u=(u*u)%m;
    if(b&1)u=(u*a)%m;
    return u;
}

int main(){
fast
read(a);read(b);read(c);
cout<<c<<" "<<a<<" "<<b;
return 0;
}




Measured memory_bytes: 3552
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>

using namespace std;
typedef long long ll;
typedef pair<int,int> Pi;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define sz(x) (int)x.size()
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) x.begin(), x.end()

int n, m, A[100010];

void solve(){
	scanf("%d%d",&n, &m);
	for(int i=1;i<=n;i++)scanf("%d", A+i);
	ll ans = 0;
	ans += max(0, A[1] - m);
	A[1] -= ans;
	for(int i=2;i<=n;i++){
		int c = max(0, A[i] + A[i-1] - m);
		A[i] -= c;
		ans += c;
	}
	printf("%lld", ans);
}

int main(){
	int Tc = 1; //scanf("%d\n", &Tc);
	for(int tc=1;tc<=Tc;tc++){
		solve();
	}
	return 0;
}

Measured memory_bytes: 764
//AOJ0117

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define INF 1000000000
int n,m,r[21][21],cost[21][21];
int x1,x2,y1,y2;
int d[21];
int BF(int a,int b){
  for(int i=0;i<21;i++)d[i]=INF;
  d[a]=0;
  for(int i=0;i<n-1;i++){
    for(int j=1;j<=n;j++){
      for(int k=1;k<=n;k++){
        if(r[j][k])
          d[k]=min(d[k],d[j]+cost[j][k]);
      }
    }
  }
  return d[b];
}
int main(){
  cin>>n>>m;
  for(int i=0;i<m;i++){
    int a,b,c,d;
    scanf("%d,%d,%d,%d",&a,&b,&c,&d);
    r[a][b]=1;r[b][a]=1;
    cost[a][b]=c;cost[b][a]=d;
  }
  scanf("%d,%d,%d,%d",&x1,&x2,&y1,&y2);
  // cout<<BF(x1,x2)<<endl;
  //cout<<BF(x2,x1)<<endl;
  cout<<y1-y2-BF(x1,x2)-BF(x2,x1)<<endl;
}

Measured memory_bytes: 1244
#include<bits/stdc++.h>
namespace QiFeng233{
	const int maxk=1e5+10;
	int f[maxk],len,k;
	void dfs(int step){
		//可以直接+1的情况： 
		if(step!=len&&f[step]<9&&f[step+1]-f[step]>=0){
			f[step]+=1;
			return;
		}
		if(step==len&&f[step]<9){
			f[step]+=1;
			return;
		}
		//需要进位：
		if(f[step]==9){
			if(step==len){
				++len;
				f[len]=1;
				for(int i=1;i<len;++i)f[i]=0;
			}else{
				dfs(step+1);
				f[step]=f[step+1]==0?0:f[step+1]-1;
			}
			return;
		} 
		//纯粹的进个位
		dfs(step+1);
		f[step]=f[step+1]==0?0:f[step+1]-1;
	}
	void solve(){
		scanf("%d",&k);
		if(k<=10)printf("%d",k);
		else{
			k-=10;
			len=2;
			f[1]=0;
			f[2]=1;
			while(k--)dfs(1);
			for(int i=len;i;--i)printf("%d",f[i]);
		}
	}
}
signed main(){
	QiFeng233::solve();
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N,l,r,i,sum=0;
  cin >> N ;
 
  for (i=0;i<N;i++){
    cin >> l >> r;
    sum=sum+r-l+1;
  }
  
  cout << sum <<endl;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
long long n, ans, cnt, mi=1, a[1005], s[2], x[505], y[505], z;
int main() {
	int i, j;
	cin>>n;
	for(i=1; i<=n; i++) {
		cin>>a[i];
		s[i%2] += max(a[i], 0LL);
		if(a[i]>a[mi]) mi=i;
	}
	for(i=s[1]>s[0]; i<=n; i+=2) if(a[i]>0) {
		x[++z] = i;
		if(z>1) cnt += y[z-1] = (x[z] - x[z-1]) / 2;
	}
	if(z) {
		ans = max(s[0], s[1]);
		cnt += x[1]-1 + n-x[z];
	} else {
		ans = a[mi];
		cnt = n-1;
		x[++z] = mi;
	}
	cout<<ans<<endl<<cnt<<endl;
    //先去掉两端
	for(i=n; i>x[z]; i--) cout<<i<<endl;
	for(i=1; i<x[1]; i++) cout<<1<<endl;
	for(i=1; i<z; i++) for(j=y[i]; j>0; j--) cout<<j+1<<endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ms(x, n) memset(x,n,sizeof(x));
#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 pb push_back
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define LL_MAX 9223372036854775807
#define LL_MIN -9223372036854775808
typedef long long int ll;
typedef unsigned long long int ull;
using namespace std;



int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int n, a[30], b[30], c[30];
    cin >> n;
    rep1(i, n)
        cin >> a[i];
    rep1(i, n)
        cin >> b[i];
    rep1(i, n-1)
        cin >> c[i];
    int ans = 0;
    ans += b[a[1]];
    for (int i = 2; i <= n; ++i) {
        ans += b[a[i]];
//        cout << ans << endl;
        if (a[i] == a[i-1] + 1) {
            ans += c[a[i-1]];
        }
    }
    cout << ans << '\n';
    return 0;
}


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

using ll = long long;

const int mod = 1e9 + 7;

template<typename T>
ostream& operator <<(ostream &os, const pair<T, T> p) {
    os << "<" << p.first << ", " << p.second << ">";
    return os;
}

template<typename T>
T gcd(T a, T b) { 
    if (b == 0) 
        return a; 
    return gcd(b, a % b);  
      
}

ll modpow(ll n, int k) {
    ll r = 1;
    while (k > 0) {
        if (k & 1) (r *= n) %= mod;
        (n *= n) %= mod;
        k >>= 1;
    }
    return r;
}

template<typename T>
pair<T, T> flip(const pair<T, T> &p) {
    T a = p.first;
    T b = p.second;

    assert(b >= 0);

    if (a < 0) {
        return {b, -a};
    } else {
        return {-b, a};
    }
}

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

    map<pair<ll, ll>, ll> cnt;

    int n;
    cin >> n;

    ll res0 = 0;
    ll res = 1;

    for (int i = 0; i < n; ++i) {
        ll a, b;
        cin >> a >> b;

        if (a == 0 && b == 0) {
            ++res0;
            continue;
        }

        if (b < 0) {
            a = -a;
            b = -b;
        }

        ll g = gcd(a, b);
        a /= g;
        b /= g;

        if (b < 0) {
            a = -a;
            b = -b;
        }

        //cout << a << " " << b << "\n";

        ++cnt[{a, b}];
    }

    for (const auto &elem: cnt) {
        ll a = elem.first.first;
        ll b = elem.first.second;

        //cout << "pair: " << elem.first << "\n";
        auto fl = flip(elem.first);
        //cout << "flipped pair " << fl << "\n";

        map<pair<ll, ll>, ll>::iterator bad;
        if (a == 0 || b == 0) {
            bad = cnt.find({b, a});
        } else {
            bad = cnt.find(fl);
        }

        ll amt = modpow(2, elem.second);

        if (bad != cnt.end()) {
            //cout << "found it\n";
            amt = amt + (modpow(2, (*bad).second)) + mod - 1;
            cnt.erase(bad);
        } else {
            //cout << "didn't find it\n";
        }

        //cout << "amt: " << amt << "\n";
        res = (res * amt) % mod;
        //cout << string(100, '-') << "\n";
    }

    ll ans = (res + res0 + mod - 1) % mod;
    cout << ans << "\n";
    return 0;
}


Measured memory_bytes: 16100
in_str = input()
ok = 0
if in_str[0] == in_str[1]:
  if in_str[2] == in_str[3]:
    ok += 1
if in_str[0] == in_str[2]:
  if in_str[1] == in_str[3]:
    ok += 1
if in_str[0] == in_str[3]:
  if in_str[1] == in_str[2]:
    ok+= 1
if(ok == 1):
  print("Yes")
else :
  print("No")

Measured memory_bytes: 3060
# coding: utf-8
import time
import re
import math

def main():
    A,B=map(int,input().split())
    S=input()
    f=1
    if S.count("-")==1:
        if S.index("-")!=A:
            f=0
    else:
        f=0
    if(f==1):print("Yes")
    else:print("No")
main()

Measured memory_bytes: 3184
n, m, qqq = map(int, input().split())
DP = [[0 for _ in range(n)]for __ in range(n)]

for i in range(m):
    l, r = map(int, input().split())
    DP[l-1][r-1]+=1


#DP = [[0 for _ in range(n)]for __ in range(n)]
for i in range(n-1)[::-1]:
    for j in range(1,n):
        DP[i][j] += DP[i+1][j]+DP[i][j-1]-DP[i+1][j-1]

for i in range(qqq):
    p, q = map(int, input().split())
    print(DP[p-1][q-1])
# print(DP)


Measured memory_bytes: 9608
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
#define sz(x) int(x.size())
#define pb push_back
#define eb emplace_back
using ll=long long;
using P = pair<int,int>;
#define chmax(x,y) x = max(x,y)
#define chmin(x,y) x = min(x,y)
const ll MOD=1000000007;



int main() {
    int N;
    cin>>N;
    vector<ll> A(N);
    rep(i,N)cin>>A.at(i);
    ll sum=0;
    rep(i,N)sum+=A.at(i);
    sum/=2;
    for(int i=1;i*2<=N;i++){
        sum-=A.at(2*i-1);
    }
    ll ans=sum;
    rep(i,N){
        cout<<ans*2<<endl;
        ans=A.at(i)-ans;
    }
}

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

#define INF_LL (int64)1e18
#define INF (int32)1e9
#define REP(i, n) for(int64 i = 0;i < (n);i++)
#define FOR(i, a, b) for(int64 i = (a);i < (b);i++)
#define all(x) x.begin(),x.end()
#define fs first
#define sc second

using int32 = int_fast32_t;
using uint32 = uint_fast32_t;
using int64 = int_fast64_t;
using uint64 = uint_fast64_t;
using PII = pair<int32, int32>;
using PLL = pair<int64, int64>;

const double eps = 1e-10;

template<typename A, typename B>inline void chmin(A &a, B b){if(a > b) a = b;}
template<typename A, typename B>inline void chmax(A &a, B b){if(a < b) a = b;}

template<typename T>
vector<T> make_v(size_t a){return vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value!=0>::type
fill_v(U &u,const V... v){u=U(v...);}

template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value==0>::type
fill_v(U &u,const V... v){
  for(auto &e:u) fill_v<T>(e,v...);
}


class UnionFind{
private:
  ::std::vector<int_fast32_t> par;
  size_t n;

public:
  UnionFind(){}
  UnionFind(size_t n):n(n){
    par.resize(n, -1);
  }

  uint_fast32_t find(uint_fast32_t x){
    return par[x] < 0 ? x : par[x] = find(par[x]);
  }

  size_t size(uint_fast32_t x){
    return -par[find(x)];
  }

  bool unite(uint_fast32_t x, uint_fast32_t y){
    x = find(x);
    y = find(y);
    if(x == y) return false;
    if(size(x) < size(y)) std::swap(x, y);
    par[x] += par[y];
    par[y] = x;
    return true;
  }

  bool same(uint_fast32_t x, uint_fast32_t y){
    return find(x) == find(y);
  }
};

int main(void) {
  int64 n;
  while (cin >> n && n) {
    vector<vector<int>> v(30);
    REP(i, n) {
      int64 m;
      cin >> m;
      REP(j, m) {
        int64 d;
        cin >> d; d--;
        v[d].push_back(i);
      }
    }
    vector<set<int>> vst(n);
    REP(i, n) vst[i].insert(i);
    bool ok = 0;
    REP(i, 30) {
      set<int> st;
      REP(j, v[i].size()) {
        st.insert(vst[v[i][j]].begin(), vst[v[i][j]].end());
      }
      if (st.size() == n) {
        cout << i+1 << endl;
        ok = 1;
        break;
      }
      REP(j, v[i].size()) {
        vst[v[i][j]] = st;
      }
    }
    if (!ok) {
      cout << -1 << endl;
    }
  }
}



Measured memory_bytes: 3220
#include <stdio.h>
#include <string.h>

int main( int argc, char *argv[] )
{
	int n = 0;
	int l = 0;
	int i = 0;
	int j = 0;
	// 	char str[0][101] = {0};
	char str[101][101];
	char tmp[101];
	
	scanf("%d %d", &n, &l);

	for(i = 0; i < n; i++){
		scanf( "%s", str[i]);
	}

	for(i = 0; i < n; i++){
		for(j = 0; j < n; j++){
			if(strcmp(str[j], str[j+1]) >= 1){
				strcpy(tmp, str[j+1]);
				strcpy(str[j+1], str[j]);
				strcpy(str[j], tmp);
			}
		}		
	}

	for(i = 0; i <= n; i++){
		printf("%s", str[i]); 
	}

	printf("\n");


	return 0;
}


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

#define rep(i, k, n) for(int i = (k); i < (n); i++)
#define irep(i, k, n) for(int i = (k); i > (n); i--)
using namespace std;
using ll = long long;

int main(void){
  int n;
  string s;
  cin >> n >> s;

  int ans = 0;
  char c = ' ';
  rep(i, 0, n){
    if(c != s[i]){
      c = s[i];
      ans++;
    }
  }

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

Measured memory_bytes: 512
#include <stdio.h>

int main(){
  int n;
  long long int result=100000;
  int i;
  scanf("%d", &n);
  for(i = 0;i<n;i++){
    result *= 1.05;
    if(result%1000 != 0){
      result = result-(result%1000)+1000;
    }
  }
  printf("%lld\n", result);
  return 0;
}

Measured memory_bytes: 592
#include<algorithm>
#include<climits>
#include<cmath>
#include<cstring>
#include<deque>
#include<iomanip>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<unordered_map>
#include<unordered_set>
#include<utility>
#include<vector>

using namespace std;

using lint = long long;
using P = pair<int, int>;
using LLP = pair<long long, long long>;

#define REP(i, x, n) for(int i = (x), i##_len = int(n) ; i < i##_len ; ++i)
#define rep(i, n) for(int i = 0, i##_len = int(n) ; i < i##_len ; ++i)
#define reps(i, n) for(int i = 1, i##_len = int(n) ; i <= i##_len ; ++i)
#define rrep(i, n) for(int i = int(n) - 1 ; i >= 0 ; --i)
#define rreps(i, n) for(int i = int(n) ; i > 0 ; --i)
#define SORT(x) sort((x).begin(), (x).end())
#define SORT_INV(x) sort((x).rbegin(), (x).rend())
#define TWINS(x) cout << ((x) ? "Yay!" : ":(") << endl

const int IINF = (1 << 30) - 1;
const long long LLINF = 1LL << 61;
const int dx4[] = {1, 0, -1, 0}, dy4[] = {0, 1, 0, -1};
const int dx8[] = {1, 1, 0, -1, -1, -1, 0, 1}, dy8[] = {0, -1, -1, -1, 0, 1, 1, 1};
const double EPS = 1e-8;

template<typename T>
bool chmax(T &a, T b){
    if(a < b){
        a = b;
        return true;
    }
    return false;
}

template<typename T>
bool chmin(T &a, T b){
    if(b < a){
        a = b;
        return true;
    }
    return false;
}

stack< P > st1;
stack<char> st2;

P calc(void){
    P res;
    P p1 = st1.top();
    st1.pop();
    P p2 = st1.top();
    st1.pop();
    if(st2.top() == '&'){
        res.first = min(p2.second + p1.first, p2.first);
        res.second = p1.second + p2.second;
    }else if(st2.top() == '|'){
        res.first = p1.first + p2.first;
        res.second = min(p2.first + p1.second, p2.second);
    }
    return res;
}

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

    string s;
    cin >> s;

    int n = s.size();
    rep(i, n){
        if(s[i] == '?'){
            st1.push({1, 1});
        }else if(s[i] == '('){
            st2.push(s[i]);
        }else if(s[i] == ')'){
            while(!st2.empty() && st2.top() != '('){
                st1.push(calc());
                st2.pop();
            }
            st2.pop();
        }else if(s[i] == '&'){
            st2.push(s[i]);
        }else if(s[i] == '|'){
            while(!st2.empty() && st2.top() == '&'){
                st1.push(calc());
                st2.pop();
            }
            st2.push(s[i]);
        }
    }
    while(!st2.empty()){
        st1.push(calc());
        st2.pop();
    }

    cout << st1.top().first << " " << st1.top().second << endl;

    return 0;
}


Measured memory_bytes: 3484
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main(){
    string s; cin >> s;
    int N = s.length();

    int cnt[3] = {0,0,0};
    char abc[3] = {'a', 'b', 'c'};

    for(int i=0;i<N;i++){
        for(int k=0;k<3;k++){
            if(s[i] == abc[k]){
                cnt[k]++;
            }
        }
    }

    sort(cnt, cnt+3);
    if(cnt[2] - cnt[0] >= 2){
        cout << "NO" << endl;
    }else{
        cout << "YES" << endl;
    }

    return 0;

}

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

using namespace std;
typedef long long ll;
typedef long double ld;
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define REPR(i,n) for(int i=n; i>-1; --i)
#define ALL(a) (a).begin(),(a).end()
#define FILL(a,n,x); REP(i,(n)){ (a)[i]=(x); }
#define CINA(a,n); REP(i,(n)){ cin >> (a)[i]; }
#define FILL2(a,n,m,x); REP(i,(n)){ REP(j,(m)){(a)[i][j]=(x);} }
#define CINA2(a,n,m); REP(i,(n)){ REP(j,(m)){cin >> (a)[i][j];} }
#define Liny "Yes\n"
#define Linn "No\n"
#define LINY "YES\n"
#define LINN "NO\n"

#define umap unordered_map
//cout << setfill('0') << right << setw(4) << 12; // "0012"
int keta(ll x){ if(x<10){return 1;} else{return keta(x/10) + 1;}}
int keta_wa(ll x){ if(x<10){return x;} else{return keta_wa(x/10) + x%10;} }
int ctoi(char c){ return ( (c>='0' && c<='9')? c - '0': 0 );}
int __stoi(string s){ return atoi(s.c_str()); }
ll sum(ll a[],ll N){ return accumulate(a,a+N,0LL);}
ll gcd(ll a,ll b){if(a<b)swap(a,b); return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){if(a<b){swap(a,b);} return a/gcd(a,b)*b;}
template<class T> void chmax(T& a, T b){ if(a<b){a=b;} }
template<class T> void chmin(T& a, T b){ if(a>b){a=b;} }


int inf = 1000000;

int main(){
    int N; cin>>N;
    int a[N]; FILL(a,N,inf);
    REP(i,N){
        int x; cin>>x;
        *lower_bound(a,a+N,x) = x;
    }
    int num = 0;
    REP(i,N){
        if(a[i]!=i+1){break;}
        ++num;
    }
    if(num==0){ cout << "-1\n"; }
    else{ cout << N-num << "\n"; }
}

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

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

  vector<vector<long long int> > A(n, vector<long long int>(m));
  vector<vector<long long int> > B(m, vector<long long int>(l));
  vector<vector<long long int> > C(n, vector<long long int>(l));

  for(int i=0; i<n; i++)
    for(int j=0; j<m; j++)
      cin >> A[i][j];

  for(int i=0; i<m; i++)
    for(int j=0; j<l; j++)
      cin >> B[i][j];

  for(int i=0; i<n; i++)
    for(int j=0; j<l; j++){
      C[i][j] = 0;
      for(int k=0; k<m; k++)
	C[i][j]+=A[i][k]*B[k][j];
    }

  for(int i=0; i<n; i++){
    for(int j=0; j<l; j++){
      cout << C[i][j];
      if(j!=l-1)
	cout << " ";
    }
    cout << endl;
  }

  return 0;
}

Measured memory_bytes: 1424
#include<bits/stdc++.h>
const int INF = 1e9;
const int MOD = 1e9+7;
using LL = long long;
const LL LINF = 1e18;
using namespace std;
#define COUT(v) cout<<(v)<<endl
#define CIN(n)  long long int(n);cin >> (n)
#define YES(n) cout<<((n)? "YES" : "NO")<<endl
#define Yes(n) cout<<((n)? "Yes" : "No")<<endl
#define POSSIBLE(n) cout << ((n) ? "POSSIBLE" : "IMPOSSIBLE"  ) << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible"  ) <<endl

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<(n);++i)
#define REPR(i,n) for(int i=n;i>=0;i--)

#define FOREACH(x,a) for(auto& (x) : (a) )

#define ALL(obj) (obj).begin(),(obj).end()

#define P pair<int,int>
#define V vector<int>
#define S set<int>
#define pb(v) push_back(v)
string A,B,C;
int main(){
    string s,ans;cin >>s;
    FOREACH(a,s){
        if(a=='1'){
            ans.pb('1');
        }
        if(a=='0'){
            ans.pb('0');
        }
        if(a=='B'&&ans.size()!=0){
            ans.pop_back();
        }
    }
    COUT(ans);
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>

#define MAX 101
#define WHITE -1
#define GRAY 0
#define BLACK 1
#define INF 1000000000

int n,head,tail;
int color[MAX],d[MAX],f[MAX],Q[MAX],Adj[MAX][MAX];

enqueue(int x){
  Q[tail]=x;
  if(tail+1==MAX) tail=0;
  else tail++;
}

int dequeue(){
  int x;

  x=Q[head];
  if(head+1==MAX) head=0;
  else head++;

  return x;
}

bfs(int s){
  int i,j;

  for(i=0;i<n;i++){
    color[i]=WHITE;
    d[i]=INF;
  }

  color[s]=GRAY;
  d[s]=0;
  enqueue(s);

  while(head!=tail){
    i=dequeue();
    for(j=0;j<n;j++){
      if(Adj[i][j]==1 && color[j]==WHITE){
	color[j]=GRAY;
	d[j]=d[i]+1;
	enqueue(j);
      }
    }
    color[i]=BLACK;
  }
}

int main(){
  int i,u,k,j,v;

  for(i=0;i<MAX;i++){
    for(j=0;j<MAX;j++){ 
      Adj[i][j]=0;
    }
  }

  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d%d",&u,&k);
    for(j=0;j<k;j++){
      scanf("%d",&v);
      Adj[u-1][v-1]=1;
    }
  }

  bfs(0);

  for(i=0;i<n;i++){
    if(d[i]==INF) d[i]=-1;
  }

  for(i=0;i<n;i++){
    printf("%d %d\n",i+1,d[i]);
  }

  return 0;
}

Measured memory_bytes: 640
#include<stdio.h>
#include<math.h>
int Sosu(int N){
  int i=3;
if(N==2)return 1;
if(N<2 || N%2==0)return 0;
while(i<=sqrt(N)){
  if(N%i==0)return 0;
  i=i+2;
}
return 1;
}
int main(void){
int N;
int n,i;
int S=0,c=0;
while(1){
scanf("%d",&n);
if(n>=1 && n<=10000)break;
}
for(i=0 ; i<n ; i++){
  while(1){
  scanf("%d",&N);
  if(N>=2 && N<=100000000)break;
  }
  S+=Sosu(N);
}
printf("%d\n",S);
return 0;
}


Measured memory_bytes: 2124
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <string.h>
using namespace std;

#define REP(i,m,n) for(int i=m;i<n;i++)
#define rep(i,n) REP(i,0,n)
int g[10][10];
string s[10];
string dpv[10][1<<10];
bool dp[10][1<<10];
int n;
string mini(const string& a,const string& b)
{
  if(a.size()==b.size())return min(a,b);
  return a.size()<b.size()?a:b;
}
string solve(int v,int u)
{
  if(u==(1<<n)-1)return "";
  if(v>=0 && dp[v][u]){
    return dpv[v][u];
  }
  string ret;
  bool f=false;
  if(v>=0)dp[v][u]=true;
  rep(i,n){
    if(u>>i&1)continue;
    string ad;
    if(v<0){
      ad=s[i];
    } else {
      ad=s[i].substr(g[i][v]);
    }
    if(f)ret=mini(ret,ad+solve(i,u|1<<i));
    else{
      ret=ad+solve(i,u|1<<i);
      f=true;
    }
  }
  return v>=0?dpv[v][u]=ret:ret;
}
int main(void)
{
  for(;;){
    scanf("%d",&n); if(!n)break;
    rep(i,n)cin>>s[i];
    int u=0;
    rep(i,n)rep(j,n){
      if(u&1<<j || u&1<<i || i==j)continue;
      if(s[i].find(s[j])!=-1){
        u|=1<<j;
      }
    }
    rep(i,n)rep(j,n){
      if(i==j)continue;
      if(u&1<<i || u&1<<j)continue;
      int c=1,cc=-1;
      for(int ii=s[i].size()-1;ii>=0;ii--){
        if(s[j].size()<c)break;
        int jj;
        for(jj=0;jj<c;jj++){
          if(s[i][ii+jj]!=s[j][jj])break;
        }
        if(jj==c){
          cc=c;
        }
        c++;
      }
      g[j][i]=cc<0?0:cc;
    }
    memset(dp,0,sizeof(dp));
    puts(solve(-1,u).data());
  }
}

Measured memory_bytes: 1240
#include <bits/stdc++.h>
#include <string>
#include <vector>
#include <algorithm>
#define rep(i,w) for (int i = 0;i < (w); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;
int INF = 1e9;

int main(){
  int a,b;cin >> a >> b;
  char grid[100][100];
  rep(i,100)rep(j,100) {
    if(i < 50) grid[i][j] = '#';
    else grid[i][j] = '.';
  }
  --a;
  --b;
  int j = 0;
  int i = 0;
  while(a > 0){
    grid[i][j] = '.';
    j += 2;
    if(j >= 100){
      j %= 100;
      i += 2;
    }
    a--;
  }

  i = 99;
  j = 0;
  while(b > 0){
    --b;
    grid[i][j] = '#';
    j += 2;
    if(j >= 100){
      j %= 100;
      i -= 2;
    }
  }
  printf("%d %d\n",100,100);
  rep(i,100){
    rep(j,100) cout << grid[i][j];
    cout << endl;
  }
}

Measured memory_bytes: 3784
/*
Author: Deep Chaklasiya
 ***************************************   UNAUTHORISED COPYING OF CODE PROHIBITED   **********************************
*/

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

#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp>
#include <functional> // for less
using namespace __gnu_pbds;

typedef tree<int, null_type, less<int>, rb_tree_tag,
             tree_order_statistics_node_update> data_set;
#define fbo find_by_order
#define ook order_of_key




#define int         long long
#define double      long double
#define pb          push_back
#define pf          push_front
#define pii         pair<int,int>
#define vi          vector<int>
#define vii         vector<pii>
#define piiii       pair<pii,pii>
#define viiii       vector<pair<pii,pii>>
#define mi          map<int,int>
#define mii         map<pii,int>
#define piii           pair<int,pair<int,int> >
#define all(a)      (a).begin(),(a).end()
#define rall(a)     (a).rbegin(),(a).rend()
#define x           first
#define y           second
#define sz(x)       (int)x.size()
#define endl        '\n'
#define hell        998244353
#define PI          3.141592653589
#define bs(v,n)     binary_search(all((v)),(n))
#define lb(v,n)     lower_bound(all((v)),(n))
#define ub(v,n)     upper_bound(all((v)),(n))
#define fo(i,l,u)   for(i=l;i<u;i++)
#define rfo(i,l,u)  for(i=l;i>=u;i--)
#define allfo(s)    for(auto it=(s).begin();it!=(s).end();it++)
#define _init(b)     memset(b,-1,sizeof(b))
#define _init0(b)     memset(b,0,sizeof(b))
#define MOD         1000000007
#define ef else if





int gcd(int a, int b) {  if (a == 0)  return b; return gcd(b % a, a); }
bool mod(double a,double b) {return a/b - floor(a/b);}

int occurs(vi v,int n){
auto it=lb(v,n);auto it1=ub(v,n);int x=it1-it;return x;}

int logb(int base, int x) {
    return (log(x) / log(base));
}


template<class A,class B>ostream&operator<<(ostream&out,const pair<A,B>&a){return out<<"("<<a.first<<","<<a.second<<")";}
template<class A>ostream&operator<<(ostream&out,const vector<A>&a){for(const A &it:a)out<<it<<" ";return out;}
template<class A,class B>istream&operator>>(istream&in,pair<A,B>&a){return in>>a.first>>a.second;}
template<class A>istream&operator>>(istream&in,vector<A>&a){for(A &i:a)in>>i;return in;}

void set_min(int &m,int a){
    if(m==-1||m>a)m=a;
}


signed main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int i,j,x,n,m,k,t;
    cin>>n;
    vi v(n);
    int flag=0;
	for(auto &x:v) cin>>x;
    for(int i=0;i<n;i++)
    {
    	if(v[i]%2==0)
    	{
    		if(v[i]%3==0 or v[i]%5==0)
    		{
    			continue;
			}
			else 
			{
				flag=1;
				break;
			}
		}
	}
	if(flag) cout<<"DENIED";
	else cout<<"APPROVED";
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define zero_pad(num) setfill('0') << std::right << setw(num)
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<ll, ll>;

int main() {
    ll n;
    cin >> n;
    
    int ans = 11;
    for(ll i = 1; i * i <= n; i++){
        if(n % i == 0){
            int la = to_string(i).size();
            int lb = to_string(n / i).size();
            ans = min(ans, max(la, lb));
        }
    }
    cout << ans << endl;
}

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

int main() {
    int R, C, sx, sy, ex, ey; 
    cin >> R >> C >> sx >> sy >> ex >> ey;
    string s[R];
    for (int i = 0; i < R; i++) cin >> s[i];

    vector<vector<int>> dist(R, vector<int>(C, -1));
    deque<tuple<int, int, int>> dq;
    dq.emplace_back(sx - 1, sy - 1, 0);
    while (!dq.empty()) {
        int x, y, d;
        tie(x, y, d) = dq.front();
        dq.pop_front();
        if(x < 0 || x >= R || y < 0 || y >= C || dist[x][y] >= 0 || s[x][y] == '#') continue;
        dist[x][y] = d;

        for(int dx = -2; dx < 3; dx++) {
            for(int dy = -2; dy < 3; dy++) {
                if(dx * dx + dy * dy == 1) {
                    dq.emplace_front(x + dx, y + dy, d);
                } else if(dx * dx + dy * dy > 1) {
                    dq.emplace_back(x + dx, y + dy, d + 1);
                }
            }
        }
    }

    cout << dist[ex - 1][ey - 1];
    return 0;
}


Measured memory_bytes: 11980
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define EPS (1e-7)
#define INF (1e9)
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
const double PI = acos(-1);
const ll MOD = 1000000007;
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;
}

vector<bool> A(1299710,true);
vector<int> B(0);

int main() {
  A[0] = A[1] = false;
  for (int i = 2; i * i <= 1299709; i++) {
    if (A[i]) {
      int j = i + i;
      while (j <= 1299709) {
        A[j] = false;
        j += i;
      }
    }
  }
  rep(i,1299710) {
    if (A[i]) B.push_back(i); 
  }

  while (true) {
    int N; cin >> N;
    if (N == 0) break;
    if (A[N]) cout << 0 << endl;
    else {
      int v = lower_bound(all(B),N) - B.begin();
      cout << B[v] - B[v-1] << endl;
    }
  }
}


Measured memory_bytes: 3448
import sys
input=sys.stdin.readline
n=int(input())
ans=0
for i in range(n):
	ans+=(i+1)*(n-i)
for i in range(n-1):
	a,b=map(int,input().split())
	a,b=min(a,b),max(a,b)
	ans-=a*(n-b+1)
print(ans)

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

#define MP make_pair
#define PB push_back
#define ALL(x)      (x).begin(),(x).end()
#define REP(i,n)    for(int i=0;i<(n);i++)
#define REP1(i,n)   for(int i=1;i<(n);i++)
#define REP2(i,d,n) for(int i=(d);i<(n);i++)
#define RREP(i,n)   for(int i=(n);i>=0;i--)
#define CLR(a)      memset((a),0,sizeof(a))
#define MCLR(a)     memset((a),-1,sizeof(a))
#define RANGE(x,y,maxX,maxY) (0 <= (x) && 0 <= (y) && (x) < (maxX) && (y) < (maxY))
 
typedef long long LL;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef vector<VI > VVI;
typedef vector<string> VS;
typedef vector<LL> VLL;
typedef pair<int,int> PII;
 
const int INF = 0x3f3f3f3f;
const LL INFL = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-9;
 
const int DX[]={1,0,-1,0},DY[]={0,-1,0,1};


void solve(std::string s){
    LL ans = 0;
    RREP(i, s.size()-1) {
        if(s[i] == 'C') {
            LL cnt = 0;
            char now = 'C';
            while(0 < i) {
                if(now == 'C' && s[i-1] == 'B') {
                    cnt++;
                    i--;
                    now = 'B';
                    continue;
                } else if (now == 'B' && s[i-1] == 'C'){
                    i--;
                    now = 'C';
                    continue;
                } else if (now == 'B' && s[i-1] == 'A') {
                    ans += cnt;
                    i--;
                    continue;
                }
                break;
            }
        }
    }

    cout << ans << endl;
}

int main(){
    std::string s;
    std::cin >> s;
    solve(s);
    return 0;
}


Measured memory_bytes: 772
#include <stdio.h>
#define N 100000
#define Q 50000

main(){
  int i, n, q, c, left, right, mid;
  int s[N], t[Q];

  scanf("%d", &n);

  for( i = 0; i < n; i++){
    scanf("%d", &s[i]);
  }

  scanf("%d", &q);

  for( i = 0; i < q; i++){
    scanf("%d", &t[i]);
  }

  c = 0;
  
  for( i = 0; i < q; i++){

    left = 0;
    right = n;

    while( left < right ){
      
      mid = ( left + right )/2;
      
      if( s[mid] == t[i] ){
	c++;
	break;
      }
      
      else if( s[mid] > t[i] ){
	right = mid;
      }
      
    else left = mid + 1;
    }
  }
  
  printf("%d\n", c);
  
  return 0;

}

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

#define For(i, j, k) for (int i = j; i <= k; i++)

using namespace std;

typedef long long LL;

int main() {

	int Case;
	scanf("%d", &Case);
	while (Case--) {
		int a, b;
		scanf("%d%d", &a, &b);
		if (a > b) swap(a, b);
		if (a == b) {
			printf("%d\n", 2 * (a - 1));
			continue;
		}

		int L = a - 1, R = b;
		while (L < R) {
			int mid = (L + R + 1) >> 1;
			if (1ll * mid * mid < 1ll * a * b) L = mid;
			else R = mid - 1;
		}
		LL lim = (1ll * a * b - 1) / L;
		printf("%d\n", L == lim ? 2 * L - 2 : 2 * L - 1);

	}

	return 0;
}

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

#define w cout
#define e '\n'
#define int long long
#define sz(x) (int)x.size()
template<class T> inline istream& operator>>(istream& str, vector<T> &a) { for (auto &i : a) str >> i; return str; }

int mod = 998244353;

void solve() {
	int n ; cin >> n;
	int v[n + 1] = {};
	for(int i = 1 ; i <= n ;i ++) cin >> v[i];
	int dd[n + 1][30];
	
	memset(dd , 0, sizeof dd);
	
	int l , q; cin >> l >> q;
	
	for(int i = 1; i <= n ;i ++){
		int can = v[i] - l;
		dd[i][0] = max(1ll , (int)(lower_bound(v + 1 , v + n + 1 , can) - v));
	}
	for(int i = 1; i <= n ;i ++) {
		for(int j = 1; j <= 17 ;j ++) {
			dd[i][j] = dd[dd[i][j-1]][j-1];
		}
	}
	
	while(q--) {
		int a ,b ; cin >> a >> b;
		if(a > b) swap(a , b);
		int ans = 0;
		
		for(int j = 17 ; j >= 0; j --) {
			if(dd[b][j] > a) {
				ans += pow(2 , j);
				b = dd[b][j];
			}
		}
		w << ans + 1 << e;
	}
}

signed main() {
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t = 1; 
	//~ cin >> t;
	while(t--) {
		solve();
	}
} 


Measured memory_bytes: 25088
import java.util.*;
//import java.util.stream.Collectors;

public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		
		String s = sc.next();
		Set<Character> set = new HashSet<>();
		for(int i=0; i<s.length(); i++){
			set.add(s.charAt(i));
		}
		System.out.println(set.size() == s.length() ? "yes" : "no");
	}
}


Measured memory_bytes: 35316
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		if(a%2==0) {
			System.out.println(a/2*a/2);
		}else {
			System.out.println(a/2*(a/2+1));
		}
	}
}

Measured memory_bytes: 22996
#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <math.h>
#include<bitset>
#include<stdio.h>
#include<iomanip>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
const int INF = 100000000;

bool isOK(int a[],int index,int key){
    if(a[index] >= key){
        return true;
    }else{
        return false;
    }
}

int binary_search(int a[],int n,int key){
    int left = -1;
    int right = n;

    while(right-left>1){
        int mid = left + (right - left)/2;
        if(isOK(a,mid,key)){
            right = mid;
        }else{
            left = mid;
        }
    }
    return right;
}

int factrial(int n){
    if(n==0){
        return 1;
    }else{
        return n*factrial(n-1);
    }
}

int main(void){
    string s,t;
    cin >> s >> t;
    int len = s.size();
    bool flag = true;
    rep(i,len){
        if(s[i]!=t[i]){
            flag = false;
        }
    }

    if(flag){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
    return 0;
}


Measured memory_bytes: 3620
# Enter your code here. Read input from STDIN. Print output to STDOUT

import numpy as np
from sys import stdin


def get_result(data):
    remainder = data[0] % data[1]
    quotient = data[0] // data[1]
    return quotient if remainder == 0 else quotient + 1

if __name__ == '__main__':
    data = list(map(int, stdin.readline().split(' ')))
    result = get_result(data)
    print(result)


Measured memory_bytes: 12476
#include<bits/stdc++.h>
using namespace std;
main() {
	int n,m,k; cin >> n >> m >>k;
	int a[n][m],b[n][m];
	for (int i = 0; i < n; i++)
	for (int j = 0; j < m; j++) {
		char c; cin >> c;
		a[i][j] = c == '#';
	}
	int ans = 0;
	for (int i = 0; i < (1 << n); i++)
	for (int j = 0; j < (1 << m); j++) {
		for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++) {
		b[i][j] = a[i][j];
		}
		for (int h = 0; h < n; h++)
			if ((1 << h) & i) {
				for (int j = 0; j < m; j++)
					b[h][j] = 0;
			}
		for (int h = 0; h < m; h++)
			if ((1 << h) & j) {
				for (int i = 0; i < n; i++)
					b[i][h] = 0;
			}
		int cnt = k;
		for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++) {
			cnt -= b[i][j];
		}
		ans += cnt == 0;
	}
	cout << ans;
	
}

Measured memory_bytes: 3588
A = []
while True:
    a, b = map(int, input().split())
    if a == b == 0:
        break
    else:
        B = []
        B.append(a)
        B.append(b)
        A.append(B)
        
for i in A:
    i.sort()
    print("{} {}".format(i[0],i[1]))


Measured memory_bytes: 5980
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int D = sc.nextInt();

        int[][] cs = new int[N][D];


        int count =0;

        for (int i = 0; i < N ; i++) {
            for (int j = 0; j < D; j++) {
                cs[i][j] = sc.nextInt();
            }
        }

        for (int i = 0; i < N ; i++) {
            for (int j = i+1; j < N; j++) {
                int sum = 0;
                for (int k = 0; k < D; k++) {
                    sum += (cs[i][k]-cs[j][k])*(cs[i][k]-cs[j][k]);
                }
                double dist =Math.sqrt(sum);
                if( (dist - Math.floor(dist))==0){
                    count++;
                }
            }
        }

        System.out.println(count);

    }

}


Measured memory_bytes: 22740
N = int(input())
A = list(map(int,input().split()))
B = [it - (idx + 1) for idx, it in enumerate(A)]
S = []

B.sort()
if N%2 == 1:
    b = B[(N-1)//2]
else:
    b = (B[(N-1)//2] + B[(N-1)//2 + 1]) // 2
    
S = sum([abs(i-b) for i in B])
    
print(S)

Measured memory_bytes: 26948