akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;

ll knap(ll i,ll w,vector<vector<ll>> &v,ll n,vector<vector<ll>> &dp)
{
    if(i>=n)
    {
        return 0;
    }
    if(w==0)
    {
        return 0;
    }
    if(dp[i][w]!=-1)
        return dp[i][w];
    ll l,r;
    if(v[i][0]<=w)
    {
        l=v[i][1]+knap(i+1,w-v[i][0],v,n,dp);
        r=knap(i+1,w,v,n,dp);
        dp[i][w]=max(l,r);
        return dp[i][w];
    }
    dp[i][w]=knap(i+1,w,v,n,dp);
    return dp[i][w];
}

int main()
{
    ll n,i,j,k;
    cin>>n>>k;
    vector<vector<ll>> v(n,vector<ll>(2,0));
    for(i=0;i<n;i++)
        cin>>v[i][0]>>v[i][1];
    vector<vector<ll>> dp(n,vector<ll>(k+1,-1));
    cout<<knap(0,k,v,n,dp)<<"\n";
    return 0;
}

Measured memory_bytes: 82356
n,p=map(int,input().split())
rem=[0]*n
cnt=[0]*p
s=input()[::-1]
if p==5:
    s=s[::-1]
    ans=0
    for i in range(n):
        if int(s[i])%5==0:
            ans+=i+1
    print(ans)
    exit()
if p==2:
    s=s[::-1]
    ans=0
    for i in range(n):
        if int(s[i])%2==0:
            ans+=i+1
    print(ans)
    exit()
kake=1
for i in range(n):
    rem[i]=rem[i-1]+int(s[i])*kake
    rem[i]%=p
    cnt[rem[i]]+=1
    kake*=10
    kake%=p
    
ans=0
for i in range(p):
    ans+=cnt[i]*(cnt[i]-1)//2
print(ans+cnt[0])


Measured memory_bytes: 11048
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson, minimum_spanning_tree
from scipy.sparse import csr_matrix, coo_matrix, lil_matrix
import numpy as np
from collections import deque, Counter, defaultdict
from itertools import product, permutations,combinations
from operator import itemgetter
from heapq import heappop, heappush
from bisect import bisect_left, bisect_right, bisect
from fractions import gcd
from math import ceil,floor, sqrt, cos, sin, pi, factorial
from functools import reduce
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
INF = float('inf')
MOD = 10**9+7
def lcm_base(a, b):
    return (a * b) // gcd(a, b)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)


def main():
  n, m = map(int, readline().split())
  a = np.array(input().split(), np.int64)
  a //= 2
  b=np.copy(a)
  while True:
    c = b%2
    if c.sum() == 0:
      b //= 2
    elif c.sum() == n:
      break
    else:
      print(0)
      sys.exit()
  d = lcm_list(a)
  if d>10**9:
    ans = 0
  else:
    ans = (m//d) - (m//(d+d))
  print(ans)
  
  
  
if __name__ == '__main__':
  main()

Measured memory_bytes: 27232
n=int(input())
for i in range(n):
    a,b,c,d=map(int,input().split())
    q,w,e,r,g=0,0,0,0,0
    q,w=a*c,b*d
    e=q+w
    f=[]
    f.append(e)
    if c<5 and d<2:
        g=(a*5+b*2)*0.8
        f.append(g)
    if c<5 and d>=2:
        g=(a*5+b*d)*0.8
        f.append(g)
    if c>=5 and d<2:
        g=(a*c+b*2)*0.8
        f.append(g)
    if c>=5 and d>=2:
        e=e*0.8
        f.append(e)
    print(int(min(f)))


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

int main()
{
  int n;
  cin>>n;
  
  vector<int>h(n);
  for(int i=0;i<n;i++)cin>>h[i];
  
  long long ans=0;
  
  for(int i=0;i<n;i++)
  {
    if(i==0)ans+=h[i];
    else 
    {
      if(h[i]>h[i-1])
      {
        ans+=(h[i]-h[i-1]);
      }
    }
  }
  cout<<ans<<endl;
  return 0;
}
        
        
    

Measured memory_bytes: 256
S = list(str(input()))

req1 = int((len(S) - 1) / 2)
req2 = int((len(S) + 3) / 2) - 1
if S == list(reversed(S)) and S[:req1] == list(reversed(S[:req1])) and S[req2:] == list(reversed(S[req2:])):
  print("Yes")
else:
  print("No")

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

// main
int main(){
    int A, B; cin >> A >> B;
    int count = 0;
    for(int num = A; num <= B; ++num){
        int num_digits[5];
        int num_tmp = num;
        for(int i = 0; i < 5; ++i){
            num_digits[i] = num_tmp % 10;
            num_tmp /= 10;
        }
        if(num_digits[0] == num_digits[4] && num_digits[1] == num_digits[3]) ++count;
    }
    cout << count << "\n";
    return 0;
}

Measured memory_bytes: 256
//CLMN
//Every cloud has a silver lining
//Hakuna matata

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> ii;

#define fi first
#define se second
#define pb push_back
#define sqr(x) ((x) * (x))

const char *fin = "";
const char *fon = "";

#define oo (int) (1e9+7)
#define maxn (int) (1e5+5)

int a[maxn];
bool fr[maxn];
int n;

void trace(int u, int cnt) {
    if (u == 2) {
        cout << cnt;
        exit(0);
    }
    if (!fr[u]) {
        cout << -1;
        exit(0);
    }
    fr[u] = false;
    trace(a[u], cnt + 1);
}

void inp() {
    cin >> n;
    for(int i = 1; i <= n; ++i) cin >> a[i];
    memset(fr, true, sizeof(fr));
    trace(1, 0);
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    //freopen(fin, "r", stdin); freopen(fon, "w", stdout);
    inp();
    return 0;
}


Measured memory_bytes: 768
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
#define rrep(i,n) for(int i=1;i<(n);++i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define dunk(a) cout << (a) << "\n"
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int inf = 1001001001;
const int mod = 1000000007;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int x;
	cin >> x;
	int ans = int(x / 500) * 1000;
	ans += int(int(x % 500) / 5) * 5;
	dunk(ans);
	return 0;
}

Measured memory_bytes: 384
#include "bits/stdc++.h"
using namespace std;
#define rep(i,n)for(int i=0;i<(int)(n);i++)
#define PI 3.141592653589793
//vector < vector<int>>a(0, vector<int>(0));二次元配列宣言


int main()
{
	int n, d;
	cin >> n >> d;
	int ans;
	ans = n / (2 * d + 1);
	if (n % (2 * d + 1) != 0)
		ans++;
	cout << ans << endl;
}


Measured memory_bytes: 3584
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const int dx[4] = { 0, -1, 1, 0 };
const int dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}

template<class T1, class T2> void chmin(T1 &a, T2 b) { if (a>b)a = b; }

template<class T1, class T2> void chmax(T1 &a, T2 b) { if (a<b)a = b; }
template<class T>
void Add(T &a, const T &b, const T &mod = 1000000007) {
	int val = ((a % mod) + (b % mod)) % mod;
	if (val < 0) { val += mod; }
	a = val;
}
////////////////////////////////////////

int main() {
	int N;
	string S;
	cin >> N >> S;
	int ans = INF;
	int key1[200100] = {};//key1[i]でi文字目までに含まれている.の数
	for (int i = 0; i < N; ++i) {
		key1[i + 1] += key1[i];
		if (S[i] == '.') {
			key1[i + 1]++;
		}
	}
	for (int i = 0; i <= N; ++i) {
		int key = 0;
		key += (i-key1[i]);
		key += (key1[N] - key1[i]);
		ans = min(ans, key);
	}
	cout << ans << endl;
	return 0;
}



Measured memory_bytes: 1412
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
using ll = long long;
using P = pair<int, int>;

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

    int X, Y, A, B, C; cin >> X >> Y >> A >> B >> C;
    priority_queue<P> que;
    for (int i = 0; i < A; i++) {
        int p; cin >> p;
        que.push(P(p, 0));
    }
    for (int i = 0; i < B; i++) {
        int q; cin >> q;
        que.push(P(q, 1));
    }
    for (int i = 0; i < C; i++) {
        int r; cin >> r;
        que.push(P(r, 2));
    }

    ll ans = 0;
    int x = 0, y = 0, z = 0;
    while (!que.empty()) {
        P p = que.top(); que.pop();
        if (p.second == 0) {
            if (x == X) continue;
            x++;
        }
        if (p.second == 1) {
            if (y == Y) continue;
            y++;
        }
        if (p.second == 2) {
            z++;
        }
        ans += p.first;
        if (x + y + z == X + Y) break;
    }
    cout << ans << "\n";
}

Measured memory_bytes: 6384
def main():
    C = [[int(_) for _ in input().split()] for i in range(3)]
    if C[0][0] - C[0][1] == C[1][0] - C[1][1] and C[2][0] - C[2][1] == C[1][0] - C[1][1]:
        if C[0][1] - C[0][2] == C[1][1] - C[1][2] and C[2][1] - C[2][2] == C[1][1] - C[1][2]:
            print("Yes")
            return
    print("No")


if __name__ == "__main__":
    main()

Measured memory_bytes: 3064
d = int(input())
c = list(map(int, input().split()))
s = [list(map(int, input().split())) for i in range(d)]
t = [int(input()) for i in range(d)]
last = [-1]*26

ans = 0
for i in range(d):
    op = t[i]-1
    ans += s[i][op]
    last[op]=i
    for j in range(26):
        ans -= c[j]*(i-last[j])
    print(ans)



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

using namespace std;
using ll = long long;
int main() {
    int a,b;
    cin>>a>>b;
    if(a+1<=b)cout<<b+b-1<<endl;
    else if(a!=b)cout<<a+a-1<<endl;
    else cout<<a+b<<endl;
    return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
#define   LF      '\n'
#define   ALL(x)  x.begin(), x.end()
#define   iostreamBooster()  do{cin.tie(nullptr);ios::sync_with_stdio(false);}while(0)
using namespace std;
typedef int64_t i64;
typedef pair<int,int> pii;
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 = 0x3f3f3f3f'3f3f3f3fLL;


signed main()
{
  int N;
  string s[1005];

  set<string> U;

  cin >> N;
  cin >> s[0];
  U.insert(s[0]);

  bool ok = true;
  for (int i = 1; i < N; ++i) {
    cin >> s[i];
    if (U.count(s[i]) || s[i].front() != s[i-1].back()) {
      ok = false;
    }
    U.insert(s[i]);
  }

  puts(ok ? "Yes" : "No");
  return 0;
}



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


//SHORTCUTS

#define ll long long
#define endl '\n'
#define i1(a) cin>>a
#define i2(a,b) cin>>a>>b
#define i3(a,b,c) cin>>a>>b>>c
#define o1(a) cout<<a<<endl
#define o2(a,b) cout<<a<<" "<<b<<endl
#define o3(a,b,c) cout<<a<<" "<<b<<" "<<c<<endl
#define f(i,a,b) for(int i = a;i<b;i++)
#define fe(i,a,b) for(int i = a;i<=b;i++)
#define fi(i,a,b) for(i=a;i<b;i++)
#define eb emplace_back
#define pb push_back
#define pob pop_back
#define mp make_pair


// DEBUG CODE & FAST OUTPUT

#define printv(a) for (int i = 0; i < a.size(); i++) cout << a[i] << ' ';
#define printvl(a) for (int i = 0; i < a.size(); i++) cout << a[i] << endl;
#define printa(a, n) for (int i = 0; i< n; i++) cout << a[i] << ' ';
#define printal(a, n) for (int i = 0; i < n; i++) cout << a[i] << endl;


//DATA STRUCTURES

#define pq priority_queue
#define ms multiset
// #define y0 _y0_
// #define y1 _y1_
// #define div divi

typedef long double ld;
typedef vector <int> vi;
typedef vector <ll> vll;
typedef vector <ld> vld;
typedef vector <string> vs;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef vector <vi > vvi;
typedef vector <vll > vvll;
typedef vector <pii > vpii;
typedef vector <pll > vpll;

//IMP CONSTANT
const int mod = 1e9 + 7, inf = 1e9 + 7;
const ll infll = 1e18 + 7;
bool google_contest = false;


//MODULAR OPERATIONS
ll myadd(ll a,ll b){
    ll ans = a+b;
    ans-= ans>=mod ? mod : 0;
    return ans; 
}
ll mysub(ll a, ll b){
    return (a-b+mod)%mod;
}
ll mymul(ll a,ll b){
    return (a*b)%mod;
}
ll mypow(ll a, ll b){
    ll ans = 1;
    while(b>0)
        if(b&1) ans = mymul(ans,a),b--;
        else a = mymul(a,a),b >>= 1;
    return ans;
}
ll nCr(ll n,ll r){
    if(r==0)return 1;
    if(r==1)return n;
    if(n==0)return 0;
    return mymul(n,mymul(nCr(n-1,r-1),mypow(r,mod-2)));
}

//    /\    |  |\  /|                      
//   /__\   |  | \/ |           
//  /    \  |  |    | 



int main(){

ios_base::sync_with_stdio(0);
cin.tie(0); 
cout.tie(0);

int t,tt;
t=1;
// i1(t);
if(google_contest)tt=1;

while(t--){

int h1,m1;
i2(h1,m1);

int h2,m2;
i2(h2,m2);

int k;
i1(k);

int a = (h2-h1)*60-k;

if(m2<m1){
    a-=(m1-m2);
}else{
    a+=(m2-m1);
}
o1(a);


if(google_contest){
    cout<<"Case "<<tt++<<": ";
}
}

return 0;   
}


//    /\    |  |\  /|                      
//   /__\   |  | \/ |           
//  /    \  |  |    |   OVER!!!!


Measured memory_bytes: 3656
#include <cstdio>
#include <iomanip>    // setw 控制输出间隔函数
#include <iostream>   // cin, cout, abs
#include <algorithm>  // max, min, swap, sort
#include <cmath>      // pow
#include <cstring>    // strlen, memset
#include <set>        // set 集合
#include <stack>      // stack 栈
#include <queue>      // queue 队列
#include <string>     // string 字(yang)符(rou)串, substr
#include <map>
#include <fstream>
using namespace std;
int a[205];
int main()
{
    int n;
    scanf("%d", &n);
    for( int i = 1; i <= n * 2; i++)
        scanf("%d", &a[i]);
    sort( a + 1, a + 2 * n + 1);
    int t = 0;
    for( int i = 1; i <= n * 2; i += 2)
        t += a[i];
    printf("%d\n", t);
    return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
using namespace std;
char q[10];
int main()
{
	scanf("%s",q);
	int ans = 0;
	for(int i = 0 ; i < strlen(q) ; i = i + 1)
	{
		if(q[i] == '2')
			ans++;
	}
	printf("%d",ans);
	return 0;
}

Measured memory_bytes: 128
#include<cstdio>
#include<cmath>
#include<string>
#include<iostream>
#include<algorithm>
#include<utility>
#include<vector>
#include<map>
#include<set>
#include<limits>
#include<bitset>
#include<array>
#include<numeric>
#include<iomanip>

using namespace std;
typedef long long int ll;

ll a,b,c;
string s;
map<char,bool> q;

int main(){
    cin>>s;
    q['N']=false;
    q['S']=false;
    q['E']=false;
    q['W']=false;
    for(int i=0;i<s.length();i++)q[s[i]]=true;
    cout<<(q['N']==q['S'] and q['W']==q['E'] ? "Yes":"No")<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mit map<int,int>::iterator
#define sit set<int>::iterator
#define itrm(g,x) for(mit g=x.begin();g!=x.end();g++)
#define itrs(g,x) for(sit g=x.begin();g!=x.end();g++)
#define ltype int
#define rep(i,j,k) for(ltype(i)=(j);(i)<=(k);(i)++)
#define rap(i,j,k) for(ltype(i)=(j);(i)<(k);(i)++)
#define per(i,j,k) for(ltype(i)=(j);(i)>=(k);(i)--)
#define pii pair<int,int>
#define fi first
#define se second
#define mpr make_pair
#define pb push_back
#define fastio ios::sync_with_stdio(false)
const int inf=0x3f3f3f3f,mod=998244353;
const double pi=3.1415926535897932,eps=1e-6;
void chmax(int &x,int y){if(x < y) x = y;}
void chmin(int &x,int y){if(x > y) x = y;}
int f[3005][3005],n,a[3005],s,ans;
int main()
{
    scanf("%d%d",&n,&s);
    rep(i,1,n) scanf("%d",a+i);
    rap(i,0,n) f[i][0] = i + 1;
    rep(i,1,n) rep(j,1,s)
    {
        f[i][j] = f[i-1][j];
        if(j >= a[i]) f[i][j] += f[i-1][j-a[i]];
        f[i][j] %= mod;
    }
    rep(i,1,n) {
        ans += (ll)(f[i][s] - f[i - 1][s] + mod) * (n - i + 1) % mod;
        if(ans >= mod) ans -= mod;
    }
    printf("%d\n",ans);
    return 0;
}

Measured memory_bytes: 35456
///supercalifragilisticexpialidocious.
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cassert>
#include <cstdlib>
#include <cctype>
#include <ctime>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <numeric>
#include <utility>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <list>
#include <bitset>
#include <complex>
using namespace std;
#define f first
#define s second
#define PB pop_back 
#define pb push_back
#define mp make_pair
#define int long long
#define y1 y_golabi
#define sz(s) (int)s.size()
#define seper(n) setprecision(n)
#define all(v) v.begin(),v.end()
#define mem(a,b) memset(a,b,sizeof a)
#define IOS ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
typedef long long ll; 
typedef map<int , int> mii;
typedef pair<int , int> pii; 
typedef map<string , int> msi;
typedef pair<int , string> pis; 
typedef pair<int , pair<int , int> > piii;
const int MAXN = 1e5 + 10;
int n , cnt , ptr , ptr2 , a[MAXN];
int32_t main()
{
	cin >> n;
	for(int i = 0; i < n; i++)
		cin >> a[i];
	for(int i = 0 ; i < n ; i ++)
	{
		ptr = i , ptr2 = i;
		while(a[ptr] <= a[ptr + 1] and ptr < n)
			ptr ++;
		while(a[ptr2] >= a[ptr2 + 1] and ptr2 < n)
			ptr2 ++;
		i = max(ptr , ptr2) , cnt ++;
	}
	return cout << cnt << endl , 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(i,m,n) for(int i=(int)(m); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define rrep(i,n) RREP(i,n-1,0)
#define all(v) v.begin(), v.end()
const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 1e9+7;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n; ll k; cin >> n >> k;
  vector<int> A(n); rep(i, n) cin >> A[i];
  vector<ll> cnt(2001);
  rep(i, n) cnt[A[i]]++;
  rep(i, 2001) if(i) cnt[i] += cnt[i-1];
  ll ans = 0;
  rep(i, n) {
    ll cur = 0;
    REP(j, i+1, n) if(A[i] > A[j]) cur++;
    (ans += cur*k%mod) %= mod;
    ll m = cnt[A[i]-1];
    (ans += (k-1)*k/2%mod*m%mod) %= mod;
  }
  cout << ans << "\n";
  return 0;
}


Measured memory_bytes: 3636
// In the name of God

#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 rep(i, a, b) for (int i = (a), i##_end_ = (b); i < i##_end_; ++i)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define x first
#define y second
#define pb push_back
#define SZ(x) (int((x).size()))
#define ALL(x) (x).begin(), (x).end()

template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
template<typename T> inline bool smin(T &a, const T &b)   { return a > b ? a = b : a;    }
template<typename T> inline bool smax(T &a, const T &b)   { return a < b ? a = b : a;    }

typedef long long LL;

const int N = (int) 1e6 + 6, mod = (int) 0;
int deg[N], mark[N];
vector<int> adj[N], ver;
void dfs(int v) {
	if (mark[v]++) return;
	ver.pb(v);
	for (int u : adj[v])
		dfs(u);
}
int main() {
	int n, m;
	cin >> n >> m;
	for (int j = 0; j < m; ++j) {
		int u, v;
		cin >> u >> v;
		--u, --v;
		adj[u].pb(v);
		adj[v].pb(u);
		deg[u]++;
		deg[v]++;
	}
	for (int j = 0; j < n; ++j)
		if (deg[j] & 1) {
			cout << "No\n";
			return 0;			
		}
	int res = 0, comps = 0;
	for (int j = 0; j < n; ++j) {
		if (!mark[j] && deg[j] > 0) {
			ver.clear();
			dfs(j);
			int cnt = 0;
			for (int x : ver)
				cnt += deg[x];
			cnt /= 2;
			int cnt_ver = (int) ver.size();
			int dif = cnt - cnt_ver + 1;
			res += dif;
		}
	}
	int a = -1, b = -1;
	for (int j = 0; j < n; ++j)
		if (deg[j] == 4) {
			++comps;
			if (a != -1)
				b = j;
			else
				a = j;
		}
	if (comps == 2 && res == 3) {
		memset(mark, 0, sizeof mark);
		int cnt = 0;
		mark[a] = 1;
		mark[b] = 1;
		for (int x : adj[a])
			if (!mark[x] || x == b) {
				dfs(x);
				++cnt;
			}
		if (cnt == 4) {
			cout << "No\n";
			return 0;
		}
	}
	if (res < 3) {
		cout << "No\n";
		return 0;
	}
	cout << "Yes\n";
}



















Measured memory_bytes: 36216
#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <string>
#include <bitset>
#include <utility>
#include <numeric>
#include <queue>
#include <stack>

using ll = long long;
using namespace std;

constexpr int MOD = 1e9 + 7;
constexpr ll MOD_LL = ll(1e9 + 7);

int main(void) {
	char c;
	cin >> c;
	
	if( c - 'a' >= 0 ) cout << 'a' << endl;
	else cout << 'A' << endl;
	
	return 0;
}


Measured memory_bytes: 3592
//コンパイラ最適化用
#pragma GCC optimize("Ofast")

//インクルード(アルファベット順)
#include<algorithm>//sort,二分探索,など
#include<bitset>//固定長bit集合
#include<climits>//INT_MAXなど
#include<chrono>//実行時間計測
#include<cmath>//pow,logなど
#include<complex>//複素数
#include<deque>//両端アクセスのキュー
#include<functional>//sortのgreater
#include<iomanip>//setprecision(浮動小数点の出力の誤差)
#include<iostream>//入出力
#include<iterator>//集合演算(積集合,和集合,差集合など)
#include<map>//map(辞書)
#include<numeric>//iota(整数列の生成),gcdとlcm,accumulate
#include<queue>//キュー
#include<set>//集合
#include<stack>//スタック
#include<string>//文字列
#include<unordered_map>//順序保持しないmap
#include<unordered_set>//順序保持しないset
#include<utility>//pair
#include<vector>//可変長配列

using namespace std;
typedef long long ll;

// clang++ main.cc -std=c++11 -stdlib=libc++

/*
  cin >> N;
  vector<int> a(N);
  for (int i = 0; i < N; i++)
    cin >> a[i];
*/

signed main(){
  ll N;
  cin >> N;

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

  unordered_map<int, int> hash;
  for (int i = 0; i < N; i++)
    hash[a[i]] = i + 1;

  for (int i = 0; i < N; i++)
    cout << hash[i + 1] << " ";
  cout << endl;

  return 0;
}

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

int main(){
	int x,y;
	const int am = 200;
	const int pm = 300;
	string str;
	for(int i=0;i<9;i++){
		cin >> str >> x >> y;
		cout << str << " " << x+y << " " << x*am+y*pm << endl;
	}
	return 0;
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
#define MSET(x,y) memset(x,y,sizeof(x))
#define F first
#define S second
#define MP make_pair
#define PB push_back
#define SZ size()
#define M 100005
#define ll long long
#define ld long double
#define INF 1e18
#define endl "\n"
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
ll MOD = 1000000007;
string yes = "YES\n";
string no = "NO\n";
#define PI 3.1415926535

int main() {
    fastio;
    ll n,k;
    cin>>n>>k;
    vector<ll> a(n);
    for( auto &itr : a) {
        cin>>itr;
    }
    vector<ll> dp(n, INF);
    dp[0] = 0;
    for(ll i=1;i<=k;i++) {
        dp[i] = abs(a[i] - a[0]);
    }
    for(ll i = 1;i < n; i++ ) {
        for(ll j = 1;j<=k and i-j>=0; j++ ) {
            dp[i] = min(dp[i-j] + abs(a[i] - a[i-j]), dp[i]);
        }
    }
    cout<<dp[n-1]<<endl;
}

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

using namespace std;
typedef long long ll;
const ll mod=1e9+7;

int main(){
 int n;cin>>n;
 int arr[n];
 for(int i=0;i<n;i++)
  cin>>arr[i];
sort(arr,arr+n);
for(int i=0;i<n-1;i++){
  if(arr[i]==arr[i+1]){
      cout<<"NO";
      break;}
  if(i==n-2)
      cout<<"YES";
}
  return 0;
}


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

int main(){
//  freopen("in.txt", "r", stdin);
//  freopen("out.txt", "w", stdout);
  int n;
  cin >> n;
  int a[n];
  for(int i = 0;i < n;i++){
    cin >> a[i];
    a[i] -= i + 1;
//    cout << a[i] << endl;
  }
  sort(a, a + n);
  int x = a[(n) / 2];
  ll res = 0;
  for(int i = 0;i < n;i++)
    res += abs(x - a[i]);
  cout << res;
  return 0;
}


Measured memory_bytes: 1024
use proconio::input;

const MOD: usize = 1_000_000_007;

fn main() {
  input! {
    s: usize,
  }
  
  let mut dp: Vec<usize> = vec![0;s+1];  
  if s < 3 {
    println!("0");
    return
  }
  
  if s < 6 {
    println!("1");
    return
  }
  
  dp[3] = 1;
  dp[4] = 1;
  dp[5] = 1;
  for i in 6..=s {
    dp[i] = (dp[i-1] + dp[i-3]) % MOD;
  }
  
  println!("{}", dp[s]);
}

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

using namespace std;

bool isprime(int n) {
	for (int i = 2; i * i <= n; i++)
		if (n % i == 0)
			return false;
	return n != 1;
}

int main() {
	int n, a, ans = 0;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a;
		if (isprime(a) == true)
			ans++;
	}
	cout << ans << endl;
	return 0;
}

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

using namespace std;

template<class T> inline T sqr(const T& a) {
  return a * a;
}

template<class T> inline int len(const T &c) {
  return static_cast<int>(c.size());
}

template<class T> inline bool maximize(T &r, const T c) {
  if (r < c) {
    r = c;
    return true;
  }
  return false;
}

template<class T> inline bool minimize(T &r, const T c) {
  if (r > c) {
    r = c;
    return true;
  }
  return false;
}

typedef long long li;
typedef long double ld;
typedef pair<int, int> pt;

const ld EPS = 1e-9;
const ld PI = 2 * acos(0.0);
const int N = 100;

int F(int n, int k) {
  if (n == 0) {
    return 0;
  }
  if (k == 0) {
    return -1;
  }
  int next = n - min(k, n);
  int r = F(next, k - 1);
  if (r == -1)
    return r;
  return 1 + r;
}

int G(int n) {
  int lf = 0, rg = n;
  while (lf + 1 < rg) {
    int m = (lf + rg) / 2;
    if (F(n, m) < 0) {
      lf = m;
    } else {
      rg = m;
    }
  }
  for (; lf <= rg; ++lf) {
    if (F(n, lf) >= 0)
      break;
  }
  return lf;
}

int main() {
  int x;
  cin >> x;
  cout << G(x) << endl;
  return 0;
}


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

using namespace std;

using ll = long long;

const ll MOD = 1000000007;

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

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

    unordered_map<ll, ll> mp;

    ll zero = 0;

    for(int i=0;i<n;i++){
        ll a; cin >> a;
        mp[a]++;
        if(a == 0) zero++;
    }

    if(zero == n){
        cout << "Yes" << endl;
        return 0;
    }

    // x x 0 x x 0 x x 0 ... 
    if(!(n % 3) && mp.size() == 2 && zero == n / 3){
        bool ok = true;
        for(auto m: mp){
            if(m.first != 0 && m.second != 2*n / 3){
                ok = false;
            }
        }
        if(ok){
            cout << "Yes" << endl;
            return 0;
        }
    }

    // x y z x y z x y z ...
    if(!(n % 3) && mp.size() == 3){
        ll sum = 0;
        bool ok = true;
        for(auto m: mp){
            sum ^= m.first;
            if(m.second != n/3){
                ok = false;
                break;
            }
        }
        if(ok && sum == 0){
            cout << "Yes" << endl;
            return 0;
        }
    }

    cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 3724
#include<bits/stdc++.h>
#define N 1000005
using namespace std;
int n,m,q;
int z,g,mod;
int u[N],v[N],w[N];
int fa[N * 6];
bool vis[2][N];

template <class T> inline void read(T &x)
{
	char c;int sign=1;
	while((c=getchar())>'9'||c<'0') if(c=='-') sign=-1; x=c-48;
	while((c=getchar())>='0'&&c<='9') x=(x<<1)+(x<<3)+c-48; x*=sign;
}
int getid(int x,int p,int q) { return (x - 1) * 6 + p * 3 + q + 1; }
int gcd(int a,int b) { return (!b) ? a : gcd(b,a%b); }
int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
void merge(int x,int y) { if(find(x) != find(y)) fa[find(x)] = find(y); }
int main()
{
	read(n);read(m);read(q);read(mod);
	for(int i=1;i<=m;++i)
	{
		read(u[i]);read(v[i]);read(w[i]);
		g = gcd(g,abs(w[i] - w[1]));
	}
	if(!g) g = mod;
	mod = gcd(mod,3 * g);
	z = w[1] % g;
	
	for(int i=1;i<=6 * n;++i) fa[i] = i;
	for(int i=1;i<=m;++i)
	{
		int c = (w[i] - z) / g;
		for(int p=0;p<=1;++p)//次幂 
		{
			for(int q=0;q<=2;++q)//常数
			{
				merge(getid(u[i],p,q),getid(v[i],p ^ 1,(q * 2 + c) % 3));
				merge(getid(v[i],p,q),getid(u[i],p ^ 1,(q * 2 + c) % 3));
			}
		}
	}
	
	for(int i=0,j=z;i<(mod*2);++i,j = j * 2 % mod) vis[i & 1][j] = 1;
	
	while(q--)
	{
		int s,t,r;
		read(s);read(t);read(r);
		bool ok = 0;
		for(int p=0;p<=1;++p)
		{
			for(int q=0;q<=2;++q)
			{
				if(find(getid(t,0,0)) == find(getid(s,p,q)))
				{
					ok |= vis[p][(r + z + (3 - q) * g) % mod];
				}
			}
		}
		puts(ok ? "YES" : "NO");
	}
	return 0;
}

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

int main(){
    int x, n;
    cin >> x >>n;
    vector<int> a(n);
    for(int i=0; i<n; i++){
        cin >> a[i];
    }
    sort(a.begin(), a.end());

    if(n==0){
        cout << x << endl;
        return 0;
    }
    
    int ans1, ans2;
    for(int i=0; i<=101; i++){
        int bo=0;
        ans1 = x-i;
        for(int j=0; j<n; j++){
            if(ans1==a[j]){
              bo=1;  
              break;
            } 
        }
        if(bo==0) break;
    }

      for(int i=0; i<=101; i++){
        int bo=0;
        ans2 = x+i;
        for(int j=0; j<n; j++){
            if(ans2==a[j]){
              bo=1;  
              break;
            } 
        }
        if(bo==0) break;
    }
    if(abs(x-ans1)>abs(x-ans2)){
        cout << ans2 << endl;
    }
    else cout << ans1 << endl;

    return 0;
}

Measured memory_bytes: 3624
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <tuple>
#include <numeric>
#include <functional>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 998244353;
const ll INF = 1e16;
const ll MAX_N = 100010;
 
int main() {
    ll n;
    cin >> n;

    vvl f(n, vl(10));
    rep(i, n) {
        rep(j, 10) {
            cin >> f[i][j];
        }
    }

    vvl p(n, vl(11));
    rep(i, n) {
        rep(j, 11) {
            cin >> p[i][j];
        }
    }

    ll ans = -INF;
    exrep(b, 1, (1<<10)-1) {
        ll now = 0;
        rep(i, n) {
            ll c = 0;
            rep(j, 10) {
                if((b & 1<<j) && f[i][j]) {
                    c++;
                }
            }
            now += p[i][c];
        }
        chmax(ans, now);
    }

    out(ans);
    re0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main()
{
    int a[3],i,j,temp,loc,min;
    for(i=0;i<3;i++)
    {
        scanf("%d",&a[i]);
    }
    for(i=0;i<(3-1);i++)
    {
        min=a[i];
        loc=i;
        for(j=i+1;j<3;j++)
        {
            if(a[j]<min)
            {
                min=a[j];
                loc=j;
            }
 }
        temp=a[i];
        a[i]=a[loc];
        a[loc]=temp;


    }
    for(i=0;i<3;i++){
        if(i!=(3-1))
            printf("%d ",a[i]);
        else
            printf("%d\n",a[i]);
    }
}



Measured memory_bytes: 2040
#include <iostream>
#include <vector>
#include <map>
#include <utility>
#include <algorithm>
#include <cmath>
#include <cstdio>

#define REP(i,a,n) for(int i=a;i<n;++i)
#define rep(i,n) REP(i,0,n)
#define vsort(v) sort(v.begin(),v.end())
#define asort(a,n) sort(a, a + n)
#define vi vector<int>
#define vd vector<double>

using namespace std;

int main(){
    ios::sync_with_stdio(false);
    string str;
    cin >> str;
    if(str.find("AC") != string::npos){
        cout << "Yes" << "\n";
    }else{
        cout << "No" << "\n";
    }

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
const int N = 1e5+10;
typedef long long LL;
const int MAXSIZE=1e5+10;
const LL mod = 1e9+7;
int Mark[MAXSIZE];  
int prime[MAXSIZE]; 
int Prime(){  
    int index = 0;  
    memset(Mark,0,sizeof(Mark));  
    for(int i = 2; i < MAXSIZE; i++)  
    {  
        //如果未标记则得到一个素数  
        if(Mark[i] == 0){  
            prime[index++] = i;  
        }   
        for(int j = 0; j < index && prime[j] * i < MAXSIZE; j++)  
        {  
            Mark[i * prime[j]] = 1;  
            if(i % prime[j] == 0){  
                break;  
            }  
        }  
    }  
    return index;  
}  
int a[N];
int main() {
	int n;
	while(scanf("%d", &n)!=EOF) {
		int index=Prime();
		//cout<<prime[0]<<endl;
		//cout<<index<<endl;
		//cout<<prime[index]<<endl;
		for(int i=0;i<index&&i<=n; i++) {
			int x=n;
			//cout<<i<<endl;
			//cout<<prime[i]<<' '<<i<<endl;
			while(x) {
				x/=prime[i];
				a[prime[i]]+=x;
			}
		}
		//cout<<a[2]<<endl;
		LL ans=1;
		for(int i=1; i<=n; i++) {
			if(a[i]!=0) ans=(ans*(a[i]+1))%mod;
		}
		printf("%lld\n",ans);
	}
	return 0;
}

Measured memory_bytes: 768
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())

int main(){
	int n,ans=0;
	cin>>n;
	vector<int>vi;
	rep(i,n){ int a; cin >> a; vi.pb(a); }
	rep(i,n)rep(j,n){
		if(i < j) ans+=vi[i]*vi[j];
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
N = int(input())
T,A = map(int,input().split())
heights = input().split()
heights = [int(x) for x in heights]
best_H = (T - A) / 0.006
diff_l, diff_h = 100000,100000
n_l,n_h = 0,N-1
for i in range(N):
    diff = abs(best_H - heights[i])
    if diff < diff_l:
        diff_l = diff
        n_l = i
print(n_l+1)

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

int main (){
    int a, b;
    cin >> a >> b;
    
    int seki = a*b;
    
    if (seki % 2 == 0){
        cout << "Even" << endl;
    }
    else{
        cout << "Odd" << endl;
    }
}

Measured memory_bytes: 3556
#include <bits/stdc++.h>
#define sort_(a) sort(a.begin(), a.end())
#define rsort(a) sort(a.rbegin(), a.rend())
#define rep(i, n) for (int i = 0; i < n; i++)
#define rrep(i, n) for (int i = n - 1; 0 <= i; i--)
#define for_(i, start, end) for (int i = start; i < end; i++)
#define rfor(i, start, end) for (int i = start - 1; 0 <= i; i--)
#define all(a) a.begin(), a.end()
using ll = long long;
using ld = long double;
using namespace std;
constexpr int INF32       = 1'050'000'000;
constexpr long long INF64 = 4'000'000'000'000'000'000;
constexpr int MOD7        = 1'000'000'007;
constexpr int MOD53       = 998'244'353;
constexpr double PI       = 3.14159265358979323846;
template <class T> inline bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template <class T> inline bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
void print() { std::cout << '\n'; }
template <class H, class... T> void print(H &&head, T &&... args) {
    std::cout << head;
    sizeof...(args) == 0 ? std::cout << "" : std::cout << ' ';
    print(std::forward<T>(args)...);
}
template <class T> void print(std::vector<T> &v) {
    for (int i = 0; i < v.size(); i++) {
        std::cout << v[i];
        i == v.size() - 1 ? std::cout << '\n' : std::cout << ' ';
    }
}
template <class T> void print(std::vector<std::vector<T>> &v) {
    for (int i = 0; i < v.size(); i++) {
        for (int j = 0; j < v[i].size(); j++) {
            std::cout << v[i][j];
            j == v[i].size() - 1 ? std::cout << '\n' : std::cout << ' ';
        }
    }
}
void scan() {}
template <class H, class... T> void scan(H &&head, T &&... args) {
    std::cin >> head;
    scan(std::forward<T>(args)...);
}
template <class T> void scan(std::vector<T> &v) {
    for (auto &&i : v) {
        scan(i);
    }
}

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

    string s;
    scan(s);

    if (s == "SUN")
        print(7);
    if (s == "MON")
        print(6);
    if (s == "TUE")
        print(5);
    if (s == "WED")
        print(4);
    if (s == "THU")
        print(3);
    if (s == "FRI")
        print(2);
    if (s == "SAT")
        print(1);

    return 0;
}

Measured memory_bytes: 256
import sys


def main():
    h, w = map(int, input().split())
    a = [input().strip() for i in range(h)]

    rd = [False] * h
    cd = [False] * w

    for i in range(h):
        rd[i] = all(a[i][j] == '.' for j in range(w))

    for j in range(w):
        cd[j] = all(a[i][j] == '.' for i in range(h))

    for i in range(h):
        line = ''
        for j in range(w):
            if rd[i] or cd[j]:
                continue
            line += a[i][j]
        if line:
            print(line)


main()


Measured memory_bytes: 3064
n = int(input())

if n <= 9:
    print(n)
elif 9 < n <= 99:
    print(9)
elif 99 < n <= 999:
    print(n - 90)
elif 999 < n <= 9999:
    print(909)
elif 9999 < n <= 99999:
    print(n - 9090)
else:
    print(90909)

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

void sort(int n);

int a[100];

int main() {
  int n, x;
  cin >> n >> x;
  int i;
  for (i = 0; i < n; i++) {
    cin >> a[i];
  }
  sort(n);
  int count = 0;
  for (i = 0; i < n; i++) {
    if (x - a[i] < 0) {
      break;
    }
    x -= a[i];
    count++;
    if (i == n - 1 && x > 0) {
      count--;
    }
  }

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

void sort(int n) {
  int front = 0;
  for (int front = 0; front < n - 1; front++) {
    int minIndex = front;
    for (int i = front + 1; i < n; i++) {
      if (a[i] < a[minIndex]) {
        minIndex = i;
      }
    }

    int temp = a[front];
    a[front] = a[minIndex];
    a[minIndex] = temp;
  }
}


Measured memory_bytes: 256
#include <algorithm>
#include <array>
#include <bitset>
#include <cctype>
#include <cinttypes>
#include <climits>
#include <cmath>
#include <complex>
#include <cstddef>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

struct Ev {
  int p, v, l;
  bool isr;
};

long long T[1 << 19], U[1 << 19];

void tupd(int p, int L, int R, int l, int r, long long v) {
  if (L == l && R == r) {
    T[p] += v;
    U[p] += v;
    return;
  }
  auto M = (L + R) >> 1;
  auto pl = p << 1;
  auto pr = pl + 1;
  if (U[p]) {
    T[pl] += U[p];
    U[pl] += U[p];
    T[pr] += U[p];
    U[pr] += U[p];
    U[p] = 0;
  }
  if (r <= M)
    tupd(pl, L, M, l, r, v);
  else if (l >= M)
    tupd(pr, M, R, l, r, v);
  else {
    tupd(pl, L, M, l, M, v);
    tupd(pr, M, R, M, r, v);
  }
  T[p] = max(T[pl], T[pr]);
}

long long tqry(int p, int L, int R, int l, int r) {
  if (L == l && R == r)
    return T[p];
  auto M = (L + R) >> 1;
  auto pl = p << 1;
  auto pr = pl + 1;
  if (U[p]) {
    T[pl] += U[p];
    U[pl] += U[p];
    T[pr] += U[p];
    U[pr] += U[p];
    U[p] = 0;
  }
  if (r <= M)
    return tqry(pl, L, M, l, r);
  if (l >= M)
    return tqry(pr, M, R, l, r);
  return max(tqry(pl, L, M, l, M), tqry(pr, M, R, M, r));
}

int main() {
  int N, M;
  scanf("%d%d", &N, &M);
  auto R = 1;
  while (R <= N)
    R <<= 1;
  auto P = 0;
  static Ev A[400000];
  for (auto i = 0; i < M; ++i) {
    int l, r, a;
    scanf("%d%d%d", &l, &r, &a);
    A[P++] = {l, a, l, false};
    A[P++] = {r, a, l, true};
  }
  sort(A, A + P, [](const Ev& a, const Ev& b) {
    return a.p != b.p ? a.p < b.p : a.isr < b.isr;
  });
  auto j = 0;
  auto res = 0ll;
  for (auto i = 1; i <= N; ++i) {
    while (j < P && A[j].p == i && !A[j].isr) {
      tupd(1, 0, R, 0, A[j].l, A[j].v);
      ++j;
    }
    auto f = tqry(1, 0, R, 0, i);
    res = max(res, f);
    tupd(1, 0, R, i, i + 1, f);
    while (j < P && A[j].p == i) {
      tupd(1, 0, R, 0, A[j].l, -A[j].v);
      ++j;
    }
  }
  printf("%lld\n", res);
  return 0;
}


Measured memory_bytes: 14208
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// #include <ext/pb_ds/detail/standard_policies.hpp>
// using namespace __gnu_pdbs;
using namespace std;

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

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define mt make_tuple
#define eb emplace_back
#define sf(x) sizeof(x)
#define len(x) x.length()
#define sz(x) x.size()
#define fastio() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)

#define LB(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define UB(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef unsigned long long ull;
typedef long double ld;
typedef tuple<int,int,int> State;

ll mod = 1e9 + 7;

void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cerr << *it << " = " << a << endl;
	err(++it, args...);
}

#define citc(tc) int tc; cin>>tc; while(tc--)
#define each(a,x) for( auto &a:(x))
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define repr(i, n) for (ll i = (n) - 1; i >= 0; i--)
#define rep2(i, l, r) for (ll i = (l); i < (r); i++)
#define rep2r(i, l, r) for (ll i = (r) - 1; i >= (l); i--)
#define range(a) a.begin(), a.end()
#define deb(x) cout<<#x<<" "<<x<<endl;
#define cini(i) int i; cin>>i;
#define cinll(l) ll l; cin>>l;
#define cinll2(l, z) ll l, z; cin>>l>>z;
#define cinll3(l, z, x) ll l, z, x; cin>>l>>z>>x;
#define cinai(a, n) vi a(n); rep(i, n) { cin>>a[i]; }
#define cinal(a, n) vl a(n); rep(i, n) { cin>>a[i]; }
#define coutai(a, n) rep(i, n) { cout<<a[i]<<" "; } ent;
#define coutal(a, n) rep(i, n) { cout<<a[i]<<" "; } ent;
#define ent cout<<endl;
#define ms(dp, x) memset(dp, x, sf(dp))
#define pi 3.14159265358979323846264338327950

ll powm(ll a, ll b, ll mod) {
	ll res=1;
	while(b) {
		if(b&1)
			res=(res*a)%mod;
		a=(a*a)%mod;
		b>>=1;
	}
	return res;
}
unordered_map<ll,ll>m;

void solve()
{

	ll n , k;
	cin>>n>>k;
	ll a[n+1];
	ll freq[n+1] = {0};

	for(ll i = 1;i<=n;i++)
	{cin>>a[i];freq[i] = -1;}

	ll ans = 0,cnt = 0;
	ll i = 1;

			while(freq[i] == -1)
			{
				freq[i] = cnt++;
				i = a[i];

			}


	if(k > freq[i])
	{
		k %= (cnt-freq[i]);
		while(k<freq[i])
		k += (cnt - freq[i]);
	}

	i = 1;
	while(k--)
	{
		i = a[i];
	}
	cout<<i<<"\n";


	// cout<<k%ans+1<<"\n";





}
int main()
{
	int tc;
	// cin>>tc;
	tc = 1;
	while(tc--)
	solve();
}
// ll n,m,x;
// cin>>n>>m>>x;
// ll c[n] ;
// vector<ll>a[n];
// for(ll i = 0;i<n;i++)
// {
// 	cin>>c[i];
// 	for(ll j = 0,x;j<m;j++)
// 	{
// 		cin>>x;
// 		a[i].pb(x);
// 	}
// }
// ll sum[n] = {0},flag  = 0;
// for(ll i = 0;i<m;i++)
// {
// 	for(ll j = 0;j<n;j++)
// 	{
// 		sum[i] += a[j][i];
// 	}
// 	if(sum[i] < x)
// 	flag = 1;
// }
// if(flag)cout<<"-1\n";


Measured memory_bytes: 6768
n = int(input())
b = list(map(int, input().split()))

a = []
a.append(b[0])

for i in range(1, n-1):
  if b[i-1] <= b[i]:
    a.append(b[i-1])
  elif b[i-1] > b[i]:
    a.append(b[i])
a.append(b[-1])
print(sum(a))     

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
vector<int>edge[100001];
int p[100001];
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=0;i<m;i++)
	{
		int a,b;
		cin>>a>>b;
		edge[a].push_back(b);
		edge[b].push_back(a);
	}

	queue<int>q;
	q.push(1);
//	cout<<q.front();
	while(!q.empty())
	{
		int now=q.front();
		for(int i=0;i<edge[now].size();i++)
		{
			if(p[edge[now][i]]==0)
			{
				p[edge[now][i]]=now;
				q.push(edge[now][i]);
			}
			
		}
		q.pop();
	}
	for(int i=2;i<=n;i++)
	{
		if(p[i]==0)
		{
			cout<<"No";
			return 0;
		}
	}
	cout<<"Yes"<<endl;
	for(int i=2;i<=n;i++)
		cout<<p[i]<<endl;
	
	return 0;	
}

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

#define MOD 10000007
#define f first
#define s second
#define es " "
#define pb push_back
#define endl "\n"
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3f
#define ll long long int
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

int n, e, s, m, memo[100005][5];

vector<int> viz[100005];

int bfs(){
    queue<pair<int, int> > fila;
    fila.push({e, 0});
    while(!fila.empty()){
        int pos=fila.front().f;
        int dist=fila.front().s;
        fila.pop();
        if(pos==s && dist%3==0){
            return dist/3;
        }
        if(memo[pos][dist%3]) continue;
        memo[pos][dist%3]=1;
        for(int i=0; i<viz[pos].size(); i++){
            int u=viz[pos][i];
            fila.push({u, dist+1});
        }
    }
    return -1;
}

int main(){
    cin >> n >> m;
    for(int i=0, a, b; i<m; i++){
        cin >> a >> b;
        viz[a].pb(b);
    }
    cin >> e >> s;
    cout << bfs() << endl;
    return 0;
}

Measured memory_bytes: 7680
import sys
N = int(input())
A = [int(x) for x in input().split()]
if N == 1:
    print(1)
    sys.exit()
 
inc = 0  # 1: 単調非減少,　-1 : 単調非増加, 0: 未確定
ans = 1
for i in range(N - 1):
    if A[i] < A[i + 1]:
        if inc == -1:
            ans += 1
            inc = 0
        elif inc == 0:
            inc = 1
    elif A[i] > A[i + 1]:
        if inc == 1:
            ans += 1
            inc = 0
        elif inc == 0:
            inc = -1
 
print(ans)

Measured memory_bytes: 19924
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner scn = new Scanner(System.in);
    long N = scn.nextInt();

    ArrayList<Info> infoList = new ArrayList<>();
    Info G = new Info(0, 0, 0);
    for (long i = 0; i < N; i++) {
      long x = scn.nextInt();
      long y = scn.nextInt();
      long h = scn.nextInt();

      infoList.add(new Info(x, y, h));
      if (h >= 1) {
        G = new Info(x, y, h);

      }
    }

    for (long cx = 0; cx <= 100; cx++) {
      for (long cy = 0; cy <= 100; cy++) {
        boolean flg = true;
        long H = Math.abs(G.x - cx) + Math.abs(G.y - cy) + G.h;
        H = Math.max(H, 0);
        for (Info info : infoList) {
          long V = Math.max(H - Math.abs(info.x - cx) - Math.abs(info.y - cy), 0L);
          if (V != info.h) {
            flg = false;
            break;
          }

        }

        if (flg) {
          System.out.printf("%d %d %d\n", cx, cy, H);
        }

      }
    }

  }

  public static class Info {
    long x;
    long y;
    long h;

    Info(long x, long y, long h) {
      this.x = x;
      this.y = y;
      this.h = h;
    }

  }

}


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


int main(void) {
	string X;
	cin >> X;

	int t = 0;
	int s = 0;

	for (int i = 0; i < X.length(); i++) {
		if (X.at(i) == 'T') {
			if (s > 0) {
				s--;
			} else {
				t++;
			}
		} else {
			s++;
		}
	}
	cout << (s+t);

	return 0;
}


Measured memory_bytes: 640
import java.io.IOException;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) throws IOException {

		new Main().run();
	}

	private void run() throws IOException {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int m = scanner.nextInt();
		Deque<Integer> deque = new ArrayDeque<Integer>();
		for (int i = 1; i <= n * 2; i++)
			deque.offer(i);
		for (int i = 0; i < m; i++) {
			int a = scanner.nextInt();
			if (a == 0) {
				Deque<Integer> tmp = new ArrayDeque<Integer>();
				Deque<Integer> tmp2 = new ArrayDeque<Integer>();
				for (int j = 0; j < n; j++)
					tmp.offer(deque.poll());
				for (int j = 0; j < n; j++) {
					tmp2.offer(tmp.poll());
					tmp2.offer(deque.poll());
				}
				deque = tmp2;
			} else {
				for (int j = 0; j < a; j++) {
					deque.offer(deque.poll());
				}
			}
		}
		while (!deque.isEmpty())
			System.out.println(deque.poll());
	}
}

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

int main(){
  string a,b,c;
  cin>>a>>b>>c;
  if(a[a.size()-1]==b[0] && b[b.size()-1]==c[0]){
    cout<<"YES"<<endl;
  }else{
    cout<<"NO"<<endl;
  }
}

Measured memory_bytes: 3636