akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
const int N=200001;
int n,d[N],maxn1=-1,maxid1=-1,maxn2=-1,maxid2=-1;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&d[i]);
		if(d[i]>maxn1)
		{
			maxn2=maxn1;
			maxid2=maxid1;
			maxn1=d[i];
			maxid1=i;
		}
		if(d[i]<maxn1 && d[i]>maxn2)
		{
			maxn2=d[i];
			maxid2=i;
		}
		if(d[i]==maxn1 && i!=maxid1)
		{
			maxn2=d[i];
			maxid2=i;
		}
	}
	for(int i=1;i<=n;i++)
	{
		if(i!=maxid1)
			printf("%d\n",maxn1);
		else
			printf("%d\n",maxn2);
	}
	return 0;
}

Measured memory_bytes: 2432
sx, sy, tx, ty = list(map(int, input().split()))

ans = "L"

dx = tx - sx
dy = ty - sy

ans += "U" * (dy + 1) + "R" * (dx + 1) + "D"
ans += "L" * dx + "D" * dy
ans += "R" * dx + "U" * dy
ans += "R" + "D" * (dy+1) + "L" * (dx+1) + "U"
print(ans)


Measured memory_bytes: 38256
#define _GLIBCXX_DEBUG

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

constexpr ll INF = 1e16;

#define rep(i, N) for(ll i=0; i<N; ++i)

ll max(ll a, ll b) {return a < b ? b : a; }
ll min(ll a, ll b) {return a > b ? b : a; }
double maxf(double a, double b) { return a < b ? b : a; }

int main() {
  char n;
  cin>>n;

  n++;

  cout<<n<<endl;

  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <complex>
#include <utility>
#include <vector>
#include <string>
#include <queue>
#include <tuple>
#include <cmath>
#include <bitset>
#include <cctype>
#include <set>
#include <map>
#include <numeric>
#include <functional>
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(ll i=ll(a);i<ll(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define PRINT(V) cout << V << "\n"
#define SORT(V) sort((V).begin(),(V).end())
#define RSORT(V) sort((V).rbegin(), (V).rend())
using namespace std;
using ll = long long;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
inline void Yes(bool condition){ if(condition) PRINT("Yes"); else PRINT("No"); }
template<class itr> void cins(itr first,itr last){
    for (auto i = first;i != last;i++){
        cin >> (*i);
    }
}
template<class itr> void array_output(itr start,itr goal){
    string ans = "",k = " ";
    for (auto i = start;i != goal;i++) ans += to_string(*i)+k;
    if (!ans.empty()) ans.pop_back();
    PRINT(ans);
}
ll gcd(ll a, ll b) {
    return a ? gcd(b%a,a) : b;
}
const ll INF = 1e18;
const ll MOD = 1000000007;
typedef pair<ll,ll> P;
const ll MAX = 20000;
constexpr ll nx[8] = {1,0,-1,0,-1,-1,1,1};
constexpr ll ny[8] = {0,1,0,-1,-1,1,-1,1};
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll x;
    cin >> x;
    ll n = x/11;
    if (x%11 == 0) PRINT(2*n);
    else if (x%11 <= 6) PRINT(2*n+1);
    else PRINT(2*n+2);
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define vi vector<int>
#define pi pair<int,int>
#define vs vector<string>
#define ll long long
#define ull unsigned long long
#define fastio ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define ld long double
#define mod 1000000007
using namespace std;
using namespace __gnu_pbds;

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

int main()
{
   string s;
   cin>>s;
   int ans = 0;
   for(int i = 0; i<s.length()/2; ++i)
   {
        if(s[i] != s[int(s.length()) - i-1]) ans += 1;
   }
   cout<<ans<<endl;
}

Measured memory_bytes: 256
#![allow(
    non_snake_case,
    unused_variables,
    unused_assignments,
    unused_mut,
    unused_imports,
    dead_code
)]
//use proconio::fastout;
use proconio::input;
use proconio::marker::*;
use std::cmp::*;
use std::collections::*;
//use std::collections::VecDeque;

fn main() {
    input! {
       N:usize,
       XYP:[(i64,i64,i64);N]
    }
    // 各鉄道パターンについて、集落からの距離
    let inf = std::i64::MAX;
    let mut dtate = vec![vec![0i64; N]; 2i64.pow(N as u32) as usize];
    let mut dyoko = vec![vec![0i64; N]; 2i64.pow(N as u32) as usize];
    for i in 0..dtate.len() {
        for j in 0..N {
            dtate[i][j] = XYP[j].0.abs();
            dyoko[i][j] = XYP[j].1.abs();
        }
        //println!("i={},l={}", i, format!("{:0>15b}", i));
        let l: Vec<bool> = format!("{:0>15b}", i).chars().map(|c| c == '1').collect();
        let sum = l.iter().fold(0, |sum, &a| sum + if a { 1 } else { 0 });

        for j in 0..N {
            for k in 0..N {
                //println!("L[k]={}", l[14 - k]);
                if l[14 - k] {
                    dtate[i][j] = min(dtate[i][j], (XYP[j].0 - XYP[k].0).abs());
                    dyoko[i][j] = min(dyoko[i][j], (XYP[j].1 - XYP[k].1).abs());
                }
            }
            dtate[i][j] *= XYP[j].2;
            dyoko[i][j] *= XYP[j].2;
        }
    }
    //println!("tate:{:?}", dtate);
    //println!("yoko:{:?}", dyoko);
    //let mut m = vec![vec![0i64; N]; 3i64.pow(N as u32) as usize];
    let mut ans = vec![std::i64::MAX; N + 1];
    for i in 0..(3usize.pow(N as u32)) {
        // i の j bit目が0なら、j番目の町に路線なし、1なら東西線、2なら南北線とする。
        // iから、dtate[x]とdyoko[y]のxとyを求める。
        let mut x = 0;
        let mut y = 0;
        let mut ii = i;
        let mut n = N;
        for j in 0..N {
            let tmp = ii % 3;
            // 順番がおかしくなるけど、全部合計するので気にしない。
            x *= 2;
            y *= 2;
            match tmp {
                1 => x += 1,
                2 => y += 1,
                _ => n -= 1,
            }
            ii /= 3;
        }
        let mut t = 0;
        for j in 0..N {
            t += min(dtate[x][j], dyoko[y][j]);
        }
        ans[n] = min(ans[n], t);
    }
    for i in 0..=N {
        println!("{}", ans[i]);
    }
}


Measured memory_bytes: 11768
H, W = map(int, input().split())
if H == 1 or W == 1:
  print('1')
elif W%2 == 1:
  if H%2 == 0:
    print(int((W+1)/2 * H/2 + H/2*(W-1)/2))
  else:
    print(int((W+1)/2 * (H+1)/2 + (H-1)/2*(W-1)/2))
else:
  if H%2 == 0:
    print(int(W/2 * H/2 + H/2*W/2))
  else:
    print(int(W/2 * (H+1)/2 + (H-1)/2*W/2))


Measured memory_bytes: 3064
#include<stdio.h>
int main(){
	char p[102] = {};
	int X, N;
	scanf("%d %d", &X, &N);
	if(N == 0)
		printf("%d", X);
	else if(N == 100){
		if(X <= 50)
			printf("0");
		else
			printf("101");
	}
	else{
		for(int i = 1; i <= N; i++){
			int IN;
			scanf("%d", &IN);
			p[IN] = 1;
		}
		int dist = 0;
		while(p[X+dist] && p[X-dist])
			dist++;
		if(p[X-dist] == 0)
			printf("%d", X - dist);
		else
			printf("%d", X + dist);
	}
	return 0;
}

Measured memory_bytes: 1736
#!python3.4.3

a = int(input())
b = int(input())

if a == 1:
    if b == 2:
        print(3)
    elif b == 3:
        print(2)
elif a == 2:
    if b == 1:
        print(3)
    elif b == 3:
        print(1)
elif a == 3:
    if b == 1:
        print(2)
    elif b == 2:
        print(1)

Measured memory_bytes: 3060
#include <malloc.h>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

//ABC171D
//ABC171C
int main(void) {
  long long n, k, i, cou=0, tmp;
  scanf("%lld", &n);
  long long a[100];

  while(n>=1){
    a[cou]=n%26;
    if(a[cou]==0) a[cou]=26;
    cou++;
    n=(n-1)/26;
  }
  for(i=0; i<cou; i++){
    printf("%c", a[cou-i-1]+96);
  }
}


Measured memory_bytes: 1736
A,B = map(int, input().split())
ans = 0
for i in range(A, B+1):
	s = i%10
	t = int(i/10000)
	u = int(i/10)%10
	v = int(i/1000)%10
	if (s==t)&(u==v):
		ans += 1
print(ans)

Measured memory_bytes: 3188
/*我是萌新*/
#include<iostream>
#include<cmath>
#include<string>
#include<algorithm>
#include <iomanip> 
using namespace std;
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    string s;
    while (cin >> s)
    {
        int ans = s.length();
        for (int i = 0; i < ans; i++)
            cout << "x";
        cout << '\n';
    }
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#define start_routine() int begtime = clock();
#define end_routine() int endtime = clock(); cerr << endl << "Time elapsed: " << (endtime - begtime)*1000/CLOCKS_PER_SEC << " ms"; return 0
#define speed() cin.tie(0), cout.tie(0), ios_base::sync_with_stdio(false)
// #define exit(a, b) return cout << a, b;

#define loop(i,a,b) for(ll i=a;i<b;i++)
#define all(v) v.begin(), v.end() 

#define print(stuff) cout << stuff << endl
#define printc(stuff) for(auto x: stuff) cout << x << " "; cout << endl;
#define printPrec(stuff) cout << fixed << setprecision(15) << stuff << endl;
#define debug(stuff) cout << #stuff << ": " << stuff <<endl
#define debugc(stuff) cout << #stuff << ": "; for(auto x: stuff) cout << x << " "; cout << endl;
#define len length
#define ret0 return 0
#define ret return 

#define ll long long
#define ld long double
#define fi first
#define endl '\n'
#define se second
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define fill(ar, x) memset(ar, x, sizeof ar)

#define vl vector<ll> 
#define sl set<ll>
#define pll pair<ll, ll>
#define mll map<ll, ll> 
#define pq priority_queue<ll>

// typedef tree<ll,null_type,less<ll>,rb_tree_tag,
// tree_order_statistics_node_update> indexed_set;

#define inf (long long int) 1e18
#define eps 0.000001
#define mod 1000000007
#define mod1 998244353
#define MAXN (ll)1e5+5

void solve(){
    ll n;
    cin>>n;
    ll a[n+1], b[n], sum=0;
    loop(i,0,n+1) {
        cin>>a[i];
        sum+=a[i];
    }
    loop(i,0,n) cin>>b[i];

    loop(i,0,n){
        if(a[i] >= b[i]){
            a[i] = a[i]-b[i];
        }
        else {
            if(a[i] < b[i]){
                b[i] = b[i]-a[i];
                a[i]=0;
                if(a[i+1] >= b[i]){
                    a[i+1] = a[i+1]-b[i];
                }
                else if(a[i+1] < b[i]){
                    a[i+1] = 0;
                }
            }
        }
    }

    ll sumf=0;
    loop(i,0,n+1){
        sumf+=a[i];
    }
    print(sum-sumf);

}

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



Measured memory_bytes: 1792
#include<stdio.h>

int main(void){
 int a,b,temp;
 while(1){
  scanf("%d", &a);
  scanf("%d", &b);
  if((a == 0) && (b==0)){
   break;
  }
  if(a > b){
   temp = b;
   b = a;
   a = temp;
  }
  printf("%d %d\n", a, b);
 }
 return 0;
}

Measured memory_bytes: 600
N, T = map(int, input().split())
A = [int(x) for x in input().split()]

minA = A[0]
maxG = 0
ans = 0
for i in range(1,N) :
    if A[i] < minA :
        minA = A[i]
    else :
        if A[i] - minA > maxG :
            maxG = A[i] - minA
            ans = 1
        elif A[i] - minA == maxG :
            ans += 1

print(ans)


Measured memory_bytes: 62832
import java.util.*;

public class Main{
    static int n;
    static int m;
    static int[][] l;
    static int[] k = new int[10];
    static int[] p;
    static int count = 0;
    static int[] st = new int[10];

    static void check(){
        /*for(int j = 0; j < n; j++){
            System.out.print(st[j] + " ");
        }
        System.out.println();*/
        int sum;
        for(int i = 0; i < m; i++){
            sum = 0;
            for(int j = 0; j < k[i]; j++){
                sum += st[l[i][j] - 1];
                //System.out.println(l[i][j]);
                //System.out.println("sum +=" + " " + st[l[i][j] - 1] + ", " + "sum = " + sum);
            }
            if(sum % 2 != p[i]) return;
        }
        //System.out.println("!");
        count++;
    }

    static void calc(int i, int v){
        if(i == n - 1){
            st[i] = v;
            /*for(int j = 0; j < n; j++){
                System.out.print(st[j] + " ");
            }
            System.out.println();*/
            check();
            //System.out.println("Check");
        }else{
            st[i] = v;
            /*for(int j = 0; j < n; j++){
                System.out.print(st[j] + " ");
            }
            System.out.println();*/
            calc(i + 1, 0);
            calc(i + 1, 1);
        }
    }

    public static void main(String args[]){

        // スキャナーの宣言
        Scanner sc = new Scanner(System.in);
        // 整数の入力
		n = sc.nextInt();
        m = sc.nextInt();
        l = new int[10][10];

        for(int i = 0; i < m; i++){
            k[i] = sc.nextInt();
            for(int j = 0; j < k[i]; j++){
                l[i][j] = sc.nextInt();
            }
        }

        p = new int[m];

        for(int i = 0; i < m; i++){
            p[i] = sc.nextInt();
        }

        calc(0, 0);
        calc(0, 1);

        // 出力
        System.out.println(count);

    }

}

Measured memory_bytes: 23508
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define all(x) (x).begin(),(x).end()
template <class T> inline bool chmin(T &a, T b) {if (a > b){a = b;return true;}return false;}
template <class T> inline bool chmax(T &a, T b) {if (a < b){a = b;return true;}return false;}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n;cin>>n;
    vector<ll> A(n);
    map<ll, ll> ma;
    ll ans = 0;
    rep(i,n) {
        ll t;cin>>t;
        ma[t]++;
        ans += t;
    }
    ll q;cin>>q;
    rep(i,q){
        ll b,c;cin>>b>>c;
        ans = ans - b*ma[b] + c*ma[b];
        cout<< ans <<endl;
        ma[c] += ma[b];
        ma[b] = 0;
    }
    return 0;

}

Measured memory_bytes: 9956
#include<iostream>
#include<string>
#include<cmath>
#include<algorithm>
#include<vector>
#include<stdio.h>
using namespace std;
typedef long long ll;



void solve(){
	
	int  N,K;
	int *H;
	cin >> N>>K;
	H = new int[N];
	int ans = 0;
	for (int i = 0;i < N;i++) {
		cin >> H[i];
		if (H[i] >= K)ans++;
	}
	cout << ans << endl;
	string str;
	cin >> str;
}


int main() {
	solve();

}

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

template<class Abel> struct UnionFind {
    vector<int> par;
    vector<int> rank;
    vector<Abel> diff_weight;

    UnionFind(int n, Abel SUM_UNITY) {
        init(n, SUM_UNITY);
    }

    void init(int n, Abel SUM_UNITY) {
        par.resize(n+1); rank.resize(n+1); diff_weight.resize(n+1);
        for (int i = 0; i <= n; ++i) par[i] = i, rank[i] = 0, diff_weight[i] = SUM_UNITY;
    }

    int root(int x) {
        if (par[x] == x) {
            return x;
        }
        else {
            int r = root(par[x]);
            diff_weight[x] += diff_weight[par[x]];
            return par[x] = r;
        }
    }

    Abel weight(int x) {
        root(x);
        return diff_weight[x];
    }

    bool issame(int x, int y) {
        return root(x) == root(y);
    }

    bool merge(int x, int y, Abel w) {
        w += weight(x); w -= weight(y);
        x = root(x); y = root(y);
        if (x == y) return false;
        if (rank[x] < rank[y]) swap(x, y), w = -w;
        if (rank[x] == rank[y]) ++rank[x];
        par[y] = x;
        diff_weight[y] = w;
        return true;
    }

    Abel diff(int x, int y) {
        return weight(y) - weight(x);
    }
};

int main(){
    int N,M;
    cin >> N >> M;
    UnionFind<int> uf(N,0);
    int i;
    int L,R,D;
    for(i=0; i<M; i++){
        cin >> L >> R >> D;
        if(uf.issame(L,R)){
            if(uf.diff(L,R)!=D){
                break;
            }
        }else{
            uf.merge(L,R,D);
        }
    }
    if(i==M){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
    system("pause");
    return 0;
}

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

for i in range(1, N):
    ABCs[i][0] += max(ABCs[i - 1][1], ABCs[i - 1][2])
    ABCs[i][1] += max(ABCs[i - 1][2], ABCs[i - 1][0])
    ABCs[i][2] += max(ABCs[i - 1][0], ABCs[i - 1][1])

print(max(ABCs[N - 1]))

Measured memory_bytes: 63064
#https://atcoder.jp/contests/abc136/tasks/abc136_c

n = int(input())
h = [int(i) for i in input().split()]

a = []
flag = 'Yes'
for i in reversed(range(n - 1)):
    if h[i+1] - h[i] < 0 and h[i+1] - h[i] > -2:
        h[i] -= 1
    elif h[i+1] - h[i] < -1:
        flag = 'No'
print(flag)

Measured memory_bytes: 14396
#include<stdio.h>
#include<math.h>
int main(){
  int p[101],m[101][101];
  int a,b,c,i,l,j,k;
  scanf("%d",&a);
  for(i=1;i<=a;i++){
    scanf("%d %d",&p[i-1],&p[i]);
  }
  
  for(i=1;i<=a;i++){m[i][i]=0;}
  
  for(l=2;l<=a;l++){
    for(i=1;i<=a-l+1;i++){
      j=i+l-1;
      m[i][j]=100000000;
      for(k=i+1;k<=j;k++){
	if(m[i][j]>m[i][k-1]+m[k][j]+p[i-1]*p[k-1]*p[j]){
	  m[i][j]=m[i][k-1]+m[k][j]+p[i-1]*p[k-1]*p[j];
	}
      }
    }
  }
  printf("%d\n",m[1][a]);
  return 0;
}




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

int main(){
    int sx, sy, tx, ty;
    cin >> sx >> sy >> tx >> ty;
    for(int i=0; i<tx-sx; i++){
      cout << "R";
    }
    for(int i=0; i<ty-sy; i++){
      cout << "U";
    }
    for(int i=0; i<tx-sx; i++){
      cout << "L";
    }
    for(int i=0; i<ty-sy; i++){
      cout << "D";
    }
    cout << "D";
    for(int i=0; i<tx-sx+1; i++){
      cout << "R";
    }
    for(int i=0; i<ty-sy+1; i++){
      cout << "U";
    }
    cout << "L";
    cout << "U";
    for(int i=0; i<tx-sx+1; i++){
      cout << "L";
    }
    for(int i=0; i<ty-sy+1; i++){
      cout << "D";
    }
    cout << "R"<<endl;
    return 0;
}

Measured memory_bytes: 256
n, x, y = map(int, input().split())
ans = [0]*(n-1)
for i in range(1, n):
    for j in range(i+1, n+1):
        ans[min(j-i, abs(i-x)+abs(j-y)+1)-1] += 1

for i in ans:
    print(i)

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

using namespace std;
using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;

#define INF LONG_MAX
#define MOD 1000000007
#define rng(a) a.begin(),a.end()
#define rrng(a) a.end(),a.begin()
#define endl "\n"

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

  int N;
  cin>>N;
  vector<ll>A(N);
  for(int i=0;i<N;i++)cin>>A[i];
  int r=0;
  ll S=0,X=0,ans=0;
  for(int l=0;l<N;l++){
    while(r<N&&(X^A[r])==(S+A[r]))X^=A[r],S+=A[r],r++;
    ans+=r-l;
    if(r==l)r++;
    else S-=A[l],X^=A[l];
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 1792
import java.util.Scanner;

public class Main {

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

		int a=Integer.parseInt(sc.next());
		int b=Integer.parseInt(sc.next());
		int c=Integer.parseInt(sc.next());

		sc.close();

		if(a<=b){
			if(a<=c&&c<=b){
				System.out.println("Yes");
			}else{
				System.out.println("No");
			}
		}else if(b<a){
			if(b<=c&&c<=a){
				System.out.println("Yes");
			}else{
				System.out.println("No");
			}
		}
	}

}

Measured memory_bytes: 21844
#include<stdio.h>
#include<string.h>
#define N 105
#define V 100010
#define ll long long 
ll minn(ll x,ll int y)
{
	return  x < y ? x : y;
}
ll dp[V];
ll w[N];
int v[N];
int n;
ll lim;
ll ans = 0;
int main()
{
	for (int i = 1; i <= V - 1; i++)
		dp[i] = 1e12;
	dp[0] = 0;
	scanf("%d %lld", &n, &lim);
	for (int i = 1; i <= n; i++)
		scanf("%lld %d", &w[i], &v[i]);
	for (int j = 1; j <= n; j++)
		for (int i = V - 1; i >= v[j]; i--)
			dp[i] = minn(dp[i], dp[i - v[j]] + w[j]);
	for (int i = 1; i <=V-1; i++)
	{
		if (dp[i] != 1e12 && dp[i] <=lim)
			ans = i;
	}
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 896
# -*- coding: utf-8 -*-
A,B=map(int, raw_input().split())

K=1000

L=[0 for i in range(K+1)]

for k in range(K,-1,-1):
	cnt=0
	sho=(B+1)/(2**(k+1))	
	amari=(B+1)%(2**(k+1))	
	cnt=sho*(2**k)+max(0,amari-2**k)	#cnt: k桁目の１の個数

	L[k]+=cnt

for k in range(K,-1,-1):
	cnt=0
	sho=A/(2**(k+1))	
	amari=A%(2**(k+1))	
	cnt=sho*(2**k)+max(0,amari-2**k)	#cnt: k桁目の１の個数

	L[k]-=cnt

ans=0
for i in range(K+1):
	ans+=2**i*(L[i]%2)

print ans


Measured memory_bytes: 32236
use proconio::{fastout, input};
use std::collections::HashMap;

#[fastout]
fn main() {
    input! {
        n: u32,
        m: u32,
        h: [u32;n],
        // com: [[u32;2];m]
        ab: [(usize, usize); m],
    }

    // println!("{:?}", ab);

    let mut v_peaks = vec![true; n as usize];

    for (a, b) in ab {
        if h[a - 1] >= h[b - 1] {
            v_peaks[b - 1] = false;
        }
        if h[b - 1] >= h[a - 1] {
            v_peaks[a - 1] = false;
        }
    }

    // // println!("{:?}", bad_peaks);

    println!("{}", v_peaks.iter().filter(|x| x == &&true).count());
}


Measured memory_bytes: 6176
import java.io.*;
import java.util.*;

public class Main{
    PrintWriter out = new PrintWriter(System.out);
    int ans = 1, H, W;
    char[][] maze;
    int[] dr = new int[]{1,0,-1,0}, dc = new int[]{0,1,0,-1};
    static public void main(String[] args) throws Exception{
        //BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        //String[] buf = reader.readLine().split(" ")
        Main main = new Main();
//        main.solve();
        System.out.println(main.solve());
    }
    long solve(){
        Scanner sc = new Scanner(System.in);
        long a = sc.nextLong(), b = sc.nextLong();
        Set<Long> as = PrimeDivisors(a), bs = PrimeDivisors(b);
        int ans = 0;
        for(long s:as){
            if(bs.contains(s)) ans += 1;
        }
        return ans;
    }
    Set<Long> PrimeDivisors(long x){
        Set<Long> ans = new HashSet<>();
        ans.add(1L);
        for(long i=2;i*i<=x;i++){
            if(x%i!=0) continue;
            ans.add(i);
            while(x>=i&&x%i==0) x /= i;
        }
        ans.add(x);
        return ans;
    }

}



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

bool is_prime(int x){
    if(x==2)return true;
    if(x%2==0)return false;
    for (int i = 3; i < sqrt(x)+1; i+=2)
    {
        if(x%i==0)return false;
        /* code */
    }
    
    return true;
}

int main(){
    int x;

    cin >> x;

    while (true)
    {
        if(is_prime(x)){
            cout << x << endl;
            return 0;
        }
        x++;
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define pp pair<int,int>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep2(i,m,n) for(int (i)=(m);(i)<(n);(i)++)
#define ll long long
#define ld long double
#define all(a) (a).begin(),(a).end()
int main(){
  int a,b,x;
  cin>>a>>b>>x;
  if(a<=x&&x<=a+b) cout<<"YES"<<endl;
  else cout<<"NO"<<endl;
return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<utility>
#include<vector>
#include<queue>
#include<functional>
#include<map>
#include<set>
#include<cstring>
#include<string>
#include<stack>
#include<malloc.h>
#include<math.h>
using namespace std;
//#define int long long
typedef pair<int, int> pii;
typedef pair<int, char> pic;
typedef priority_queue<pii, vector<pii>, greater<pii> > RPQ;
#define mk make_pair
#define INF (1 << 30)
#define INFL (1ll << 60ll)
#define mod 1000000007

int N;
struct node{
    int left = -1, right = -1;
    int par = -1, sib = -1, deg = 0, dep = 0, hei = 0, typ = 0;
};
node no[100];
char name[3][100] = {"root", "internal node", "leaf"};

int dfs(int v, int d){
    no[v].dep = d;
    int h1 = -1, h2 = -1;
    if(no[v].left >= 0){
        h1 = dfs(no[v].left, d + 1);
    }
    if(no[v].right >= 0){
        h2 = dfs(no[v].right, d + 1);
    }
    return no[v].hei = max(h1, h2) + 1;
}

signed main(){
    cin >> N;
    for(int i = 0; i < N; i++){
        int a, b, c;
        cin >> a >> b >> c;
        no[a].left = b;
        no[a].right = c;
        no[b].par = a;
        no[c].par = a;
        no[b].sib = c;
        no[c].sib = b;
        no[a].deg = (int)(b >= 0) + (int)(c >= 0);
        if(b < 0 && c < 0)no[a].typ = 2;
        else no[a].typ = 1;
    }
    int root = -1;
    for(int i = 0; i < N; i++){
        if(no[i].par < 0){
            root = i;
            break;
        }
    }
    if(root < 0)return 1;
    no[root].typ = 0;
    dfs(root, 0);
    for(int i = 0; i < N; i++){
        node v = no[i];
        printf("node %d: parent = %d, sibling = %d, degree = %d, depth = %d, height = %d, %s\n", i, v.par, v.sib, v.deg, v.dep, v.hei, name[v.typ]);
    }

    return 0;
}

/*

*/


Measured memory_bytes: 3152
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

#define CIN_ONLY if(1)
struct cww{cww(){
    CIN_ONLY{
        ios::sync_with_stdio(false);cin.tie(0);
    }
}}star;
#define fin "\n"
#define FOR(i,bg,ed) for(int i=(bg);i<(ed);i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
#define pb push_back
#define DEBUG if(0)
#define REC(ret, ...) std::function<ret (__VA_ARGS__)>
template <typename T>inline bool chmin(T &l,T r)
{bool a=l>r;if(a)l=r;return a;}
template <typename T>inline bool chmax(T &l,T r)
{bool a=l<r;if(a)l=r;return a;}
template <typename T>
istream& operator>>(istream &is,vector<T> &v){
    for(auto &it:v)is>>it;
    return is;
}
int N,M,X,Y;
typedef vector<int> V;
typedef vector<V> VV;
VV G;
vector<string> op;
int val[1<<6];
int pack(vector<int> v){
    int res=0;
    REP(i,3){
        res<<=2;
        res+=v[i];
    }
    return res;
}
V unpack(int v){
    V res(3);
    REP(i,3){
        res[2-i]=v&3;
        v>>=2;
    }
    return res;
}
inline int f(int x,int y,int i){
    int a=(x>>i)&1;
    int b=(y>>i)&1;
    return a*2+b;
}
int minmax(int v,int p,int T,int turn){
    if(op[v]=="")T=0;
    else{
        int tr=X;
        if(op[v][4]=='Y')tr=Y;
        if(op[v][3]=='|')T=T|tr;
        if(op[v][3]=='^')T=T^tr;
        if(op[v][3]=='&')T=T&tr;
    }
    auto f=turn?[&](int &l,int r){chmax(l,r);}:[&](int &l,int r){chmin(l,r);};
    if(G[v].size()-(v!=0)==0)return T;
    int res=turn?0:(1<<16)-1;
    for(auto &u:G[v])
        if(p!=u){
            f(res,minmax(u,v,T,1-turn));
        }
    return res;
}
int main(){
    cin>>N>>M;
    G.assign(N,V());
    op.assign(N,"");
    FOR(i,1,N)cin>>op[i];
    
    REP(i,N-1){
        int u,v;
        cin>>u>>v;
        G[u].pb(v);
        G[v].pb(u);
    }
    V ord={1,2,3};
    do{
        X=0,Y=0;
        REP(i,3){
            X<<=2;X+=ord[i]>>1;
            Y<<=2;Y+=ord[i]&1;
        }
        val[pack(ord)]=minmax(0,0,0,1);
    }while(next_permutation(ALL(ord)));
    REP(q,M){
        cin>>X>>Y;
        vector<int> exist(4,0),pri;
        REP(i,16){
            int xy=f(X,Y,15-i);
            if(xy==0||exist[xy])continue;
            exist[xy]=1;pri.pb(xy);
        }
        FOR(i,1,4)if(exist[i]==0)pri.pb(i);
        V nobu=unpack(val[pack(pri)]);
        int res=0;
        REP(i,16){
            res<<=1;
            int xy=f(X,Y,15-i);
            if(xy!=0){
                REP(j,3)if(xy==pri[j])res+=nobu[j];
            }
        }
        cout<<res<<endl;
        
    }
    return 0;
}

Measured memory_bytes: 23152
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def main():
    from itertools import combinations
    n = int(readline())
    mat = [list(map(int, readline().split())) for _ in range(n)]

    if n == 1:
        return print(1)

    ans = INF
    for com in combinations(range(n), r=2):
        first, second = com
        dx = mat[first][0] - mat[second][0]
        dy = mat[first][1] - mat[second][1]
        uf = UnionFind(n)
        for i in range(n):
            cx, cy = mat[i]
            for j in range(n):
                nx, ny = mat[j]
                if (cx - nx == dx and cy - ny == dy) or (-cx + nx == dx and - cy + ny == dy):
                    uf.union(i, j)
        ans = min(ans, uf.group_count())

    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 70256
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;

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

struct State {
  char field[4][4];
  int cost;
  explicit State(int c): cost(c) {}
};

struct Drop {
  int y, x, dir;
  Drop(int y, int x, int dir): y(y), x(x), dir(dir) {}
};

void blowup(char field[4][4], int sy, int sx) {
  vector<Drop> drops;
  field[sy][sx] = 0;
  for (int dir = 0; dir < 4; ++dir) {
    drops.push_back(Drop(sy, sx, dir));
  }
  while (!drops.empty()) {
    for (int i = 0; i < int(drops.size()); ) {
      Drop& d = drops[i];
      d.y += dy[d.dir];
      d.x += dx[d.dir];
      if (d.y < 0 || d.y >= 4 || d.x < 0 || d.x >= 4) {
        drops.erase(drops.begin()+i);
        continue;
      }
      if (field[d.y][d.x] != 0) {
        field[d.y][d.x] += 1;
        drops.erase(drops.begin()+i);
        continue;
      }
      ++i;
    }
    for (int y = 0; y < 4; ++y) {
      for (int x = 0; x < 4; ++x) {
        if (field[y][x] > 4) {
          field[y][x] = 0;
          for (int dir = 0; dir < 4; ++dir) {
            drops.push_back(Drop(y, x, dir));
          }
        }
      }
    }
  }
}

int main() {
  char goal[4][4] = {};
  State init_state(0);

  for (int y = 0; y < 4; ++y) {
    for (int x = 0; x < 4; ++x) {
      int d; scanf("%d", &d);
      init_state.field[y][x] = d;
    }
  }

  queue<State> Q;
  Q.push(init_state);
  int ans = -1;
  while (!Q.empty()) {
    State s = Q.front(); Q.pop();

    if (memcmp(s.field, goal, sizeof(goal)) == 0) {
      ans = s.cost;
      break;
    }

    if (s.cost < 5) {
      for (int y = 0; y < 4; ++y) {
        for (int x = 0; x < 4; ++x) {
          if (s.field[y][x] == 0) {
            // do nothing
          } else {
            State next(s.cost+1);
            memcpy(next.field, s.field, sizeof(s.field));
            next.field[y][x] += 1;
            if (next.field[y][x] == 5) { blowup(next.field, y, x); }
            Q.push(next);
          }
        }
      }
    }
  }

  printf("%d\n", ans);
}

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

using namespace std;


void solve(){
    int n; cin>>n;
    map<int, int> m;
    long long sum = 0;
    for(int i=0; i<n; ++i){
        int a; cin>>a;
        m[a]++;
        sum+=a;
    }
    int q; cin>>q;
    while(q--){
        int b, c; cin>>b>>c;
        m[c]+=m[b];
        sum+=m[b]*(c-b);
        m[b] = 0;
        cout<<sum<<"\n";
    }
}


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

    // int T; cin>>T; while(T--)
        solve();
}

Measured memory_bytes: 8020
n, m = map(int, input().split())
index = 0
listForL = []
listForL2 = []
while index < m:
    p, y = map(int, input().split())
    listForL.append([p, y])
    listForL2.append([p, y, index])
    index+=1

listForL2.sort()
listForAns=[0]*m
index2 =0
count = 0
before=0
while index2 < len(listForL2):
    if before!=listForL2[index2][0]:
        count=1
        before = listForL2[index2][0]
    else:
        count+=1
    mojiR=str(listForL2[index2][0])
    mojiL=str(count)
    index3=0
    if len(mojiR)==1:
        mojiR="00000"+mojiR
    elif len(mojiR)==2:
        mojiR = "0000"+mojiR
    elif len(mojiR)==3:
        mojiR = "000"+mojiR
    elif len(mojiR)==4:
        mojiR = "00"+mojiR
    elif len(mojiR)==5:
        mojiR = "0"+mojiR
    if len(mojiL) == 1:
        mojiL = "00000"+mojiL
    elif len(mojiL) == 2:
        mojiL = "0000"+mojiL
    elif len(mojiL) == 3:
        mojiL = "000"+mojiL
    elif len(mojiL) == 4:
        mojiL = "00"+mojiL
    elif len(mojiL) == 5:
        mojiL = "0"+mojiL
    listForAns[listForL2[index2][2]]=mojiR+mojiL
    index2+=1

for ans in listForAns:
    print(ans)

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

#define int long long

int32_t main()
{
    ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int n;cin>>n;
    if(n>=30) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}
/*



*/



Measured memory_bytes: 3608
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy,copy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def main():
    n, m = MAP()
    ac = defaultdict(int)
    wa = defaultdict(int)
    for i in range(m):
        p, s = input().split()
        p = int(p)
        if s == "AC":
            ac[p] = 1
        else:
            if ac[p] == 0:
                wa[p] += 1
    for i in range(1,n+1):
        if ac[i] == 0:
            wa[i] = 0

    # print(ac)
    # print(wa)
    print(sum(ac.values()), sum(wa.values()))


if __name__=='__main__':
    main()


Measured memory_bytes: 23856
n = int(input())
def calc(a,b):
    return max(len(str(round(a))),len(str(round(b))))
L = 11
x = int(round(n**(1/2)))
for y in range(1,x+1):
    if n % y == 0:
        if L > calc(n/y,y):
            L = calc(n/y,y)
print(L)

Measured memory_bytes: 3060
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
using namespace std;
typedef long long unsigned int ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define SZ(x) ((int)(x).size())
#define m0(x) memset(x,0,sizeof(x))
#define fill(x,y) memset(x,y,sizeof(x))
#define SIZE_OF_ARRAY(array) (sizeof(array)/sizeof(array[0]))



int main() {
  string S;
  cin >> S;
  long count = 0;
  long Bcount = 0;

  for (int i = 0; i < S.length(); i++)
  {
    if (S[i] == 'W') {
      count += Bcount;
    } else {
      Bcount++;
    }
  }
    cout << count << endl;
  return 0;
}


Measured memory_bytes: 644
package main

import (
	"fmt"
	"math"
)

func main() {
	var n int
	fmt.Scan(&n)

	min := math.MaxInt64
	for i := 1; i < n; i++ {
		a := i
		b := n - a
		sum := sumDigit(a) + sumDigit(b)
		if sum < min {
			min = sum
		}
	}

	fmt.Println(min)
}

func sumDigit(n int) int {
	sum := 0
	for n > 0 {
		sum += n % 10
		n /= 10
	}
	return sum
}


Measured memory_bytes: 512
class Cat:
    def __init__(self, input):
        self.id = int(input[1])
        self.size = int(input[2])

    def sleep(self, index):
        self.index = index

    def last(self):
        return self.index + self.size


def lastindex(list, val):
    result = len(list) - 1
    for n in range(len(list)):
        if list[n] == val:
            result = n
    return result

def indexSleepable(wall, size):
    index = 0
    while index < len(wall):
        target = wall[index:index+size]
        if target == [False] * size:
            return index
        else:
            next_index = lastindex(target, True)
            index += next_index + 1
    else:
        return -1

while True:
    W, Q = [int(n) for n in input().split() ]

    if W == Q == 0:
        break

    lines = [input().strip().split() for n in range(Q) ]

    wall = [False] * W

    Catdict = {}

    for l in lines:
        if l[0] == "s":
            cat = Cat(l)
            index = indexSleepable(wall, cat.size)
            if index != -1:
                cat.sleep(index)
                print(index)
                wall[cat.index:cat.last()] = [True] * cat.size
                Catdict[cat.id] = cat
            else:
                print("impossible")
        elif l[0] == "w":
            cat = Catdict[int(l[1])]
            wall[cat.index:cat.last()] = [False] * cat.size

    print("END")

Measured memory_bytes: 7808
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int r = in.nextInt();
        Pair[] pairs = new Pair[r];
        for( int i = 0; i < r; i++ ) {
            pairs[i] = new Pair(in.nextInt(), in.nextInt());
        }
        Arrays.sort(pairs);
        // System.out.println();
        // for( Pair p : pairs ) System.out.printf("%d %d\n", p.a, p.b);
        int prev_a = pairs[0].a;
        int prev_b = pairs[0].b;
        int ct = 1;
        for( int i = 1; i < r; i++ ) {
            Pair temp = pairs[i];
            // is overlapping with current line ..?
            if( prev_a > temp.a && prev_a < temp.b ) {
                continue;
            } else if ( prev_b < temp.b && prev_b > temp.a ) {
                continue;
            } else {
                // update current line to add split to, if not overlapping
                ct++;
                prev_a = temp.a;
                prev_b = temp.b;
            }
        }
        System.out.println(ct);
    }
    public static class Pair implements Comparable<Pair>{
        int a, b;
        public Pair(int a, int b) {
            this.a = a;
            this.b = b;
        }
        public int compareTo( Pair p ) {
            // sort by a descending, and ascending by b if equal a's
            if( a == p.a ) return b - p.b;
            return p.a - a;
        }
    }
}

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

int main() {
string s;
cin >>s;
int  ans =0,che =0;
for(int i=0;i<s.size();i++){
  if(s.at(i)=='A'||s.at(i)=='C'||s.at(i)=='G'||s.at(i)=='T'){
    che++;
  }
  else{
    ans =max(ans,che);
    che =0;
  }
}
ans = max(ans,che);
cout << ans << endl;
}





Measured memory_bytes: 256
n,k = map(int,input().split())

arr = []
for i in range(n):
	arr += [int(input())]
	
arr2 = sorted(arr)

ans = float('inf')

for y in range(n-k+1):
	mx = arr2[y+k-1]
	mn = arr2[y]
	ans = min(ans,mx-mn)

print(ans)
	

Measured memory_bytes: 8280
using System;

namespace ABC071
{
    class B
    {
        static void Main(string[] args)
        {
            var S = Console.ReadLine();

            for (var i = 'a'; i <= 'z'; i++)
            {
                if (!S.Contains(i.ToString())) { Console.WriteLine(i); return; }
            }
            Console.WriteLine("None");
        }
    }
}


Measured memory_bytes: 11232
#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    int N;
    cin >> N;
    double v[N];
    for (int i = 0; i < N; ++i) cin >> v[i];
    sort(v, v + N);
    double sum = 0;
    for (int i = 0; i < N - 1; ++i) {
        v[i + 1] = (v[i] + v[i + 1]) / 2;
        sort(v + i + 1, v + N);
    }
    printf("%.10f\n", v[N - 1]);
}

Measured memory_bytes: 888
#include "bits/stdc++.h"
#include <unordered_set>

#define _CRT_SECURE_NO_WARNINGS

#define REP(i, n) for(decltype(n) i = 0; i < (n); i++)
#define REP2(i, x, n) for(decltype(x) i = (x); i < (n); i++)
#define REP3(i, x, n) for(decltype(x) i = (x); i <= (n); i++)
#define RREP(i, n) for (decltype(n) i = (n) - 1; i >= 0; i--)

#define ALL(a) (a).begin(),(a).end()
#define SORT(c) sort((c).begin(),(c).end())
#define DESCSORT(c) sort(c.begin(), c.end(), greater<int>())

using namespace std;

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

using LL = long long int;
using LD = long double;

const int INF = (1 << 30) - 1;
const LL INF64 = ((LL)1 << 62) - 1;
const double PI = 3.1415926535897932384626433832795;

using pii = pair<int, int>;
using pll = pair<LL, LL>;
using pdd = pair<double, double>;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vl = vector<LL>;
using vvl = vector<vl>;
using vvvl = vector<vvl>;
using vd = vector<double>;
using vs = vector<string>;
using vb = vector<bool>;

//==============================================

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

	int n, a, b;
	cin >> n >> a >> b;

	int t, ans = 0;
	REP(i, n) {
		cin >> t;

		if (a <= t && t < b) continue;
		ans++;
	}

	cout << ans << "\n";
	return 0;
}

Measured memory_bytes: 256
package main

import (
	"fmt"
)

var (
	finv, inv, fac [MAX]int
)

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

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

const (
	MOD = 1000000007
	MAX = 510000
)

func ModAdd(a, b int64) int64 {
	return (a + b) % MOD
}

func ModMul(a, b int64) int64 {
	return a * b % MOD
}

func ModSub(a, b int64) int64 {
	r := (a%MOD - b%MOD) % MOD
	if r < 0 {
		r += MOD
	}
	return r
}

func ModDiv(a, b int64) int64 {
	return a % MOD * ModInv(b) % MOD
}

func ModPow(a, n int64) int64 {
	var r int64 = 1
	for n > 0 {
		if n&1 == 1 {
			r = r * a % MOD
		}
		a = a * a % MOD
		n >>= 1
	}
	return r
}

func ModInv(a int64) int64 {
	var b, u, v int64 = MOD, 1, 0
	for b > 0 {
		t := a / b
		a -= t * b
		a, b = b, a
		u -= t * v
		u, v = v, u
	}
	u %= MOD
	if u < 0 {
		u += MOD
	}
	return u
}

type Q struct {
	value int
	index int
	A, B  int
}

type QS []*Q

func (p QS) Len() int           { return len(p) }
func (p QS) Less(i, j int) bool { return p[i].value > p[j].value }
func (pq QS) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
	pq[i].index = i
	pq[j].index = j
}

func (pq *QS) Push(x interface{}) {
	n := len(*pq)
	item := x.(*Q)
	item.index = n
	*pq = append(*pq, item)
}

func (pq *QS) Pop() interface{} {
	old := *pq
	n := len(old)
	item := old[n-1]
	old[n-1] = nil  // avoid memory leak
	item.index = -1 // for safety
	*pq = old[0 : n-1]
	return item
}

func FactoredPrimeNumber(num int) map[int]int {
	m := map[int]int{}
	return factor(m, num, 2)
}

func factor(result map[int]int, num, pnum int) map[int]int {
	if pnum*pnum > num {
		if num != 1 {
			result[num] += 1
		}
		return result
	}

	if num%pnum == 0 {
		num /= pnum
		result[pnum]++
	} else {
		pnum++
	}
	return factor(result, num, pnum)
}

func GCD(a, b int64) int64 {
	if b == 0 {
		return a
	}
	return GCD(b, a%b)
}

func LCM(a, b int64) int64 {
	return a * b / GCD(a, b)
}

func main() {
	var S, T string
	fmt.Scanf("%s\n%s\n", &S, &T)

	if string([]rune(S)) == string([]rune(T)[:len(S)]) {
		fmt.Println("Yes")

	} else {
		fmt.Println("No")

	}

}

func Reverse(runes []rune) []rune {
	for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
		runes[i], runes[j] = runes[j], runes[i]
	}
	return runes
}


Measured memory_bytes: 13804
#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <vector>
#define DEBUG 0
constexpr int kMax = 100001;
constexpr int kMod = 1000000007;
typedef long long LL;

enum Color {
  kWhite = 0, kBlack = 1
};

void dfs(int node, int parent,
         const std::vector<std::vector<int>>& edges,
         LL dp[][2]) {
#if DEBUG
  std::cout << "dfs " << node << " from " << parent << std::endl;
#endif

  for (int v : edges[node]) {
    if (v == parent) continue;
    dfs(v, node, edges, dp);

    dp[node][kWhite] *= dp[v][kWhite] + dp[v][kBlack];
    dp[node][kBlack] *= dp[v][kWhite];

    dp[node][kWhite] %= kMod;
    dp[node][kBlack] %= kMod;
  }
}

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

  LL dp[kMax][2];
  for (int i = 1; i <= N; ++i) {
    dp[i][kBlack] = 1;
    dp[i][kWhite] = 1;
  }

  std::vector<std::vector<int>> edges(N+1);
  for (int i = 1; i <= N-1; ++i) {
    int x, y; std::cin >> x >> y;
    edges[x].push_back(y);
    edges[y].push_back(x);
  }

#if DEBUG
  for (int i = 1; i <= N; ++i) {
    std::cout << i << ":";
    for (int v : edges[i]) {
      std::cout << v << " ";
    }
    std::cout << std::endl;
  }
#endif

  dfs(1, -1, edges, dp);
  std::cout << (dp[1][kWhite] + dp[1][kBlack]) % kMod << std::endl;
}


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

struct TEAM{
	int i;
	int u;
	int a;
	int p;
};
bool operator<(const TEAM &a,const TEAM &b){
	pair<pair<int,int>,int> A = make_pair(make_pair(a.a,-a.p),-a.i);
	pair<pair<int,int>,int> B = make_pair(make_pair(b.a,-b.p),-b.i);
	return A < B;
}

int main(){
	int n;
	while(cin >> n){
		vector<TEAM> team(n);
		rep(i,n)cin >> team[i].i >> team[i].u >> team[i].a >> team[i].p;
		sort(team.begin(),team.end());
		reverse(team.begin(),team.end());
		map<int,int> memo;
		vector<int> ret;
		
		int i=0;
		while(1){
			if(i >= team.size() || ret.size()>=26)break;
			TEAM use = team[i];
			if(ret.size()<10){
				if(memo[use.u]<3){
					ret.push_back(use.i);
					memo[use.u]++;
				}
			}else if(ret.size()<	20){
				if(memo[use.u]<2){
					ret.push_back(use.i);
					memo[use.u]++;
				}
			}else{
				if(memo[use.u]<1){
					ret.push_back(use.i);
					memo[use.u]++;
				}
			}
			i++;
		}
		rep(i,ret.size()){
			cout << ret[i] << endl;
		}
	}
}

Measured memory_bytes: 0
import bisect
import cmath
import heapq
import itertools
import math
import operator
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

H, W = list(map(int, sys.stdin.buffer.readline().split()))
A = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(H)]

X = []
Y = []
for i in range(H):
    if i % 2 == 0:
        X += list(range(W))
    else:
        X += list(reversed(range(W)))
    Y += [i] * W

op = []
for i in range(len(X) - 1):
    x1, y1 = X[i], Y[i]
    x2, y2 = X[i + 1], Y[i + 1]
    if A[y1][x1] % 2 == 1:
        op.append((y1 + 1, x1 + 1, y2 + 1, x2 + 1))
        A[y2][x2] += 1
print(len(op))
for row in op:
    print(*row)


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

int n;
vector<int> a;

int main() {
    while (scanf("%d", &n) == 1) {
        a.assign(n, 0);
        for (int i = 0; i < n; i++) scanf("%d", &a[i]);

        long long s = 0;
        map<int, int> m;
        for (auto &x : a) m[x]++, s += x; 

        int q;
        scanf("%d", &q);
        while (q--) {
            int b, c;
            scanf("%d %d", &b, &c);
            if (m.count(b)) {
                int count = m[b];
                s += 1ll * count * c - 1ll * count * b;
                m[c] += count;
                m[b] -= count;
            }
            printf("%lld\n", s);
        }
    }
    return 0;
}


Measured memory_bytes: 7596
n = gets.chomp.to_i
a = gets.chomp.split(" ").map(&:to_i)

mt = [0]*n

(0..n-1).each do |i|
    mt[0] += (i%2==1 ? -a[i] : a[i])
end

(0..n-1).each do |i|
    mt[i+1] = 2 * a[i] - mt[i]
end

(0..n-1).each do |i|
    print "#{mt[i]} "
end
puts ""

Measured memory_bytes: 14084
#include<iostream>
#include<vector>

using namespace std;

int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    int cnt = 0;
    for(int i = 0; i < n; i++){
        
        for(int j = n - 1; j > i; j--){
            if(a[j] < a[j - 1]){
                cnt++;
                swap(a[j],a[j - 1]);
            }
        }
    }
    for(int i = 0; i < n; i++){
        cout << a[i] << (i != n - 1 ? " ": "\n");
    }
    cout << cnt << endl;
}


Measured memory_bytes: 3064