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


using namespace std;
typedef long long ll;
#define REP(i,n) for(int i=0; i<int(n); i++)
#define FOR(i,m,n) for(int i=int(m); i<int(n); i++)
#define ALL(obj) (obj).begin(),(obj).end()
#define VI vector<int>
#define VLL vector<long long>
#define VVI vector<vector<int>>
#define VVLL vector<vector<long long>>
#define VC vector<char>
#define VS vector<string>
#define VVC vector<vector<char>>
#define VB vector<bool>
#define VVB vector<vector<bool>>
#define fore(i,a) for(auto &i:a)

typedef pair <int, int> P;
template<class T> bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; }
const int  INF = 1 << 30;
const ll INFL = 1LL << 60;
const ll mod = 998244353;




int main() {

	string s;
	cin >> s;
	ll k;
	cin >> k;
	ll n = s.size();
	char a;
	a = s[0];
	bool b = true;

	REP(i, s.size()) {
		if (s[i] != a)b = false;
	}
	if (b) {
		cout << k * n / 2 << endl;
		return 0;
	}
	if (s[0] != s[n - 1]) {
		ll ans = 0;
		REP(i, n - 1) {
			if (s[i] == s[i + 1]) {
				s[i + 1] = '_';
				ans++;
			}
		}
		cout << ans * k << endl;
		return 0;
	}


	ll c = 0;
	ll d = n-1;

	while (true) {
		if (s[0] == s[c])c++;
		else break;
	}
	while (true) {
		if (s[0] == s[d])d--;
		else break;
	}


	ll ans = 0;
	ans += c / 2;
	ans += (n - d - 1) / 2;
	ll e = c + (n - d - 1);
	ans += (e / 2)*(k - 1);
	ll cnt = 0;

	FOR(i, c, d) {
		if (i + 1 == n - 1)break;
		if (s[i] == s[i + 1]) {
			s[i + 1] = '_';
			cnt++;
		}
	}
	ans += cnt * k;

	cout << ans << endl;



}




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

const int bB = 9;
const int B = 1 << bB;

int up(int x) {
	return (x + (1 << bB) - 1) >> bB;
}

int down(int x) {
	return x >> bB;
}

int main()
{
	ios::sync_with_stdio(false), cin.tie(0);
	int n, q;
	cin >> n >> q;
	const int H = up(n);
	vector<int> bv(H, 0), v(n, 0);
	while (q--) {
		int com, x, y;
		cin >> com >> x >> y; x--;
		if (com == 0) {
			v[x] += y;
			bv[down(x)] += y;
		}
		else {
			int res = 0;
			for (int i = x; i < y && i < (up(x) << bB); i++) {
				res += v[i];
			}
			if (up(x) <= down(y)) {
				for (int i = up(x); i < down(y); i++) {
					res += bv[i];
				}
				for (int i = down(y) << bB; i < y; i++) {
					res += v[i];
				}
			}
			printf("%d\n", res);
		}
	}
	return 0;
}



Measured memory_bytes: 3260
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
mod = 1000000007


def comb(n, k):
    if k > n:
        return 0
    x = 1
    for j in range(n - k + 1, n + 1):
        x = x * j
    for l in range(1, k + 1):
        x = x // l
    return x

n, a, b = LI()
V = LI()
V.sort(reverse=True)
s = V[a - 1]
cnt1 = V.count(s)
cnt2 = V[:a].count(s)
print(sum(V[:a]) / a)
if cnt2 != a:
    print(comb(cnt1, cnt2))
    exit()
ret = 0
for i in range(a, b + 1):
    ret += comb(cnt1, i)
    cnt2 += 1

print(ret)







Measured memory_bytes: 82588
;; A - Table Tennis Training

(let* ((n (read))
       (a (read))
       (b (read)))
  (print
    (if (evenp (- b a))
        (/ (- b a) 2)
        (min (- b 1) ; bが卓1へ
             (- n a) ; aが卓nへ
             (/ (+ a b -1) 2) ; aが卓1へ行った後折り返す
             (/ (+ (- n a) (- n b) 1) 2))))) ; bが卓nへ行った後折り返す

Measured memory_bytes: 13284
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int N, M;
    ll K;
    cin >> N >> M >> K;
    ll A[N], B[M];
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    for (int i = 0; i < M; i++) {
        cin >> B[i];
    }
    int ans = 0;
    ll c[M + 1]{};
    for (int i = 0; i < M; i++) {
        c[i + 1] = c[i] + B[i];
    }
    ll t = 0;
    for (int i = 0; i <= N; i++) {
        if (i != 0) {
            t += A[i - 1];
        }
        if (t > K) break;
        int l = -1;
        int r = M + 1;
        while (r - l > 1) {
            int m = (l + r) / 2;
            if (t + c[m] <= K) {
                l = m;
            } else {
                r = m;
            }
        }
        ans = max(ans, i + l);
    }
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 8300
import std.stdio, std.string, std.conv, std.range;
import std.algorithm, std.array, std.typecons, std.container;
import std.math, std.numeric, std.random, core.bitop;

void main() {
    int x;
    scan(x);
    x -= 400;
    auto ans = 8 - (x / 200);
    writeln(ans);
}

void scan(T...)(ref T args) {
    auto line = readln.split; // @suppress(dscanner.suspicious.unmodified)
    foreach (ref arg; args) {
        arg = line.front.to!(typeof(arg));
        line.popFront;
    }
    assert(line.empty);
}

void fillAll(R, T)(ref R arr, T value) {
    static if (is(typeof(arr[] = value))) {
        arr[] = value;
    }
    else {
        foreach (ref e; arr) {
            fillAll(e, value);
        }
    }
}

bool chmin(T, U...)(ref T x, U args) {
    bool isChanged;
    foreach (arg; args)
        if (x > arg) {
            x = arg;
            isChanged = true;
        }
    return isChanged;
}

bool chmax(T, U...)(ref T x, U args) {
    bool isChanged;
    foreach (arg; args)
        if (x < arg) {
            x = arg;
            isChanged = true;
        }
    return isChanged;
}

void yes(bool ok, string y = "Yes", string n = "No") {
    return writeln(ok ? y : n);
}


Measured memory_bytes: 2740
from scipy.special import comb
S = int(input())
m = 10**9 + 7
n_max = S // 3
ans = 0
for i in range(1, n_max + 1):
    res = S - (i * 3)
    ans += comb(res + i - 1, i - 1, exact=True)
    ans = ans % m
print(ans)

Measured memory_bytes: 42240
a, b, c, d = map(int,input().split())
mod = 998244353
A = [[0] * (d+1) for i in range(c+1)]

A[a][b] = 1

for i in range(a, c+1):
    for j in range(b, d+1):
        A[i][j] = (A[i][j] + A[i][j-1] * i + A[i-1][j] * j ) % mod
        if i!=a and j!=b:
            A[i][j] = (A[i][j] - A[i-1][j-1] * (i-1)*(j-1)) % mod
print(A[c][d])
# print(A)

Measured memory_bytes: 133992
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, starter, n) for (int i = (starter); i < (int)(n); i++)

int main(){
    int N;
    cin >>N;
    vector<int> brick(N);
    rep(i,N){
        cin >> brick.at(i);
    }
    int broke=0;
    int counter=0;
    rep(i,N){
        int diff = brick.at(i)-counter;
        if (diff == 1){
            //cout << brick.at(i) <<"hit" << endl;
            counter = brick.at(i);
        }else{
            broke++;
        }
    }
    if (broke == N) cout << -1 << endl;
    else cout << broke << endl;
}

Measured memory_bytes: 1024
//This code was made by Chinese_zjc_.
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<string>
#include<vector>
#include<map>
#include<queue>
#define int long long
#define INF 0x3fffffffffffffff
using namespace std;
int a,b;
signed main()
{
	std::ios::sync_with_stdio(false);
	cin>>a>>b;
	if(b&1)
	{
		cout<<"No"<<endl;
		return 0;
	}
	b>>=1;
	b-=a;
	if(0<=b&&b<=a)
	{
		cout<<"Yes"<<endl;
	}
	else
	{
		cout<<"No"<<endl;
	}
	return 0;
}


Measured memory_bytes: 3616
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <queue>
#include <set>
#include <map>

using namespace std;
typedef long long ll;
int N;
int C[200000];
#define N_MAX 200002

const ll MOD = 1000000007;

ll inv[N_MAX],fac[N_MAX],finv[N_MAX], pow[N_MAX];

void init(){
    fac[0]=fac[1]=1;
    finv[0]=finv[1]=1;
    inv[1]=1;
    pow[0] = 1;
    pow[1] = 2;
    for(int i=2;i<N_MAX;i++){
        inv[i]=MOD-inv[MOD%i]*(MOD/i)%MOD;
        fac[i]=fac[i-1]*(ll) i%MOD;
        finv[i]=finv[i-1]*inv[i]%MOD;
        pow[i] = (pow[i-1]*2)%MOD;
    }
}

ll inv_(ll n){
    if(n == 1) return 1;
    else return MOD-inv_(MOD%n)*(MOD/n)%MOD;
}

ll comb(ll n, ll r){
  ll ans;
  if(n < r){
      ans = 0;
  }else{
      ans = (fac[n]*finv[r])%MOD;
      ans = (ans*finv[n-r])%MOD;
      ans = (ans+MOD)%MOD;
  }
  return ans;
}


int main(){
    init();
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << setprecision(10) << fixed;
    cin >> N;
    for(int i = 0; i < N; i++) cin >> C[i];
    sort(C, C+N);
    ll ans = 0;
    ll tmp = 1;
    for(int i = 0; i < N; i++){
        ll cur = (((N-i-1)*pow[N-i-2]+pow[N-i-1])%MOD)*pow[N-i];
        // cout << cur << endl;
        cur %= MOD;
        cur *= C[i];
        cur %= MOD;
        cur *= tmp;
        cur %= MOD;
        ans += cur;
        ans %= MOD;
        tmp *= 4;
        tmp %= MOD;
        // cout << cur << endl;
    }
    cout << ans << endl;
}

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

template<typename T> void drop(const T &x){cout<<x<<'\n';exit(0);}

void solve() {
  int n;
  cin >> n;
  for(int i = 1; i <= 9; ++i) {
    if(!(n%i) && n/i < 10) drop("Yes");
  }
  cout << "No" << '\n';
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int T=1;
  //cin >> T;
  while(T--) solve();

  return 0;
}


Measured memory_bytes: 3604
#include<stdio.h>

int main(){

  int H,W,t,y;
  while(1){
    scanf("%d%d",&H,&W);
    if(H==0 && W==0)break;
    for(t=0;t<H;t++){
      for(y=0;y<W;y++){
	if(t==0 || t==H-1 || y==0 || y==W-1){
	  printf("#");
        } else {
       printf(".");
	}
      }
	printf("\n");
      }
    printf("\n");
  }
    return 0;
}

Measured memory_bytes: 572
# coding: utf-8
import sys

stdin = sys.stdin
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip() # ignore trailing spaces


def main():
    x = ni()
    memo = [0.1 for _ in range(-125, 125)]
    xmod10 = x%10
    for a in range(-125, 125):
        for b in range(-125, 125):
            if (a-b)%10 == xmod10:
                if memo[a+125] == 0.1:
                    memo[a+125] = pow(a, 5)
                if memo[b+125] == 0.1:
                    memo[b+125] = pow(b, 5)
                if memo[a+125] - memo[b+125] == x:
                    print(a,b)
                    return
    print("Erorr")
    return


if __name__ == '__main__':
    main()

Measured memory_bytes: 65964
#include<bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b){return b!=0?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}

int main(){
    ll h,w;
    cin>>h>>w;
    vector<vector<char>> s(h,vector<char>(w));
    rep(i,h){
        rep(j,w){
            cin>>s[i][j];
        }
    }
    ll mx=0;
    rep(i,h){
        rep(j,w){
            if(s[i][j]=='.'){
                queue<pair<ll,ll>> q;
                vector<vector<ll>> d(h,vector<ll>(w,-1));
                d[i][j]=0;
                q.push(make_pair(i,j));
                while(!q.empty()){
                    pair<ll,ll> p=q.front();
                    q.pop();
                    ll fr=p.first,sc=p.second;
                    mx=max(mx,d[fr][sc]);
                    if(fr>0&&s[fr-1][sc]=='.'&&d[fr-1][sc]==-1){
                        q.push(make_pair(fr-1,sc));
                        d[fr-1][sc]=d[fr][sc]+1;
                    }
                    if(fr<h-1&&s[fr+1][sc]=='.'&&d[fr+1][sc]==-1){
                        q.push(make_pair(fr+1,sc));
                        d[fr+1][sc]=d[fr][sc]+1;
                    }
                    if(sc>0&&s[fr][sc-1]=='.'&&d[fr][sc-1]==-1){
                        q.push(make_pair(fr,sc-1));
                        d[fr][sc-1]=d[fr][sc]+1;
                    }
                    if(sc<w-1&&s[fr][sc+1]=='.'&&d[fr][sc+1]==-1){
                        q.push(make_pair(fr,sc+1));
                        d[fr][sc+1]=d[fr][sc]+1;
                    }
                }
                

            }
        }
    }
    cout<<mx<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
#define ll long long
#define ld long double

int main(void){
int n;
cin>>n;
vector<int> vec(n);
for(int i=0;i<n;i++){
    cin>>vec[i];
}

sort(vec.begin(),vec.end(), greater<int>());

int ans=1;
for(int i=1;i<n;i++){
    if(vec[i]<vec[i-1])
    ans++;
}

cout<<ans;

}

Measured memory_bytes: 3144
#include <bits/stdc++.h>
using namespace std;
int main()
{
	int N;
	cin >> N;
	
	if ((N - 9) % 10 == 0) {
		cout << "Yes" << endl;
	}

	else if (90 <= N) {
		cout << "Yes" << endl;
	}

	else {
		cout << "No" << endl;
	}
}





Measured memory_bytes: 3636
#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
int main() {
	int a, b;
	cin >> a ;
	vector<int> c(a);
	double num=0;
	for (int i = 0;i < a;i++) {
		cin >> c[i];
		num += c[i];
	}
	num /= a;
	num=round(num);
	int p = 0;
	for (int i = 0;i < a;i++) {
		p+=pow(c[i] - num, 2);
	}
	cout << p;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
//#include <boost/multiprecision/cpp_int.hpp>
//namespace mp = boost::multiprecision;

using namespace std;

const double PI = 3.14159265358979323846;
typedef long long ll;
const double EPS = 1e-9;
#define rep(i, n) for (int i = 0; i < (n); ++i)
//#define rep(i, n) for (ll i = 0; i < (n); ++i)
typedef pair<ll, ll> P;
const ll INF = 10e17;
#define cmin(x, y) x = min(x, y)
#define cmax(x, y) x = max(x, y)
#define ret() return 0;

double equal(double a, double b) {
    return fabs(a - b) < DBL_EPSILON;
}

std::istream &operator>>(std::istream &in, set<int> &o) {
    int a;
    in >> a;
    o.insert(a);
    return in;
}

std::istream &operator>>(std::istream &in, queue<int> &o) {
    ll a;
    in >> a;
    o.push(a);
    return in;
}

bool contain(set<int> &s, int a) { return s.find(a) != s.end(); }

//ofstream outfile("log.txt");
//outfile << setw(6) << setfill('0') << prefecture << setw(6) << setfill('0') << rank << endl;
// std::cout << std::bitset<8>(9);
//const ll mod = 1e10;

typedef priority_queue<ll, vector<ll>, greater<ll> > PQ_ASK;

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

    set<ll> s;
    ll sum = 0;

    for (ll i = 1; i <= n; i++) {
        sum += i;
        s.insert(i);
        if (sum >= n) break;
    }
    if (sum > n) {
        ll diff = sum - n;
        s.erase(diff);
    }

    for(ll l : s) cout << l << endl;

}


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

int main(){
    int w,a,b;	cin >> w >> a >> b;
    if(a+w < b){
	cout << b-(a+w) << endl;
    }else if(a > b+w){
	cout << a-(b+w) << endl;
    }else{
	cout << 0 << endl;
    }
}


Measured memory_bytes: 256
N = int(input())

N_list = list(map(int,input().split()))

if len(N_list) <= 2:
  print(0)
  
else:
  cnt = 0
  for i in range(len(N_list)-2):
    for j in range(i+1,len(N_list)-1):
      for k in range(j+1,len(N_list)):
        if (abs(N_list[i]-N_list[j])<N_list[k]<N_list[i]+N_list[j]) and (abs(N_list[j]-N_list[k])<N_list[i]<N_list[j]+N_list[k]) and (abs(N_list[i]-N_list[k])<N_list[j]<N_list[i]+N_list[k]) and (N_list[i]!=N_list[j]) and (N_list[j]!=N_list[k]) and (N_list[i]!=N_list[k]):
          cnt+=1
          
  print(cnt)



Measured memory_bytes: 9228
import std;

const MOD = 998244353;

const N = 2 * 10^^5 + 10;
long[N] fact;
long[N] invfact;

void initFact() {
    fact[0] = fact[1] = 1;
    foreach (i; 2..N)
        fact[i] = fact[i-1] * i % MOD;

    invfact[N-1] = modPow(fact[N-1], MOD-2, MOD);
    foreach_reverse (i; 0..N-1)
        invfact[i] = invfact[i+1] * (i+1) % MOD;
}

long nck(long n, long k) {
    long x = fact[n] * invfact[k] % MOD;
    return x * invfact[n-k] % MOD;
}

long calc(int n, int m, int k) {
    initFact();

    long ans = 0;
    foreach (i; 0..k+1) {
        auto x = m * modPow(m-1, n-i-1, MOD) % MOD;
        x = x * nck(n-1, i) % MOD;
        ans = (ans + x) % MOD;
    }
    return ans;
}

void main() {
    int n, m, k; scan(n, m, k);
    writeln(calc(n, m, k));
}

void scan(T...)(ref T a) {
    string[] ss = readln.split;
    foreach (i, t; T) a[i] = ss[i].to!t;
}
T read(T=string)() { return readln.chomp.to!T; }
T[] reads(T)() { return readln.split.to!(T[]); }
alias readints = reads!int;

long modPow(long x, long k, long m) {
    if (k == 0) return 1;
    if (k % 2 == 0) return modPow(x * x % m, k / 2, m);
    return x * modPow(x, k - 1, m) % m;
}


Measured memory_bytes: 6776
#include <bits/stdc++.h>
#include <string>
using namespace std;
bool pal(string n){
	string r=n;
	reverse(n.begin(),n.end());
	if(r==n)return true;
	else return false;
}
int main() {
	string n;
	cin>>n;
	int t=n.size();
	if(pal(n) and t%2==1){
		if(pal(n.substr(0,(t-1)/2)) and pal(n.substr((t+1)/2,(t-1)/2))){
			cout<<"Yes";
		}else{
			cout<<"No";
		}
	}else{
		cout<<"No";
	}

}

Measured memory_bytes: 256
a,b = map(int,input().split())

c = []
for i in range(b):
  c.append(list(map(int,input().split())))

c.sort(key = lambda x:x[1])

s = c[0][0]
l = c[0][1]
re = 1

for i in range(1,b):
  if l <= c[i][0]:
    re += 1
    l = c[i][1]
    
print(re)


Measured memory_bytes: 64600
BOX = [int(j) for j in input().split(' ')]
if len([j for j in BOX if j % 2 == 0]) > 0:
    print(0)
else:
    BOX = [BOX[0] * BOX[1],BOX[1]*BOX[2],BOX[0]*BOX[2]]
    BOX.sort()
    print(BOX[0])


Measured memory_bytes: 2940
#include <iostream>
using namespace std;
 
int main()
{
   char CF2016[] = "CODEFESTIVAL2016";
   char S[17];
   int count = 0;

   cin >> S;
 
   for (int i=0; i<16; i++)
   {
       if (S[i] != CF2016[i])
       {
          S[i] = CF2016[i];
          count++;
       }
   }
 
   cout << count << endl;
 
   return 0;
}

Measured memory_bytes: 760
package main

import "fmt"

func main() {
	var H, W int
	var flag bool
	for {
		if flag == true {
			fmt.Println("")
		}
		fmt.Scan(&H, &W)
		if H == 0 && W == 0 {
			break
		}
		for i := 0; i < H; i++ {
			for j := 0; j < W; j++ {
				fmt.Print("#")
			}
			fmt.Println("")
		}
		flag = true
	}
	return
}



Measured memory_bytes: 1124
a,b,k = gets.split.map(&:to_i)
tar=nil
if a==b
  tar=a
else
  tar=(b-a).abs
end

cnt=0
tar.downto(1) do |n|
  cnt+=1 if a%n==0&&b%n==0
  if cnt==k
    puts n
    exit
  end
end

Measured memory_bytes: 1788
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
#define rep(i,m,n) for(int (i)=(m);(i)<(n);++(i))
#define rREP(i,m,n) for(int (i)=(n)-1;(i)>=(m);--(i))
#define all(x) (x).begin(),(x).end()
#define out(y,x,h,w) (y)<0||(x)<0||(y)>=(h)||(x)>=(w)
constexpr int INF = 1000000001;
constexpr ll mod = 1000000007;
constexpr double PI = 3.1415926535897932;
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;
}
inline void init() {
	cin.tie(nullptr); cout.tie(nullptr);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(15);
}

//Binary Indexed Tree
//1-indexed
template<class T> class BIT {
private:
	vector<T>arr;
	const int n;

public:
	//初期化
	BIT(int _n) :arr(_n + 1, 0), n(_n) {}

	//１番目からi番目までの和
	T sum(int i) {
		T s = 0;
		while (i > 0) {
			s += arr[i];
			i -= i & (-i); //LSB減算
		}
		return s;
	}

	//[i, j]の要素の総和
	T sum(int i, int j) {
		T ret_i = sum(i - 1);
		T ret_j = sum(j);
		return ret_j - ret_i;
	}

	//i番目に要素xを追加
	void add(int i, T x) {
		while (i <= n) {
			arr[i] += x;
			i += i & (-i);
		}
	}
};

int main() {
	init();

	int n, q; cin >> n >> q;
	BIT<int>bit(n);
	rep(i, 0, q) {
		int com; cin >> com;
		if (com == 0) {
			int a, b; cin >> a >> b;
			bit.add(a, b);
		}
		else {
			int l, r; cin >> l >> r;
			int res = bit.sum(l, r);
			cout << res << "\n";
		}
	}

	return 0;
}


Measured memory_bytes: 3348
#include <iostream>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
#include <map>
#include <cmath>
#include <time.h>
using namespace std;
typedef long long ll;
int main() {
	string s;
	cin >> s;
	int a = -1;
	bool b = false;
	if (s[0] != 'A') {
		cout << "WA" << endl;
		system("PAUSE");
		return 0;
	}
	for (int i = 1; i < s.size(); i++) {
		if (s[i] <= 'Z'&&s[i]>='A'&&s[i]!='C') {
			cout << "WA" << endl;
			system("PAUSE");
			return 0;
		}
		if (s[i] == 'C'&&i >= 2 && i <= s.size() - 2&&a==-1) {
			b = true;
			a = i;
		}
		else if (s[i] == 'C') {
			cout << "WA" << endl;
			system("PAUSE");
			return 0;
		}
	}
	if (b == false) {
		cout << "WA" << endl;
		system("PAUSE");
		return 0;
	}
	cout << "AC" << endl;
	system("PAUSE");
	return 0;
}


Measured memory_bytes: 504
#include<bits/stdc++.h>
using namespace std;
typedef long long ll; 
const int maxn=200020;
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define ROF(i,a,b) for(int i=(a);i>=(b);i--)
#define MEM(x,v) memset(x,v,sizeof(x))
inline int read(){
	int x=0,f=0;char ch=getchar();
	while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar();
	while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
	return f?-x:x;
}
int n,m,el,head[maxn],to[maxn],nxt[maxn],dep[maxn],cnt[2],tot;
ll ans;
bool ok;
inline void add(int u,int v){
	to[++el]=v;nxt[el]=head[u];head[u]=el;
}
void dfs(int u,int f){
	dep[u]=(dep[f]^1);
	tot++;
	cnt[dep[u]]++;
	for(int i=head[u];i;i=nxt[i]){
		int v=to[i];
		if(v==f) continue;
		if(~dep[v]){
			if(dep[v]!=(dep[u]^1)) ok=false;
		}
		else dfs(v,u);
	}
}
int main(){
	n=read();m=read();
	FOR(i,1,m){
		int u=read(),v=read();
		add(u,v);add(v,u);
	}
	MEM(dep,-1);dep[0]=0;
	FOR(i,1,n) if(dep[i]==-1){
		ok=true;
		cnt[0]=cnt[1]=tot=0;
		dfs(i,0);
		if(ok) ans+=1ll*cnt[0]*cnt[1];
		else ans+=1ll*tot*(tot-1)/2;
	}
	printf("%lld\n",ans-m);
}

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

inline long long gcd(long long a, long long b){ //最大公約数
    if(a < b)swap(a, b); if(b == 0)return a;
    for(long long r; r = a % b; a = b, b = r); return b;
}

// AtCoder Beginner Contest 142
int main(){

    ll a, b;
    cin >> a >> b;

    ll g = gcd(a, b);
    ll ans = 0;
    for(ll i = 2; i * i <= g; i++){
        if(g % i == 0){
            ans++;
            while(g % i == 0)g /= i;
        }
    }

    if(g != 1)ans++;
    cout << ans + 1 << endl;

}

Measured memory_bytes: 256
using System;

class Program
{
    static void Main(string[] args)
    {
        var str = Console.ReadLine();
        var input = Console.ReadLine();
        var tmp = input;
        var count = 0;
        do
        {
            var index = tmp.IndexOf("ABC");
            if(index < 0)
            {
                break;
            }
            else
            {
                count++;
                tmp = tmp.Substring(index + 3, tmp.Length - 3 - index);
            }
        } while (true);
        Console.WriteLine(count);
    }
}


Measured memory_bytes: 13280
#include <cstdio>
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <string>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <functional>
#include <queue>
#include <stack>
#include <cmath>
#include <iomanip>
#include <list>
#include <tuple>
#include <bitset>
#include <ciso646>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> T;
typedef vector<ll> vec;

inline bool cheak(ll x, ll y, ll xMax, ll yMax){ return x >= 0 && y >= 0 && xMax > x && yMax > y; }
inline ll toInt(string s) { ll v; istringstream sin(s); sin >> v; return v; }
template<class T> inline string toString(T x) { ostringstream sout; sout << x; return sout.str(); }
template<class T> inline T sqr(T x) { return x*x; }

#define For(i,a,b)	for(ll (i) = (a);i < (b);(i)++)
#define rep(i,n)	For(i,0,n)
#define rFor(i,a,b)	for(ll (i) = (a-1);i >= (b);(i)--)
#define rrep(i,n)	rFor(i,n,0)
#define clr(a)		memset((a), 0 ,sizeof(a))
#define mclr(a)		memset((a), -1 ,sizeof(a))
#define all(a)		(a).begin(),(a).end()

const ll mod = 1e9 + 7;
const ll INF = 1e9 + 9;

int main(){
	int n, a, d;
	cin >> n >> a >> d;

	map<int, int> mp;

	int m;
	cin >> m;
	rep(i, m){
		int x, y, z;
		cin >> x >> y >> z;

		int yc, zc;
		if (mp.count(y)){
			yc = mp[y];
		}
		else{
			yc = a + (y - 1) * d;
		}
		if (mp.count(z)){
			zc = mp[z];
		}
		else{
			zc = a + (z - 1) * d;
		}

		if (x == 0){
			mp[z] = yc;
			mp[y] = zc;
		}
		if (x == 1){
			mp[y] = zc;
		}
	}
	int k;
	cin >> k;

	if (mp.count(k)){
		cout << mp[k] << endl;
	}
	else{
		cout << a + (k - 1) * d << endl;
	}


	return 0;
}

Measured memory_bytes: 1196
A, B, C, K = map(int, input().split())
sum = 0
if A <= K:
    K -= A
    sum += 1 * A
elif K > 0:
    sum += 1 * K
    K = 0
if B <= K:
    K -= B
elif K > 0:
    K = 0
if C <= K:
    K -= C
    sum -= 1 * C
elif K > 0:
    sum -= 1 * K
print(sum)

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

int main()
{
	map < int , int > cnt;
	int N;

	cin >> N;
	for ( int i = 0; i < N; i++ ) {
		int A;
		cin >> A;
		if ( cnt.count(A) == 0 ) {
			cnt[A] = 1;
		} else {
			cnt[A]++;
		}
	}
	int sum = 0;
	for ( auto &x : cnt ) {
		if ( (x.first) > (x.second) ) {
			sum += (x.second);
		} else {
			sum += (x.second) - (x.first);
		}
	}
	cout << sum << endl;	
	return ( 0 );
}

Measured memory_bytes: 4736
#include<bits/stdc++.h>
using namespace std;
const int maxn = 500005;
class BIT {
   private:
    int a[maxn];
    int sum(int i) {
        int r = 0;
        while (i > 0) r += a[i], i -= i & -i;
        return r;
    }
   public:
    // size = maxn 的空 BIT ，所有元素都是零
    BIT() { memset(a, 0, sizeof(a)); }
    // 注意 1-based
    void add(int i, int v) {
        while (i < maxn) a[i] += v, i += i & -i;
    }
    // 注意 1-based
    int sum(int l, int r) { return sum(r) - sum(l - 1); }
} b[26];
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n, q;
	string s;
	cin >> n >> s >> q;
	vector<int> a(n + 1);
	for (int i = 1; i <= n; i++) {
		a[i] = s[i - 1] - 'a';
		b[a[i]].add(i, 1);
	}
	while (q--) {
		int op;
		cin >> op;
		if (op == 1) {
			int i, c;
			char ch;
			cin >> i >> ch;
			c = ch - 'a';
			b[a[i]].add(i, -1);
			a[i] = c;
			b[c].add(i, 1);
		} else {
			int l, r;
			cin >> l >> r;
			int ans = 0;
			for (int i = 0; i < 26; i++) {
				if (b[i].sum(l, r)) ans++;
			}
			cout << ans << "\n";
		}
	}
	return 0;
}

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

const int MAX = 2019;
const int MOD = 1e9 + 7;

long long f[MAX], finv[MAX], inv[MAX];

void CombInit() {
  f[0] = f[1] = 1;
  finv[0] = finv[1] = 1;
  inv[1] = 1;
  for (int i = 2; i < MAX; i++) {
    f[i] = f[i - 1] * i % MOD;
    inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
    finv[i] = finv[i - 1] * inv[i] % MOD;
  }
}

long long Comb(int n, int k) {
  if (n < k || k < 0) return 0;
  return f[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main()
{
  CombInit();

  int N, K; cin >> N >> K;

  for (int i = 1; i <= K; i++)
  {
    long long ans = Comb(K - 1, i - 1) * Comb(N - K + 1, i) % MOD;
    cout << ans << endl;
  }
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(){
 string s;
  cin >> s;
  
  if(s[0]==s[1] && s[2]==s[3] && s[1]!=s[2]){
   cout << "Yes" << endl; 
  }
  else if(s[0]==s[2] && s[1]==s[3] && s[0]!=s[1]){
   cout << "Yes" << endl;
  }
  else if(s[0]==s[3] && s[1]==s[2] && s[0]!=s[1]){
   cout << "Yes" << endl; 
  }
  else{
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
package main

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

var sc = bufio.NewScanner(os.Stdin)

func Scan() string {
	sc.Scan()
	return sc.Text()
}
func iScan() int {
	n, _ := strconv.Atoi(Scan())
	return n
}
func fScan() float64 {
	n, _ := strconv.ParseFloat(Scan(), 64)
	return n
}
func stringToInt(s string) int {
	n, _ := strconv.Atoi(s)
	return n
}
func SScan(n int) []string {
	a := make([]string, n)
	for i := 0; i < n; i++ {
		a[i] = Scan()
	}
	return a
}
func iSScan(n int) []int {
	a := make([]int, n)
	for i := 0; i < n; i++ {
		a[i] = iScan()
	}
	return a
}
func abs(x int) int {
	if x < 0 {
		x = -x
	}
	return x
}
func larger(a, b int) int {
	if a < b {
		return b
	} else {
		return a
	}
}
func smaller(a, b int) int {
	if a > b {
		return b
	} else {
		return a
	}
}
func max(a []int) int {
	x := a[0]
	for i := 0; i < len(a); i++ {
		if x < a[i] {
			x = a[i]
		}
	}
	return x
}
func min(a []int) int {
	x := a[0]
	for i := 0; i < len(a); i++ {
		if x > a[i] {
			x = a[i]
		}
	}
	return x
}
func sum(a []int) int {
	x := 0
	for _, v := range a {
		x += v
	}
	return x
}

var mod int = 1000000007

func main() {
	buf := make([]byte, 0)
	sc.Buffer(buf, mod)
	sc.Split(bufio.ScanWords)
	n := iScan()
	v := iSScan(n)
	sort.Ints(v)
	ans := float64(v[0])
	for _, x := range v[1:] {
		ans = (ans + float64(x)) / 2
	}
	fmt.Println(ans)
}


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

int main(void){
  
   char moji;
   scanf("%c",&moji);
  
  if((moji>= 'a') && (moji<='z')){
    printf("a");
  }
  else if((moji>= 'A') && (moji<='Z')){
    printf("A");
  }


   return 0;
}

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

typedef long long ll;
typedef vector<ll> vll;
typedef vector<int> vz;
typedef vector<vz> vvz;
typedef pair<ll, ll> pll;
#define sz(x) ll((x).size())
#define fo(i,n) for(ll i=0; i<(n); i++)
#define FO(i,a,b) for(ll i=(a); i!=(b); i+=(b)>(a)?1:-1)
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define all(c) c.begin(), c.end()
#define F first
#define S second
#define os(x) cout<<x<<' '
#define on(x) cout<<x<<"\n"
#define nl cout<<"\n"
#define maxe(x) max_element(all(x))-(x).begin()
#define mine(x) min_element(all(x))-(x).begin()
const ll P=1e9+7;

ll gcd(ll a, ll b)
{
	ll m=min(a, b), M=max(a, b);
	if(m==0) return M;
	return gcd(m, M%m);
}

ll powmod(ll x, ll y)
{
	ll ans=1;
	while(y>0)
	{
		if(y%2) ans=(ans*x)%P;

		x=(x*x)%P;
		y/=2;
	}
	return ans;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
#ifndef ONLINE_JUDGE
	freopen("C:\\Users\\ASISH\\Desktop\\coding\\input1.txt", "r", stdin);
	freopen("C:\\Users\\ASISH\\Desktop\\coding\\output1.txt", "w", stdout);
#endif

	string s;
	cin>>s;
	if(s.back()=='s') s=s+"es";
	else s=s+"s";
	on(s);
	cerr << "Time : " << ((double)clock()) / (double)CLOCKS_PER_SEC << "s\n";
	return 0;
}

Measured memory_bytes: 3848
#define _USE_MATH_DEFINES
#include <algorithm>
#include <cstdio>
#include <functional>
#include <iostream>
#include <cfloat>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <vector>
using namespace std;

typedef unsigned int ui;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> i_i;
typedef pair<ll, int> ll_i;
typedef pair<double, int> d_i;
typedef pair<ll, ll> ll_ll;
typedef pair<double, double> d_d;
struct edge { int u, v; ll w; };

int INF = INT_MAX / 2;
ll MOD = 1000000007;
ll _MOD = 1000000009;
double EPS = 1e-10;

int f(int w, int x, int t) {
	t += x;
	if (t / w % 2 == 0) return t % w;
	else return w - 1 - t % w;
}

int g(int W, int x, int t) {
	return W - 1 - f(W, W - 1 - x, t);
}

int main() {
	int h, w, n; cin >> h >> w >> n;
	vector<vector<int> > v(h);
	while (n--) {
		int a, b; cin >> a >> b;
		a--; b--;
		v[a].push_back(b);
	}
	vector<int> ans(w);
	for (int x = 0; x < w; x++)
		if (x % 2 == 0) ans[x] = f(w, x, h);
		else ans[x] = g(w, x, h);
	for (int y = h - 1; y >= 0; y--)
		for (int i = 0; i < v[y].size(); i++) {
			int x = v[y][i];
			swap(ans[g(w, x, y)], ans[f(w, x + 1, y)]);
		}
	for (int x = 0; x < w; x++)
		cout << ans[x] + 1 << endl;
}

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

int max(int, int);

int main(void)
{
	int n;
	int i = 0;
	int ans = 0;
	int table[100000][3];
	int value[100000][3];
	
	scanf("%d",&n);
	while(i<n){
		scanf("%d%d%d",&table[i][0],&table[i][1],&table[i][2]);
		i++;
	}
	value[0][0] = table[0][0];
	value[0][1] = table[0][1];
	value[0][2] = table[0][2];
	i = 1;
	while(i<n){
		value[i][0] = max(value[i-1][1],value[i-1][2]) + table[i][0];
		value[i][1] = max(value[i-1][0],value[i-1][2]) + table[i][1];
		value[i][2] = max(value[i-1][0],value[i-1][1]) + table[i][2];
		i++;
	}
	i = 0;
	while(i<3){
		if(ans < value[n-1][i])
			ans = value[n-1][i];
		i++;
	}

	printf("%d",ans);
	return 0;
}

int max(int a, int b)
{
	if(a > b)
	{
		return a;
	}
	return b;
}

Measured memory_bytes: 4052
#include<bits/stdc++.h>
#include<string>
#include <chrono>
using namespace std;
using namespace std::chrono;
typedef long long ll;

int main(){
    int x , n;
    cin >> x >> n;
    map<int , int> m;
    for(int i = 0 , val ; i < n ; i++)
        cin >> val , m[val]++;
    int i = 0;
    for(; ; i++){
        if(!m[x-i])
        {
            i = x - i;
            break;
        }
        if(!m[i+x]){
            i = i + x;
            break;
        }

    }
    cout<<i;
}


Measured memory_bytes: 3640
#include<bits/stdc++.h>
#define forr(i, a, b) for(int i = (a); i < (b); i++)
#define rep(i,n) for(int i = 0; i < (n); i++)
#define rrep(i,n) for(int i = 1; i <= (n); i++)
#define ALL(a) (a.begin()),(a.end())
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<ll, ll> LP;
const ll LINF = 1LL<<60;
const int INF = 1001001001;
const int MOD = 1000000007;

/* --------------------------------------------------- */

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> C(n + 1, 0);
    rep(i, m) {
        int a, b;
        cin >> a >> b;
        C[a]++;
        C[b]++;
    }
    rrep(i, n) cout << C[i] << endl;
    
    return 0;
}

Measured memory_bytes: 256
n,x=map(int,input().split())
a=list(map(int,input().split()))
a.append(x)
a=sorted(a)
distance=[0]*n
for i in range(n):
    distance[i]=a[i+1]-a[i]
tmp=0
import fractions
for i in range(n):
    tmp=fractions.gcd(distance[i],tmp)
print(tmp)
    

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

#define for_(i,a,b) for(int i=a;i<b;++i)

typedef pair< int, int > pii;
typedef pair< pii, pii > ppii;

const int dx[4] = {0,1,0,-1}, dy[4] = {-1,0,1,0};
int n, x[20020], y[20020], visit[20020][2];
char dir[20020];
pii pos[40040], ids[40040];

int xadd(int i) { return dir[i] == 'x' ? 1 : 0; }
int yadd(int i) { return dir[i] == 'y' ? 1 : 0; }

bool rec(int i, int j, int v, vector< pii >& upd) {
	bool res = 1;
	
	if (visit[i][j] < 0) {
		visit[i][j] = v;
		visit[i][j^1] = v^1;
		upd.push_back(pii(i,j));
		upd.push_back(pii(i,j^1));
		
		for_(d,0,4) {
			pii nx(x[i] + dx[d], y[i] + dy[d]);
			int k = lower_bound(pos, pos + 2*n, nx) - pos;
			if (k < 2*n && pos[k] == nx && ids[k].second != i) res &= rec(ids[k].second, ids[k].first, j ? v^1 : v, upd);
			
			nx.first += xadd(i); nx.second += yadd(i);
			k = lower_bound(pos, pos + 2*n, nx) - pos;
			if (k < 2*n && pos[k] == nx && ids[k].second != i) res &= rec(ids[k].second, ids[k].first, j ? v : v^1, upd);
		}
	} else {
		res = (visit[i][j] == v);
	}
	
	return res;
}

int main() {
	while (scanf("%d", &n), n) {
		vector< ppii > vp;
		
		for_(i,0,n) {
			scanf("%d %d %c", &x[i], &y[i], &dir[i]);
			vp.push_back(ppii(pii(x[i], y[i]), pii(0, i)));
			vp.push_back(ppii(pii(x[i] + xadd(i), y[i] + yadd(i)), pii(1, i)));
		}
		
		sort(vp.begin(), vp.end());
		
		for_(i,0,2*n) {
			pos[i] = vp[i].first;
			ids[i] = vp[i].second;
		}
		
		memset(visit, -1, sizeof(visit));
		
		bool ok = 1;
		for_(i,0,n && ok) {
			if (visit[i][0] < 0) {
				vector< pii > upd;
				if (!rec(i, 0, 0, upd)) {
					int u_size = (int)upd.size();
					for_(j,0,u_size) visit[upd[j].first][upd[j].second] = -1;
					ok = rec(i, 0, 1, upd);
				}
			}
		}
		cout << (ok ? "Yes" : "No") << endl;
	}
	
	return 0;
}

Measured memory_bytes: 6996
// A.

#include <iostream>
#include <sstream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <vector>

using namespace std;

int main(int argc, char* argv[]) {
	int m, d;
	cin >> m >> d;
	int ans = 0;
	for (int i = 4; i <= m; ++i) {
		for (int j = 22; j <= d; ++j) {
			ans += (j % 10) >= 2 && i == (j / 10) * (j % 10);
		}
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<string>
#include<cstring>
#include<algorithm>
#include<set>
#include<map>
#include<iomanip>

#define REP(i,n) for(int i=0;i<(n);i++)
#define EPS (1e-7)
#define INF (2e9)
// cout << setprecision(10)

using namespace std;
typedef long long int ll;

string s;
int main(void){
    cin >> s;
    if (s[2] == s[3] and s[4] == s[5]) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}



Measured memory_bytes: 256
# include <cstdio>
# include <cstring>
# include <algorithm>
# define ll long long
using namespace std;
const ll PR = 1e9 + 7;
ll n, m;
ll f[100050], e[100050];
ll pwr(ll x, ll y){
	y = y % (PR - 1);
	ll ans = 1;
	while (y){
		if (y & 1) ans = ans * x % PR;
		x = x * x % PR;
		y >>= 1;
	}
	return ans;
}
ll C(ll x, ll y){
	return (f[x] * e[y] % PR) * e[x - y] % PR;
}
int main(){
//	freopen("1.in", "r", stdin);
	scanf("%lld%lld", &m, &n);
	ll x = n, ans = 1;
	f[0] = 1;
	e[0] = 1;
	for (int i = 1; i < 100050; i++){
		f[i] = f[i - 1] * i % PR;
		e[i] = pwr(f[i], PR - 2);
	}
	for (int i = 2; i * i <= n; i++){
		if (x % i != 0) continue;
		ll cnt = 0;
		while (x % i == 0){
			x /= i;
			cnt++;
		}
		ans = ans * C(cnt + m - 1, m - 1) % PR;
	}
	if (x != 1) ans = ans * m % PR;
	printf("%lld\n", ans);
	return 0;
}

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

//begin( Union-Find )//

const ll MAX_N = 1000000;


//親の番号
ll par[MAX_N];
//ノードの高さ
ll rk[MAX_N];

ll sz[MAX_N];


//n要素で初期化
void init(ll n) {
  for (ll i = 0; i < n; i++) {
    par[i] = i;
    rk[i] = 0;
    sz[i] = 1;
  }
}

//木の根を求める
ll find(ll x) {
  if (par[x] == x) {
    return x;
  } else {
    return par[x] = find(par[x]);
  }
}

//xとyの属する集合を併合
void unite(ll x, ll y) {
  x = find(x);
  y = find(y);
  if (x == y) return;
  
  if (rk[x] < rk[y]) {
    ll n = sz[x]+sz[y];
    par[x] = y;
    sz[x] = sz[y] = n;
  } else {
    ll n = sz[x]+sz[y];
    par[y] = x;
    sz[x] = sz[y] = n;
    if (rk[x] == rk[y]) rk[x]++;
  }
}

//xとyが同じ集合に属するか否か
bool same(ll x, ll y) {
  return find(x) == find(y);
}

//end( Union-Find )//

int main() {
  ll N, M, K; cin >> N >> M >> K;
  init(N);
  P pf[M], pb[K];
  ll res[N];
  for (ll i = 0; i < M; i++) {
    ll a,b; cin >> a >> b; a--; b--; pf[i] = P(a,b);
    unite(a,b);
  }
  for (ll i = 0; i < N; i++) {
    res[i] = sz[find(i)]-1;
  }
  for (ll i = 0; i < K; i++) {
    ll c,d; cin >> c >> d; c--; d--; pb[i] = P(c,d);
  }
  
  for (ll i = 0; i < M; i++) {
    P p = pf[i];
    if (same(p.first, p.second)) {res[p.first]--; res[p.second]--;}
  }
  for (ll i = 0; i < K; i++) {
    P p = pb[i];
    if (same(p.first, p.second)) {res[p.first]--; res[p.second]--;}
  }
  
  for (ll i = 0; i < N; i++) {
    cout << res[i] << " ";
  }
  cout << endl;
}

Measured memory_bytes: 13696
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef double dd;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> ii;
typedef pair<ll, int> li;
typedef pair<int, ll> il;
typedef pair<ll , ll> lli;
typedef vector<ii> vii;
typedef vector<il> vil;
typedef vector<li> vli;
typedef vector<lli> vlli;
 
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define in insert
#define f0(b) for(int i=0;i<(b);i++)
#define f00(b) for(int j=0;j<(b);j++)
#define f1(b) for(int i=1;i<=(b);i++)
#define f11(b) for(int j=1;j<=(b);j++)
#define f2(a,b) for(int i=(a);i<=(b);i++)
#define f22(a,b) for(int j=(a);j<=(b);j++)
#define sf(a) scanf("%lld",&a)
#define sff(a,b) scanf("%lld %lld", &a , &b)
#define pf(a) printf("%lld\n",a)
#define pff(a,b) printf("%lld %lld\n", a , b)
#define PI 3.14159265359
#define bug printf("**!\n")
#define mem(a , b) memset(a, b ,sizeof(a))
#define front_zero(n) __builtin_clzll(n)
#define back_zero(n) __builtin_ctzll(n)
#define total_one(n) __builtin_popcountll(n)

const ll mod = 1000000007;
const ll maxn = (ll)2e5+5;
const int nnn = 1048590;
const int inf = numeric_limits<int>::max()-1;
//const ll INF = numeric_limits<ll>::max()-1;
const ll INF = 1e18;

ll dx[]={0,1,0,-1};
ll dy[]={1,0,-1,0};
ll dxx[]={0,1,0,-1,1,1,-1,-1};
ll dyy[]={1,0,-1,0,1,-1,1,-1};


void solve(){
	ll n , k;
	cin >> n >> k;
	ll step[n+5] , a[n+5] , p[n+5];
	f1(n) cin >> a[i];
	mem(step , -1);
	mem(p , -1);
	p[1] = 0;
	step[0] = 1;
	ll pos = 1;
	while(1){
		if(k == 0){
			cout << pos;
			return;
		}
		if(p[a[pos]] != -1){
			k--; 
			ll total = abs(p[a[pos]] - p[pos]) + 1;
			ll head = k%total;
			//cout << total << ' ' << head << '\n';
			cout << step[ p[a[pos]]+ head];
			return; 
		}
		k--;
		p[a[pos]] = p[pos]+1;
		step[p[pos]+1] = a[pos];
		pos = a[pos];
	}
	return;
}


int main() {
   
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    ll T;
    T=1;
    //cin >> T;
    //scanf("%lld",&T);
    ll CT = 0;
    //work();
    while(T--){
    	//cout << "Case " << ++CT <<": " ;
    	//printf("Case %lld: ",++CT);
		solve();
	}
    
    return 0;
}


Measured memory_bytes: 8300
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <tuple>
#include <queue>
#include <bitset>
#include <unordered_map>
#include <tuple>
#include <utility>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <sys/time.h>

using namespace std;

void solve(long long N, vector<long long> A){
  if (N == 2) {
    long long a, b;
    a = min(A[0], A[1]);
    b = max(A[0], A[1]);
    std::cout << b - a << std::endl;
    std::cout << b << " " << a << std::endl;
    return;
  }
  vector<long long> neg;
  vector<long long> pos;
  for (int i = 0; i < N; i++) {
    if (A[i] < 0) {
      neg.push_back(A[i]);
    } else {
      pos.push_back(A[i]);
    }
  }
  if (neg.size() == 0) {
    sort(pos.begin(), pos.end());
    neg.push_back(pos[0]);
    pos.erase(pos.begin());
  }
  if (pos.size() == 0) {
    sort(neg.begin(), neg.end());
    pos.push_back(neg.back());
    neg.pop_back();
  }
  long long ans = - accumulate(neg.begin(), neg.end(), 0LL) + accumulate(pos.begin(), pos.end(), 0LL);
  long long x, n;
  std::cout << ans << std::endl;
  if (pos.size() > 1) {
    std::cout << neg.back() << " " << pos.back() << std::endl;
    x = neg.back() - pos.back();
    neg.pop_back();
    pos.pop_back();
    n = pos.size();
    for (int i = 0; i < n-1; i++) {
      std::cout << x << " " << pos.back() << std::endl;
      x = x - pos.back();
      pos.pop_back();
    }
    std::cout << pos.back() << " " << x << std::endl;
    x = pos.back() - x;
  } else {
    x = pos.back();
  }

  n = neg.size();
  for (int i = 0; i < n; i++) {
    std::cout << x << " " << neg.back() << std::endl;
    x = x - neg.back();
    neg.pop_back();
  }
  return;
}

int main(){
  long long N;
  scanf("%lld",&N);
  vector<long long> A(N);
  for(int i = 0 ; i < N ; i++){
    scanf("%lld",&A[i]);
  }
  solve(N, A);
  return 0;
}


Measured memory_bytes: 4340
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <math.h>
#include <cmath>
using namespace std;

#define int long long
#define endl "\n"
#define all(v)  v.begin(),v.end()
#define fir first
#define sec second
#define m_p make_pair
#define rep(i,n)  for(int i=0; i<(int) (n); i++)
#define vecin(v) for(int i=0; i<(int)v.size(); i++)cin>>v[i];
#define vecout(v,n) for(int i=0; i<n; i++)cout<<v[i]<<" "; cout<<endl;

const int mod = 1000000007;
const int INF = 2000000015;
const int MAX = 510000;
const int MOD = 1000000007;
long long fac[MAX], finv[MAX], inv[MAX];
int jousu(int x00, int y00) {
	int z00 = 1;
	for (int i = 0; i < y00; i++) {
		z00 *= x00;
	}
	return z00;
}
int keta(int x00) {
	int z00 = x00;
	int w00 = 0;
	while (z00 != 0) {
		z00 /= 10;
		w00++;
	}
	return w00;
}
int krag(double xx) {
	return INF - (int)(INF - xx);
}


int modinv(int a, int m) {
	int b = m, u = 1, v = 0;
	while (b) {
		int t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}
int modpow(int a, int n) {
	int res = 1;
	while (n > 0) {
		if (n & 1) res = res * a % mod;
		a = a * a % mod;
		n >>= 1;
	}
	return res;
}
int com(int xx, int yy) {
	int zz = 1;
	for (int i = xx; i > xx - yy; i--) {
		zz *= i;
		zz %= mod;
	}
	for (int i = 1; i <= yy; i++) {
		zz *= modinv(i, mod);
		zz %= mod;
	}
	return zz;
}
int gcd(int xx, int yy) {
	int p = xx;
	int q = yy;
	if (q > p)swap(p, q);
	while (p % q != 0) {
		p %= q;
		swap(p, q);
	}
	return q;
}
int lcm(int xx, int yy) {
	return xx * yy / gcd(xx, yy);
}
bool prime(int xx) {
	int a = xx;
	for (int i = 2; i * i <= xx; i++) {
		if (xx % i == 0) {
			return 0;
		}
	}
	return 1;
}




signed main() {
	int n,ans=0;
	cin >> n;
	vector<int>vec(n);
	vecin(vec);
	map<int, int>ma;
	rep(i, n) {
		if (ma.count(-vec[i] + i)) {
			ans += ma[-vec[i] + i];
		}
		if (!ma.count(vec[i] + i)) {
			ma[vec[i] + i] = 1;
		}
		else {
			ma[vec[i] + i]++;
		}
	}
	cout << ans << endl;
}



Measured memory_bytes: 17036
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
	int a,b,c,d=0,e;
	cin >>a;
	for(int n=0;n<=a;n++){
		b=0,c=n;
		while(c){
			c=c/10,b++;
		}
		if(b%2==1) d++;
	}
	cout <<d<<'\n';
	return 0;
}

Measured memory_bytes: 256
/*#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>
#include<map>
#include<cstdio>
#include<stack>
#include<queue>
#include<fstream>
#include<cstdio>
#include<deque>
#include<iomanip>
#include <numeric>*/
#include<bits/stdc++.h>

using namespace std;
#define ok1 printf("ok1\n");
#define ok2 printf("ok2\n");
#define M 1000000000000000000LL
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,s,n) for(int i=(s);i<(n);i++)
#define repr(i,n) for(int i=n-1;i>=0;i--)
#define REPR(i,s,n) for(int i=(s);i>=(n);(i)--)
#define all(a) (a).begin(),(a).end()
#define reall(a) (a).rbegin(),(a).rend()
#define pb push_back
#define pf push_front
#define MIN(a,b) a=min((a),(b))
#define MAX(a,b) a=max((a),(b))
#define SIZE(v) (int)v.size()
const double pi = acos(-1.0);

typedef vector<int> vi;
typedef vector<string> vs;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef deque<ll> dll;
typedef pair<ll, ll> P;
typedef vector<P> vP;
const ll mod = 1e9 + 7;
ll dx[4] = {1,0,-1,0};
ll dy[4] = {0,1,0,-1};

int main(){
    ll n,m;
    cin >> n >> m;
    ll ans = 0;
    if(n >= m/2){
        ans = m/2;
    }
    else{
        m -= n*2;
        ans = n + (m/4);
    }
    cout << ans << endl;
    return 0;
}  


Measured memory_bytes: 256