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

using namespace std;

#define int long long
#define ALL(x) (x).begin(),(x).end()
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))

typedef pair<int,int> PI;
typedef pair<int,pair<int,int>> PII;
static const int INF=1010000000000000017LL;
static const double eps=1e-12;
static const double pi=3.14159265358979323846;
static const int dx[4]={1,-1,0,0};
static const int dy[4]={0,0,1,-1};
static const int ddx[8]={1,-1,0,0,1,1,-1,-1};
static const int ddy[8]={0,0,1,-1,1,-1,1,-1};

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;}

const int MAX_D=365;
const int MAX_type=26;
const int BeamWidth=100;

int D;
int c[MAX_D+5];
int s[MAX_D+5][MAX_type+5];

struct State{
    vector<int> contest;
    vector<int> last;
    int day;
    int score;

    State(){
        //cout<<"hoge"<<endl;
        day=1;
        score=0;
        for(int i=0;i<MAX_type+5;++i)last.push_back(0);
        //fill(last.begin(),last.end(),0);
        //cout<<last[0]<<endl;
    }

    void update(int type){
        contest.push_back(type);
        last[type]=day;
        score+=s[day][type];
        for(int i=1;i<=MAX_type;++i){
            score-=c[i]*(day-last[i]);
        }
        day++;
    }

    State nextState(State now,int type){
        State next;
        next=now;
        next.update(type);
        return next;
    }
};

bool operator< (const State &state1, const State &state2){
    return state1.score < state2.score;
};

bool operator> (const State &state1, const State &state2){
    return state1.score > state2.score;
};

State beamsearch(){
    int D_=D;
    priority_queue<State, vector<State>, greater<State> > nowpq;
    //priority_queue<State> nowpq;
    for(int type=1;type<=MAX_type;++type){
        State s;
        //cout<<s.score<<endl;
        //cout<<s.nextState(s,type).contest[0]<<endl;
        nowpq.push(s.nextState(s,type));
    }
    while(nowpq.size()>BeamWidth)nowpq.pop();
    D_--;
    while(D_--){
        //cout<<D<<endl;
        priority_queue<State, vector<State>, greater<State> > nextpq;
        //priority_queue<State> nextpq;
        while(nowpq.size()){
            State now=nowpq.top();
            nowpq.pop();
            for(int type=1;type<=MAX_type;++type){
                nextpq.push(now.nextState(now,type));
            }
        }
        while(nextpq.size()>BeamWidth)nextpq.pop();
        nowpq=nextpq;
    }
    while(nowpq.size()>1)nowpq.pop();
    State ret=nowpq.top();
    return ret;
}

void input(){
    cin>>D;
    for(int i=1;i<=MAX_type;++i)cin>>c[i];
    for(int i=1;i<=D;++i){
        //cout<<D<<endl;
        for(int j=1;j<=MAX_type;++j){
            cin>>s[i][j];
        }
    }
}

signed main(){
    input();
    auto res=beamsearch();
    if(res.contest.size()!=D)cout<<0/0<<endl;
    for(auto u:res.contest){
        cout<<u<<endl;
    }
    //cout<<"score is "<<res.score<<endl;
    //for(int i=0;i<MAX_type;++i)cout<<res.last[i]<<endl;
    //int score=0;
}

Measured memory_bytes: 19752
with Ada.Text_IO; use Ada.Text_IO;
with Ada.Integer_Text_IO; use Ada.Integer_Text_IO;

procedure Solve is
   A : Integer;
   B : Integer;
   C : Integer;
begin
   Get (A);
   Get (B);
   Get (C);
   Put_Line (Integer'Image (A*B/2));
end Solve;

Measured memory_bytes: 3660
N = int(input())
L = [2,1]
if N == 1 :
    print(1)
elif N > 1 :
    for i in range(N+1) :
        L.append(sum(L))
        if i == (N-2) :
            print(L[-1])
            break
        else :
            L.pop(0)
    

Measured memory_bytes: 2940
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <ctime>
#include <algorithm>
#include <vector>
#include <cstring>
#include <stack>
#include <queue>
#include <utility>
#include <cmath>
using namespace std;

int n;
long ans;

int main(){
	int mscore = 1145141919;
	int minpos = 0;
	scanf("%d", &n);
	for(int i = 0; i < n; i++){
		int a, b;
		scanf("%d%d", &a, &b);
		if(a > minpos){
			minpos = a;
			mscore = b;
		}
	}
	printf("%d\n", minpos + mscore);
	return 0;
}

Measured memory_bytes: 384
#pragma comment (linker, "/STACK:256000000")
#include "bits/stdc++.h"
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a),i##_len=(b);i<i##_len;++i)
#define BUGAVOID(x) x
#define rep(...) BUGAVOID(_overload3(__VA_ARGS__,repi,_rep,_rep)(__VA_ARGS__))
#define sz(c) (int)(c.size())
#define all(c) c.begin(),c.end()
#define mp make_pair
#define write(x) cout<<(x)<<"\n"
using namespace std; typedef long long ll;
typedef vector<int> vi; typedef vector<ll> vll; template<class T, class U>using vp = vector<pair<T, U>>;
template<class T>using vv = vector<vector<T>>; template<class T, class U>using vvp = vv<pair<T, U>>;
template<class T>vv<T> vvec(const size_t n, const size_t m, const T v) { return vv<T>(n, vector<T>(m, v)); }
template<class T>bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; }return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; }return 0; }
constexpr ll pow2(const int n) { return 1ll << n; }
constexpr int INF = 1 << 28; constexpr ll LINF = 1ll << 60;
constexpr int MAX = 1e5 + 5; constexpr int MOD = 1e9 + 7; constexpr double EPS = 1e-6;
constexpr int dy[4] = { 0,1,0,-1 }; constexpr int dx[4] = { 1,0,-1,0 };
struct aaa { aaa() { cin.tie(0); ios::sync_with_stdio(0); }; }aaaa;

int N;
ll C;
vll X;
vi V;

int main() {
    cin >> N >> C;
    X.resize(N + 2);
    V.resize(N + 2);
    rep(i, 1, N + 1) {
        cin >> X[i] >> V[i];
    }
    X[0] = 0; X[N + 1] = C;

    vll clockwise_oneway(N + 2), clockwise_twoway(N + 2);
    {
        ll now_ow = 0, now_tw = 0;
        rep(i, 1, N + 1) {
            now_ow += V[i] - (X[i] - X[i - 1]);
            now_tw += V[i] - (X[i] - X[i - 1]) * 2;
            clockwise_oneway[i] = max(clockwise_oneway[i - 1], now_ow);
            clockwise_twoway[i] = max(clockwise_twoway[i - 1], now_tw);
        }
    }
    vll countercw_oneway(N + 2), countercw_twoway(N + 2);
    {
        ll now_ow = 0, now_tw = 0;
        for (int i = N; i > 0; --i) {
            now_ow += V[i] - (X[i + 1] - X[i]);
            now_tw += V[i] - (X[i + 1] - X[i]) * 2;
            countercw_oneway[i] = max(countercw_oneway[i + 1], now_ow);
            countercw_twoway[i] = max(countercw_twoway[i + 1], now_tw);
        }
    }

    ll ans = 0;
    rep(i, 0, N + 1) {
        chmax(ans, clockwise_oneway[i] + countercw_twoway[i + 1]);
        chmax(ans, clockwise_twoway[i] + countercw_oneway[i + 1]);
    }
    write(ans);
}

Measured memory_bytes: 4608
from operator import itemgetter

A, B, C, D, E, F = map(int, input().split())


def f(x, y):
    max_i = F // x
    max_j = F // y
    arr = []
    for i in range(max_i + 1):
        for j in range(max_j + 1):
            a = x * i + y * j
            if a <= F:
                arr.append(a)
    return list(set(arr))


water = f(100 * A, 100 * B)
sugar = f(C, D)

ans = []
for w in water:
    if w == 0:
        continue
    for s in sugar:
        if w + s <= F and s / w <= E / 100:
            ans.append((w + s, s, s / (w + s)))
ans = sorted(ans, key=itemgetter(2), reverse=True)
print(ans[0][0], ans[0][1])

        


Measured memory_bytes: 12588
#include <bits/stdc++.h>
using namespace std;
#define SELECTER(_1, _2, _3, SELECT, ...) SELECT
#define REP1(i, n) for(int i=0; (i)<(n); (i)++)
#define REP2(i, a, b) for(int i=(a); (i)<(b); (i)++)
#define REP(...) SELECTER(__VA_ARGS__, REP2, REP1,) (__VA_ARGS__)
#define MOD 1000000007

template <class T> ostream& operator<<(ostream& os, const vector<T>& v){ os << "{"; for(size_t i=0; i<v.size(); i++) os << v[i] << (i+1==v.size() ? "" : ", "); os << "}"; return os; }
template <class T, class U> ostream& operator<<(ostream& os, const pair<T, U>& p){ return os << "{" << p.first << ", " << p.second << "}"; }

int bipow(int n, int m, int p){
    if(m==0) return 1;
    if(m%2) return (n*bipow(n, m-1, p)) % p;
    return bipow((n*n)%p, m/2, p) % p;
}

int comb[3000][3000];
int main(){
    int p;
    cin >> p;
    vector<int> a(p);
    REP(i, p) cin >> a[i];
    vector<int> b(p);
    REP(i, 3000) comb[i][0] = comb[i][i] = 1;
    REP(i, 1, 3000) REP(j, 1, i)
        comb[i][j] = (comb[i-1][j] + comb[i-1][j-1]) % p;

    REP(i, p){
        if(!a[i]) continue;
        b[0] = (b[0] + 1) % p;
        REP(j, p){
            int tmp2 = (comb[p-1][j] * bipow(i, j, p)) % p;
            if(j%2) b[p-1-j] += tmp2;
            else b[p-1-j] += p - tmp2;
            b[p-1-j] %= p;
        }
    }
    REP(i, p)
        cout << b[i] << " ";
    cout << endl;

    // REP(i, p){
    //     int tmp = 0;
    //     REP(j, p){
    //         tmp += (bipow(i, j, p) * b[j]) % p;
    //         tmp %= p;
    //     }
    //     assert(tmp == a[i]);
    // }

    return 0;
}



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

void dfs(int n, int c, const vector<int>& v, vector<int> y, int& cnt) {
  if (n == c) {
    int tmp = 1;
    for (auto e : y)
      tmp *= e;
    if (tmp % 2 == 0)
      ++cnt;
  } else {
    for (auto e : v) {
      y[c] += e;
      dfs(n, c + 1, v, y, cnt);
    }
  }
}

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

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

  vector<int> v = {-1, 0, 1}, y = x;
  int ans = 0;
  dfs(n, 0, v, y, ans);

  cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>

using namespace std;
int main (){
    int n,m;
    cin >> n >> m;
    string tmp;
    bool a[n][n];
    bool b[m][m];
    for (int i = 0; i < n; i++){
        cin >> tmp;
        for (int j = 0; j < n; j++){
            if(tmp[j]=='#') a[i][j]=1;
            else            a[i][j]=0;
        }
    }
    for (int i = 0; i < m; i++){
        cin >> tmp;
        for (int j = 0; j < m; j++){
            if(tmp[j]=='#') b[i][j]=1;
            else            b[i][j]=0;
        }
    }

    int wdiff=n-m;
    int row,col,trow,tcol;
    bool jud,tjud;
    jud=true;
    for (int i = 0; i < wdiff*wdiff; i++){
        if(i==0) jud=false;
        row=i/wdiff;
        col=i%wdiff;
        tjud=true;
        for (int j = 0; j < m*m; j++){
            trow=j/m;
            tcol=j%m;
            if(b[trow][tcol]!=a[row+trow][col+tcol]) tjud=false;
        }
        if(tjud) jud=true;
    }
    if(jud) cout << "Yes\n";
    else    cout << "No\n";
}


Measured memory_bytes: 256
#!/usr/bin/perl
use Data::Dumper;
my ($a,$b) = split(/\s+/,<STDIN>);

my $mul = 0;
if( $b =~ /\./o ){
  my $x1 = $`;
  my $x2 = $';
  $mul = length($x2);
  $b = $x1 . $x2;
  $b =~ s/^0+//ios;
  $b = '0' unless length($b);
}

my $aa = '' . ( ($a-0) * ($b-0) );
if( $mul > 0 and length($aa)<( $mul + 1 ) ){
  $aa = ( '0' x ($mul + 1 -length($aa)) ) . $aa;
}

print (substr($aa,0,length($aa)-$mul) . "\n");



Measured memory_bytes: 6352
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 998244353;
const int maxn = 200 + 50;
int n;
ll p[maxn];
ll x[maxn], y[maxn];
map<pair<ll, ll>, ll> mp;
void pre(){
    p[0] = 1;
    for(int i = 1; i < maxn; i++){
        p[i] = (p[i-1] * 2) % mod;
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    pre();
    while(cin >> n){
        for(int i = 0; i < n; i++)
            cin >> x[i] >> y[i];
        ll ans = p[n] - n - 1;//减去空集和单点集
        ll deltay, deltax, k;
        for(int i = 0; i < n; i++){
            mp.clear();
            for(int j = i+1; j < n; j++){
                deltay = y[j] - y[i];
                deltax = x[j] - x[i];
                k = __gcd(deltay, deltax);
                deltay/=k;
                deltax/=k;
                ++mp[{deltay,deltax}];
            }
            for(map<pair<ll, ll>, ll>::iterator iter = mp.begin(); iter != mp.end(); iter++){
                ll tmp = p[iter->second] - 1;//除i点以外共线集的个数，减去只有一个i点的情况
                ans = (ans - tmp + mod) % mod;
            }
        }
        cout << ans << "\n";
    }
    return 0;
}

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

using namespace std;

const int maxN = 1000000;
const long long oo = 1000000000000ll;

#define foru(i, l, r) for (int i = l; i <= r; ++i)
#define ford(i, r, l) for (int i = r; i >= l; --i)
#define repu(i, r) for (int i = 0; i < r; ++i)
#define ll long long
#define F first
#define S second
#define mp make_pair
#define pint pair < ll, int >

ll res, right_sum, left_sum;
int n, a[maxN], check[maxN];

struct cmp_min {
    bool operator () (int i, int j) {
        return a[j] < a[i];
    }
};

priority_queue < int, vector < int >, cmp_min > left_heap, right_heap;

int main() {
    cin >> n;
    foru(i, 1, 3 * n) scanf("%d", &a[i]);
    foru(i, 1, n) 
        left_sum += a[i], left_heap.push(i);
    foru(i, n + 1, 3 * n)
        right_heap.push(i);
    foru(i, 1, n) {
        int j = right_heap.top();
        right_heap.pop();
        check[j] = 1;
        right_sum += a[j];
    }
    res = left_sum - right_sum;
    foru(i, n + 1, 2 * n) {
        if (check[i]) {
            right_sum -= a[i];
            while (!right_heap.empty()) {
                int j = right_heap.top();
                right_heap.pop();
                if (j < i) continue;
                right_sum += a[j];
                check[j] = 1;
                break;
            }
        }
        int j = left_heap.top();
        if (a[j] < a[i]) {
            left_sum -= a[j];
            left_sum += a[i];
            left_heap.pop();
            left_heap.push(i);
        }
        res = max(res, left_sum - right_sum);
    }
    cout << res << endl;
}


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


struct kenka_t {
	int a;
	int b;
} ;

int compare_kenka(const void *c, const void *d) {
  struct kenka_t *A = (struct kenka_t *)c;
  struct kenka_t *B = (struct kenka_t *)d;
  return A->a - B->a;
}


int main(void)
{
	//変数の宣言
	int n,m;
	int i,j,k;
	int flag;
	int ans,temp;
	static int anew[100010];
	static int bnew[100010];
	struct kenka_t kenka[100010];
	
	//データの読み込み
	scanf("%d %d",&n,&m);
	
	for(i=0;i<m;i++){
		scanf("%d %d",&kenka[i].a,&kenka[i].b);
	}
	
//	printf("nは%dです\n", n);
//	printf("データの読み込み終了\n");
	//実際の処理
	
	qsort(kenka, m, sizeof(struct kenka_t), compare_kenka);
	
	k=0;
	for(i=0;i<m-1;i++){
//		printf("%d番目の要素についてチェック\n",i);
		j=i+1;
		flag=1;
		while(kenka[j].a<kenka[i].b){
			if(kenka[j].b<kenka[i].b){
				flag=0;
				break;
			}
			j++;
		}
//		printf("while文終了\n");
		if(flag==1){
			anew[k]=kenka[i].a;
			bnew[k]=kenka[i].b;
			k++;
//			printf("%d %dは極小\n",kenka[i].a,kenka[i].b);
		}else{
//			printf("%d %dは極小でない\n",kenka[i].a,kenka[i].b);
		}
	}
	anew[k]=kenka[m-1].a;
	bnew[k]=kenka[m-1].b;
	k++;
	
//	printf("\n");
//	for(i=0;i<k;i++){
//		printf("%d %d\n",anew[i],bnew[i]);
//	}
	
	ans=0;
	for(i=0;i<k;i++){
		if(i==0){
			ans++;
			temp=bnew[i];
//			printf("%dの左側を切断\n",temp);
		}else if(anew[i]>=temp){
			ans++;
			temp=bnew[i];
//			printf("%dの左側を切断\n",temp);
		}
	}
	
	
	
	
//	printf("計算部分終了\n");
	
	//出力
	printf("%d",ans);
	
//	printf("結果の出力終了\n");
	
	return 0;
}

Measured memory_bytes: 1788
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct edge{
    int u,v,cost;
    bool operator<(const edge& v) const {
        return cost < v.cost;
    }
};
const int INF = 1001001001;
const edge imEg = {-1,-1,INF};
vector<edge> es(10000, imEg);
int V,E;
vector<int> par;
vector<int> rnk;

void init_union_find(int n) {
    par.resize(n);
    rnk.resize(n);
    for(int i=0; i<n; i++) {
        par[i] = i;
        rnk[i] = 0;
    }
}

int find(int x) {
    if(x != par[x]) par[x] = find(par[x]);
    return par[x]; 
}

void unite(int x, int y) {
    x = find(x);
    y = find(y);
    if(x == y) return;
    if(rnk[x] > rnk[y]) par[y] = x;
    else par[x] = y;
    if(rnk[x] == rnk[y]) rnk[y]++;
}

int kruskal() {
    init_union_find(V);
    sort(es.begin(), es.end());
    int res = 0;
    for(int i=0; i<E; i++) {
        edge e = es[i];
        if(find(e.u) != find(e.v)) {
            unite(e.u, e.v);
            res += e.cost;
        }
    }
    return res;
}

int main() {
    cin >> V >> E;
    es.resize(E);
    for(int i=0; i<E; i++) {
        int s,t,w;
        cin >> s >> t >> w;
        struct edge e = {s,t,w};
        es[i] = e;
    }
    cout << kruskal() << endl;
    return 0;
}


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

#define int long long

typedef pair<int,int>pint;
typedef vector<int>vint;
typedef vector<pint>vpint;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
template<class T,class U>void chmin(T &t,U f){if(t>f)t=f;}
template<class T,class U>void chmax(T &t,U f){if(t<f)t=f;}

int N;
string S;

int A[111111];

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

    rep(latte,2)rep(malta,2){
        A[0]=latte;
        A[1]=malta;
        for(int i=2;i<N;i++){
            if(S[i-1]=='o')A[i]=A[i-2];
            else A[i]=A[i-2]^1;
            if(A[i-1])A[i]^=1;
        }
        int t=A[N-2]==A[0];
        if(A[N-1])t^=1;
        if(t!=(S[N-1]=='o'))continue;

        t=A[N-1]==A[1];
        if(A[0])t^=1;
        if(t!=(S[0]=='o'))continue;

        rep(i,N){
            if(A[i])printf("W");
            else printf("S");
        }
        puts("");
        return 0;

    }
    puts("-1");
    return 0;
}


Measured memory_bytes: 1408
n=int(input())
tens=[]
others=[]
for i in range(n):
    s=int(input())
    if s%10==0:
        tens.append(s)
    else:
        others.append(s)
tens.sort(reverse=True)
others.sort(reverse=True)

score=sum(tens)+sum(others)
if score%10==0:
    if len(others)!=0:
        print(score-min(others))
    else:
        print(0)
else:
    print(score)

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

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

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

    long long m = 1000, idx = 0;
    while (idx < n){
        long long small = a[idx];
        while (idx < n && a[idx] <= small){
            small = a[idx];
            idx += 1;
        }

        if (idx < n){
            long long big = a[idx];
            while (idx < n && a[idx] >= big){
                big = a[idx];
                idx += 1;
            }

            long long x = m / small;
            m -= x * small;
            m += x * big;
        }
    }
    cout << m << '\n';

    return 0;
}


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

int h, w;
int h2, w2;
int main()
{
	std::cin >> h >> w;
	std::cin >> h2 >> w2;

	std::cout << h * w - h2 * w - w2 * (h - h2) << std::endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
const ll NMAX = 1e5+7;
std::map<pair<string ,string>, int> ma;
ll n, res=0;
string s;
int main(){
   std::cin >> n >> s;
   for(int i = 0; i<(1<<n); i++){
     string a = "", b = "";
     for(int j = 0; j<n; j++){
      if(i&(1<<j)) a+=s[j];
      else b+=s[j];
     }
     ma[{a,b}]++;
   }

   for(int i = 0; i<(1<<n); i++){
     string a = "", b = "";
     for(int j = 0; j<n; j++){
      if(i&(1<<j)) a+=s[n+j];
      else b+=s[n+j];
     }
     reverse(a.begin(), a.end());
     reverse(b.begin(), b.end());
     res+=ma[{b,a}];
   }
   std::cout << res << '\n';
}


Measured memory_bytes: 87040
#include <iostream>

using namespace std;

typedef struct rect
{
    int w;
    int h;
} rect_t;

int main()
{
    rect_t rect1;
    rect_t rect2;

    cin >> rect1.w >> rect1.h >> rect2.w >> rect2.h;

    // cout << rect1.w << rect1.h << rect2.w << rect2.w;

    const int area1 = rect1.w * rect1.h;
    const int area2 = rect2.w * rect2.h;

    if (area1 > area2)    
        cout << area1 << endl;
    else if (area1 <= area2)    
        cout << area2 << endl;

    return 0;
}


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

#include <iostream>
using namespace std;

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

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

int main(int argc, char* argv[]){
        char* ptr=NULL;
        int N = 0;
        int t1=0, t2=0, x1=0, x2=0, y1=0, y2=0;
        int dt=0, dx=0, dy=0;
        int possible = 1;

        cin >> N;

        for(int i=1; i<=N && possible==1; i++){
                cin >> t2 >> x2 >> y2 ;
                dt = t2 - t1;
                dx = x2 - x1;
                dy = y2 - y1;

                if((dt+dx+dy)%2!=0){ possible=0; break; }
                if((dt+dx-dy)%2!=0){ possible=0; break; }

                int u = (dt+dx+dy)/2;
                int v = (dt+dx-dy)/2;

                if( max(0,dx)>min(u,v) ){ possible=0; break; }

                t1 = t2;
                x1 = x2;
                y1 = y2;

        }

        if(possible==1){printf("Yes\n");}
        else{printf("No\n");}

        return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
 
int main(){
  int N,D;
  cin >> N >> D;
  int count=0;
  long double d=0;
  for(int i=0; i<N; i++){
    long int x,y;
    cin >> x >> y;
    d=sqrt(x*x+y*y);
    if(d<=D){
      count = count + 1;
    }
  }
  cout << count << endl;
  return 0;
}  

Measured memory_bytes: 3620
l=int(input())

a=[]

for i in range(4):
    x=int(input())
    a.append(x)
r1=0
r2=0

if a[0]%a[2]==0:
    r1=a[0]//a[2]
else:
    r1=a[0]//a[2]+1

if a[1]%a[3]==0:
    r2=a[1]//a[3]
else:
    r2=a[1]//a[3]+1

print(l-max(r1,r2))

Measured memory_bytes: 7680
h,w,n = map(int, input().split())
stage = [input() for i in range(h)]
starts = [str(i) for i in range(n)]
goals = [str(i+1) for i in range(n)]
starts_y = [0 for i in range(n)]
starts_x = [0 for i in range(n)]
goals_y = [0 for i in range(n)]
goals_x = [0 for i in range(n)]

starts[0] = "S"
for y in range(h):
	for x in range(w):
		if stage[y][x] in starts:
			starts_y[starts.index(stage[y][x])] = y
			starts_x[starts.index(stage[y][x])] = x
		if stage[y][x] in goals:
			goals_y[goals.index(stage[y][x])] = y
			goals_x[goals.index(stage[y][x])] = x

move_y = [1,-1,0,0]
move_x = [0,0,1,-1]
sum = 0

for start_y, start_x, goal_y, goal_x in zip(starts_y, starts_x, goals_y, goals_x):
	bfs_map = [[-1 for j in range(w)] for i in range(h)]
	data_y = [start_y]
	data_x = [start_x]
	bfs_map[start_y][start_x] = 0
	goal = False
	
	while len(data_y) != 0 and not goal:
		y = data_y.pop(0)
		x = data_x.pop(0)
		goal = False
	
		for i in range(4):
			y += move_y[i]
			x += move_x[i]
			
			if y >= 0 and y < h and x >= 0 and x < w:
				if bfs_map[y][x] == -1 and stage[y][x] != "X":
					bfs_map[y][x] = bfs_map[y-move_y[i]][x-move_x[i]]+1
					data_y.append(y)
					data_x.append(x)
				if bfs_map[goal_y][goal_x] != -1:
					sum += bfs_map[goal_y][goal_x]
					goal = True
					break
			y -= move_y[i]
			x -= move_x[i]

print(sum)


Measured memory_bytes: 36508
#include <iostream>

using namespace std;

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

    int tmp, d[N], i=0;

    while(cin >> tmp){
        d[i] = tmp;
        i++;
        if(i >= N){
            break;
        }
    }

    int total_point = 0;

    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            if(i != j){
                int tmp1 = d[i];
                int tmp2 = d[j];
                total_point += (tmp1 * tmp2);
            }
        }
    }

    cout << total_point/2 << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#define rep(i,n) for(int i=0; i<(n); i++)
#define L 2000
using namespace std;
int A[L];
int n,q,m;

bool solve(int i,int m)
{
  if(m==0)
    return true;
  else if(i >= n)
    return false;
 
  else if(solve(i + 1, m)==true)
  	return true;
  else if(solve(i + 1, m - A[i])==true)
  	return true;
}

int main()
{
	cin >> n;
	rep(i,n)
	  cin >> A[i];
	cin >> q;
	rep(i,q){
		cin >> m;
		if(solve(0,m))
			cout << "yes" << endl;
	    else
	    	cout << "no" << endl;			 
	}
}



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

void make_fib(vector<int>& fib){
  for(int i=2; i<fib.size(); i++){
    fib[i] = fib[i-1] + fib[i-2];
  }
}

int main(){
  vector<int> fib(50,1);
  make_fib(fib);
  int n; cin >> n;
  cout << fib[n] << "\n";
}

Measured memory_bytes: 1200
#include <iostream>
#include <algorithm>
#include <queue>
#include <cassert>
#include <set>
using namespace std; typedef long long ll; const int MINF=-1e9; typedef pair<int,int> P;

int main() {
  ll n,x; cin>>n>>x;
  ll a[n]; for(int i=0;i<n;i++) cin>>a[i];
  if (n==1) {
    cout<<a[0]<<endl; return 0;
  }
  ll an=1e18;
  ll b[n];for(int i=0;i<n;i++) b[i]=a[i];
  for(ll i=0;i<=n;i++) {
    ll sm=0;
    for(int j=0;j<n;j++) {
      sm+=b[j];
    }
    an=min(an,sm+x*i);
    //cout<<i<<" "<<an<<endl;
    if (i==n) break;

    ll temp0=min(b[0],b[n-1]);
    for(int j=n-1;j>=1;j--) {
      b[j]=min(b[j-1],b[j]);
    }
    b[0]=temp0;
    //for(int j=0;j<n;j++) cout<<b[j]<<" "; cout<<endl;
  }
  cout<<an<<endl;
}

Measured memory_bytes: 256
using System;
using System.Linq;

namespace _168.C
{
    internal class Program
    {
        private static void Main(string[] args)
        {
            var i = Console.ReadLine()
                .Split()
                .Select(int.Parse)
                .ToList();
            var (a, b, h, m) = (i[0], i[1], i[2], i[3]);
            var hd = (360 * h / 12.0 + m / 2.0) * Math.PI / 180;
            var md = 360 * m / 60.0 * Math.PI / 180;
            var ax = a * Math.Sin(hd);
            var ay = a * Math.Cos(hd);
            var bx = b * Math.Sin(md);
            var by = b * Math.Cos(md);
            Console.WriteLine(Math.Sqrt(Math.Pow(ax - bx, 2) + Math.Pow(ay - by, 2)));
        }
    }
}

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

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

const long long INF = 1LL << 60;

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

  int ac = 0;
  int wa = 0;
  int tle = 0;
  int re = 0;
  rep(i, n){
    string s;
    cin >> s;
    if(s == "AC") ac++;
    else if(s == "WA") wa++;
    else if(s == "TLE") tle++;
    else if(s == "RE") re++;
  }

  cout << "AC x " << ac << endl;
  cout << "WA x " << wa << endl;
  cout << "TLE x " << tle << endl;
  cout << "RE x " << re << endl;

  return 0;
}


Measured memory_bytes: 3628
#include <iostream>
#include <string>
#include <sstream>
#include <iomanip> 
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <functional>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <bitset>

using namespace std;


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

	int n, i, j, k, odd, even, x;
	cin >> n;
	odd = 0; even = 0;
	for (i = 0; i < n; i++) {
		cin >> x;
		if (x % 2 == 0) even++;
		else odd++;
	}
	even += odd / 2;
	odd %= 2;

	if ((odd > 0) && (even > 0)) cout << "NO\n";
	else cout << "YES\n";

	return 0;
}



Measured memory_bytes: 256
s = input()
n = len(s)
t = input()
m = len(t)

if n < m:
    print("UNRESTORABLE")
    exit()
p = False
for i in reversed(range(n-m+1)):
    flag = True
    for j in range(m):
        if s[i+j] != "?" and s[i+j] != t[j]:
            flag = False
            break
    if flag:
        s = s[:i] + t + s[i+m:]
        p = True
        break

if not p:
    print("UNRESTORABLE")
    exit()
elif p:
    for i in range(n):
        if s[i] == "?":
            s = s[:i] + "a" + s[i+1:]
print(s)

Measured memory_bytes: 61788
fun main(args: Array<String>) {
    val N = nextInt()
   val S = Array(N) { next() }
    val cnt  =LongArray(26)
   val T = listOf(
            "MAR", 
            "MAC",
            "MAH", 
            "MRC", 
            "MRH", 
            "MCH", 
            "ARC",
            "ARH", 
            "ACH", 
            "RCH")
        repeat (N) { n ->
            cnt[S[n][0] - 'A'] += 1
        }
        var ans = 0L
        for (t in T) {
            val c0 = cnt[t[ 0] - 'A']
            val c1 = cnt[t[1] - 'A']
            val c2 = cnt[t[2] - 'A']
            ans += c0 * c1 * c2
        }
        println(ans)
    }
 fun next() = readLine()!!
fun nextInt() = Integer.parseInt(next())
fun nextInt(offset: Int = 0) = nextInt() + offset
fun nextLong() = java.lang.Long.parseLong(next())
fun nextLong(offset: Long = 0L) = nextLong() + offset
fun nextDouble() = next().toDouble()
fun listOfString() = next().split(" ")


Measured memory_bytes: 41064
import java.util.Scanner;
public class Main{
  public static void main(String[] args){
	Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int[] X = new int[N];
    int minScore = -1;
    for(int i=0; i<N; i++)
      X[i] = sc.nextInt();
    
    for(int i=1; i<=100; i++){ //集会の座標
      int score = 0;
    	for(int j=0; j<N; j++){
          	score += (X[j] - i)*(X[j] - i);
        }
     	if(minScore < 0 || minScore > score)
          minScore = score;
    }
    System.out.println(minScore);    
  }
}



Measured memory_bytes: 21972
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define endl "\n"
#define se second
#define ls( s) (s&(-s))
#define ll long long
const int N = 1000300;
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
const ll mod =    1e9+7;

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

cin>>n;
vector<pair<int,int> > v;
rep(i,0,n)
{
	int x;
	cin>>x;
	v.push_back({x,i+1});
}
sort(v.begin(),v.end());
rep(i,0,n)
cout<<v[i].se<<" ";
}

Measured memory_bytes: 1780
#include<stdio.h>
int main(){
  int n,c,i;
  while(scanf("%d %d",&n,&c),n||c){
    int w=c,s[50]={0};
    for(i=0;1;i++){
      if(i==n)i=0;
      if(w){
	w--;
	s[i]++;
	if(s[i]==c)break;
      }
      else{
	w=s[i];
	s[i]=0;
      }
    }
    printf("%d\n",i);
  }
  return 0;
}
      

Measured memory_bytes: 600
a=int(input())

def sum30():
  return (1+2+4+7+8+11+13+14+16+17+19+22+23+26+28+29)

def sumx(x):
  ret = 0
  if(x ==0):
    return ret
  
  for j in range(1,x+1):
    if(j%3 != 0 and j%5 != 0):
      ret+=j
  return ret

def numx(x):
  ret = 0
  if(x ==0):
    return ret
  
  for j in range(1,x+1):
    if(j%3 != 0 and j%5 != 0):
      ret+=1
  return ret
sum=0

i=1
#if()
#sum+=temp*sum30()+sumx(a%30)
while(a > 0):
  if(a >= 30):
    temp=(i-1)*30*16+sum30()
    #print(temp)
    sum+=temp
  else:
    sum+=(i-1)*30*numx(a)+sumx(a)
  i+=1
  a-=30
#while(temp > 0):
#  sum+= temp*sum30()
#  temp-=1

    
print(sum)


Measured memory_bytes: 63616
n = int(input())
l = []
tmp = 0 
for _ in range(n):
    a = list(map(int,input().split()))
    l.append(a)
    if a[len(a)-1] > tmp:
        tmp = a[len(a)-1]

ans = [[0 for i in range(tmp)] for j in range(n)]
for i in range(n):
    if l[i][1] > 0:
        for j in range(2,len(l[i])):
            tmp1 = l[i][j]
            ans[i][tmp1-1] = 1

for i in range(n):
    print(" ".join(map(str,ans[i])))


Measured memory_bytes: 5676
#![allow(
  non_snake_case,
  unused_variables,
  unused_assignments,
  unused_mut,
  unused_imports,
  unused_macros,
  dead_code
)]
use proconio::fastout;
use proconio::input;
use proconio::marker::*;
use std::cmp::*;
use std::collections::*;
//use std::collections::VecDeque;
macro_rules! debug {
  ($($a:expr),* $(,)*) => {
      #[cfg(debug_assertions)]
      eprintln!(concat!($("| ", stringify!($a), "={:?} "),*, "|"), $(&$a),*);
  };
}
#[fastout]
fn main() {
  input! {
    N:usize,
    A:[usize;N]
  }
  let N: usize = N;
  let mut nmax = 1000_000usize;
  let mut h = vec![0usize; nmax + 1];
  for i in 0..N {
    h[A[i]] += 1;
  }
  let mut mx = 0;
  let mut isprime = vec![true; nmax + 1];
  let mut i = 2;
  let mut j = 0;
  let mut f = 0;
  while i <= 1000 {
    if isprime[i] {
      j = i * 2;
      while j <= nmax {
        isprime[j] = false;
        j += i;
      }
    }
    i += 1;
  }
  for i in 2..=nmax {
    if isprime[i] {
      f = 0usize;
      j = i;
      while j <= nmax {
        f += h[j];
        j += i;
      }
      mx = max(mx, f);
    }
  }
  if mx <= 1 {
    println!("pairwise coprime");
    return;
  } else if mx < N {
    println!("setwise coprime");
  } else {
    println!("not coprime")
  }
}


Measured memory_bytes: 25236
#include<bits/stdc++.h>
using namespace std;
typedef long long int uli;
const int mx=55;
int a[mx];
int main(){
  int n;
  scanf("%d",&n);
  int neg=-1,pos=-1;
  for(int i=0;i<n;i++){
    scanf("%d",&a[i]);
    if(a[i]<0){
      if(neg==-1 || a[i]<a[neg])neg=i;
    }
    else{
      if(pos==-1 || a[i]>a[pos])pos=i;
    }
  }
  vector<pair<int,int> >ans;
  if(neg!=-1 && pos!=-1){
    if(-a[neg]>a[pos]){
      for(int i=0;i<n;i++)if(i!=neg){
        ans.push_back({neg,i});
        a[i]+=a[neg];
      }
    }
    else{
      for(int i=0;i<n;i++)if(i!=pos){
        ans.push_back({pos,i});
        a[i]+=a[pos];
      }
    }
  }
  bool allneg=true;
  for(int i=0;i<n;i++)if(a[i]>=0)allneg=false;

  if(allneg){
    for(int i=n-1;i-1>=0;i--){
      ans.push_back({i,i-1});
      a[i-1]+=a[i];
    }
  }
  else{
    for(int i=0;i+1<n;i++){
      ans.push_back({i,i+1});
      a[i+1]+=a[i];
    }
  }
  printf("%d\n",int(ans.size()));
  for(auto p:ans)printf("%d %d\n",p.first+1,p.second+1);

  for(int i=0;i+1<n;i++)assert(a[i]<=a[i+1]);
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <set>
#include <string>
#include <map>
#include <list>
#include <bitset>
#include <algorithm>
#include <functional>
#include <utility>
using namespace std;

#define mp make_pair
#define pb push_back

typedef long long int64;
typedef unsigned long long uint64;

template<typename T>
void printVector(string &txt, vector<T> &a){
    cout << txt;
    for (int i = 0; i < a.size(); ++i)
        cout << a[i] << ' ';
    cout << endl;
}


int main(){

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

    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    int i = 0;
    while (i < n && a[i] == i + 1)
        ++i;
    if (i >= n){
        cout << "YES" << endl;
        return 0;
    }
    int j = i + 1;
    while (j < n && a[j] != i + 1)
        ++j;
    int t = a[i];
    a[i] = a[j];
    a[j] = t;

    while (i < n && a[i] == i + 1)
        ++i;
    if (i >= n)
        cout << "YES" << endl;
    else
        cout << "NO" << endl;

    return 0;
}



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

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

ll N;
vector<ll> A, B;

void solve(){

}

int main(){
  cin >> N;
  rep(i, N+1){
    ll a;
    cin >> a;
    A.push_back(a);
  }
  rep(i, N){
    ll b;
    cin >> b;
    B.push_back(b);
  }
  ll monMax = 0;

  rep(i, N){
    if(A[i] >= B[i]){
      monMax += B[i];
    }else{
      monMax += A[i];
      ll c = B[i] - A[i];
      if(A[i+1] >= c){
        monMax += c;
        A[i+1] -= c;
      }else{
        monMax += A[i+1];
        A[i+1] = 0;
      }
    }
  }

  cout << monMax << endl;
  solve();
}

Measured memory_bytes: 2548
//It is good to start with zero//
//    kyu @Aryabhatta//




#include<bits/stdc++.h> 
using namespace std;                          
#pragma GCC optimize("O3")
typedef long long ll;
#define rep(i, n)    for(ll i = 0; i < (n); ++i)
#define repA(i, a, n)  for(ll i = a; i <= (n); ++i)
#define repD(i, a, n)  for(ll i = a; i >= (n); --i)
#define vec(i, a)  for( auto i=a.begin();i != a.end(); ++i)
#define all(x) x.begin(), x.end()
#define sz(x) (ll)(x).size()
#define fill(a)  memset(a, 0, sizeof (a))
#define mp make_pair
#define pb push_back
#define fast  ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define in  freopen("input.txt","r",stdin);
#define out freopen("output.txt","w",stdout);
#define sixfive in out 
typedef long double ld;
typedef std::pair<ll, ll> pii;
typedef std::vector<ll> vi;
const ll MOD = 1e9 + 7;
ll n_bits(ll n ) { ll x= __builtin_popcount(n) ;return x ;}
int pow(int a, int b, int m)
{
    int ans=1;
    while(b)
    {
        if(b&1)
            ans=(ans*a)%m;
        b/=2;
        a=(a*a)%m;
    }
    return ans;
}
int main()
{    
    #ifndef ONLINE_JUDGE
    sixfive
    #endif
    fast
    ll t=1;
    //cin>>t;
    while(t--)
    {    
        ll a,b,c,d;
        cin>>a>>b>>c>>d;
        ll ans;
        ans=a*c;
        ans=max(ans,b*d);
        ans=max(ans,a*d);
        ans=max(ans,b*c);
        ans=max(ans,(a+1)*c);
        ans=max(ans,(b-1)*d);
        ans=max(ans,a*(c+1));
        ans=max(ans,b*(d-1));
        cout<<ans;
    }
    return 0;
}

//            sometimes I do it for her...//

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

int main(){
  string s,t;
  cin >> s;
  int n = s.size();
  int j = 0;
  rep(i,n){
    if(s[i] == 'B' && t != ""){
      t.pop_back();
    }
    else if(s[i] == 'B') continue;
    else{
      t.push_back(s[i]);
    }
  }
  cout << t << endl;
  return 0;
}


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

using namespace std;

int main()
{
    string input;
    int c = 0;
    cin >> input;
    int sz = input.size();
    for(int i = 0; i < sz; i += 2){
        if(sz%2 == 0){
            if(input[i] == 'R' || input[i] == 'U' || input[i] == 'D'){
                if(input[i+1] == 'L' || input[i+1] == 'U' || input[i+1] == 'D'){
                    c++;
                }
            }
        }
        else if(sz%2 != 0){
            if(i < sz-1){
                if(input[i] == 'R' || input[i] == 'U' || input[i] == 'D'){
                    if(input[i+1] == 'L' || input[i+1] == 'U' || input[i+1] == 'D'){
                        c++;
                }
            }
            }
            else{
                if(input[i] == 'R' || input[i] == 'U' || input[i] == 'D'){
                    c++;
                }
            }
        }
    }
    double e = sz / 2.0;
    if(c == ceil(e)){
        cout << "Yes" << "\n";
    }
    else{
        cout << "No" << "\n";
    }

    return 0;
}

Measured memory_bytes: 3588
#include<bits/stdc++.h>
using namespace std;
#define fi(a) scanf("%d",&a);
#define fli(a) scanf("%ld",&a);
#define fll(a) scanf("%lld",&a);
#define pi(a) printf("%d\n",a);
#define ppi(i,a) printf("Case %d: %d\n",i,a);
#define ll long long
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

int main()
{
    fast
    int arr[1005],n,k,sum=0;
    cin >> n >> k;
    for(int i=0;i<n;i++) cin >> arr[i];

    sort(arr,arr+n);

    for(int i=0;i<k;i++) sum+=arr[i];

    cout << sum << endl;
    return 0;
}



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

#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define INF 1e9
#define LINF 1e18
typedef long long ll;


int main() {
    int N,M; cin >> N >> M;
    vector<int> a(N+1,0);
    REP(i,M){
        int l,r; cin >> l >> r;
        l--;
        r--;
        a[l]++;
        a[r+1]--;
    }

    int ans = 0;
    REP(i,N){
        a[i+1] += a[i];
    }
    REP(i,N){
        if(a[i]==M) ans++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3708
#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>

using ll = long long int;
const int INF = (1<<30);
const ll INFLL = (1ll<<60);
const ll MOD = (ll)(1e9+7);

#define l_ength size

void mul_mod(ll& a, ll b){
	a *= b;
	a %= MOD;
}

void add_mod(ll& a, ll b){
	a = (a<MOD)?a:(a-MOD);
	b = (b<MOD)?b:(b-MOD);
	a += b;
	a = (a<MOD)?a:(a-MOD);
}

int db[225816][66];

int main(void){
	int n,i,j,ans=0;
	ll k;
	std::cin >> n >> k;
	for(i=0; i<n; ++i){
		std::cin >> db[i][0];
		--db[i][0];
	}
	for(j=0; j<60; ++j){
		for(i=0; i<n; ++i){
			db[i][j+1] = db[db[i][j]][j];
		}
	}
	for(j=60; j>=0; --j){
		if(k&(1ll<<j)){
			ans = db[ans][j];
		}
	}
	++ans;
	std::cout << ans << std::endl;
	return 0;
}


Measured memory_bytes: 55192
#include <stdio.h>
#include <iostream>
#include <vector>
#include <list>
#include <cmath>
#include <fstream>
#include <algorithm>
#include <string>
#include <queue>
#include <set>
#include <map>
#include <complex>
#include <iterator>
#include <cstdlib>
#include <cstring>
#include <sstream>

using namespace std;

#define EPS (1e-10)
#define EQ(a,b) (abs((a) - (b)) < EPS)
#define EQV(a,b) (EQ((a).real(),(b).real()) && EQ((a).imag(),(b).imag()))

typedef complex<double> P;
typedef long long ll;

ll dp[1000001];
ll a[100];


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

ll InclusionExclusion(int n,int m){
    // a1,a2,..Ì¤¿A­È­ÆàPÂÅèØêéàÌÌa
    ll sum=0;
    // ­È­ÆàPÂÅèØêéàÌÌÂ
    ll res=0;
    for(int i=1;i<(1<<m);i++){
        ll num=0;
        for(int j = i;j!=0;j>>=1)
            num+=j&1;
        ll lcm=1;
        for(int j = 0; j <m; j++){
            if((i>>j)&1){
                lcm=lcm/gcd(lcm,a[j])*a[j];
                if(lcm>n)
                    break;
            }
        }
        if(num%2==0){
            ll t=n/lcm;
            sum-=lcm*t*(t+1)/2;
            res-=n/lcm;
        }
        else{
            res+=n/lcm;
            ll t=n/lcm;
            sum+=lcm*t*(t+1)/2;
        }
    }
    return res;
}
set<int> pf(int n){
    set<int> s;
    for(int i = 2; i * i <=n; i++){
        if(n%i==0){
            s.insert(i);
            while(n%i==0)
                n/=i;
        }
    }
    if(n!=1)s.insert(n);
    return s;
}

int dfs(int n){
    if(dp[n]!=0)
        return dp[n];
    int res=dfs(n-1);
    // öðßé
    set<int> s=pf(n);
    int cnt=0;
    for(set<int>::iterator it =s.begin();it!=s.end();it++){
        a[cnt++]=*it;
    }
    // Ù¤¶å´ðp¢é
    int r=InclusionExclusion(n,cnt);
    return dp[n]=res+n-r;
}


void solve(){
    memset(dp,0,sizeof(dp));
    int t;
    cin>>t;
    dp[1]=2;
    dp[2]=3;
    for(int i = 3; i < 1000001; i++){
       // cout<<i<<endl;
        dp[i]=dp[i-1];
        set<int> s=pf(i);

        int cnt=0;
        for(set<int>::iterator it =s.begin();it!=s.end();it++){
            a[cnt++]=*it;
        }
        dp[i]+=i-InclusionExclusion(i,cnt);
    }

    for(int i = 0; i < t; i++){
        int a;
        cin>>a;
        cout<<dp[a]<<endl;
    }
}

int main(){

    solve();

    return 0;
}

Measured memory_bytes: 8732
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def isk():
    cnt=0
    for i in range(h):
        if hbit>>i&1:continue
        for j in range(w):
            if wbit>>j&1:continue
            cnt+=cc[i][j]
    return cnt==k

h,w,k=MI()
cc=[[c=="#" for c in SI()] for _ in range(h)]
ans=0
for hbit in range(1<<h):
    for wbit in range(1<<w):
        ans+=isk()
print(ans)


Measured memory_bytes: 9236
//	Totally unrelated and not AT ALL stolen from hohohaha's, generic_placeholder_name's or katoriyuu's template
#include <bits/stdc++.h>

using namespace std;

#pragma GCC optimize("O3")
#pragma GCC target("avx")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define gcd __gcd
#define rep(i,s,end) for(int i = (s); i <  (end); ++i)
#define rep0(i, end) for(int i =   0; i <= (end); ++i)
#define rep1(i, end) for(int i =   1; i <= (end); ++i)
#define lb lower_bound
#define ub upper_bound

#define vt vector
#define endl "\n"

#define fileopen(filename, in_type, out_type) if (fopen(filename in_type, "r")) {freopen(filename in_type, "r", stdin);freopen(filename out_type, "w", stdout);}
#define local_input(x) if (x && fopen("input.txt","r")) freopen("input.txt","r",stdin);
#define fastio ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)

#define fscan(x)   scanf("%d",  &x)
#define fscandb(x) scanf("%lf", &x)
#define fscanll(x) scanf("%lld",&x)
//	Until next time, remember:
//			You are closer than you think.
//						_Dan Lok_

#define db double
#define ll long long
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
#define pi 3.1415926535897932	//faster than pi = acos(-1); but sometimes doesn't work?
//	srand(chrono::steady_clock::now().time_since_epoch().count());
//	freopen("input.txt","r",stdin);

#define mn 1 << 18
int n;
int id1[mn],id2[mn],dp1[mn],dp2[mn];
signed main()
{
	fastio;
	cin >> n; rep(i,0,1 << n){
		cin >> dp1[i]; id1[i] = i, dp2[i] = id2[i] = -1;
	}
	rep(i,1,1 << n){
		rep(j,0,n) if(i & (1 << j)){
			int jj = i ^ (1 << j);
			if(jj){
				if(id1[i] == id1[jj]) continue;
				else if(dp1[i] <= dp1[jj]){
					dp2[i] = dp1[i],  id2[i] = id1[i];
					dp1[i] = dp1[jj], id1[i] = id1[jj];
					if(dp2[i] <= dp2[jj] && id2[i] != id2[jj]){
						dp2[i] = dp2[jj], id2[i] = id2[jj];
					}
				}
				else if(dp2[i] <= dp1[jj] && id2[i] != id1[jj]){
					dp2[i] = dp1[jj], id2[i] = id1[jj];
				}
			}
			else{
				if(dp1[0] > dp1[i]){
					dp2[i] = dp1[i], id2[i] = id1[i];
					dp1[i] = dp1[0], id1[i] = id1[0];
				}
				else if(dp1[0] > dp2[i]){
					dp2[i] = dp1[0], id2[i] = id1[0];
				}
			}
		}
	}
	int ans = 0;
	rep(i,1,1 << n){
		cout << (ans = max(ans, dp1[i] + dp2[i])) << endl;
	}
	return 0;
}
// with the aura of Dora, AC!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!1!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
// Why is there a one in my row of exclamation marks?
 

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

int h, w, n;

int main()
{
    cin >> h >> w >> n;
    queue<int> que;
    rep(i, n)
    {
        int a;
        cin >> a;
        rep(j, a)
        {
            que.push(i + 1);
        }
    }
    
    int res[h][w];
    for(int i = 0; i < h; i++)
    {
        if(i % 2 == 0)
        {
            for(int j = 0; j < w; j++)
            {
                res[i][j] = que.front();
                que.pop();
            }
        }
        else
        {
            for(int j = w - 1; j >= 0; j--)
            {
                res[i][j] = que.front();
                que.pop();
            }
        }
        
    }

    rep(i, h)
    {
        rep(j, w)
        {
            cout << res[i][j] << " ";
        }
        cout << "\n";
    }
    
    return 0;
}

Measured memory_bytes: 384
s = gets.chomp
n = s.length + 1
a = Array.new(n, 0)
0.upto(n - 2) do |i|
  if s[i] == "<"
    a[i + 1] = [a[i] + 1, a[i + 1]].max
  end
end
(n - 2).downto(0) do |i|
  if s[i] == ">"
    a[i] = [a[i], a[i + 1] + 1].max
  end
end
puts a.reduce(0) { |sum, v| sum += v }


Measured memory_bytes: 6788