akhauriyash/Code-Regression huggingface dataset:
#include <iostream>

#define N 11
#define Q 51
using namespace std;

int ans=0; 
int n,m,q;
int A[N];
int a[Q],b[Q],c[Q],d[Q];

void calc(int x){
    if(x==n+1){
        int res=0;
        for(int i=0;i<q;i++){
            if(A[b[i]]-A[a[i]]==c[i]) res+=d[i];
        };
        ans=max(res,ans);
    }else{
        for(int i=0;A[x-1]+i<=m;i++){
            A[x]=A[x-1]+i;
            calc(x+1);
        }
    }
}
 
int main() {
    cin >> n >> m >> q;
    for(int i=0;i<q;i++){
        cin >> a[i] >> b[i] >> c[i] >> d[i];
    }
    A[1]=1;
    calc(2);
    cout << ans << endl;
}

Measured memory_bytes: 3644
#include<iostream>
#include<queue>
typedef long long int ll;
using namespace std;

int n;
int num[101];
int ans;

ll solve(){
	ll dp[21][n];

	for(int i=0;i<21;i++)
		for(int j=0;j<n;j++)
			dp[i][j]=0;

	dp[ num[0] ][0]=1;


	for(int i=0;i<n;i++){
		for(int val=0;val<=20;val++){
			if(dp[val][i]>0){
				if(0<=val+num[i+1] && val+num[i+1]<=20)
					dp[ val+num[i+1] ][i+1]+=dp[val][i];
				if(0<=val-num[i+1] && val-num[i+1]<=20)
					dp[ val-num[i+1] ][i+1]+=dp[val][i];
			}
		}
	}
	return dp[ans][n-1];
}

int main(){

	cin>>n;
	n--;
	for(int i=0;i<n;i++)
		cin>>num[i];
	cin>>ans;

//end input

	cout<<solve()<<endl;
	return 0;
}

Measured memory_bytes: 1168
import math
import fractions
import copy
#以下てんぷら
def j(q):
    if q==1: print("YES")
    elif q == 0:print("NO")
    exit(0)
rem = pow(10,9)+7
"""
def ct(x,y):
    if (x>y):print("+")
    elif (x<y): print("-")
    else: print("?")
"""

def ip():
    return int(input())
def printrow(a):
    for i in a:
        print(i)
def combinations(n,r):
    if n<r:return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
def permutations(n,r):
    if n<r:return 0
    return math.factorial(n) // math.factorial(n - r)
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)


#n = ip()                                     #入力整数1つ
n,m= (int(i) for i in input().split())       #入力整数横2つ以上
a = [int(i) for i in input().split()]        #入力整数配列
#a = input()                                  #入力文字列
#a = input().split()                          #入力文字配列
#n = ip()                      #入力セット(整数改行あり)(1/2)
#a=[ip() for i in range(n)]    #入力セット(整数改行あり)(2/2)
#a=[input() for i in range(n)]    #入力セット(整数改行あり)(2/2)
#jの変数はしようできないので注意
#全足しにsum変数使用はsum関数使用できないので注意
b = []
for i in range(m):
    x,y = (int(i) for i in input().split())
    b.append([y,x])
b.sort(reverse=True)
a.sort()
s = 0
pa = 0
pb = 0
while (pa < len(a)):
    if a[pa] < b[pb][0]:
        pa+=1
        s+=b[pb][0]
        b[pb][1]-=1
        if b[pb][1] == 0:
            pb+=1
            if len(b) == pb:
                s += sum(a[pa:])
                break
    else:
        pb+=1
        if len(b) == pb:
            s+=sum(a[pa:])
            break
print(s)

Measured memory_bytes: 26036
// AOJ 1588: Potatoes
// 2017.11.29 bal4u@uu

#include <stdio.h>
#include <stdlib.h>

typedef struct { int a, b; } T;
T tbl[16];

int cmp(T *a, T *b) { return b->a - a->a; }

int main() 
{
	int N, M, K, i, j, k;
	int a1, b1, m1, a2, b2, m2, a3, b3, m3, ans;

	scanf("%d%d%d", &N, &M, &K);
	for (i = 0; i < N; i++) scanf("%d", &tbl[i].a);
	for (i = 0; i < N; i++) scanf("%d", &tbl[i].b);
	qsort(tbl, N, sizeof(T), cmp);

	ans = 0;
	for (i = 0; i < N; i++) {
		b1 = tbl[i].b; if (b1 > M) b1 = M;
		m1 = M - b1;
		a1 = tbl[i].a * b1;
		if (K > 1 && m1 > 0) for (j = i+1; j < N; j++) {
			b2 = tbl[j].b; if (b2 > m1) b2 = m1;
			m2 = m1 - b2;
			a2 = tbl[j].a * b2;
			if (K > 2 && m2 > 0) for (k = j+1; k < N; k++) {
				b3 = tbl[k].b; if (b3 > m2) b3 = m2;
				m3 = m2 - b3;
				a3 = tbl[k].a * b3;
				if (a1 + a2 + a3 + m3 > ans) ans = a1 + a2 + a3 + m3;
			} else if (a1 + a2 + m2 > ans) ans = a1 + a2 + m2;
		} else if (a1 + m1 > ans) ans = a1 + m1;
	}
	printf("%d\n", ans);
	return 0; 
}

Measured memory_bytes: 1812
import java.util.Scanner;

class Main{
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int d=sc.nextInt();
		if(d==22) {
		System.out.println("Christmas Eve Eve Eve");
		}
		if(d==23) {
			System.out.println("Christmas Eve Eve");
			}
		if(d==24) {
			System.out.println("Christmas Eve");
			}
		if(d==25) {
			System.out.println("Christmas");
			}

	}
}

Measured memory_bytes: 22228
def get_s(w, e):
    s = w + 1
    if s == k:
        if e == "A":
            return "a"
        elif e == "B":
            return "b"
        else:
            return "c"
    else:
        return e


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

k = i[1]


a = list(input())


ab = 0

while ab < i[0]:

    a[ab] = get_s(ab, a[ab])
    ab += 1

p = ""


for d in range(i[0]):
    p += a[d]
 
print(p)


Measured memory_bytes: 3064
/**
  * @file pb.cpp
  * @brief atcoder

  *

  * @author yao
  * @date 2018-09-29
  */
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <utility>
#include <algorithm>
#include <functional>
#define N 1048576
#define INF ((int)1e9)
#ifdef DBG
#   define dbg_pri(x...) fprintf(stderr,x)
#else
#   define dbg_pri(x...) 0
#endif //DBG

typedef unsigned int uint;
typedef long long int lli;
typedef unsigned long long int ulli;

char s[N];

int main()
{
    int x;
    scanf("%d",&x);
    while(x%111) ++x;
    printf("%d\n",x);
    return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h> 
#define rep(i,n) for(long long i = 0; i < (long long)(n); i++)
#define per(i,n) for(long long i = (long long)(n-1);i >= 0;--i)
#define REP(i,s,t) for(long long i=s;i<t;i++)
#define PER(i,s,t) for(long long i=s;i>t;--i)
#define all(x) x.begin(),x.end()
#define sp(n) setprecision(n)
typedef long long ll;
using namespace std;
int main(){
  int n;
  cin>>n;
  if(n<1200){cout<<"ABC"<<endl;}
  else if(n<2800){cout<<"ARC"<<endl;}
  else cout<<"AGC"<<endl;
}

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

import math
import copy
def sieve_of_eratosthenes(target):
    dest = int(math.sqrt(target))
    target_list = list(range(2, target + 1))
    prime_list = []
    
    while True:
        num_min = min(target_list)
        if num_min >= dest:
            prime_list.extend(target_list)
            break
        prime_list.append(num_min)
 
 
        i = 0
 
        while True:
            if i >= len(target_list):
                break
            elif target_list[i] % num_min == 0:
                target_list.pop(i)
            i += 1
    return prime_list

def binary_search_exist(nums, target):
    left = 0
    right = len(nums)
    while left < right:
        center = int((left + right) / 2)
        if target == nums[center]:
            return True
        elif target < nums[center]:
            right = center
        else:
            left = center + 1
    return False

def binary_search(nums, target):
    left = 0
    right = len(nums)
    while left < right:
        center = int((left + right) / 2)
        if target == nums[center]:
            return center
        elif target < nums[center]:
            right = center
        else:
            left = center + 1
    return right

prime_list = sieve_of_eratosthenes(X + 1000)
if binary_search_exist(prime_list, X):
    print(X)
else:
    prime_list.append(X)
    prime_list.sort()
    r = binary_search(prime_list, X)
    print(prime_list[r + 1])

Measured memory_bytes: 7412
#include<bits/stdc++.h>
#define Set(a, b) memset(a, b, sizeof(a))
#define For(i, j, k) for (int i = j; i <= k; ++i)
#define Forr(i, j, k) for (int i = j; i >= k; --i)
using namespace std;

inline int read() {
	int x = 0, p = 1; char c = getchar();
	while(!isdigit(c)) { if(c == '-') p = -1; c = getchar(); }
	while(isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
	return x *= p;
}

inline void File() {
	freopen("arc101e.in", "r", stdin);
	freopen("arc101e.out", "w", stdout);
}

const int N = 5e3 + 10, mod = 1e9 + 7;
int dp[N][N], cur[N], n, g[N], siz[N]; 
vector<int> G[N];

inline int add(int a, int b) { return (a += b) >= mod ? a - mod : a; }

inline void dfs(int u, int f) {
	siz[u] = 1, dp[u][1] = 1;
	for (int v : G[u]) if (v != f) {
		dfs(v, u), Set(cur, 0);	
		For(i, 1, siz[u]) For(j, 0, siz[v])
			cur[i + j] = add(cur[i + j], 1ll * dp[u][i] * dp[v][j] % mod);
		siz[u] += siz[v];
		For(i, 1, siz[u]) dp[u][i] = cur[i]; 
	}
	For(i, 1, siz[u]) if (!(i & 1)) dp[u][0] = add(dp[u][0], mod - 1ll * dp[u][i] * g[i] % mod);	
}

int main() {

	n = read(), g[0] = 1;
	For(i, 2, n) {
		int x = read(), y = read();
		G[x].push_back(y), G[y].push_back(x);
		(!(i & 1)) ? g[i] = 1ll * g[i - 2] * (i - 1) % mod : 0;
	}

	dfs(1, 0);
	printf("%d", mod - dp[1][0]);
	return 0;
}


Measured memory_bytes: 97280
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <math.h>
#include <algorithm>
#include <chrono>
#include <queue>
#include <functional>

#define out(t) cout << (t) << "\n"

using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef unsigned int uint;

int popcount(uint x) {
    x -= x >> 1 & 0x55555555;
    x = (x & 0x33333333) + (x >> 2 & 0x33333333);
    x = x + (x >> 4) & 0x0F0F0F0F;
    return x * 0x01010101 >> 24;
}

int tzcnt(uint x) {
    return popcount(~x & x - 1);
}

struct Point {
    int x, y;

    Point(int p, int q) : x(p), y(q) {}
};

ll ans[100];

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

    string a, b, c;
    cin >> a >> b >> c;

    cout << a[0] << b[1] << c[2] << "\n";

    int aaa;
    cin >> aaa;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

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

        while (0 == 0) {

            int ninzu = scanner.nextInt();
            if (ninzu == 0) {
                break;
            }
            double[] tensu = new double[ninzu];

            for (int i = 0; ninzu > i; i++) {
                tensu[i] = scanner.nextInt();
            }

            double goukei = 0;

            for (int i = 0; ninzu > i; i++) {
                goukei += tensu[i];
            }

            double heikin = goukei / ninzu;

            double bunsan = 0;

            for (int i = 0; ninzu > i; i++) {
                bunsan += (tensu[i] - heikin) * (tensu[i] - heikin) / ninzu;
            }
            double bunsan2;
            bunsan2 = Math.sqrt(bunsan);

            System.out.println(bunsan2);
        }
    }
}

Measured memory_bytes: 31380
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
   ll n,k,i,j,num,ans;
  	cin>>n>>k;
  	vector<pair<ll,ll>> a(n);
  	for(i=0;i<n;i++){
      cin>>a[i].first>>a[i].second;
    }
  
  	sort(a.begin(),a.end());
  
  	for(i=0;k>0;i++){
      if(k>a[i].second){
		k-=a[i].second;
      }else{
		cout<<a[i].first<<endl;
        return 0;
      }
    }

      
      
}
		



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

int main(){
  int N;
  unsigned long long int ans = 0;
  cin >> N;
  
  vector<int> num(100001, 0);
  for (int i = 0; i < N; i++){
    int A;
    cin >> A;
    
    ans += A;
    num.at(A)++;
  }
  
  int Q;
  cin >> Q;
  
  for (int i = 0; i < Q; i++){
    int B, C;
    cin >> B >> C;
    
    ans += (C - B) * num.at(B);
    num.at(C) += num.at(B);
    num.at(B) = 0;
    
    cout << ans << endl;
  }
  
}

Measured memory_bytes: 3768
## subroutines

def erase(as, k)
  da = as[k]
  k0 = k - 1
  k1 = k + 1

  er = 0
  seq = 1

  loop do
    while as[k0] == da
      k0 -= 1
      seq += 1
    end
    while as[k1] == da
      k1 += 1
      seq += 1
    end

    return er if seq < 4

    er += seq
    seq = 0

    return er if as[k0] != as[k1] || k0 <= 0 || k1 > as.length

    da = as[k0]
  end
end

### main

loop do
  n = gets.strip.to_i
  break if n == 0

  as = n.times.map{gets.strip.to_i}
  nas = as.length
  as.unshift 0
  as.push 0
  #p as

  max_er = 0

  for k in (1..nas)
    ak = as[k]
    for i in (0..1)
      as[k] = (ak + i) % 3 + 1
      er = erase(as, k)
      max_er = er if max_er < er
    end

    as[k] = ak
  end

  puts (n - max_er)
end

Measured memory_bytes: 6276
n, k = map(int, raw_input().split())
logs = map(int, raw_input().split())

l = 0
r = 10**9


def check(v):
    c = k
    for i in logs:
        if i%v==0:
            p=i/v
        else:
            p=i/v+1
        if(p-1 <= c):
            c -= p-1
        else:
            return 0
    return 1


ans = 10**9
while l+1<r:
    mid = (l+r)/2
    if(check(mid)):
        ans = min(ans, mid)
        r = mid
    else:
        l = mid
print ans


Measured memory_bytes: 101476
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

def main():
    A = [[]for _ in range(3)]
    for i in range(3):
        A[i] = LI()
    A_ = [[]for _ in range(3)]
    for i in range(3):
        for j in range(3):
            A_[j].append(A[i][j])
    A__ = [[]for  _ in range(2)]
    for i in range(3):
        A__[0].append(A[i][i])
        A__[1].append(A[i][2 - i])

    N = I()
    B = []
    for i in range(N):
        b = I()
        B.append(b)
        for i in range(3):
            if b in A[i]:
                ind = A[i].index(b)
                A[i][ind] = 0
            if b in A_[i]:
                ind = A_[i].index(b)
                A_[i][ind] = 0
        for j in range(2):
            if b in A__[j]:
                ind = A__[j].index(b)
                A__[j][ind] = 0
    ans_list = []
    for i in range(3):
        ans_list.append(sum(A[i]))
        ans_list.append(sum(A_[i]))
    for j in range(2):
        ans_list.append(sum(A__[j]))

    if 0 in ans_list:
        print('Yes')
    else:
        print('No')






if __name__ == "__main__":
    main()

Measured memory_bytes: 68008
#include<stdio.h>
int main(){
  int n,k,i,j,t,a=0,b=0,c=0;
  int a1[201],a2[201],a3[201],tensu[201];

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

  for(t=0;t<201;t++){
    tensu[t]=0;
  }
  
  //テ、ツサツ」テ・ツ?・テ」ツ?甘」ツ?療」ツ?セテ」ツ??
  //----------------------
  for(j=0;j<n;j++){
    for(k=j+1;k<n;k++){
      if(a1[j] == a1[k]){
	a+=1;
      }
    }
    for(k=j-1;k>=0;k--){
      if(a1[j] == a1[k]){
	a+=1;
      }
    }
    
    if(a == 0){
      tensu[j]+=a1[j];
    }
    a=0;
  }

  k=j=0;
  
  //-----------------------
  for(j=0;j<n;j++){
    for(k=j+1;k<n;k++){
      if(a2[j] == a2[k]){
	b+=1;
      }
    }
    for(k=j-1;k>=0;k--){
      if(a2[j] == a2[k]){
	b+=1;
      }
    }
    
    if(b == 0){
      tensu[j]+=a2[j];
    }
    b=0;
  }

  k=j=0;
  // ----------------------
  for(j=0;j<n;j++){

    for(k=j+1;k<n;k++){
      if(a3[j] == a3[k]){
        c+=1;
      }
    }
    for(k=j-1;k>=0;k--){
      if(a3[j] == a3[k]){
	c+=1;
      }
    }
    if(c == 0){
      tensu[j]+=a3[j];
    }
    c=0;
  }
  i=k=j=0;
  //----------
  for(i=0;i<n;i++){
    printf("%d\n",tensu[i]);
  }
  
  return 0;
  
}

Measured memory_bytes: 600
def main():
    N  = int(input())
    A1 = list(map(int, input().split())) 
    A2 = list(map(int, input().split())) 
    m = 0

    for i in range(N):
        temp = 0
        for j in range(i+1):
            temp += A1[j]
        for j in range(i,N):
            temp += A2[j]
        if temp > m:
            m = temp
    print(m)



if __name__ == '__main__':
    main()


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

int main() {
    ll a, b, c, d;
    cin >> a >> b >> c >> d;
    while (true) {
        c -= b;
        if (c <= 0) {
            cout << "Yes" << endl;
            return 0;
        }
        a -= d;
        if (a <= 0) {
            cout << "No" << endl;
            return 0;
        }
    }

    return 0;
}


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

N_str = str(N)
N_keta = []
N_sum = 0

for i in range(len(N_str)):
    N_keta.append(int(N_str[i]))
N_sum = sum(N_keta)

if N % N_sum == 0:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int inf = 1e9 + 7;
const ll longinf = 1LL << 60;
const ll mod = 1e9 + 7;

int main() {
    long double Q, H, S, D, N;
    cin >> Q >> H >> S >> D >> N;

    vector<pair<long double, string>> v;
    v.push_back({Q * 4, "Q"});
    v.push_back({H * 2, "H"});
    v.push_back({S, "S"});
    v.push_back({D / 2, "D"});
    sort(v.begin(), v.end());
    ll ans = 0;

    if(v[0].second == "D") {
        ans += D * ((ll)N / 2) + v[1].first * ((ll)N % (ll)2);
    } else {
        ans += (ll)v[0].first * (ll)N;
    }

    cout << ans;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define PREP(i, s, x) for(ll i = (s); i < (x); i++)
#define MREP(i, s, x) for(ll i = (s); i >= (x); i--)
#define REP(i, x) PREP(i, 0, x)
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
template<typename T> inline bool chmax(T &a, T b) { return ((a < b) ? (a = b, true) : (false)); }
template<typename T> inline bool chmin(T &a, T b) { return ((a > b) ? (a = b, true) : (false)); }

// variable -------------------------------------------

constexpr ll INF = (1ll << 59);
constexpr ll MOD = 1000000007ll;

// structure ------------------------------------------

// function -------------------------------------------

// main -----------------------------------------------

int main() {
    char s;
    cin >> s;
    if(s >= 'A' && s <= 'Z'){
        cout << "A" << endl;
    } else {
        cout << "a" << endl;
    }
    return 0;
}


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

using namespace std;
typedef long long ll;
  
int n, m, R;
int r[10];
int g[205][205];
int ans;
    
int main(){
  cin >> n >> m >> R;
  for(int i=0; i<R; i++) {
    cin >> r[i];
    r[i]--;
  }
  memset(g, 63, sizeof(g));
  for(int i=0; i<m; i++) {
                int u, v, w;
    cin >> u >> v >> w;
    u--; v--;
    g[u][v] = g[v][u] = w;
  }
  for (int k=0; k<n; k++)
    for (int i=0; i<n; i++)
      for (int j=0; j<n; j++)
        g[i][j] = min(g[i][j], g[i][k]+g[k][j]);
  
  sort(r, r+R);
  ans = (1<<29);
  do {
    int cost = 0;
    for(int i=1; i<R; i++) {
      cost += g[r[i-1]][r[i]];
    }
    ans = min(ans, cost);
  } while (next_permutation(r, r+R));
  printf("%d\n", ans);
  return 0;
}


Measured memory_bytes: 384
import java.io.IOException;
import java.util.Scanner;
public class Main {

	public static void main(String[] args) throws IOException{
		// TODO ?????????????????????????????????????????????
          Scanner sc = new Scanner(System.in);
          int w = sc.nextInt();
          int h = sc.nextInt();
          int x = sc.nextInt();
          int y = sc.nextInt();
          int r = sc.nextInt();
          
          if(x<=w-r && x>=r && y<=h-r && y>=r){System.out.println("Yes");}
          else{System.out.println("No");}
          
          
	}

}

Measured memory_bytes: 26316
#include <bits/stdc++.h>
using namespace std;
template<typename T>
void fin(T a){
  cout<<a<<endl;
  exit(0);
}
struct tree{
  vector<vector<int>> G,son,ancestor;
  vector<int> depth,parent;
  queue<int> que;
  int root=-1;
  bool made_lca=false;

  tree(int n):G(n),son(n),parent(n,-1),depth(n,-1),ancestor(n){
    for(int i=0;i<n;i++)ancestor[i].resize(30);
  }

  void add_edge(int u,int v){
    G[u].push_back(v);
    G[v].push_back(u);
  }

  inline void reset_root(){
    root=-1;
    fill(depth.begin(),depth.end(),-1);
    fill(parent.begin(),parent.end(),-1);
    for(auto &p:ancestor)for(int &q:p)q=-1;
    for(auto &p:son)p.resize(0);
    made_lca=false;
  }

  void have_root(int r){
    reset_root();
    root=r;
    depth[r]=0;
    que.push(r);
    while(que.size()){
      int p=que.front();que.pop();
      for(int q:G[p]){
        if(parent[p]==q)continue;
        son[p].push_back(q);
        parent[q]=p;
        depth[q]=depth[p]+1;
        que.push(q);
      }
    }
  }

  inline void make_lca(){
    assert(~root);
    for(int i=0;i<G.size();i++)ancestor[i][0]=parent[i];
    for(int j=1;j<30;j++)
      for(int i=0;i<G.size();i++)
        if(~ancestor[i][j-1])
          ancestor[i][j]=ancestor[ancestor[i][j-1]][j-1];
    made_lca=1;
  }

  int lca(int u,int v){
    if(!made_lca)make_lca();
    if(depth[u]>depth[v])swap(u,v);
    int diff=depth[v]-depth[u],cnt=0;
    while(diff){
      if(diff&1)v=ancestor[v][cnt];
      cnt++;
      diff>>=1;
    }
    if(u==v)return u;
    for(int k=28;k>=0;k--)
      if(ancestor[u][k]!=ancestor[v][k])
        u=ancestor[u][k],v=ancestor[v][k];
    return ancestor[u][0];
  }
};

int n,odd,now[4],ans[223456],s=-1;
int f(int a,int b,int c){
  int v[3]={a,b,c};
  for(int p:v)if(now[p]*3+p<=n)return now[p]++*3+p;
  return -1;
}

signed main(){
  cin>>n;
  tree t(n);
  for(int i=1;i<n;i++){
    int u,v;cin>>u>>v;u--;v--;
    t.add_edge(u,v);
  }
  t.have_root(0);
  for(int i=0;i<n;i++)odd+=t.depth[i]&1;
  if(odd<=n/3)s=1;
  if(n-odd<=n/3)s=0;
  for(int i=0;i<n;i++){
    if((t.depth[i]&1)==s)ans[i]=f(3,2,1);
    else if(~s)ans[i]=f(1,2,3);
    else ans[i]=f(1+(t.depth[i]&1),3,2-(t.depth[i]&1));
  }
  for(int i=0;i<n;i++)cout<<ans[i]<<" ";cout<<endl;
}


Measured memory_bytes: 52992
#include <bits/stdc++.h>
using namespace std;
int main() {
  string S, T, U;
  int A, B;
  cin >> S >> T;
  cin >> A >> B;
  cin >> U;

  if (U == S) cout << A-1 << " " << B << endl;
  else cout << A << " " << B-1 << endl;
  return 0;
}


Measured memory_bytes: 3588
#include "bits/stdc++.h"
using namespace std;
#define REP(i, n) for(ll i = 0;i < n;i++)
#define ll long long
#define MOD 1000000007
using vi = vector<ll>; // intの1次元の型に vi という別名をつける
using vvi = vector<vi>; // intの2次元の型に vvi という別名をつける

int a,b,c;

int main(){
  ll ans=0;
  cin >> a >> b>>c;
  if ((a+b+c)>=22){
  cout<<"bust"<<endl;
  }else{
  cout<<"win"<<endl;
  }
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i, n) for (int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
 
int main(void){
    int a, b;
    cin>>a>>b;
    int ans = 0;
    if(a>b){
        ans = a-1;
    }
    else ans = a;
    cout<<ans<<endl;
    return 0;
}   

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

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

    if (a > b) {
        cout << 0 << endl;
    } else {
        n--;
        if (a != b) n--;
        if (n < 0) cout << 0 << endl;
        else cout << b*n-a*n+1 << endl;
    }
}

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

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    rep(i, n) cin >> a[i];

    rep(i, n-k) {
        if (a[i] < a[i+k]) {
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }
    }
    return 0;
}

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

main(){

  ll n,m;
  cin>>n>>m;
  vector<ll> a(n);
  rep(i,n)cin>>a[i];
  vector<ll> b(m),c(m);
  rep(i,m)cin>>b[i]>>c[i];

  priority_queue<pair<ll,ll>> que;
  rep(i,n)que.emplace(a[i],1);
  rep(i,m)que.emplace(c[i],b[i]);

  ll sum=0,card=0;
  while(card<n){
    ll val,num;
    tie(val,num)=que.top();
    que.pop();
    if(card+num<n){
      sum+=val*num;
      card+=num;
    }
    else{
      while(card<n){
        sum+=val;
        card++;
      }
    }
  }
  cout<<(sum)<<endl;


}

Measured memory_bytes: 8176
#include<iostream>
#include<string>
#include<vector>
#include<utility>
#include<queue>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<complex>
#define INF -2047483647
#define llINF 9223372036854775807
#define pb push_back
#define mp make_pair 
#define F first
#define S second
#define ll long long

using namespace std;
ll ma=INF;
int open[100][11];
int mise[100][10];
int n;
int misec[100]={};
void dfs(int depth,int total,int bits){
  if(depth==10){
    ll sum=0;
    int zero=0;
    for(int i=0;i<n;i++){
      int cnt=0;
      int bits2=bits;
      for(int j=0;j<10;j++){
	if((mise[i][j]&(bits2>>j)))cnt++;
      }
      if(cnt==0)zero++;
      sum+=(ll)open[i][cnt];
    }
    if(zero!=n){
      ma=max(ma,sum);
 
    }
    return;
  }
  dfs(depth+1,total+1,bits+(1<<depth));
  dfs(depth+1,total,bits);
}
int main(){
  cin>>n;
  for(int i=0;i<n;i++){
    for(int j=0;j<10;j++){
      cin>>mise[i][j];
    }
  }
  for(int i=0;i<n;i++)
    for(int j=0;j<11;j++){
      cin>>open[i][j];
    }
  dfs(0,0,0);
  cout<<ma<<endl;
  return 0;
}


Measured memory_bytes: 256
import bisect

a,b,q = map(int,input().split())

s = [int(input()) for i in range(a)]
t = [int(input()) for i in range(b)]
x = [int(input()) for i in range(q)]

ans = 10**100

for i in range(q):
    ans = 10**100
    s_idx = bisect.bisect_left(s,x[i])
    t_idx = bisect.bisect_left(t,x[i])
    s_idx -= 1
    t_idx -= 1
    #print(x[i],s_idx,t_idx)
    for j in range(2):
        for k in range(2):
            ans = min(ans,abs(x[i] - s[min(s_idx+j,a-1)]) + abs(s[min(s_idx+j,a-1)] - t[min(t_idx+k,b-1)]))
            ans = min(ans,abs(x[i] - t[min(t_idx+k,b-1)]) + abs(s[min(s_idx+j,a-1)] - t[min(t_idx+k,b-1)]))
            
    print(ans)

Measured memory_bytes: 93400
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    int N;
    cin >> N;
    vector<int> H(N);
    for(int i=0; i<N; i++) cin >> H[i];
    vector<int> C(N);
    C[0] = 0;
    C[1] = abs(H[1] - H[0]);
    for(int i=2; i<N; i++) {
        C[i] = min(C[i-1] + abs(H[i-1] - H[i]), C[i-2] + abs(H[i-2] - H[i]));
    }
    cout << C[N-1] << endl;
}

Measured memory_bytes: 3996
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); i++) 
#define all(v) begin(v),end(v)
using ll = long long;

int main() {
  int n;cin>>n;
  vector<pair<string,int>> pr(n);
  int cnt=0;
  rep(i,n){
    string s;int p;cin>>s>>p;
    pr[i]=make_pair(s,p);
    cnt+=p;
  }
  string x;cin>>x;
  int cnt1=0;
  rep(i,n){
    cnt1+=pr[i].second;
    if(x==pr[i].first)break;
  }
  cout<<cnt-cnt1<<endl;
}

Measured memory_bytes: 3616
#include<algorithm>
#include<iostream>
#include<vector>
#include<string>
#define rep(i, start, end) for (int i = (int)start; i < (int)end; ++i)
#define rrep(i, start, end) for (int i = (int)start - 1; i >= (int)end; --i)
#define all(x) (x).begin(), (x).end()
using namespace std;
using ll = long long;
template<typename T> inline bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return 0;}
template<typename T> inline bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return 0;}

void dfs(const vector<vector<int>>& graph, int node, vector<int>& group, int now_group) {
    group[node] = now_group;
    for (auto& nxt_node : graph[node]) {
        if (group[nxt_node] < 0) {
            dfs(graph, nxt_node, group, now_group);
        }
    }
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, M;
    cin >> N >> M;
    int u, v;
    vector<vector<int>> graph(N);
    rep(i, 0, M) {
        cin >> u >> v;
        --u, --v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    vector<int> group(N, -1);
    int now_group = 0;
    rep(u, 0, N) {
        if (group[u] < 0) {
            dfs(graph, u, group, now_group);
            ++now_group;
        }
    }
    vector<int> cnt(now_group, 0);
    rep(i, 0, N) {
        ++cnt[group[i]];
    }
    sort(all(cnt));
    int ans = 0;
    int cumsum = 0;
    rep(i, 0, now_group) {
        cnt[i] -= cumsum;
        ans += cnt[i];
        cumsum += cnt[i];
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 24296
#include <bits/stdc++.h>
#define fst first
#define snd second
#define fore(i,a,b) for(int i=a,ThxDem=b;i<ThxDem;++i)
#define pb push_back
#define ALL(s) s.begin(),s.end()
#define FIN ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define SZ(s) int(s.size())
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;

double EPS=1e-9;
struct pt {  // for 3D add z coordinate
	double x,y;
	pt(double x, double y):x(x),y(y){}
	pt(){}
	double norm2(){return *this**this;}
	double norm(){return sqrt(norm2());}
	bool operator==(pt p){return abs(x-p.x)<=EPS&&abs(y-p.y)<=EPS;}
	pt operator+(pt p){return pt(x+p.x,y+p.y);}
	pt operator-(pt p){return pt(x-p.x,y-p.y);}
	pt operator*(double t){return pt(x*t,y*t);}
	pt operator/(double t){return pt(x/t,y/t);}
	double operator*(pt p){return x*p.x+y*p.y;}
//	pt operator^(pt p){ // only for 3D
//		return pt(y*p.z-z*p.y,z*p.x-x*p.z,x*p.y-y*p.x);}
	double angle(pt p){ // redefine acos for values out of range
		return acos(*this*p/(norm()*p.norm()));}
	pt unit(){return *this/norm();}
	double operator%(pt p){return x*p.y-y*p.x;}
	// 2D from now on
	bool operator<(pt p)const{ // for convex hull
		return x<p.x-EPS||(abs(x-p.x)<=EPS&&y<p.y-EPS);}
	bool left(pt p, pt q){ // is it to the left of directed line pq?
		return (q-p)%(*this-p)>EPS;}
	pt rot(pt r){return pt(*this%r,*this*r);}
	pt rot(double a){return rot(pt(sin(a),cos(a)));}
};
pt ccw90(1,0);
pt cw90(-1,0);

int main(){FIN;
	double a,b; cin>>a>>b;
	pt h(0,a),m(0,b);
	double x,y; cin>>x>>y;
	x+=y/60;
	
	x=360./12*x;
	y=360./60*y;
	x=x*acos(-1)/180.;
	y=y*acos(-1)/180.;
	
	x=2*acos(-1)-x;
	y=2*acos(-1)-y;
	
	h=h.rot(x);
	m=m.rot(y);
	cout<<fixed<<setprecision(10)<<(h-m).norm()<<"\n";
}

Measured memory_bytes: 4144
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define fi first
#define se second
#define pb push_back
#define forn(i,n) for(int i=0;i<(n);i++)
#define for1(i,n) for(int i=1;i<=n;i++)
#define forr(i,n) for(int i=n;i>=0;i--)
#define all(x) x.begin(), x.end()
const int MAXN = 1e5 +5;

void fio(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
}

LL dp[MAXN][3];
int main(){
  fio();
  int n ;cin>>n;
  vector<LL> a(n), b(n),c(n);
  forn(i,n) cin>>a[i]>>b[i]>>c[i];

  dp[0][0] = a[0];
  dp[0][1] = b[0];
  dp[0][2] = c[0];

  for1(i,n-1){
  	dp[i][0] = a[i] + max(dp[i-1][1], dp[i-1][2]);
  	dp[i][1] = b[i] + max(dp[i-1][0], dp[i-1][2]);
  	dp[i][2] = c[i] + max(dp[i-1][1], dp[i-1][0]);
  }
  LL an = 0;
  forn(i,3) an = max(an, dp[n-1][i]);
  cout<<an<<endl;
    return 0;
}

Measured memory_bytes: 4992
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdint>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <regex>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <utility>
#include <vector>

using namespace std;
using ll = long long;

#define EPS (1e-7)

int main() {
  ll N;
  cin >> N;
  vector<ll> H(N);
  for (ll i = 0; i < N; i++) {
    cin >> H[i];
  }
  ll maxvalue = 0;
  for (ll i = 0; i < N; i++) {
    if (H[i] + 1 < maxvalue) {
      cout << "No" << endl;
      return 0;
    }
    maxvalue = max(maxvalue, H[i]);
  }
  cout << "Yes" << endl;
  return 0;
}


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

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define eb emplace_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second

using vint=vector<int>;
using pint=pair<int,int>;
using vpint=vector<pint>;

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

template<class A,class B>
ostream& operator<<(ostream& ost,const pair<A,B>&p){
    ost<<"{"<<p.first<<","<<p.second<<"}";
    return ost;
}

template<class T>
ostream& operator<<(ostream& ost,const vector<T>&v){
    ost<<"{";
    for(int i=0;i<v.size();i++){
        if(i)ost<<",";
        ost<<v[i];
    }
    ost<<"}";
    return ost;
}

inline int topbit(unsigned long long x){
    return x?63-__builtin_clzll(x):-1;
}

inline int popcount(unsigned long long x){
    return __builtin_popcountll(x);
}

inline int parity(unsigned long long x){
    return __builtin_parity(x);
}

int H,W;
char fld[333][333];

const int B=1000;
int acc[2222][2222];
int solve(){
    memset(acc,0,sizeof(acc));
    rep(i,H)rep(j,W){
        if(fld[i][j]=='#')acc[i+B][j+B]++;
    }

    rep(i,2222)rep(j,2222){
        if(i&&j)acc[i][j]+=acc[i-1][j-1];
    }

    int ret=0;
    rep(i,H)rep(j,W){
        if(fld[i][j]=='.')continue;
        for(int t=1;;t++){
            int ii=i+t;
            int jj=j+t;
            if(ii>=H||jj>=W)break;
            if(fld[ii][jj]=='.')continue;
            ret+=acc[ii-t+B][jj+t+B]-acc[ii-2*t-1+B][jj-1+B];
            ret+=acc[ii+t+B][jj-t+B]-acc[ii-1+B][jj-2*t-1+B];
        }
    }
    return ret;
}

bool ex(int y,int x){
    if(y<0||y>=H||x<0||x>=W)return false;
    return fld[y][x]=='#';
}

signed main(){
    cin>>H>>W;
    rep(i,H)cin>>fld[i];

    int ans=solve();
    rep(i,H)reverse(fld[i],fld[i]+W);
    ans+=solve();

    rep(i,H)rep(j,W){
        if(fld[i][j]=='.')continue;
        for(int t=1;;t++){
            int ii=i+t;
            int jj=j+t;
            if(ii>=H||jj>=W)break;
            if(fld[ii][jj]=='.')continue;
            if(ex(ii-t,jj+t))ans--;
            if(ex(ii-2*t,jj))ans--;
            if(ex(ii+t,jj-t))ans--;
            if(ex(ii,jj-2*t))ans--;
        }
    }
    cout<<ans<<endl;
    return 0;
}

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

int main() {
  int A,B;
  cin >> A >> B;
  
  if(1 <= A && A <= 9 && 1 <= B && B <= 9){
    cout << A * B << endl;
  }
  
  else{
    cout << -1 << endl;
  }
}

Measured memory_bytes: 256
#!/usr/bin/env python3

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

N = int(input())
C = input()

left = 0
right = N-1
count = 0

while left < right:
    if C[left] == 'W' and C[right] == 'R':
        count += 1
        left += 1
        right -= 1

    if C[left] == 'R':
        left += 1
    if C[right] == 'W':
        right -= 1

print(count)


Measured memory_bytes: 9520
#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>
#include <iomanip>
#include <limits>
using namespace std;
// 素因数分解
typedef pair<long long, long long> P;
vector<P> prime_factorize(long long n)
{
vector<P> res;
for (long long p = 2; p * p <= n; ++p)
{
if (n % p != 0)
continue;
int num = 0;
while (n % p == 0)
{
++num;
n /= p;
}
res.push_back(make_pair(p, num));
}
if (n != 1)
res.push_back(make_pair(n, 1));
return res;
}
// 因数分解
long long gcd(long long x, long long y)
{
  if (y == 0)
  {
    return x;
  }
  else
  {
    return gcd(y, x % y);
  }
}
const int MOD = 1000000007;
typedef long long int ll;
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define rep(i, n) for (int i = 0; i < (n); i++)

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

    return 0;
}

Measured memory_bytes: 3592
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<math.h>
using namespace std;
typedef long long ll;
typedef vector<int> VI;
#define REP(i,n) for(int i=0;i<n;i++)
#define eREP(i,n) for(int i=0;i<=n;i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define eFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define SORT(c) sort((c).begin(),(c).end())
#define rSORT(c) sort((c).rbegin(),(c).rend())
#define LB(x,a) lower_bound((x).begin(),(x).end(),(a))
#define UB(x,a) upper_bound((x).begin(),(x).end(),(a))
#define INF 1000000000
#define LLINF 9223372036854775807
#define mod 1000000007
//vector<vector<int> > dp;
//vector<vector<vector<int> > > vvvi;
//dp=vector<vector<int> >(N, vector<int>(M,0));
//vector<pair<int,int> > v;
//v.push_back(make_pair(x,y));
int N,M;
bool G[60][60];
bool vis[60];

void dfs(int x){
	if(vis[x])return;
	vis[x]=true;
	REP(i,N){
		if(G[x][i]){
			dfs(i);
		}
	}
}
int main(){
cin.tie(0);
ios::sync_with_stdio(false);

	int ans=0;
	cin>>N>>M;
	REP(i,N){
		REP(j,N)
			G[i][j]=false;
	}
	VI A(M);
	VI B(M);
	
	REP(i,M){
		cin>>A[i]>>B[i];
		A[i]--;
		B[i]--;
		G[A[i]][B[i]]=true;
		G[B[i]][A[i]]=true;
	}
	REP(i,M){
		G[A[i]][B[i]]=false;
		G[B[i]][A[i]]=false;
		REP(i,N)vis[i]=false;
		dfs(0);
		bool brige=false;
		REP(i,N)if(!vis[i])brige=true;
		if(brige)ans++;
		
		G[A[i]][B[i]]=true;
		G[B[i]][A[i]]=true;
	}
	
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
card = ["a","b","c"]
S = dict()
for i in card:
    S[i] = input()
    
turn = "a"
while(True):
    if len(S[turn])==0:
        print(turn.upper())
        break
    else:
        next_turn = S[turn][0]
        S[turn] = S[turn][1:]
        turn = next_turn

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

using ll = long long;

ll gcd(ll a, ll b) {
    if(b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

ll lcm(ll a, ll b) {
    int g = gcd(a, b);
    a /= g;
    b /= g;
    return a * b * g;
}

int main() {
    vector<ll> a(3), m(3);
    while(true) {
        for(int i=0; i<3; ++i) {
            cin >> a[i] >> m[i];
        }
        if(m[0] == 0) {
            break;
        }
        vector<ll> cnt(3, 1);
        for(int i=0; i<3; ++i) {
            ll now = (a[i] % m[i]);
            while(now != 1) {
                cnt[i]++;
                (now *= a[i]) %= m[i];
            }
        }
        ll res = lcm(cnt[0], cnt[1]);
        res = lcm(res, cnt[2]);
        cout << res << endl;
    }
}


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

#define rep(i, n) for (int i = 0; i < n; ++i)
#define ALL(a) (a).begin(), (a).end()
#define SZ(x) ((int)(x).size())

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

using ll = long long;
using P = pair<int, int>;
using llP = pair<ll, ll>;
using DoP = pair<double, double>;

const int di[] = {0, 1, 0, -1, 1, 1, -1, -1};
const int dj[] = {1, 0, -1, 0, 1, -1, 1, -1};
const int INF = 1 << 29;
const ll INF64 = 1ll << 45;
const int mod = 1000000007;

struct mint
{
  ll x; // typedef long long ll;
  mint(ll x = 0) : x((x % mod + mod) % mod) {}
  mint operator-() const { return mint(-x); }
  mint &operator+=(const mint a)
  {
    if ((x += a.x) >= mod)
      x -= mod;
    return *this;
  }
  mint &operator-=(const mint a)
  {
    if ((x += mod - a.x) >= mod)
      x -= mod;
    return *this;
  }
  mint &operator*=(const mint a)
  {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const
  {
    mint res(*this);
    return res += a;
  }
  mint operator-(const mint a) const
  {
    mint res(*this);
    return res -= a;
  }
  mint operator*(const mint a) const
  {
    mint res(*this);
    return res *= a;
  }
  mint pow(ll t) const
  {
    if (!t)
      return 1;
    mint a = pow(t >> 1);
    a *= a;
    if (t & 1)
      a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const
  {
    return pow(mod - 2);
  }
  mint &operator/=(const mint a)
  {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const
  {
    mint res(*this);
    return res /= a;
  }
};

int main()
{
  int n;
  ll k;
  cin >> n >> k;
  vector<int> a(n+1);
  rep(i, n) cin >> a[i+1];
  int now = 1;
  vector<int> city(n), num(n+1,-1);
  vector<bool> visit(n+1, false);
  visit[1] = true;
  city[0] = 1;
  num[1] = 0;
  rep(i, n) {
    now = a[now];
    if(visit[now]) {
      if(k < num[now]) {
        cout << city[k] << endl;
        return 0;
      }
      int loop = i+1-num[now];
      k = (k-num[now])%loop;
      cout << city[num[now]+k] << endl;
      return 0;
    }
    visit[now] = true;
    city[i+1] = now;
    num[now] = i+1;
  }
}

Measured memory_bytes: 5640
#include <stdio.h>

int main(void) {
	int asumikana,kitamuraeri;
	int mimorisuzuko,tokuisora;
	int tomatuharuka,igutiyuka;
	int murakawarie,isikawakaito;
	double sakuraayane=10000000.0;
	if(scanf("%d%d",&asumikana,&kitamuraeri)!=2)return 1;
	if(scanf("%d%d",&mimorisuzuko,&tokuisora)!=2)return 1;
	if(scanf("%d%d",&tomatuharuka,&igutiyuka)!=2)return 1;
	for(murakawarie=0;murakawarie*tomatuharuka<kitamuraeri;murakawarie++) {
		for(isikawakaito=0;isikawakaito*igutiyuka<=kitamuraeri-murakawarie*tomatuharuka;isikawakaito++) {
			if(murakawarie+isikawakaito>0) {
				double nakamurayuuiti=tomatuharuka*murakawarie;
				double sakagutidaisuke=igutiyuka*isikawakaito;
				double tanedarisa=(mimorisuzuko*nakamurayuuiti+tokuisora*sakagutidaisuke)/(nakamurayuuiti+sakagutidaisuke);
				double minaseinori=asumikana-tanedarisa;
				if(minaseinori<0)minaseinori=-minaseinori;
				if(minaseinori<sakuraayane)sakuraayane=minaseinori;
			}
		}
	}
	printf("%.15f\n",sakuraayane);
	return 0;
}

Measured memory_bytes: 636
a = list(map(int, input().split()))
b = list(map(int, input().split()))
L = []
for i in range(a[0]):
    L.append(list(map(int, input().split())))

res = 0
for i in range(a[0]):
    if sum([L[i][ii] * b[ii] for ii in range(a[1])]) + a[2] > 0:
        res += 1

print(res)



Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
int main () {
  int H, W;
  cin >> H >> W;
  int amari2 = 0;
  int odd = 0;
  if (H % 2) {
    amari2 += (W / 2);
  }
  if (W % 2) {
    amari2 += (H / 2);
  }
  if ((H % 2) && (W % 2)) {
    odd = 1;
  }
  vector<int>alpha(26, 0);
  for (int i = 0; i < H; i ++) {
    for (int j = 0; j < W; j ++) {
      char c;
      cin >> c;
      alpha[(int)c - (int)'a'] ++;
    }
  }
  for (int i = 0; i < 26; i ++) {
    if (alpha[i] % 2) odd --;
    if (alpha[i] % 4 == 2) amari2 --;
  }
  cout << ((odd < 0 || amari2 < 0) ? "No" : "Yes") << endl;
}

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


int main()
{
	long long t, c, x;
	cin >> t;
	c=0;
	for(long long i=0; i<t; i++)
	{
		cin >> x;
		if(i%2==0 && x%2==1)
			c++;
	}
	cout << c << endl;
	return 0;
}

Measured memory_bytes: 3160
#include <stdio.h>

int main() {
  int number_n;
  scanf("%d", &number_n);
  if(number_n % 2 == 0) {
    printf("%d\n", (number_n / 2) * (number_n / 2));
  } else {
    printf("%d\n", (number_n / 2) * (number_n /2 + 1));
  }
  return 0;
}


Measured memory_bytes: 128
/* ファイル名：ITP1_2_A	*/
/* 内容：２つの整数 a, b を読み込んで、a と b の大小関係を出力する	*/

/* include	*/
#include <stdio.h>

/* 外部変数宣言	*/

/* プロトタイプ宣言	*/

/* 関数名:main	*/
/* 処理内容:２つの整数 a, b を読み込んで、a と b の大小関係を出力する	*/
int main( void )
{
	/* 内部変数定義	*/
	int a;	/* 1つ目の整数a	*/
	int b;	/* 2つ目の整数b	*/
	
	scanf("%d %d",&a,&b);	/* 	aとbを読み込む	*/
	
	if( a < b ){
		printf("a < b\n");
	}
	else if( a > b ){
		printf("a > b\n");
	}
	else{
		printf("a == b\n");
	}
	
	return 0;
}



Measured memory_bytes: 2044
#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(c) (c).begin(),(c).end()
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
#define MINF(a) memset(a,0x3f,sizeof(a))
#define POW(n) (1LL<<(n))
#define IN(i,a,b) (a <= i && i <= b)
using namespace std;
template <typename T> inline bool CHMIN(T& a,T b) { if(a>b) { a=b; return 1; } return 0; }
template <typename T> inline bool CHMAX(T& a,T b) { if(a<b) { a=b; return 1; } return 0; }
template <typename T> inline void SORT(T& a) { sort(ALL(a)); }
template <typename T> inline void REV(T& a) { reverse(ALL(a)); }
template <typename T> inline void UNI(T& a) { sort(ALL(a)); a.erase(unique(ALL(a)),a.end()); }
const int MOD = 1000000007;
const int INF = 0x3f3f3f3f3f3f3f3f;
const double EPS = 1e-10;
/* ---------------------------------------------------------------------------------------------------- */

int N;
int a[1010];

signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(10);

  cin >> N;
  REP(i,N) cin >> a[i];
  int s = 0, t = 0;
  REP(i,N) {
    if (i % 2 == 0) s += max(0LL,a[i]);
    else t += max(0LL,a[i]);
  }
  int ans = max(s,t);
  vector<int> v;
  int l, r, sz = N;
  if (ans == 0) {
    l = 0, r = N-1;
    int pos = max_element(a,a+N)-a;
    while (l < pos) {
      v.push_back(1);
      sz--;
      l++;
    }
    while (pos < r) {
      v.push_back(sz--);
      r--;
    }
    ans = a[pos];
  } else if (s > t) {
    l = 0, r = (N-1)/2*2;
    if (r+1 != N) {
      v.push_back(sz--);
    }
    while (l < N && a[l] < 0) {
      v.push_back(1);
      v.push_back(1);
      sz -= 2;
      l += 2;
    }
    while (r >= 0 && a[r] < 0) {
      v.push_back(sz--);
      v.push_back(sz--);
      r -= 2;
    }
    while (r-l > 2) {
      if (a[l+2] < 0) v.push_back(3);
      else v.push_back(2);
      l += 2;
    }
    v.push_back(2);
  } else {
    l = 1, r = N/2*2-1;
    v.push_back(1);
    sz--;
    if (r+1 != N) {
      v.push_back(sz--);
    }
    while (l < N && a[l] < 0) {
      v.push_back(1);
      v.push_back(1);
      sz -= 2;
      l += 2;
    }
    while (r >= 0 && a[r] < 0) {
      v.push_back(sz--);
      v.push_back(sz--);
      r -= 2;
    }
    while (r-l > 2) {
      if (a[l+2] < 0) v.push_back(3);
      else v.push_back(2);
      l += 2;
    }
    v.push_back(2);
  }
  cout << ans << endl;
  cout << v.size() << endl;
  for (int vv : v) cout << vv << endl;

  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
ll N;
string s;
int main(){
  cin>>N>>s;bool y=false;vector<ll>a(N);
  for(ll I=0;I<2;I++){
    for(ll J=0;J<2;J++){
  a[0]=I;a[1]=J;
    for(ll i=1;i<N-1;i++)
      if((a[i]==1 && s[i]=='o')||(a[i]==0 && s[i]=='x')){
      a[i+1]=1-a[i-1];
      }else
        a[i+1]=a[i-1];
      bool x=true;
 if((a[N-1]==1 && s[N-1]=='o')||(a[N-1]==0 && s[N-1]=='x')){
      if(a[N-2]==a[0])x=false;
      }else{
  if(a[N-2]!=a[0])x=false;
 }
      if((a[0]==1 && s[0]=='o')||(a[0]==0 && s[0]=='x')){
      if(a[N-1]==a[1])x=false;
      }else{
  if(a[N-1]!=a[1])x=false;
 }if(x==true){y=true;break;}
        
    }if(y)break;
  }if(!y)
      cout<<-1<<endl;
  else{
  string S="";
    for(ll i=0;i<N;i++)
      if(a[i]==0)
        S+='S';
    else
      S+='W';
  cout<<S<<endl;
  }
  return 0;
}

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

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

  if (s[2] == s[3] && s[4] == s[5])
    cout << "Yes" << endl;
  else 
    cout << "No" << endl;

  return 0;
}


Measured memory_bytes: 256
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
    
    def reset(self):
        t = self.tree
        for i in range(len(t)):
            t[i] = 0

get_ints = lambda: [int(st) for st in input().split()]
N=int(input())
inarr=get_ints()
sorted_in = sorted(inarr)
comb = N*(N+1) // 2

bit = Bit(2*N+1)
def binsearch(lft, rgt):
    half = (lft + rgt) // 2
    if lft >= half:
        return half
    summed = 0
    res = 0
    bit.reset()
    bit.add(N, 1)
    for x in inarr:
        value = 1 if x >= sorted_in[half] else -1
        summed += value
        count = bit.sum(N + summed)
        bit.add(N + summed, 1)
        res += count
    return binsearch(half, rgt) if res >= comb // 2 else binsearch(lft, half)

res = binsearch(0, N)
print(sorted_in[res])


Measured memory_bytes: 63984
#include<iostream>
using namespace std;
int main(){
int s[31],m;
for(int i=1;i<=28;i++){
cin >> m;
s[m]=1;
}
for(int i=1;i<=30;i++){
if(s[i]!=1){
cout << i << endl;
}
}
return 0;
}


Measured memory_bytes: 3060