akhauriyash/Code-Regression huggingface dataset:
#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 x,a=100,count=0;
    cin >> x;
    while(a < x){
        a += a/100;
        count++;
    }
    cout << count << endl;
    return 0;
}

Measured memory_bytes: 3596
import math
n,p=map(int,input().split(' '))
k=0
dio=math.sqrt(p)
jo=2
maxn=1
if n==1:
    print(p)
else:
    while jo<dio:
        if p%jo==0:
            p/=jo
            k+=1
            if k>=n:
                maxn*=jo
                k=0
        else:
            jo+=1
            k=0
    print(maxn)

Measured memory_bytes: 3188
fn main() {
    proconio::input! {
        n: usize,
        m: usize,
        k: i64,
        a_s: [i64; n],
        b_s: [i64; m],
    }
    let suma = a_s.iter().sum::<i64>();
    let sumb = b_s.iter().sum::<i64>();
    if suma + sumb <= k {
        let ans = n + m;
        println!("{}", ans);
        return;
    }

    let mut ia = 0;
    let mut count = 0;
    let mut cur = 0i64;
    for a in &a_s {
        cur += *a;
        if cur > k {
            cur -= *a;
            break;
        }
        ia += 1;
        count += 1;
    }

    let mut ib = 0;
    if cur <= k {
        for b in &b_s {
            cur += *b;
            if cur > k {
                cur -= *b;
                break;
            }
            ib += 1;
            count += 1;
        }
    }
    let mut max = count;
    loop {
        if ia == 0 {
            break;
        }
        if ib == m {
            break;
        }
        cur -= a_s[ia - 1];
        count -= 1;
        ia -= 1;
        while ib != m && cur + b_s[ib] <= k {
            cur += b_s[ib];
            ib += 1;
            count += 1;
        }
        max = std::cmp::max(max, count);
    }
    let ans = max;
    println!("{}", ans);
}


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

#define MAXN 1000001
int spf[MAXN];
int n;

void seive(){
    spf[1] = 1; 
    for (int i=2; i<MAXN; i++){
        spf[i] = i; 
    }
    for (int i=4; i<MAXN; i+=2){
        spf[i] = 2; 
    }
    for (int i=3; i*i<MAXN; i++) 
    { 
        if (spf[i] == i) 
        { 
            for (int j=i*i; j<MAXN; j+=i) 
                if (spf[j]==j){
                    spf[j] = i; 
            }
        } 
    } 
}

map<int,int> ma;
bool flag = true;

void getFactorization(int x) 
{ 
    set<int> s;
    while (x != 1)
    {   
        s.insert(spf[x]);
        x = x / spf[x]; 
    }

    for(auto x: s){
        if(ma.find(x)!=ma.end()){
            flag=false;
            break;
        }else{
            ma[x]++;
        }
    }

} 

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);

    seive();

    cin >> n;
    int arr[n];
    for(int i=0; i<n; i++){
        cin >> arr[i];
    }

    bool setwise = false;
    int setwisegcd = arr[0];
    for(int i=1; i<n; i++){
        setwisegcd = __gcd(setwisegcd, arr[i]);
    }

    if(setwisegcd==1){
        setwise = true;
    }

    for(int i=0; i<n; i++){
        if(flag) getFactorization(arr[i]);
        else{
            break;
        }
    }

    if(flag){
        cout<<"pairwise coprime\n";
    }else if(setwise){
        cout<<"setwise coprime\n";
    }else{
        cout<<"not coprime\n";
    }

    return 0;
}


Measured memory_bytes: 11488
#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
using namespace std;
 
int main(){
    bool p=false;
    int A,B,ans,x,y,z;
    cin>>A>>B;
    x=A*12;
    y=B*10;
    z=min(x,y);
while(z<=(A*15)&&z<=(B*15)){
        int a=z*0.08;
        int b=z*0.1;
        if(a==A&&b==B){ans=z;p=true; break;}
        z+=1;
    }
if(p)cout<<ans;
else cout<<"-1";
    return 0;
}

Measured memory_bytes: 256
//author:luckYrat(twitter:@luckYrat_)
//#include <bits/stdc++.h>

//def
#include <iostream>

#include <cmath>
#include <algorithm>
#include <iomanip>

//array
#include <vector>
#include <set>
#include <stack>
#include <queue>
#include <map>
#include <utility>
#include <climits>



using namespace std;

typedef pair<int,int> P;
typedef long long ll;

#define anyfill(n,s) setw(n) << setfill(s)
#define loop(s) for(int i = 0; s > i; i++)
#define rep(i,q) for(int i = 0; (q) > i; i++)
#define repp(i,n,q) for(int i = n; (q) > i; i++)
#define dep(i,q) for(int i = (q); 0 < i; i--)


#define MAX 1000000000
const int mod = 1000000007;
#define EPS (1e-10)

#define pb push_back
#define fir first
#define scn second
#define ednl endl

#define YesNo(a) (a?"Yes":"No")
#define YESNO(a) (a?"YES":"NO")
#define yesno(a) (a?"yes":"no")



/*
確認ポイント
cout << fixed << setprecision(n) << 小数計算//n桁の小数表記になる
vector.unique()は隣接した同じ要素を削除するので先にソートをする

計算量は変わらないが楽できるシリーズ
C++11以降でmin({a,b,c...})で複数個のmic,maxを処理できる
min(max)_element(iter,iter)で一番小さい(大きい)値のポインタが帰ってくる
count(iter,iter,int)でintがiterからiterの間にいくつあったかを取得できる

*/
bool pairSecond(const P& pf,P&ps){
  return pf.second+pf.first < ps.second+ps.first;
}
__attribute__((constructor))
void initial() {
 cin.tie(0);
 ios::sync_with_stdio(false);
}
P dp[100000][2];
int main() { 
  int n;cin>>n;
  vector<P> a(n);
  for(int i = 0; n > i; i++){
    cin>>a[i].first >> a[i].second;
  }
  sort(a.begin(),a.end(),pairSecond);
  int ans = 1;
  int nw = a[0].first+a[0].second;
  for(int i = 1; n > i; i++){
    if(a[i].first-a[i].second >= nw){
      ans++;
      nw = a[i].first+a[i].second;
    }
  }
  
  cout << ans << endl;
  
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
struct sorter{
	bool operator()(const pair<int,int> & a, const pair<int,int> & b){
		if(a.second == b.second){
			return a.first > b.first;
		}
		return a.second < b.second;
	}
};
int main(){
	int n, a, b;
	cin>>n;
	vector<pair<int,int> > vec;
	for(int i = 0; i < n; ++i){
		cin>>a>>b;
		vec.push_back(make_pair(a, b));
	}
	sort(vec.begin(), vec.end(), sorter());
	int sum = 0;
	bool ok = true;
	for(int i = 0; i < n; ++i){
		sum += vec[i].first;
		if(sum > vec[i].second)ok = false;
	}
	if(ok){
		cout<<"Yes"<<endl;
	}
	else{
		cout<<"No"<<endl;
	}
	
	

	
	return 0;
}


Measured memory_bytes: 2420
def power(x, n):
  return (x-n) * (x-n)

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

ave = round(sum(nums) / n)

new_nums = []

for i in nums:
  r = power(i, ave)
  new_nums.append(r)

print(sum(new_nums))

Measured memory_bytes: 3060
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
H, W = map(int, input().split())
visited = [[True] * (W + 2)]
visited += [[True] + [x == '#' for x in input().rstrip()] + [True] for _ in range(H)]
visited.append([True] * (W + 2))

q = []
for i in range(1, H + 1):
    for j in range(1, W + 1):
        if visited[i][j]:
            q.append((i, j))

ans = -1
while q:
    tmp = []
    ans += 1
    for h, w in q:
        if not visited[h - 1][w]:
            visited[h - 1][w] = True
            tmp.append((h - 1, w))
        if not visited[h + 1][w]:
            visited[h + 1][w] = True
            tmp.append((h + 1, w))
        if not visited[h][w - 1]:
            visited[h][w - 1] = True
            tmp.append((h, w - 1))
        if not visited[h][w + 1]:
            visited[h][w + 1] = True
            tmp.append((h, w + 1))
    q = tmp
print(ans)


Measured memory_bytes: 109984
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cmath>
#define rep(i, n) for(i = 0; i < n; i++)
#define int long long
using namespace std;

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

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

int n, m;
int a[100000];

signed main() {
	int i;
	
	cin >> n >> m;
	rep(i, n) cin >> a[i];
	
	int l = 1;
	rep(i, n) {
		l = lcm(l, a[i]);
		if (l > 2 * m) { cout << 0 << endl; return 0; }
	}
	
	rep(i, n) {
		if ((l / 2) % a[i] != a[i] / 2) { cout << 0 << endl; return 0; }
	}
	
	cout << (m - (l / 2)) / l + 1 << endl;
	return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
 
using namespace std;
 
long long int n;
int a[100010];
string s;

int pos(int i){
    return (i+n)%n;
}

int check(){
    for(int i = 0; i < n; i++){
        //wolf
        if(a[i]){
            if(s[i] == 'o'){//o
                if(a[pos(i+1)] == a[pos(i-1)])return 0;
            }else{//x
                if(a[pos(i+1)] != a[pos(i-1)])return 0;
            }
        }else{//seep
            if(s[i] == 'o'){//o
                if(a[pos(i+1)] != a[pos(i-1)])return 0;
            }else{//x
                if(a[pos(i+1)] == a[pos(i-1)])return 0;
            }
        }
    }
        
    return 1;
}
 
int func(){
        
        
        for(int i = 1; i < n-2; i++){
            //wolf
            if(a[i]){
                if(s[i] == 'o'){//o
                    a[i+1] = !a[i-1];
                }else{//x
                    a[i+1] = a[i-1];
                }
            }else{//seep
                if(s[i] == 'o'){//o
                    a[i+1] = a[i-1];
                }else{//x
                    a[i+1] = !a[i-1];
                }
            }
        }
        
        
        
        if(check()){
            for(int i = 0; i < n; i++) cout << ( (a[i] == 0) ? 'S' : 'W' );
            cout << endl;
            return 1;
        }
        
        return 0;
}
 
int main(void){
    // Here your code !
    
    cin >> n >> s;
    
    if( s[0] == 'o' ){
        //seep
        //1
        a[0] = 0;
        a[1] = 0;
        a[n-1] = 0;
        
        if(func()) return 0;
        
        //2
        a[0] = 1;
        a[1] = 0;
        a[n-1] = 1;
        
        if(func()) return 0;
        
        //wolf
        //1
        a[0] = 1;
        a[1] = 1;
        a[n-1] = 0;
        
        if(func()) return 0;
        
        //2
        a[0] = 0;
        a[1] = 1;
        a[n-1] = 1;
        
        if(func()) return 0;
        
    }else{
        //x
        //seep
        //1
        a[0] = 1;
        a[1] = 0;
        a[n-1] = 0;
        
        if(func()) return 0;
        
        //2
        a[0] = 0;
        a[1] = 0;
        a[n-1] = 1;
        
        if(func()) return 0;
        
        //wolf
        //1
        a[0] = 1;
        a[1] = 1;
        a[n-1] = 1;
        
        if(func()) return 0;
        
        //2
        a[0] = 0;
        a[1] = 1;
        a[n-1] = 0;
        
        if(func()) return 0;
    }
    
    cout << -1 << endl;
    
}

Measured memory_bytes: 896
#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
using ll = long long;
using P = pair<int, int>;
ll GCD(ll a, ll b) { return b?GCD(b, a%b):a; }
ll LCM(ll a, ll b) { return a/GCD(a, b)*b; }


int main() {
    for(int i = 0; i < 5; ++i) {
        int x; cin >> x;
        if(x == 0) cout << i+1 << endl;
    }
}

Measured memory_bytes: 3620
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <sstream>
#include <algorithm>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <list>
#include <cstdio>
#include <iostream>
#include <cmath>
#include <climits>
#include <bitset>
#include <functional>
#include <numeric>
#include <ctime>
#include <cassert>
#include <cstring>
#include <fstream>

#define FOR(i, a, b) for(int (i)=(a); (i)<(b); (i)++)
#define IFOR(i, a, b) for(int (i)=(a);(i)<=(b);(i)++)
#define RFOR(i, a, b) for(int (i)=(a);(i)>=(b);(i)--)

using namespace std;

int main() {
	int n, x;
	cin >> n >> x;
	vector<long long> a(n);
	FOR(i, 0, n) {
		cin >> a[i];
		
	}
	long long cnt = 0;
	FOR(i, 0, n-1) {
		long long sumx = a[i] + a[i + 1];
		if (sumx > x) {
			long long diff = sumx - x;
			long long diff2 = 0;
			if (a[i + 1] < diff) {
				diff2 = diff - a[i + 1];
				a[i] -= diff2;
				diff -= diff2;
			}
			a[i + 1] -= diff;
			cnt += diff + diff2;
		}
	}
	cout << cnt << endl;

	return 0;
}

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

int main() {
   int f, s, t, tmp;
   cin >> f >> s >> t;

   if(f > s) { tmp = s; s = f; f = tmp; }
   if(s > t) { tmp = t; t = s; s = tmp; }
   if(f > s) { tmp = f; f = s; s = tmp; }
   
  
   cout << f  << " " << s << " " << t << endl;
}
   
   
      
   
   
   

Measured memory_bytes: 1164
#include <cstdio>
#include <climits>
#include <iostream>
#include <string>
#include <algorithm>
#include <numeric>
#include <functional>
#include <tuple>
#include <list>
#include <map>
#include <queue>
#include <stack>
#include <set>
#include <vector>

#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)

using namespace std;
typedef long long ll;
typedef pair<int,int> PI;
typedef pair<ll,ll> PL;
typedef vector<int> VI;
typedef vector<ll> VL;

struct uf {
  VI par;
  uf(int n) : par(n) {
    REP(i,0,n) {
      par[i] = i;
    }
  }
  int find(int x) {
    if(par[x] == x) return x;
    return par[x] = find(par[x]);
  }
  void unite(int x, int y) {
    par[find(x)] = find(y);
  }
  bool same(int x, int y) {
    return find(x) == find(y);
  }
};

int main() {
  int N, M;
  cin >> N >> M;
  uf u(M+1);
  vector<VI> peo(N);
  int mink = 1e6;
  int minkp = -1;
  REP(i,0,N) {
    int K;
    cin >> K;
    if(K < mink) {
      mink = K;
      minkp = i;
    }
    int l1 = 0;
    REP(j,0,K) {
      int l;
      cin >> l;
      peo[i].push_back(l);
      if(l1) {
        u.unite(l1,l);
      } else {
        l1 = l;
      }
    }
  }
  bool pos = true;
  REP(i,0,N) {
    if(i == minkp) continue;
    bool posi = false;
    for(const auto &l1 : peo[minkp]) {
      for(const auto &l2 : peo[i]) {
        if(u.same(l1, l2)) {
          posi = true;
        }
      }
    }
    if(!posi) {
      pos = false;
      break;
    }
  }
  cout << (pos ? "YES\n" : "NO\n");

  return 0;
}


Measured memory_bytes: 6144
#include "bits/stdc++.h"
#define ALL(x) x.begin(), x.end()
#define iostreamBooster() do{ cin.tie(nullptr); ios_base::sync_with_stdio(false); }while(0)
#define rep(i, s, n)      for(int i(s); i < int(n); ++i)
using namespace std;
using i64 = long long;
using pii = pair<int, int>;
template<class A, class B>inline bool chmax(A &a, const B &b){return b>a ? a=b,1 : 0;}
template<class A, class B>inline bool chmin(A &a, const B &b){return b<a ? a=b,1 : 0;}
constexpr int INF  = 0x3f3f3f3f;
constexpr i64 LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr int MOD  = int(1e9) + 7;

signed main()
{
  string a, b;

  cin >> a >> b;

  reverse(ALL(b));

  puts(a==b ? "YES" : "NO");
  return 0;
}



Measured memory_bytes: 256
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]

def unite(x,y):
    x, y = find(x), find(y)
    if x == y:
        return False
    
    if par[x] > par[y]:
        x,y = y,x
    par[x] += par[y]
    par[y] = x
    return True

def size(x):
    return -par[find(x)]

n, m = map(int, input().split())
ab = []
for _ in range(m):
    a, b = map(int, input().split())
    ab.append([a-1, b-1])
par = [-1]*n
ans = n*(n-1)//2
ansl = [ans]
for a, b in ab[::-1]:
    if find(a)!=find(b):
        ans -= size(a)*size(b)
    unite(a, b)
    ansl.append(ans)
for i in range(m-1, -1, -1):
    print(ansl[i])

Measured memory_bytes: 29444
#include <algorithm>
#include <iostream>
#include <map>
#include <set>
#include <vector>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;

vector<int> dp; // 頂点 i から始まるパスで最長のものの長さ
multimap<int, int> mp; // 入力値(from, to)

// 一番遠い場所を探す
int rec(int from) {
    if (dp[from] != 0) {
        return dp[from];
    }
    int res = 0;
    // キーを持つ値を列挙する
    auto p = mp.equal_range(from);
    for (auto it = p.first; it != p.second; ++it) {
        res = max(res, rec(it->second) + 1);
    }
    return dp[from] = res;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m, ans = 0;
    cin >> n >> m;
    dp.resize(n + 1, 0);
    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        mp.emplace(x, y);
    }
    for (int i = 1; i <= n; i++) {
        if (dp[i] == 0) {
            ans = max(ans, rec(i));
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 7424
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define rep(i,n); for(long long i = 0;i < (n);i++)
using ll = long long;
using P = pair<long long,long long>;
template <class T> using vec = vector<T>;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n; cin >> n;
    n %= 10;
    if(n == 3)cout << "bon" << endl;
    else if(n == 0 || n == 1 || n == 6 || n == 8)cout << "pon" << endl;
    else cout << "hon" << endl;
}

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

int main()
{
  string s, t;
  cin >> s >> t;
  
  vector<char> ss, tt;
  for (int i = 0; i < s.size(); i ++)
    ss.push_back(s.at(i));
  for (int i = 0; i < t.size(); i ++)
    tt.push_back(t.at(i));
  
  // sのアナグラムの最弱(ss)とtのアナグラムの最強(tt)を比べる
  sort(ss.begin(), ss.end());
  sort(tt.begin(), tt.end(), greater<>{});
  
  // ttがssに勝ってたら勝ち抜け
  if (tt.at(0) > ss.at(0))
  {
    cout << "Yes";
    return 0;
  }

  // ttがssに負けてたら負け抜け
  if (tt.at(0) < ss.at(0))
  {
    cout << "No";
    return 0;
  }
  
  // 頭が同じときは一文字ずつ見ていって勝負
  if (tt.at(0) == ss.at(0))
  {
    int index = 0;
    while(ss.size() > 0 && tt.size() > 0)
    {
      // 勝ち抜け
      if (tt.at(index) > ss.at(index))
      {
        cout << "Yes";
        return 0;
      }
      // 負け抜け
      else if (tt.at(index) < ss.at(index))
      {
        cout << "No";
        return 0;
      }
      ss.erase(ss.begin());
      tt.erase(tt.begin());
    }
  }
  
  // 勝ち抜け、負け抜けが出ずにループが終わった時
  // 先にssとttのどちらが尽きたかで勝敗が確定
  if (tt.size() > 0)
  {
    cout << "Yes";
    return 0;
  }
  else
  {
    cout << "No";
    return 0;
  }

  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
using namespace std;
long long a[200005];
long long b[200005][2];
int main()
{
    int n;
    cin >> n;
    for(int i = 0;i < n;i++){
        cin >> a[i];
    }
    sort(a,a+n);
    int l = 0;
    int r = n - 1;
    int cnt = 0;
    long long tt = a[0];
    if(a[r] < 0){
        tt = a[r];
        for(int i = 0;i <= r - 1;i++){
            b[cnt][0] = tt;
            b[cnt][1] = a[i];
            tt = tt - a[i];
            cnt++;
        }
        cout << tt << endl;
        for(int i = 0;i < cnt;i++){
            cout << b[i][0] << " " << b[i][1] << endl;
        }
        return 0;
    }

    if(a[l] >= 0){
       if(n == 2){
          cout << a[r] - a[l] << endl;
          cout << a[r] << " " << a[l] << endl;
          return 0;
       }
       for(int i = n - 1;i > 1;i--){
          b[cnt][0] = tt;
          b[cnt][1] = a[i];
          tt = tt - a[i];
          cnt++;
       }
       b[cnt][0] = a[1];
       b[cnt][1] = tt;
       tt = a[1] - tt;
       cnt++;
       cout << tt << endl;
       for(int i = 0;i < cnt;i++){
            cout << b[i][0] << " " << b[i][1] << endl;
       }
       return 0;
    }

    int loc;
    for(int i = 0;i < n;i++){
        if(a[i] >= 0){
            loc = i;
            break;
        }
    }
    //cout << tt << endl;
    //cout << loc << endl;
    for(int i = n - 1;i >= loc + 1;i--){
            b[cnt][0] = tt;
            b[cnt][1] = a[i];
            tt = tt - a[i];
            //cout << b[cnt][0] << " " << b[cnt][1] << endl;
            cnt++;
    }
    //cout << tt << endl;
    b[cnt][0] = a[loc];
    b[cnt][1] = tt;
    //cout << a[loc] << " " <<tt << endl;
    tt = a[loc] - tt;
    cnt++;
    for(int i = 1;i < loc;i++){
        b[cnt][0] = tt;
        b[cnt][1] = a[i];
        tt = tt - a[i];
        cnt++;
    }
    cout << tt << endl;
    for(int i = 0;i < cnt;i++){
        cout << b[i][0] << " " << b[i][1] << endl;
    }
    //cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 5504
a, b, m = gets.chomp.split(" ").map{|e|e.to_i}
aa = gets.chomp.split(" ").map{|e|e.to_i}
bb = gets.chomp.split(" ").map{|e|e.to_i}

cost = []

m.times do
	x, y, c = gets.chomp.split(" ").map{|e|e.to_i}
	cost << (aa[x-1] + bb[y-1] - c)
end

min1 = cost.sort[0]
min2 = aa.sort[0] + bb.sort[0]

if min1>min2 then
	print(min2)
else
	print(min1)
end




Measured memory_bytes: 21388
package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
)

func generated_lib_ModPow() int64 {
	return int64(math.Max(1, 3))
}
func generated_lib_unUsedFunction() string {
	return "I am unused unexported function"
}
func generated_lib_UnUsedFunction() string {
	return "I am unused exported function"
}
func generated_lib_swap(a int, b int) (int, int) {
	return b, a
}
func (u generated_lib_UnionFind) Size(x int) int {
	return -u.par[u.Find(x)]
}
func (u generated_lib_UnionFind) Same(x, y int) bool {
	return u.Find(x) == u.Find(y)
}
func (u generated_lib_UnionFind) Union(x, y int) {
	xr := u.Find(x)
	yr := u.Find(y)
	if xr == yr {
		return
	}
	if u.Size(yr) < u.Size(xr) {
		yr, xr = generated_lib_swap(yr, xr)
	}
	u.par[yr] += u.par[xr]
	u.par[xr] = yr
}
func (u generated_lib_UnionFind) Find(x int) int {
	if u.par[x] < 0 {
		return x
	}
	u.par[x] = u.Find(u.par[x])
	return u.par[x]
}
func generated_lib_NewUnionFind(N int) *generated_lib_UnionFind {
	u := new(generated_lib_UnionFind)
	u.par = make([]int, N)
	for i := range u.par {
		u.par[i] = -1
	}
	return u
}

type generated_lib_UnionFind struct{ par []int }

func main() {
	r := bufio.NewReader(os.Stdin)
	w := bufio.NewWriter(os.Stdout)
	defer w.Flush()
	var n, m int
	fmt.Fscan(r, &n, &m)
	uf := generated_lib_NewUnionFind(n)
	for i := 0; i < m; i++ {
		var a, b int
		fmt.Fscan(r, &a, &b)
		a--
		b--
		uf.Union(a, b)
	}
	ans := 0
	for i := 0; i < n; i++ {
		if ans < uf.Size(i) {
			ans = uf.Size(i)
		}
	}
	fmt.Fprintln(w, ans)
}


Measured memory_bytes: 6320
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author emli
 */


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

class BTrickOrTreat {
public:
    void solve(std::istream& cin, std::ostream& cout) {
		ios::sync_with_stdio(false);
        cin.tie(nullptr);

        int n,k;

        cin >> n >> k;

        vector<int> used(n + 1);
        for (int i = 0; i < k; ++i) {
            int d;
            cin >> d;

            for (int j = 0; j < d; ++j) {
                int x;
                cin >> x;
                used[x] = 1;
            }
        }

        int ans = 0;
        for (int l = 1; l <= n; ++l) {
            ans += !used[l];
        }

        cout << ans << endl;
	}
};


int main() {
	BTrickOrTreat solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


Measured memory_bytes: 3664
import java.util.Scanner;
public class Main{
	public static void main(String[] args){
		Scanner scan = new Scanner(System.in);
		String dic = "yuiophjklnm";
		while(scan.hasNext()){
			String str = scan.nextLine();
			if(str.equals("#")){
				break;
			}
			int count = 0;
			boolean hand = (dic.indexOf(str.charAt(0)) >= 0)?true:false;
			for(int i = 1;i < str.length();i++){
				if(dic.indexOf(str.charAt(i)) >= 0){
					if(!hand){
						count++;
						hand = true;
					}
				}else{
					if(hand){
						count++;
						hand = false;
					}
				}
			}
			System.out.println(count);
		}
	}
}

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

int main(void) {
  char n[4];

  if(scanf("%s", n) != 0);

  for(int i = 0; i < 3; i++) {
    if(n[i] == '1') {
      n[i] = '9';
    } else {
      n[i] = '1';
    }
  }

  printf("%s", n);

  return 0;
}


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

int main(){
	int n,m;
	bool flag = false;
	string s[50],t[50];
	cin >> n >> m;
	for(int i = 0;i < n;i++) cin >> s[i];
	for(int i = 0;i < m;i++) cin >> t[i];
	for(int i = 0;i < n - m + 1;i++){
		for(int j = 0;j < n - m + 1;j++){
			bool f = true;
			for(int k = 0;k < m;k++){
				for(int l = 0;l < m;l++){
					if(s[i + k][j + l] != t[k][l]) f = false;
				}
			}
			if(f) flag = true;
		}
	}
	if(flag) cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void){
 int S;
 scanf("%d",&S);
 
 int h,m,s;
  
 h=S/(60*60);
 m=(S%(60*60))/60;
 s=(S%(60*60))%60;
 
 printf("%d:%d:%d\n",h,m,s);
 return 0;
}

Measured memory_bytes: 592
import java.util.*;
 
public class Main{

       public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        
        int H = sc.nextInt() + 2;
        int W = sc.nextInt() + 2;
        String[] s = new String[H];

        for(int i = 0; i < H; i++){
            if(i == 0 || i == H-1){
                for(int j = 0; j < W; j++){
                    if(j == 0){
                        s[i] = "#";
                    } else {
                        s[i] += "#";
                    }
                }
            } else {
                s[i] = "#" + sc.next() + "#";
            }
        }
        
        sc.close();
        for(int i = 1; i <= H-2; i++){
            for(int j = 1; j <= W-2; j++){
                if(s[i].charAt(j)== '.')
                    continue;
                else{
                    if(s[i+1].charAt(j) != '#' &&
                    s[i-1].charAt(j) != '#' &&
                    s[i].charAt(j+1) != '#' &&
                    s[i].charAt(j-1) != '#'){
                        System.out.println("No");
                        return;
                    }
                }
            }
        }
        System.out.println("Yes");
    }
}

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

int main(){
  int N;
  cin >> N;
  vector<int> a(N);
  for(int i = 0; i < N; i++){
    cin >> a[i];
  }

  int j = 1;
  int cnt = 0;
  for(int i = 0; i < N; i++){
    if(a[i] != j){
      cnt++;
    }else{
      j++;
    }
  }
  if(cnt == N){
    cout << -1 << endl;
  }else{
    cout << cnt << endl;
  }
}


Measured memory_bytes: 1024
import java.util.Scanner;

public class Main {

	public static void main(String... nui) {
		Scanner sc = new Scanner(System.in);
		
		int r = sc.nextInt(), g = sc.nextInt(), b = sc.nextInt();
		
		System.out.println(((r * 100 + g * 10 + b) % 4 == 0) ? "YES" : "NO");
	}

}

Measured memory_bytes: 21972
#include <iostream>

using namespace std;

int a,b;
string aa,bb;

inline char to(int x)
{
	return '0'+x;
}

int main()
{
	cin >> a >> b;
	for (int i=1; i<=a; i++) aa+=to(b);
	for (int i=1; i<=b; i++) bb+=to(a);
	cout << min(aa,bb);
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using uint = unsigned int;
using lint = long long int;
using ulint = unsigned long long int;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;
template<class T, class U> void assign(V<T>& v, int n, const U& a) { v.assign(n, a); }
template<class T, class... Args> void assign(V<T>& v, int n, const Args&... args) { v.resize(n); for (auto&& e : v) assign(e, args...); }


int main() {
  cin.tie(nullptr); ios_base::sync_with_stdio(false);
  V<string> c(10);
  c[1] = ".,!? ";
  c[2] = "abc";
  c[3] = "def";
  c[4] = "ghi";
  c[5] = "jkl";
  c[6] = "mno";
  c[7] = "pqrs";
  c[8] = "tuv";
  c[9] = "wxyz";
  int q; cin >> q;
  while (q--) {
    string s; cin >> s;
    int n = s.size();
    string res;
    char curr = 0;
    int j = 0;
    for (int i = 0; i < n; ++i) {
      if (s[i] == '0') {
        if (curr) res += curr;
        curr = 0;
        j = 0;
      } else {
        curr = c[s[i] - '0'][j++ % c[s[i] - '0'].size()];
      }
    }
    cout << res << '\n';
  }
}


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

int main(void){
  int s;
  cin >> s;
  
  int a;
  map<int, int> mp;
  
  
  int cnt=1;
  while(1){
    if(mp[s] ==1){
      break;
    }
    mp[s]++;
    if(s%2 == 0) s = s/2;
    else s = 3*s+1;
    cnt++;
  }
  cout << cnt << endl;
  
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int[][] A = new int[3][3];
    for (int i = 0; i < 3; i++) {
      for (int j = 0; j < 3; j++) {
        A[i][j] = sc.nextInt();
      }
    }
    int N = sc.nextInt();
    while (N-- > 0) {
      int n = sc.nextInt();
      for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
          if (A[i][j] == n) {
            A[i][j] = 0;
            break;
          }
        }
      }
    }
    for (int i = 0; i < 3; i++) {
        if (A[i][0] == A[i][1] && A[i][1] == A[i][2] && A[i][2] == 0) {
          System.out.println("Yes");
          return;
        }
    }
    for (int i = 0; i < 3; i++) {
      if (A[0][i] == A[1][i] && A[1][i] == A[2][i] && A[2][i] == 0) {
        System.out.println("Yes");
        return;
      }
    }
    if (A[0][0] == A[1][1] && A[1][1] == A[2][2] && A[2][2] == 0) {
      System.out.println("Yes");
      return;
    }
    if (A[0][2] == A[1][1] && A[1][1] == A[2][0] && A[2][0] == 0) {
      System.out.println("Yes");
      return;
    }
    System.out.println("No");
  }
}


Measured memory_bytes: 22612
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>
#include<climits>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<bitset>
#include<iomanip>
using namespace std;

#define rep(i,j,n) for(int i=(j);i<(n);i++)
#define erep(i,j,n) for(int i=(j);i<=(n);i++)
#define all(i) i.begin(),i.end()
#define rall(i) i.rbegin(),i.rend()
#define INF 1e9
const int mod = 1e9+7;

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<string> vs;
typedef vector<vector<string>> vvs;
typedef pair<int, int> pi;
typedef long long i64;

int main() {
  int H,W;
  cin>>H>>W;
  vvs s(H,vs(W));
  rep(i,0,H) rep(j,0,W) cin>>s[i][j];

  string a="ABCDEFGHIGKLMNOPQRSTUVWXYZ";
  rep(h,0,H){
    rep(w,0,W){
      if(s[h][w]=="snuke"){
        cout<<a[w]<<h+1<<endl;
        return 0;
      }
    }
  }
}


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

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

  char a, b;
  a = S[0];
  int var = 1;
  for(int i = 1; i < 4; i++){
    if(var == 1 && a != S[i]){
      b = S[i];
      var++;
    }
    if(a != S[i] && b != S[i]){
      cout << "No" << endl;
      return 0;
    }
  }

  if(var == 2){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
 
  return 0;
}

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

#define endl '\n'
#define ends ' '
#define die(x) return cout << x << endl, 0
#define all(v) v.begin(), v.end()
#define sz(x) (int)(x.size())
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) { cerr << ends << H; debug_out(T...); }
#define debug(...) cerr << "{" << #__VA_ARGS__ << "}:", debug_out(__VA_ARGS__)
typedef long long ll;
typedef pair<int, int> pii;
const ll INF = 1e9;
const ll MOD = 1e9 + 7;
 
////////////////////////////////////////////////////////////////////

const int N = 5e1 + 5;

int A[N], B[N];
bool M[N];

bool DFS(int v, int u) {
	if (v == u) return true;
	for (int i = 1; i <= v; i++) if (!M[i] && DFS(v % i, u)) return true;
	return false;
}

int main() {

	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	mt19937 Rnd(time(0));
		
	int n; cin >> n;
	for (int i = 0; i < n; i++) cin >> A[i];
	for (int i = 0; i < n; i++) cin >> B[i];
	for (int i = 0; i < n; i++) if (!DFS(A[i], B[i])) die(-1);
	ll ans = 0;
	for (int i = N - 1; i > 0; i--) {
		bool f = M[i] = true;
		for (int j = 0; j < n; j++) f &= DFS(A[j], B[j]);
		if (!f) M[i] = false, ans += (1LL << i);
	}
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 256
#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;
/* ---------------------------------------------------------------------------------------------------- */

string L;
int dp[100010][2];

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

  cin >> L;
  dp[0][0] = 1;
  REP(i,L.size()) {
    if (L[i] == '0') {
      (dp[i+1][0] += dp[i][0]) %= MOD;
      (dp[i+1][1] += dp[i][1] * 3 % MOD) %= MOD;
    } else {
      (dp[i+1][0] += dp[i][0] * 2 % MOD) %= MOD;
      (dp[i+1][1] += (dp[i][0] + dp[i][1] * 3 % MOD) % MOD) %= MOD;
    }
  }
  cout << (dp[L.size()][0] + dp[L.size()][1]) % MOD << endl;

  return 0;
}

Measured memory_bytes: 2128
program prob3
    implicit none
    integer::N, i,j,a,b,c,d,tmp,e
    character(len=9)::S
    integer::v(4)
    read(*,*) N
    a = N/1000
    N = N - N/1000*1000
    b = N/100
    N = N - N/100*100
    c = N/10
    N = N - N/10*10
    d = N
    v(1) = a
    v(2) = b
    v(3) = c
    v(4) = d
    S(1:1) = char(ichar('0')+a)
    S(3:3) = char(ichar('0')+b)
    S(5:5) = char(ichar('0')+c)
    S(7:7) = char(ichar('0')+d)
    S(9:9) = char(ichar('0')+7)
    S(8:8) = "="
    do i = 0,7
        tmp = i
        e = 0
        do j = 2,0,-1
            if(tmp >= 2**j) then
                e = e + v(j+2) 
                tmp = tmp - 2**j
                S(2*j+2:2*j+2) = "+"
            else
                e = e - v(j+2)
                S(2*j+2:2*j+2) = "-"
            end if
        end do
        e = e + v(1)
        if(e == 7)then
            write(*,'(a)') S
            stop
        end if
    end do
end program

Measured memory_bytes: 2928
#include <bits/stdc++.h>
#define long long long int
using namespace std;

// @author: pashka

int main() {
    ios::sync_with_stdio(false);

    string s;
    cin >> s;
    if (s[0] != s[1] || s[0] != s[2] || s[1] != s[2]) {
        cout << "Yes";
    } else {
        cout << "No";
    }

    return 0;
}

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

int main(){
  int n;
  cin >> n;
  int ans=0;
  vector<int>kati(n);
  vector<int>kane(n);
  for(int i=0;i<n;i++)
    cin >> kati.at(i);
  for(int i=0;i<n;i++)
    cin >> kane.at(i);
  for(int i=0;i<n;i++){
    if(kati.at(i)-kane.at(i)>0)
      ans+=kati.at(i)-kane.at(i);
  }
  cout << ans << endl;
  return 0;
}

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

#define endl '\n'
#define mod (1000000000 + 7)

typedef long long ll;
int h, w;
ll dp[1003][1003];
char a[1003][1003];

ll f(int y, int x){
  if(x==w && y==h) return 1;
  if(dp[y][x]!=-1) return dp[y][x];
  dp[y][x]=0;
  if(x<w && a[y][x+1]!='#') dp[y][x]+=f(y,x+1)%mod;
  if(y<h && a[y+1][x]!='#') dp[y][x]+=f(y+1, x)%mod;
  return dp[y][x]=dp[y][x]%mod;
}

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

  cin >> h >> w;
  for(int i=1; i<=h; i++){
    for(int j=1; j<=w; j++){
      cin >> a[i][j];
    }
  }

  for(int i=1; i<=h; i++){
    for(int j=1; j<=w; j++){
      dp[i][j]=-1;
    }
  }

  cout << f(1,1) << endl;
}

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

int main() {
  int n; cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; i++) cin >> a[i];
  int ans = 0;
  while (ans < 30) {
    for (int i = 0; i < n; i++) {
      if (a[i] & 1) {
        cout << ans << endl;
        return 0;
      }
      a[i] >>= 1;
    }
    ans++;
  }
}

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

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

Measured memory_bytes: 256
#include <stdio.h>
#include <vector>
#include <iostream>
#include <queue>
#include <bits/stdc++.h>
 
#define rep(i,n) for (int i=0;i<(n);++i)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<double> vd;



int main() {
  vi a(3);
  rep(i, 3) cin >> a[i];
  sort(a.begin(), a.end());
  cout << a[2] * 10 + a[1] + a[0] << endl;
  return 0;
}

Measured memory_bytes: 256
S=input()
N=len(S)
f=True
for i in range(N//2):
    if S[i]!=S[-1-i]:f=False
if f==True:
    s1=S[0:(N-1)//2]
    s2=S[(N+3)//2-1::]
    for i in range(N//2//2):
        if s1[i]!=s1[-1-i] or s2[i]!=s2[-1-i]:f=False
print("Yes") if f==True  else print("No")


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

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

using namespace std;

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

  if(s[0]==s[s.size()-1] ^ s.size()%2==1)cout<<"First";
  else cout<<"Second";

  return 0;
}

Measured memory_bytes: 512
var input = require('fs').readFileSync('/dev/stdin', 'utf8');
var [n,arr]= input.trim().split("\n");
arr=arr.split(" ").map(Number);
arr.sort(function(a,b){
   return a-b;
});
var sum = arr.reduce(function(a,b){
   return a+b;
});
if(sum%2==0)console.log(sum/2);
else {
   for(var i=0;i<arr.length;i++){
      if(arr[i]%2==1){
         console.log((sum-arr[i])/2);
         break;
      }
   }
}


Measured memory_bytes: 15496
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>

// c++11
#include <array>
#include <tuple>
#include <unordered_map>
#include <unordered_set>

#define mp make_pair
#define mt make_tuple
#define rep(i, n) for (int i = 0; i < (n); i++)

using namespace std;

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

const int INF = 1 << 29;
const double EPS = 1e-9;
const ll MOD = 1000000007;

const int dx[] = {1, 0, -1, 0}, dy[] = {0, -1, 0, 1};
int N;
vector<int> A;
int main() {
  cin >> N;
  A.resize(N);
  for (auto &val : A){
    cin >> val;
  }
  if (N < 2){
    cout << 1 << endl;
    return 0;
  }
  //N >= 2

  int pre = A[0];
  int flag;
  if (A[0] < A[1]){
    flag = 1;
  }else if (A[0] > A[1]){
    flag = -1;
  }else{
    flag = 0;
  }
  int res = 0;
  for (int i = 1; i < N; i++){
    if (pre < A[i]){
      //ok
      if (flag == 1 or flag == 0){
        flag = 1;
      }else{
        res++;
        flag = 0;
      }
    }else if(pre > A[i]){
      if (flag == -1 or flag == 0){
        flag = -1;
      }else{
        res++;
        flag = 0;
      }
    }
    pre = A[i];
  }
  res++;
  cout << res << endl;
  return 0;
}


Measured memory_bytes: 764
#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>
#include <deque>
#include <assert.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <stdio.h>
#include <string.h>
#include <utility>
#include <math.h>
#include <bitset>
#include <iomanip>
#include <complex>
using namespace std;
#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
#define ALL(x) (x).begin(),(x).end()
#define RALL(x) (x).rbegin(),(x).rend()
#define IDX(vec, element_iter) distance((vec).begin(), element_iter)
#define print(x) cout<<(x)<<'\n'
#define print_vec(v) rep(i,v.size()){if(i!=0)cout<<" ";cout<<v[i];}cout<<'\n'
#define pe(x) cout<<(x)<<" "
#define DEBUG(x) cout<<#x<<": "<<x<<'\n'
#define DEBUG_VEC(v) cout<<#v<<":";rep(i,v.size())cout<<" "<<v[i];cout<<'\n'
#define pb push_back
#define mp make_pair
#define MOD 1000000007 //10^9+7
#define fi first
#define sc second
using ll=long long;
using pi=pair<ll,ll>;
using vi=vector<int>;
using vll=vector<ll>;
using vstr=vector<string>;
int dx[4]={0,0,-1,1};
int dy[4]={-1,1,0,0};
void yes(bool c) { if (c)print("Yes"); else print("No"); };

void solve() {
    ll N, K; cin >> N >> K;
    vll A(N);
    rep(i,N) {
        cin >> A[i];
        A[i]--;
    }
    vi before(N,-1);
    before[0] = 0;
    int town = 0;
    ll cnt = 0;
    ll offset = -1;
    ll duration = -1;
    ll loopstart = -1;
    if(K <= N){
        rep(i,K){
            town = A[town];
        }
        print(town+1);
        return;
    }else{
        rep(i,N){
            // DEBUG(town);
            town = A[town];
            cnt++;
            // if(before[town] != -1)
            if(before[town] == -1) {
                before[town] = cnt;
            }else{
                offset = before[town];
                duration = cnt - before[town];
                loopstart = town;
                break;
            }
        }
        // DEBUG(offset);
        // DEBUG(duration);
        // DEBUG(loopstart);
        K -= offset;
        K %= duration;
        town = loopstart;
        rep(i,K%duration){
            town = A[town];
        }
        print(town+1);
        return;
    }
}

int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
	cout<<fixed<<setprecision(20);
    //int q; cin >> q;
	//while (q--)
		solve();
    return 0;
}


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

int dotCnt(string s) {
    int c = 0;
    while (s[c] == '.') c++;
    return c;
}

int main(void) {
    while (1) {
        int n;
        string s;
        cin >> n;
        if (n == 0) break;

        vector<string> ls;
        vector<int> dc;

        char pref[1050][2000];

        for (int i = 0; i < n; i++) {
            cin >> s;
            ls.push_back(s);
            dc.push_back(dotCnt(ls[i]));

            for (int j = 0; j < dc[i]; j++) {
                if (j == dc[i] - 1) pref[i][j] = '+';
                else pref[i][j] = ' ';
            }
        }

        for (int i = n - 1; i > 0; i--) {
            int pos = i;
            for (int j = i - 1; j > 0; j--) {
                if (dc[i] > dc[j]) break;
                if (dc[i] == dc[j]) {
                    pos = j;
                    break;
                }
            }
            for (int j = i - 1; j > pos; j--) pref[j][dc[i] - 1] = '|';
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < dc[i]; j++) {
                cout << pref[i][j];
            }
            cout << ls[i].substr(dc[i], ls[i].size() - dc[i]) << endl;
        }

    }

    return 0;
}

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

int n;
int a[200000];
bool f = 1;

int main()
{
	cin >> n;

	for (int i = 0; i < n; i++)
		cin >> a[i];

	sort(a, a + n);

	for (int i = 1; i < n; i++) {
		if (a[i] == a[i - 1]) {
			f = 0;
			break;
		}
	}

	if (f)
		cout << "YES" << endl;
	else
		cout << "NO" << endl;

	return 0;
}

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

using namespace std;

long long inf=1000000007;

int main(){
	long long a;
	string b;
	cin>>a>>b;
	long long ans=0;

	ans+=a*(b.at(0)-'0');

	long long pre=0;

	pre+=a*(b.at(2)-'0')*10;
	pre+=a*(b.at(3)-'0')*1;

	cout<<ans+pre/100<<endl;

	return 0;
}


Measured memory_bytes: 3632
from itertools import combinations

n = int(input())
towns = []
for town in range(n):
  x, y = [int(xy) for xy in input().split()]
  towns.append((x,y))

lengths = [((a[0]-b[0])**2 + (a[1]-b[1])**2)**0.5 for a, b in combinations(towns, 2)]
average_lengths = 2*sum(lengths)/n

print(average_lengths)

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

const string DAYS_OF_WEEK[7] = {"Thursday",
                                "Friday",
                                "Saturday",
                                "Sunday",
                                "Monday",
                                "Tuesday",
                                "Wednesday"};

const int FIRST_DAY_NUM[12] = {0, 31, 60, 91, 121, 152, 182, 213, 244, 274, 305, 335};

int main()
{
    int m;
    int d;
    while(1)
    {
        int day_num;
        cin >> m >> d;
        if(m == 0 && d == 0)
        {
            break;
        }
        /* calculate nunmber of days from Jan 1 */
        day_num = FIRST_DAY_NUM[m - 1] + d - 1;
        cout << DAYS_OF_WEEK[day_num % 7] << endl; 
    }
    return 0;
}



Measured memory_bytes: 3136
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
using P = pair<int,int>;
/* ちゃんと考えてわかって実装 */

int main(void){
    int n;
    cin >> n;
    vector<double> c(n), s(n), f(n);
    for(int i=1; i<=n; i++){
        cin >> c[i] >> s[i] >> f[i];
    }

    for(int i=1; i<=n; i++){
        double time = 0;
        time += s[i] + c[i];
        for(int j=i+1; j<=n-1; j++){
            double wait;
            if(time < s[j]){
                wait = s[j] - time;
            }
            else{
                wait = ceil(time/f[j])*f[j] - time;
            }
            time += wait;
            time += c[j];
        }
        cout << int(time) << endl;
    }
    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

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

		// 整数の入力
		String S = sc.next();

		if(S.equals("Sunny")){
			System.out.println("Cloudy");
		}else if(S.equals("Cloudy")){
			System.out.println("Rainy");
		}else{
			System.out.println("Sunny");
		}

		sc.close();
	}
}


Measured memory_bytes: 22612
#include <iostream>
#include <cstring>
#include <string>

using namespace std;

int main() {
    string S;
    int count = 0;

    cin >> S;

    if (S[0] == 'o') {
        count++;
    } 
    if (S[1] == 'o') {
        count++;
    }
    if (S[2] == 'o') {
        count++;
    }

    int total = 700 + 100 * count;

    cout << total << endl;

    return 0;
}

Measured memory_bytes: 256
//#pragma warning disable

using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Text;

public class Test
{
    public static void Main()
    {
        // 貪欲法

        var N = long.Parse(Console.ReadLine());

        var a = Console.ReadLine().Split(' ').Select(long.Parse).ToArray();



        long count = 0;

        for (int i = 0; i < N - 1; i++)
        {
            if (a[i] == i + 1)
            {
                count++;

                var temp = a[i];
                a[i] = a[i + 1];
                a[i + 1] = temp;
            }
        }

        for (int i = (int)N - 1; i >= 1; i--)
        {
            if (a[i] == i + 1)
            {
                count++;

                var temp = a[i];
                a[i] = a[i - 1];
                a[i - 1] = temp;
            }
        }

        Console.WriteLine(count);
    }
}

Measured memory_bytes: 19168