akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <cstring>
#include <functional>
#include <queue>
#include <cmath>
#include <utility>

using namespace std;

#define int long long
#define rep(i,n) for(int i=0;i<(int)n;++i)
#define rep1(i,n) for(int i=1;i<=(int)n;++i)

int N, Q;

vector<int> G[200010];
int	X[200010];
int ans[200010];

void dfs(int cur, int par, int sum)
{
	X[cur] += sum;

	// leaf
	if (G[cur].size() == 1 and G[cur][0] == par) return;

	for (int &nxt : G[cur]) {
		if (nxt == par) continue;
		dfs(nxt, cur, X[cur]);
	}
}

signed main()
{
	scanf("%lld%lld", &N, &Q);

	rep(i, N-1) {
		int a, b;
		scanf("%lld%lld", &a, &b);
		--a,--b;
		G[a].push_back(b);
		G[b].push_back(a);
	}

	rep(i, Q) {
		int p, x;
		scanf("%lld%lld", &p, &x);
		--p;
		X[p] += x;
	}

	dfs(0, -1, 0);

	rep(i, N) printf("%lld%c", X[i], i==N-1?'\n':' ');
}


Measured memory_bytes: 24320
#include<bits/stdc++.h>
#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)
using namespace std;
typedef long long ll;
#include<bits/stdc++.h>
using namespace std;
int main(){
  int x,y;
  cin >> x >> y;
  cout << x+y/2 << endl;
  return 0;
}

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

#define mem(t, v)   memset ((t) , v, sizeof(t))
#define all(x)      x.begin(),x.end()
#define un(x)       x.erase(unique(all(x)), x.end())
#define sf(n)       scanf("%d", &n)
#define sff(a,b)    scanf("%d %d", &a, &b)
#define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)
#define sl(n)       scanf("%lld", &n)
#define sll(a,b)    scanf("%lld %lld", &a, &b)
#define slll(a,b,c) scanf("%lld %lld %lld", &a, &b, &c)
#define D(x)        cerr << #x " = " << (x) << '\n'
#define DBG         cerr << "Hi" << '\n'
#define pb          push_back
#define PI          acos(-1.00)
#define xx          first
#define yy          second
#define eps         1e-9

typedef unsigned long long int ULL;
typedef long long int LL;
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;


inline int setBit(int N, int pos) { return N=N | (1<<pos); }
inline int resetBit(int N, int pos) { return N= N & ~(1<<pos); }
inline bool checkBit(int N, int pos) { return (bool)(N & (1<<pos)); }

//int fx[] = {+0, +0, +1, -1, -1, +1, -1, +1};
//int fy[] = {-1, +1, +0, +0, +1, +1, -1, -1}; //Four & Eight Direction
map<int,int>freq;
int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int n, a;
    sf(n);
    for(int i = 1; i<=n; i++)
    {
        sf(a);
        freq[a]++;
    }
    int ans = 0;
    for(auto u: freq)
    {
        if(u.xx <= u.yy)
            ans += u.yy - u.xx;
        else
            ans += u.yy;
    }
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 4736
#include<iostream>

using namespace std;

int main(){
  int a,b;
  cin >> a >> b;
  if(a == 1) a = 13 + 1;
  if(b == 1) b = 13 + 1;
   if(a>b) cout << "Alice" << endl;
   else if(a<b) cout << "Bob" << endl;
   else cout << "Draw" << endl;

  return 0;
}


Measured memory_bytes: 256
def slove():
    import sys
    import bisect
    import collections
    import copy
    import fractions
    import heapq
    input = sys.stdin.readline
    n, m = list(map(int, input().rstrip('\n').split()))
    d = collections.defaultdict(list)
    for i in range(m):
        a, b = list(map(int, input().rstrip('\n').split()))
        d[a-1] += [b-1]
        d[b-1] += [a-1]

    ql = collections.deque()
    ql.append([0, [0]])
    cnt = 0
    while True:
        if len(ql) != 0:
            qp, ls = ql.popleft()
            for v in d[qp]:
                if v not in ls:
                    tls = copy.deepcopy(ls)
                    tls.append(v)
                    if len(tls) < n:
                        ql.append([v, tls])
                    else:
                        cnt += 1
        else:
            break
    print(cnt)


if __name__ == '__main__':
    slove()


Measured memory_bytes: 75860
package main

import (
	"fmt"
)

func main() {
	var n int
	fmt.Scanf("%d", &n)

	d := scanNums(n)

	fmt.Println(answer(n, d))
}

func answer(n int, d *[]int) int {
	sum := 0
	for _, v := range *d  {
		sum += v
	}

	res := 0
	for _, v := range *d {
		res += (sum - v)*v
	}
	return res/2
}

func scanNums(len int) *[]int {
	var num int
	nums := make([]int, len)
	for i := 0; i < len; i++ {
		fmt.Scan(&num)
		nums[i] = num
	}
	return &nums
}


Measured memory_bytes: 512
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
int n,m,x;
int a[1000];

int main()
{
    cin>>n>>m>>x;
    int ans1=0,ans2=0;
    for (int i=0; i<m; ++i)
    {
        cin>>a[i];
        ans1+=(a[i]<x);
        ans2+=(a[i]>x);
    }
    cout<<min(ans1,ans2)<<endl;
        

    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
int main(void)
{
	int D;
	scanf("%d", &D);
	switch (D)
	{
	case 25:
		printf("Christmas",D);
		break;
	case 24:
		printf("Christmas Eve", D);
		break;
	case 23:
		printf("Christmas Eve Eve", D);
		break;
	case 22:
		printf("Christmas Eve Eve Eve", D);
		break;
	}
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h> // {{{
// clang-format off
#pragma GCC optimize "O3,omit-frame-pointer,inline"
#pragma GCC target "tune=native"
#define ARG4(_1, _2, _3, _4, ...) _4
#define rep(...) ARG4(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define REP(i, a) FOR(i, 0, a)
#define FOR(i, a, b) for (int i = (a); i < (int)(b); ++i)
#define rrep(...) ARG4(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
#define RREP(i, a) RFOR(i, 0, a)
#define RFOR(i, a, b) for (int i = (b)-1; i >= (int)(a); --i)
#define ALL(c) (c).begin(), (c).end()
#define TEN(n) ((ll)(1e##n))
#define pb emplace_back
#define mp make_pair
#define fi first
#define se second
#define USE1(T) template<typename T>inline
#define USE2(T, U) template<typename T,typename U>inline
#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)

template<typename T>using duo=std::pair<T,T>;
template<typename T>using vec=std::vector<T>;
using ll=long long;
using pii=duo<int>;
USE2(T,U)bool chmax(T&x,U a){return x<a&&(x=a,1);}
USE2(T,U)bool chmin(T&x,U a){return a<x&&(x=a,1);}
USE1(T=int)T in(){T x;std::cin>>x;return x;}
USE1(T=int)vec<T>in(int n){vec<T>v;v.reserve(n);rep(i,n)v.pb(in<T>());return v;}
USE1(T=int)vec<T>in(int n,T a){vec<T>v;v.reserve(n);rep(i,n)v.pb(in<T>()+a);return v;}
USE1(T)vec<std::pair<T,int>>enume(const vec<T>&x,int s=0){int N=x.size();vec<std::pair<T,int>>v;v.reserve(N);rep(i,N)v.pb(x[i],s+i);return v;}
USE1(T)vec<T>ndvec(T v,int n){return vec<T>(n,v);}
USE2(T,...Ts)auto ndvec(T v,int n,Ts...ns)->vec<decltype(ndvec(v,ns...))>{return ndvec(ndvec(v,ns...),n);}
USE1(T)void pr(T x){std::cout<<x<<'\n';}
USE2(T,...Ts)void pr(T x,Ts...xs){std::cout<<x<<' ';pr(xs...);}
USE1(T=int)T rd(){T x=0,m=0,k;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||'9'<k)break;x=x*10+k-'0';}return x;}
USE1(T=int)void wr(T x,char c='\n'){int s=0,m=0;char b[32];if(x<0)m=1,x=-x;for(;x;x/=10)b[s++]=x%10;if(!s)b[s++]=0;if(m)mypc('-');for(;s--;)mypc(b[s]+'0');mypc(c);}
// clang-format on
// }}}
struct IoSetup { // {{{
  IoSetup() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.precision(10);
    std::cerr.precision(10);
  }
} iosetup; //}}}
using namespace std;
const int inf = 1001001001;
const ll infl = 1001001001001001001ll;
const int dd[] = {0, 1, 0, -1, 0};

inline bool ok(int x, int N) {
  int A = N;
  for (int i = x; i >= 1; i--) {
    if (A <= i) return true;
    A -= i;
  }
  return false;
}

signed main() { //
  int N = in();
  int l = 0, r = N;
  while (r - l > 1) {
    int m = (r + l) / 2;
    if (ok(m, N)) {
      r = m;
    } else {
      l = m;
    }
  }
  vec<int> ans;
  for (int i = r; i >= 1; i--) {
    if (N >= i) {
      ans.pb(i);
      N -= i;
    }
  }
  reverse(ALL(ans));
  for (auto&& a : ans) {
    pr(a);
  }
  return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
#include <numeric>
typedef long long ll;
#define rep(i,a,b) for(int i=a;i<b;++i)
#define rrep(i,a,b) for(int i=a;i>=b;--i)
using namespace std;

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

    vector<int> A(3); 
    cin >> A[0] >> A[1] >> A[2];
    sort(A.begin(), A.end(), greater<int>());

    int res = 0;
    if (A[0]-A[1] >= 2) {
        int opNum = (A[0]-A[1])/2;
        A[1] += opNum*2;
        res += opNum;
    }
    if (A[0]-A[2] >= 2) {
        int opNum = (A[0]-A[2])/2;
        A[2] += opNum*2;
        res += opNum;
    }

    int isDiffOne = 0;
    if (A[0]-A[1] == 1) ++isDiffOne;
    if (A[0]-A[2] == 1) ++isDiffOne;

    if (isDiffOne == 1) res += 2;
    if (isDiffOne == 2) res += 1;

    cout << res << endl;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(void)
{
  int n,i,x,count;

  while(1){
    scanf("%d",&n);
    if(n==0)break;
    count=0;
    for(i=5;i<=n;i+=5){
      x=i;
      while(x%5==0){
        count++;
        x/=5;
      }
  }   
     printf("%d\n",count);
  }
  return 0;
}

Measured memory_bytes: 600
# 左から，逆立ちしている人(1)が連続して並んでいる人数，直立している人(0)が連続して並んでいる人数を順にaに格納していく。
# 一番左の人が直立している(0)ときは，aの先頭に0を追加し，a[0]=0とする。
# 一番右の人が直立している(0)ときにも，aの末尾に0を追加する。
# この操作により，aの最初と最後は，逆立ちしている人(1)の人数となる。
# m=len(a))はN人の人が何ブロックに分かれるかを表す。ただし，最初又は最後に付加され得る，0人の逆立ちしている人から成るブロックを含む。このときmは奇数なので，m=2*l+1と表せる(l>=0)。
# i回の操作により，1のブロックから始まる連続した2*i+1ブロックの全員を1とできる。
# K>=l=(m-1)//2,すなわち2*K+1>=mであれば，N人全員を1にできる。
# K<(m-1)//2であれば，「aの偶数番目の要素a[j]から始まる連続した2*K+1個の要素(a[j+2*K]まで(この要素を含む。))の総和の人数」の最大値を1にできる。(j+2*K<=m-1=2*l,よってj<=2*(l-K))

N,K=map(int,input().split())
S=input()
a=[]

now=S[0]
cnt=1
for c in S[1:]:
    if c==now:
        cnt+=1
    else:
        a.append(cnt)
        now=c
        cnt=1
a.append(cnt)

if S[0]=='0':
    a=[0]+a
if S[-1]=='0':
    a=a+[0]

# print(a)

m=len(a) # m=2*l+1

# print(m)

if 2*K+1>=m:
    ans=N
else:
    l=0;r=2*K+1
    nowsum=sum(a[l:r])
    # print(l,r,nowsum)
    maxsum=nowsum
    while True:
        l+=2;r+=2
        if r>m:
            break
        nowsum=nowsum-a[l-2]-a[l-1]+a[r-2]+a[r-1]  
        maxsum=max(maxsum,nowsum)
        # print(l,r,nowsum)
    ans=maxsum
print(ans)

Measured memory_bytes: 4980
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
import java.util.List;

public class Main {
    public static Scanner sc = new Scanner(System.in);
    public static void main(String[] args) throws Exception {
        int n = sc.nextInt();
        long sum = 0;
        List<Long> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            long l = sc.nextLong();
            list.add(l);
            sum += l;
        }
        
        Collections.sort(list);
        
        System.out.println(list.get(0) + " " + list.get(n-1) + " " + sum);
    }
}

Measured memory_bytes: 41724
#include<bits/stdc++.h>
#define fo(i,a,b)for(int i=a,_e=b;i<=_e;++i)
#define fd(i,a,b)for(int i=b,_e=a;i>=_e;--i)
#define id(x,y,z)(((x)-1)*6+(y)*3+(z)%3+1)
using namespace std;
const int N=50005,M=1e6+5;
int n,m,q,mo,g,c0,s,t,r;
int a[N],b[N],c[N];
int f[N*6];
bool is[M][2],can;
int F(int x){return f[x]==x?x:f[x]=F(f[x]);}
int gcd(int x,int y){
	for(;y;y%=x)swap(x,y);
	return x;
}
void link(int x,int y){f[F(x)]=F(y);}
int main(){
	ios::sync_with_stdio(false);
	cin>>n>>m>>q>>mo;
	fo(i,1,m){
		cin>>a[i]>>b[i]>>c[i];
		if(i>1)g=gcd(g,abs(c[i]-c[1]));
	}
	if(!g)g=mo;
	mo=gcd(g*3,mo);
	c0=c[1]%(g*3);
	for(int i=0,a=c0;i<=mo*2;++i,a=a*2%mo)is[a][i%2]=1;
	fo(i,1,6*n)f[i]=i;
	fo(i,1,m){
		c[i]=(c[i]-c0+g*3)/g%3;
		fo(p,0,1)
			fo(q,0,2)
				link(id(a[i],p,q),id(b[i],!p,q*2+c[i])),link(id(b[i],p,q),id(a[i],!p,q*2+c[i]));
	}
	for(;q--;){
		cin>>s>>t>>r;
		can=0;
		fo(p,0,1)
			fo(q,0,2)
				if(F(id(t,0,0))==F(id(s,p,q))&&is[(r+c0+(3-q)*g)%mo][p])
					can=1;
		printf(can?"YES\n":"NO\n");
	}
}

Measured memory_bytes: 4096
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) throws NumberFormatException,
			IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(in.readLine()), maximum = Integer.MIN_VALUE, minimum;
		int[] timeRate = new int[n];
		for (int i = 0; i < n; i++) {
			timeRate[i] = Integer.parseInt(in.readLine());
		}
		minimum = timeRate[0];
		for (int x = 1; x < n; x++) {
			if (maximum < timeRate[x] - minimum) {
				maximum = timeRate[x] - minimum;
			}
			if (minimum > timeRate[x]) {
				minimum = timeRate[x];
			}
		}
		System.out.println(maximum);
	}
}

Measured memory_bytes: 37716
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**18
eps = 10**-7
 
x,y = map(int,readline().split())
 
if x*y > 0:
    if x > y:
        print(x-y+2)
    else:
        print(y-x)
elif x*y < 0:
    print(abs(abs(x)-abs(y))+1)
else:
    if x == 0:
        if y > 0:
            print(y)
        else:
            print(-y+1)
    else:
        if x > 0:
            print(x+1)
        else:
            print(-x)


Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define REP(i,m,n) for(int i=(m);i<(n);i++)
#define rep(i,n) REP(i,0,n)
#define pb push_back
#define all(a) a.begin(),a.end()
#define rall(c) (c).rbegin(),(c).rend()
#define mp make_pair
#define endl '\n'
#define fi first
#define se second
typedef long long ll;
typedef pair<ll,ll> pll;
typedef long double ld;
const ll inf=1e9+7;
const ll mod=998244353;
signed main(){
    ll x,y;cin>>x>>y;
    if((4*x-y)>=0&&(4*x-y)%2==0&&(4*x-y)<=2*x){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }
}

Measured memory_bytes: 3676
import sys

input = sys.stdin.readline
n = int(input())
v_list = list(map(int, input().split()))
c_list = list(map(int, input().split()))
ans = 0
for i in range(n):
    dis = v_list[i] - c_list[i]
    if dis > 0:
        ans += dis
print(ans)


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  cin >> N;

  vector<int>a(N);
  for (int i = 0; i < N; i++) {
    cin >> a.at(i);
  }
  
  vector<int>count(N,0);
  for (int i = 2; i < 142; i++) {
    for (int j = 2; j < 142; j++) {
      for (int k = 2; k < 142; k++) {
        if ((i*i + j*j + k*k)%2 == 0 && i*i + j*j + k*k <= 2*N){
          if ((i+k-j)>= 2 && (i+k-j)%2 == 0 && (i+j-k)>= 2 && (i+j-k)%2 == 0 &&(j+k-i)>= 2 && (j+k-i)%2 == 0){
            count.at((i*i + j*j + k*k)/2 - 1)++;
          }
        }
      }
    }
  }
  
  for (int i = 0; i < N; i++) {
    cout << count.at(i) << endl;
  }
}
        

Measured memory_bytes: 3704
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;

public class Main {
    public static void main(String[] args) throws IOException {
//    	long l = System.currentTimeMillis();
        new Main().exec();
//    	long l2 = System.currentTimeMillis();
//    	System.out.println(l2 - l);
    }
    
    public void exec() throws IOException {
        InputUtil in = new InputUtil();
        PrintWriter out = new PrintWriter(System.out);
        int N = in.nextInt();
        int ans = 1;
        while (ans*2 <= N) {
        	ans *= 2;
        }
        out.println(ans);
        out.flush();
    }
    
}

class InputUtil {
	//Static Fields
	private static final int BUFSIZ = 50000;
	
	//Fields
	protected InputStream in;
	private char[] buf = null;
	private int ptr = 0;
	private int max = -1;
	private BufferedReader br = null;
	
	//Constructors
	public InputUtil() {this(System.in,BUFSIZ);}
	public InputUtil(InputStream in, int bufsiz) {
		initBuf(bufsiz);
		initIn(in);
	}
	
	//Methods
	//Initializer
	protected void initIn(InputStream in) {br = new BufferedReader(new InputStreamReader(this.in = in));}
	protected void initBuf(int bufsiz) {buf = new char[bufsiz];}
	
	//buffer operation
	private void next() throws IOException {ptr++; readBuf();}
	private void readBuf() throws IOException {
		if(ptr >= max && br.ready()) {
			max = br.read(buf);
			ptr = 0;
		}
	}
	//Number Input Reader/Parser
	private boolean isNum(char b) {return '0' <= b && b <= '9'; }
	private boolean isMinus(char b) {return b=='-'; }

	private int _nextInt() throws IOException {
		int sign = 1;
		int res = 0;
		char c;
		while (!isNum(c=buf[ptr]) && !isMinus(c)) 
			next();
		if (isMinus(buf[ptr])) {
			sign = -1;
			next();
		}
		while (isNum(c=buf[ptr])) {
			res *= 10;
			res += c - '0' ;
			next();
		}
		next();
		return sign * res;
	}
	
	public int nextInt() throws IOException {
		readBuf();
		return _nextInt();
	}

	public int[] nextInt(int[] result) throws IOException {
		readBuf();
		for(int i=0; i<result.length; i++) {
			result[i] = _nextInt();
		}
		return result;
	}
	
	//Close 
	public void close() throws IOException {
		if(!this.in.equals(System.in)) 
			this.in.close();
	}

}

Measured memory_bytes: 22996
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;

int main()
{
	ll sum = 0;
	int n; cin >> n;
	while (n--)
	{
		ll x; cin >> x;
		sum += x;
	}
	cout << (sum & 1 ? "NO\n" : "YES\n") << "\n";
}

Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.Scanner;
import java.util.HashSet;
import java.util.Iterator;

class Main {

    static final int MOD = 1000000007;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        int ans = 0;
        for(int i=0;i<N;i++){
            if(K<=sc.nextInt())ans++;
        }
        System.out.println(ans);
    }
}

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

typedef long long int lli;

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

    int n;
    cin >> n;

    vector<lli> v(n + 1);
    lli sum = 0;

    for(int i = 1; i <= n; i++)
    {
        cin >> v[i];
        sum += v[i];
    }

    int m;
    cin >> m;

    while(m--)
    {
        int p, x;
        cin >> p >> x;

        cout << sum - v[p] + x << endl;
    }


}


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

//create arrays outside of main()

int a[5];

int main(){

    int N;
    int digits;
    int odds = 0;
    int digitWorking;
    cin >> N;

    for (int i=1; i<N+1; i++){
        digits =0;
        digitWorking = i;
        while(digitWorking>=1){
            digits += 1;
            digitWorking = digitWorking/10;
        }

        if(digits%2==1){
            odds += 1;
        }
    
    }

    cout << odds;

    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
 
struct node{
  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};
typedef struct node * Node;
#define NIL NULL
 
Node root;
 
Node treeMinimum(Node x){
while(x->left != NIL){
x = x->left;
}
return x;
 
}
 
Node treeSearch(Node u, int k){
if(u == NIL || k == u->key) return u;
if(k < u->key) return treeSearch(u->left,k);
else return treeSearch(u->right,k);
 
 
while(u != NIL && k != u->key){
if(k < u->key) u = u->left;
else u = u->right;
}
return u;
}
 
Node treeSuccessor(Node x){
Node y;
 
if(x->right != NIL) return treeMinimum(x->right);
y = x->parent;
 
while(y != NIL && x == y->right){
x = y;
y = y->parent;
}
 
return y;
 
}
 
void treeDelete(Node z){
  Node y; // node to be deleted
  Node x; // child of y
if(z->left == NIL || z->right == NIL) y = z;
else y = treeSuccessor(z);
 
if(y->left != NIL) x = y->left;
else x = y->right;
 
if(x != NIL) x->parent = y->parent;
if(y->parent == NIL) root = x;
else if(y == y->parent->left) y->parent->left = x;
else y->parent->right = x;
 
if(y != z) z->key=y->key;
 
 
 
 
 
}
 
void insert(int k){
  Node a = root;
  Node b = NIL;
  Node c;
 
  c = malloc(sizeof(struct node));
  c->key = k;
  c->left = NIL;
  c->right = NIL;
 
while(a != NIL){
 b = a;
 if(c->key < a->key){
 a = a->left;
 }
 
 else a = a->right;
}
 
 c->parent = b;
 
 if(b == NIL) root = c;
 
 else if(c->key < b->key) b->left = c;
 else b->right = c;
 
 
 
 
 
}
 
void inorder(Node n){
if(n != NIL){
 inorder(n->left);
 printf(" %d",n->key);
 inorder(n->right);
 }
}
void preorder(Node n){
if(n != NIL){
 printf(" %d",n->key);
 if(n->left != NIL)preorder(n->left);
 if(n->right != NIL)preorder(n->right);
 }
}
 
 
int main(){
  int n, i, x;
  char com[20];
  scanf("%d", &n);
 
  for ( i = 0; i < n; i++ ){
    scanf("%s", com);
    if ( com[0] == 'f' ){
      scanf("%d", &x);
      Node t = treeSearch(root, x);
      if ( t != NIL ) printf("yes\n");
      else printf("no\n");
    } else if ( com[0] == 'i' ){
      scanf("%d", &x);
      insert(x);
    } else if ( com[0] == 'p' ){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    } else if ( com[0] == 'd' ){
      scanf("%d", &x);
      treeDelete(treeSearch(root, x));
    }
  }
 
  return 0;
}

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

class UnionFindTree {
private:
  int S[10000];
  int h[10000];
public:
  void init(int N) {
    for (int i=0; i<N; i++) {
      S[i]=i;
      h[i]=0;
    }
  }
  int root(int c) {
    if (c==S[c]) {
      return c;
    } else {
      return (S[c]=root(S[c]));
    }
  }
  void unite(int a,int b) {
    a=root(S[a]);
    b=root(S[b]);
    if (a==b) {
      return ;
    }
    if (h[a]<h[b]) {
      S[a]=b;
    } else {
      S[b]=a;
      if (h[a]==h[b]) {
        h[a]++;
      }
    }
  }
  bool same(int a,int b) {
    return (root(a)==root(b));
  }
};
int main() {
  int n, q;
  cin >> n >> q;
  UnionFindTree f;
  f.init(n);
  while (q--) {
    int com, x, y;
    cin >> com >> x >> y;
    if (!com) {
      f.unite(x,y);
    } else {
      printf("%d\n",f.same(x,y));
    }
  }
  return 0;
}

Measured memory_bytes: 3280
import java.util.*; import java.io.*; import java.math.*;
public class Main{
	//Don't have to see. start------------------------------------------
	static class InputIterator{
		ArrayList<String> inputLine = new ArrayList<String>(1024);
		int index = 0; int max; String read;
		InputIterator(){
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			try{
				while((read = br.readLine()) != null){
					inputLine.add(read);
				}
			}catch(IOException e){}
			max = inputLine.size();
		}
		boolean hasNext(){return (index < max);}
		String next(){
			if(hasNext()){
				return inputLine.get(index++);
			}else{
				throw new IndexOutOfBoundsException("There is no more input");
			}
		}
	}
	static HashMap<Integer, String> CONVSTR = new HashMap<Integer, String>();
	static InputIterator ii = new InputIterator();//This class cannot be used in reactive problem.
	static PrintWriter out = new PrintWriter(System.out);
	static void flush(){out.flush();}
	static void myout(Object t){out.println(t);}
	static void myerr(Object t){System.err.print("debug:");System.err.println(t);}
	static String next(){return ii.next();}
	static boolean hasNext(){return ii.hasNext();}
	static int nextInt(){return Integer.parseInt(next());}
	static long nextLong(){return Long.parseLong(next());}
	static double nextDouble(){return Double.parseDouble(next());}
	static ArrayList<String> nextStrArray(){return myconv(next(), 8);}
	static ArrayList<String> nextCharArray(){return myconv(next(), 0);}
	static ArrayList<Integer> nextIntArray(){
		ArrayList<String> input = nextStrArray(); ArrayList<Integer> ret = new ArrayList<Integer>(input.size());
		for(int i = 0; i < input.size(); i++){
			ret.add(Integer.parseInt(input.get(i)));
		}
		return ret;
	}
	static ArrayList<Long> nextLongArray(){
		ArrayList<String> input = nextStrArray(); ArrayList<Long> ret = new ArrayList<Long>(input.size());
		for(int i = 0; i < input.size(); i++){
			ret.add(Long.parseLong(input.get(i)));
		}
		return ret;
	}
	static String myconv(Object list, int no){//only join
		String joinString = CONVSTR.get(no);
		if(list instanceof String[]){
			return String.join(joinString, (String[])list);
		}else if(list instanceof ArrayList){
			return String.join(joinString, (ArrayList)list);
		}else{
			throw new ClassCastException("Don't join");
		}
	}
	static ArrayList<String> myconv(String str, int no){//only split
		String splitString = CONVSTR.get(no);
		return new ArrayList<String>(Arrays.asList(str.split(splitString)));
	}
	public static void main(String[] args){
		CONVSTR.put(8, " "); CONVSTR.put(9, "\n"); CONVSTR.put(0, "");
		solve();flush();
	}
	//Don't have to see. end------------------------------------------
	static void solve(){//Here is the main function
		int N = nextInt();
		ArrayList<Long> list = nextLongArray();
		long output = 0;
		for(int i = 1; i < N; i++){
			if(list.get(i - 1) > list.get(i)){
				output += list.get(i - 1) - list.get(i);
				list.set(i, list.get(i - 1));
			}
		}
		myout(output);
	}
	//Method addition frame start



	//Method addition frame end
}


Measured memory_bytes: 62640
#include "bits/stdc++.h"
using namespace std;

#define rep(i,beg,end)   for (auto i=(beg);i<(end);i++)
#define all(cont)           begin(cont), end(cont)
#define rall(cont)           rbegin(cont), rend(cont)
using ll = long long;
using vi = vector<ll>;
const ll INFMAX = LLONG_MAX;
const ll INFMIN = LLONG_MIN;
const ll MOD = 1000000007;


int main(void)
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll n;
	cin >> n;
	ll s=0;
	rep(i, 1, n) {
		s += i;
	}
	cout << s << endl;

	return 0;
}


Measured memory_bytes: 256
#include<algorithm>
#include<bitset>
#include<cmath>
#include<complex>
#include<deque>
#include<functional>
#include<iomanip>
#include<iostream>
#include<iterator>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<unordered_map>
#include<unordered_set>
#include<utility>
#include<vector>

using namespace std;
typedef long long ll;

// i: index, n: size, a: start, b: end
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)

// x: container(array, vector etc..)
#define ALL(x) (x).begin(),(x).end()
#define SIZE(x) ((ll)(x).size())
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))

#define INF 1000000000000 //10^12
#define MOD 10000007 //10^9+7
#define MAXR 100000 //10^5

#define PB push_back
#define MP make_pair
#define F first
#define S second

signed main() {
  string s;
  cin >> s;
  string nickName;
  int maxStartIndex = s.length() - 3;
  srand((unsigned int)time(NULL));
  int startIndex = 0;
  if (maxStartIndex != 0) {
    startIndex = rand() % maxStartIndex;
  }
  FOR(i, startIndex, startIndex + 2) {
    nickName += s[i];
  }
  cout << nickName << endl;
  return 0;
}


Measured memory_bytes: 3620
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i, n) for(int i=0; i<(n); ++i)
#define FOR(i, a, b) for(int i=(a); i<(b); ++i)
#define FORR(i, a, b) for(int i=(b)-1; i>=(a); --i)
// const ll MOD=1000000007ll;
const ll MOD=1000000007ll;
const int MAX=2510000;

ll fact[MAX], fact_inv[MAX];

// 繰り返し二乗法
ll power(ll a, ll b){
	ll res=1;
	while(b>0){
		if(b&1) res=res*a%MOD;
		a=a*a%MOD;
		b>>=1;
	}
	return res;
}

ll comb(ll n, ll r){
	return (fact[n]*fact_inv[r])%MOD*fact_inv[n-r]%MOD;
}

int main(){
  
  int x,y;
  cin>>x>>y;
  if((x+y)%3!=0){
    cout<<"0"<<endl;
    return 0;
  }
  int c,d;
  c=y-(x+y)/3;
  d=x-(x+y)/3;
  if(c<0||d<0){
    cout<<"0"<<endl;
    return 0;
  }
  
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n=c+d;
	// cin>>n;
	fact[0]=1;
        // 階乗の計算
	REP(i, n) fact[i+1]=fact[i]*(i+1)%MOD;
	fact_inv[n]=power(fact[n], MOD-2);
        // 逆元の計算
	FORR(i, 0, n) fact_inv[i]=fact_inv[i+1]*(i+1)%MOD;
        // nCrの計算
  cout<<comb(c+d,d);
        return 0;
}

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

typedef pair<int, int> Pair;

int n;
int m;
int A[514][514];
bool used[1145];
int cnt[1145];

bool check(int x) {
  for (int i=0; i<m; i++) {
    cnt[i] = 0;
    used[i] = true;
  }

  for (int i=0; i<n; i++) {
    int k = A[i][0];
    cnt[k]++;
  }

  while (1) {
    bool update = false;
    for (int k=0; k<m; k++) {
      if (cnt[k] > x) {
        used[k] = false;
        update = true;
      }
      cnt[k] = 0;
    }
    if (!update) return true;

    for (int i=0; i<n; i++) {
      bool found = false;
      for (int j=0; j<m; j++) {
        int c = A[i][j];
        if (used[c]) {
          cnt[c]++;
          found = true;
          break;
        }
      }

      if (!found) return false;
    }
  }
  return true;
}

int main() {
  scanf("%d%d", &n, &m);
  for (int i=0; i<n; i++) {
    for (int j=0; j<m; j++) {
      scanf("%d", &A[i][j]);
      A[i][j]--;
    }
  }

  int low = -1;
  int high = n+1;
  while (high - low > 1) {
    int mid = (low+high)/2;
    if (check(mid)) high = mid;
    else low = mid;
  }
  printf("%d\n", high);
}


Measured memory_bytes: 896
#include <iostream>
#include <cmath>
#include <stdio.h>
using namespace std;

int main() {
  int a, b;
  double degree;
  cin >> a >> b >> degree;
  double rad = M_PI*(degree/180);
  double s = a*b*sin(rad)/2;
  printf("%.5lf\n", s);
  double c = a*a + b*b - 2*a*b*cos(rad);
  c = sqrt(c);
  printf("%.5lf\n", a+b+c);
  printf("%.5lf\n", s*2/a);
  return 0;
}

Measured memory_bytes: 3428
#include"bits/stdc++.h"
#define int long long
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=(a);i<(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define itr(i,x) for(auto i=(x).begin();i!=(x).end();++i)
#define All(x) (x).begin(),(x).end()
#define rAll(x) (x).rbegin(),(x).rend()
using namespace std;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
const int mod=1000000007;
int gcd(int x,int y){return y?gcd(y,x%y):x;}
int lcm(int x,int y){return x*y/gcd(x,y);}
void YN(bool flg){cout<<(flg?"YES":"NO")<<endl;}
void Yn(bool flg){cout<<(flg?"Yes":"No")<<endl;}
void yn(bool flg){cout<<(flg?"yes":"no")<<endl;}
signed main(){
	int x,y;
	cin>>x>>y;
	int ans=0;
	while(++ans){
		if(y-x<x) break;
		x*=2;
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 256
input=input().split()

N=int(input[0])
L=int(input[1])
taste=0
if L>0:
	for i in range(N-1):
		L+=1
		taste+=L
		
	print(taste)

elif L<0 and -L>=N:
	for i in range(N-1):
		taste+=L
		L+=1

	print(taste)
else:
	for i in range(N):
		taste+=L
		L+=1
		#print("taste",taste)
		#print("LA",L)
	print(taste)



Measured memory_bytes: 3064
#include <iostream>
#include <string>
#include <string.h>
#include <map>
#include <set>
#include <algorithm>
#include <vector>
#include <queue>
#include <stdio.h>
#include <cstdio>
#include <math.h>
#include <cmath>
#include <sstream>
#include <cassert>
#include <functional>
#include <cfloat>
#include <climits>
#include <cstring>
#include <stack>
#include <time.h>
#include <complex>
using namespace std;
int main()
{
    int N,a,b,cnt=0;
    cin>>N;
    for(int i=1;i<=N;i++){
        cin>>a>>b;
        cnt=cnt+b-a+1;
        a=0;
        b=0;
    }
    cout<<cnt<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>

int main()
{
    int i, n;
    int x[100], y;
    int d1=0, di=0;
    double d2=0, d3=0;
    scanf("%d", &n);
    for(i=0; i<n; i++) {
        scanf("%d", &x[i]);
    }
    for(i=0; i<n; i++) {
        scanf("%d", &y);
        y=abs(y-x[i]);
        d1+=y;
        d2+=y*y;
        d3+=y*y*y;
        if(di<y) di=y;
    }
    printf("%d\n%f\n%f\n%d\n", d1, sqrt(d2), pow(d3, 1.0/3.0), di);
    return 0;
}

Measured memory_bytes: 672
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define pa pair<int,int>
int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x*f;
}
int main()
{
	int n=read(),t=0;
	for(int i=1;i<=n;i++)t+=(read()&1);
	if(t)puts("first");
	else puts("second");
}


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

using namespace std;

int l[1000],r[1000];
int main(){
  int N,count;

  cin >> N;

  for (int i =0; i < N; i++) {
    cin >> l[i] >> r[i];
  }

  for(int i=0; i < N; i++){
    count +=  r[i] - l[i] + 1;
  }

  cout << count << endl ;
  return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {

    private void solve() {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();

        List<Shop> shops = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            shops.add(new Shop(sc.nextInt(), sc.nextInt()));
        }
        shops.sort((a, b) -> a.value - b.value);

        long sumValue = 0; // answer
        int sumCount = 0;
        for (Shop shop : shops) {
            for (int j = 0; j < shop.count; j++) {
                sumValue += shop.value;
                sumCount++;
                if (sumCount == M) {
                    System.out.print(sumValue);
                    return;
                }
            }
        }
    }
    class Shop {
        int value;
        int count;
        Shop(int value, int count) {
            this.value = value;
            this.count = count;

        }
    }
    // Main
    public static void main(String[] args) {
        new Main().solve();
    }
}


Measured memory_bytes: 84880
def dfs(cnt):
    global ans
    if cnt == N:
        onF = True
        for i in range(M):
            tmp = 0
            for j in range(ks[i][0]):
                if bit[ks[i][j + 1] - 1] == 1:
                    tmp += 1
            if tmp % 2 != p[i]:
                onF = False
                break
        if onF:
            ans += 1
        return
    for i in range(2):
        bit[cnt] = i
        dfs(cnt + 1)


N, M = map(int, input().split())
ks = [list(map(int, input().split())) for _ in range(M)]
p = list(map(int, input().split()))
bit = [0] * N
ans = 0
dfs(0)
print(ans)

Measured memory_bytes: 3064
using System;

class Program
{
    static void Main(string[] args)
    {
        string[] line = Console.ReadLine().Split(null);

        int Takahashi = int.Parse(line[0]);
        int Aoki = int.Parse(line[1]);
        int conter = int.Parse(line[2]);

        for (int i = 0; i < conter; i++){

            if (i % 2 == 0)
            {
                EatCookie(ref Takahashi, ref Aoki);
            }
            else
            {
                EatCookie(ref Aoki, ref Takahashi);
            }

        }

        Console.WriteLine("{0} {1}", Takahashi, Aoki);
        Console.ReadKey();
    }

    private static void EatCookie(ref int myCookie, ref int opponentCookie)
    {
        //青木
        if (myCookie % 2 != 0)
        {
            myCookie--;
        }

        opponentCookie += myCookie / 2;
        myCookie -= myCookie / 2;
    }
}

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

int main() {
    int a,b;
    cin >> a >> b;
    if(a <= 5){
        cout << 0 << endl;
    }else if(a <= 12){
        cout << b/2 << endl;
    }else{
        cout << b << endl;
    }
}

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

using namespace std;
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define RFOR(i, a, b) for (int i = (b)-1; i >= (a); i--)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep1(i, n) for (int i = 1; i < (n); i++)
#define rrep(i, n) for (int i = (n)-1; i >= 0; i--)
#define all(i) (i).begin(), (i).end()
#define rall(i) (i).begin(), (i).end(), greater<int>()
#define int long long
#define elif else if
#define eb emplace_back
#define pb push_back
#define mp make_pair
#define fst first
#define sec second
#define mod 1000000007
#define INF 10e10
template <typename T>

void print(T x)
{
	std::cout << x << " ";
}
template <typename T>

void println(T x)
{
	std::cout << x << "\n";
}

signed main(void) {
	int a, b;
	cin >> a >> b;
	rep(i, max(a, b)) {
		cout << min(a,b);
	}
	
}

Measured memory_bytes: 256
X, K, D = map(int,input().split())
absX = abs(X)
t = abs(X // D)
remain_K = K - t
l = X % D
if remain_K < 0:
    a = abs(X - (K * D))
    b = abs(X + (K * D))
    if a < b:
        ans = a
    else:
        ans = b
else:
    if remain_K % 2 == 0:
        a = abs(l - (D * 2))
        b = abs(l + (D * 2))
        if a < b and a < l:
            ans = a
        elif a > b and b < l:
            ans = b
        else:
            ans = l
    else:
        a = abs(l - D)
        b = abs(l + D)
        if a < b:
            ans = a
        else:
            ans = b
print(ans)

Measured memory_bytes: 9124
s = int(input())

lis = []

flag = True
while flag:
    lis.append(s)
    if s%2==0:
        s /= 2
    else:
        s = s*3 + 1
    s = int(s)

    if s in lis:
        print(len(lis)+1)
        flag = False

Measured memory_bytes: 2940
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
using P = pair<int,int>;
const int MOD = 1000000007;

int main() {
    int n,m,k,ans=0;
    cin>>n>>m;
    vector<int> p(m),l(m);
    vector<vector<int>> s(m);
    rep(i,m) {
        cin>>k;
        rep(j,k) {
            int temp;
            cin>>temp;
            temp--;
            s[i].push_back(temp);
        }
    }
    rep(i,m) cin>>p[i];
    for (int bit=0; bit<(1<<n); bit++) {
        bool ok=true;
        rep(i,m) {
            int cnt=0;
            for (auto v:s[i]) {
                if (bit&(1<<v)) cnt++; 
            }
            if (cnt%2!=p[i]) ok=false;
        }
        if (ok) ans++;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define FasterIO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
typedef unsigned long long ull;
typedef long long ll;
typedef double db;

#define mem(a,x) memset(a,x,sizeof(a))
#define pb push_back
#define ff first
#define ss second
#define mk make_pair
#define pi pair<int,int>
#define vi vector<int>
#define pL pair<ll,ll>
#define vL vector<ll>
#define vp vector<pi>
#define vpL vector<pL>

const int MX=2000000;
const int inf=1e9;
const ll mod=1000000007;
const double eps=0.0000000001;

int n, cnt;
void dfs(int lvl, string s, int ch)
{
    if(lvl==n)
    {
        cnt++;
        cout<<s<<endl;
        return;
    }
    string s1=s;
    for(int i=0; i<=ch; i++)
    {
        s1+=('a'+i);
        dfs(lvl+1, s1, ch+(i==ch));
        s1.pop_back();
    }
}
int main()
{
    FasterIO;
    cin>>n;
    dfs(1, "a", 1);
    return 0;
}


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

int main() {
	long long a, b;
	cin >> a >> b;
	long long n = __gcd(a, b);

    vector<long long> factor;
	for (long long i = 1; i * i <= n; i++) {
		if (n % i == 0) {
            factor.push_back(i);
            if (i * i != n) {
                factor.push_back(n / i);
            }
		}
	}
	sort(factor.begin(), factor.end());
    int len = factor.size();
    vector<int> used(len, 0);
    int ans = 0;

    for (int i = 0; i < len; i++) {
    	if (used[i]) continue;
    	if (factor[i] == 1) ans++;
    	else {
    		ans++;
    		for (int j = i + 1; j < len; j++) {
    			if (factor[j] % factor[i] == 0)
    				used[j] = 1;
    		}
    	} 
    }	
    cout << ans << "\n";	
	return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
template<class T> struct rge { T b, e; };
template<class T> rge<T> range(T i, T j) { return rge<T>{i, j}; }
struct debug {
#ifdef LOCAL
	~debug(){cerr<<endl;}
	template<class T> debug& operator<<(T x){cerr<<boolalpha<<x; return *this;}
	template<class B, class C> debug& operator<<(pair<B, C> x){return *this<<"("<<x.first<<", "<<x.second<<")";}
	template<class T> debug& operator<<(rge<T> x){*this<<"[";for(auto it=x.b;it!=x.e;it++){*this<<", "+2*(it==x.b)<<*it;}return *this<<"]";}
	template<class T> debug& operator<<(vector<T> x){ return *this<<range(x.begin(),x.end());}
#else
	template<class T> debug& operator <<(const T&){return *this;}
#endif
};
#define nav(...) << "[ " << #__VA_ARGS__ ": " << (__VA_ARGS__) << " ] "
using ll = long long;
#define int long long
const int BITS = 32;

struct P {
    int x, y;
};

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

    /*  all points must have same parity of manhattan dist 
     * 
     * 
     *  to get to point (x, y):
     *          
     * 
     *          m = L + R + U + D (m <= 40)
     *
     */
    int n;
    cin >> n;
    vector<P> a(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i].x >> a[i].y;
    }
    
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            if(((a[i].x+a[i].y)%2+2)%2 != ((a[j].x+a[j].y)%2+2)%2) {
                cout << "-1\n";
                exit(0);
            }
        }
    }
    
    bool even = (a[0].x + a[0].y) % 2 == 0;
    
    vector<int> d(BITS);
    for(int i = 0; i < BITS; i++) {
        d[i] = 1LL<<i;
    }
    if(even) {
        d.push_back(1);
    }
    int m = d.size();
    cout << m << '\n';
    for(int i = 0; i < m; i++) {
        cout << d[i] << " \n"[i==m-1];
    }
    
    for(int i = 0; i < n; i++) {
        P p = a[i];
        if(even) {
            p.x--;
        }
        string ans;
        int x = p.x, y = p.y;
        for(int b = BITS-1; b >= 0; b--) {
            int take = 1LL<<b;
            int need = (1LL<<b)-1;
            debug() nav(x) nav(y) nav(need);
            if(abs(x-take) + abs(y) <= need) {
                ans.push_back('R');
                x -= take;
            } else if(abs(x+take) + abs(y) <= need) {
                ans.push_back('L');
                x += take;
            } else if(abs(x) + abs(y-take) <= need) {
                ans.push_back('U');
                y -= take;
            } else if(abs(x) + abs(y+take) <= need) {
                ans.push_back('D');
                y += take;
            }
            else {
                assert(false); // :( so sad
            }
        }
        reverse(ans.begin(), ans.end());
        if(even) {
            ans.push_back('R');
        }
        cout << ans << '\n';
    }
    
}


Measured memory_bytes: 256
from collections import defaultdict
inpl = lambda: list(map(int,input().split()))

P_MAX = 32000
P = []
for i in range(2,P_MAX):
    sieve = 1
    for p in P:
        if p*p > i:
            break
        elif i % p == 0:
            sieve = 0
            break
    if sieve == 0:
        continue
    else:
        P.append(i)

def factorize(n):
    primes = []
    powers = []
    for p in P:
        if p * p > n:
            break
        elif n % p == 0:
            k = 0
            while n % p == 0:
                n //= p
                k += 1
            primes.append(p)
            powers.append(k)
    if n > 1:
        primes.append(n)
        powers.append(1)
    return primes, powers

N = int(input())
A = inpl()
infty = 100
lowest_powers = defaultdict(lambda: [infty,infty])
bottle_necks = defaultdict(lambda: -1)
all_factors = set()
for n in range(N):
    primes, powers = factorize(A[n])
    prev_primes = list(bottle_necks.keys())
    done = defaultdict(int)
    for i in range(len(primes)):
        done[primes[i]] = 1
        if not primes[i] in all_factors:
            all_factors.add(primes[i])
            if n == 1:
                lowest_powers[primes[i]] = [0,powers[i]]
                bottle_necks[primes[i]] = 0
            elif n == 0:
                lowest_powers[primes[i]] = [powers[i],infty]
                bottle_necks[primes[i]] = 0
        lowest = lowest_powers[primes[i]]
        if powers[i] == lowest[0]:
            lowest[1] = lowest[0]
            bottle_necks[primes[i]] = -1
        elif powers[i] < lowest[0]:
            lowest[1] = lowest[0]
            lowest[0] = powers[i]
            bottle_necks[primes[i]] = n
        elif powers[i] < lowest[1]:
            lowest[1] = powers[i]
    for p in all_factors:
        if done[p] == 0:
            lowest = lowest_powers[p]
            if lowest[0] == 0:
                lowest[1] = 0
                bottle_necks[p] = -1
            else:
                lowest[1] = lowest[0]
                lowest[0] = 0
                bottle_necks[p] = n

bnl = defaultdict(lambda: [])
for p,n in bottle_necks.items():
    if n >= 0:
        lowest = lowest_powers[p]
        bnl[n].append([p,lowest[1]-lowest[0]])
best_n = -1
largest_f = 1
for n in range(N):
    f = 1
    for pp in bnl[n]:
        f *= pp[0]**pp[1]
    if f > largest_f:
        largest_f = f
        best_n = n

ans = 1
bn = bnl[best_n]
pn = [ s[0] for s in bn]
for p in all_factors:
    if p in pn:
        ans *= p**lowest_powers[p][1]
    else:
        ans *= p**lowest_powers[p][0]
print(ans)

Measured memory_bytes: 78880
#include "bits/stdc++.h"
#include <cmath>
#include <iomanip>
using namespace std;

#define f first
#define s second

#define pb push_back
#define pp pop_back
#define mp make_pair

#define sz(x) (int)x.size()
#define sqr(x) ((x) * 1ll * (x))
#define all(x) x.begin(), x.end()
#define clr(a,v) memset(a, v, sizeof(a))

#define rep(i, l, r) for (int i = (l); i <= (r); i++)
#define per(i, l, r) for (int i = (l); i >= (r); i--)
#define reflex ios_base::sync_with_stdio(false)

#define nl '\n'
#define ioi exit(0);

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int N= (int)2e5 + 7;
const int inf = (int)1e9 + 7;
const int mod = (int)1e9 + 7;
//const int mod = 1000000007;
const ll linf = (ll)1e18 + 7;

const int dx[] = {-1, 0, 1, 0, 1, -1, -1, 1};
const int dy[] = {0, 1, 0, -1, 1, -1, 1, -1};
const int kx[] = {-1,1,2,2,1,-1,-2,-2};
const int ky[] = {2,2,1,-1,-2,-2,-1,1};

vector< pair<int,int> > v;
int main(){
	int n; cin>> n;
	if(n %2 == 0){
		cout<< setprecision(20)<< ((n/2.0)*1.0/n);
	}
	else{
		cout<< setprecision(20)<< ((n/2 + 1)*1.0/n);
	}
	return 0;
}


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

typedef long long ll;
typedef long double ld;

#define mp 				make_pair
#define ff 				first
#define ss 				second
#define sz(x) 			(int)(x).size()
#define all(x) 			begin(x), end(x)
#define rall(x) 		(x).rbegin(), (x).rend() 
#define rsz 			resize
#define ins 			insert 
#define ft 				front() 
#define bk 				back()
#define pf 				push_front 
#define pb 				push_back
#define eb 				emplace_back 
#define lb 				lower_bound 
#define ub 				upper_bound 
#define w(x)			int x;cin>>x;while(x--)
#define pqmax			priority_queue<int>
#define pqmin			priority_queue<int,vector<int>,greater<int>>

#define rep(i,a,b) 		for (int i = (a); i < (b); ++i)
#define per(i,a,b) 		for (int i = (b)-1; i >= (a); --i)
#define trav(a,x) 		for (auto a: x)

#define setbits(x)  	__builtin_popcountll(x)
#define zerobits(x)		__builtin_ctzll(x)

const ll mod = 1e9+7; // 998244353;
const ll inf = 1e18; 
const ld pie = acos((ld)-1);

void solve(){

	int n;
	cin>>n;
	if(n%1000==0){
		cout<<0<<'\n';
	}else{
		int x=1000;
		while(x<n){
			x+=1000;
		}
		cout<<x-n<<'\n';
	}

	return;

}

int main(){

	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	solve();
	/*STUFF TO LOOK:	
	1. Special cases/corner cases(n==0||n==1)
	2. Variables in for loops
	3. Input ranges
	*/

	return 0;
}


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


using namespace std;

int main(){
  int a,b,c;
  cin>>a>>b>>c;
  int k;
  cin>>k;
  int d;
  d=a;
  if(d<b)d=b;
  if(d<c)d=c;
  cout<<int(pow(2,k))*d-d+a+b+c;
  // cout<<(int)pow(max([a,b,c]),k)-max([a,b,c])+a+b+c;
  return 0;
}


Measured memory_bytes: 256
N=int(input())
r=[0,0,0,0]
for i in range(N):
  a=input()
  if a=="AC":
    r[0]+=1
  if a=="WA":
    r[1]+=1
  if a=="TLE":
    r[2]+=1
  if a=="RE":
    r[3]+=1
print("AC x",r[0])
print("WA x",r[1])
print("TLE x",r[2])
print("RE x",r[3])

Measured memory_bytes: 9244
import java.util.*;


public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int N = scan.nextInt();
		int[] A = new int[100];
		int[] B = new int[100];
		int[] C = new int[100];

		for(int i=1; i<=N; i++) {
			A[i] = scan.nextInt();
		}
		for(int i=1; i<=N; i++) {
			B[i] = scan.nextInt();
		}		
		for(int i =1; i<=N-1; i++) {
			C[i] = scan.nextInt();
		}		
		
		int ans=0;
		
		for (int i=1;i<=N;i++) {
			ans += B[A[i]];
			if(A[i] == A[i-1]+1) {
				ans += C[A[i-1]];							
			}
		}
		
		System.out.println(ans);
	}
}

Measured memory_bytes: 21972