akhauriyash/Code-Regression huggingface dataset:
/**
  * BInary Search tree (insert & search)
  * output 1)node_number, 2)parent_number, 3)depth, 4)kind_of_node, 5)child_list
  */

/* inclution */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>

/* Definition */
#define MAX 500000
#define LEN 10

/* Global Variables */
struct Node {
  int key;
  struct Node *right, *left, *parent;
};

/* Prototype */
void insert(int);
struct Node* find(struct Node*, int);
void inOrderWalk(struct Node*);
void preOrderWalk(struct Node*);

struct Node *root, *NIL;

int n;

/* main */
int main(){
  int i,x; //n: length of input, z: insert node key
  char str[LEN]; //insert???????´?
  
  /* input the number of A[] */
  scanf("%d",&n);
  
  /* input datas */
  for(i=0;i<n;i++){
    scanf("%s", str);
    if(!strcmp(str, "find")) {
      scanf("%d", &x);
      struct Node *result = find(root, x);
      if(result!=NIL) {
        printf("yes\n");
      }else {
        printf("no\n");
      }
    }else if(!strcmp(str, "insert")) {
      scanf("%d", &x);
      insert(x);
    }else if(!strcmp(str, "print")) {
      inOrderWalk(root);
      printf("\n");
      preOrderWalk(root);
      printf("\n");
    }
  }

  return 0;
}

/* insertion */
void insert(int k) {
  struct Node *y = NIL; //x ??? ???
  struct Node *x = root;
  struct Node *z;

  z = (struct Node *)malloc(sizeof(struct Node));
  z->key = k;
  z->left = NIL;
  z->right = NIL;

  while(x != NIL) {
    y = x; // ???????¨????
    if (z->key < x->key) {
      x = x->left; // ?????????????§????
    }else {
      x = x->right; // ?????????????§????
    }
  }
  z->parent = y;

  if (y == NIL) { // T ???????????´???
    root = z;
  }else if (z->key < y->key) {
    y->left = z; // z ??? y ?????????????????????
  }else {
    y->right = z; // z ??? y ?????????????????????
  }
}

struct Node *find(struct Node *v, int k) {
  while(v!=NIL && k!=v->key) {
    if(k<v->key) {
      v = v->left;
    }else {
      v = v->right;
    }
  }
  return v;
}

void inOrderWalk(struct Node *v) {
  if(v==NIL) {
    return;
  }
  inOrderWalk(v->left);
  printf(" %d", v->key);
  inOrderWalk(v->right);
}

void preOrderWalk(struct Node *v) {
  if(v==NIL) {
    return;
  }
  printf(" %d", v->key);
  preOrderWalk(v->left);
  preOrderWalk(v->right);
}

Measured memory_bytes: 19364
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
  private static class FastScanner {
    private BufferedReader reader = null;
    private StringTokenizer tokenizer = null;

    public FastScanner(InputStream in) {
      reader = new BufferedReader(new InputStreamReader(in));
      tokenizer = null;
    }

    public String next() {
      if (tokenizer == null || !tokenizer.hasMoreTokens()) {
        try {
          tokenizer = new StringTokenizer(reader.readLine());
        } catch (IOException e) {
          throw new RuntimeException(e);
        }
      }
      return tokenizer.nextToken();
    }

    public String nextLine() {
      if (tokenizer == null || !tokenizer.hasMoreTokens()) {
        try {
          return reader.readLine();
        } catch (IOException e) {
          throw new RuntimeException(e);
        }
      }

      return tokenizer.nextToken("\n");
    }

    public long nextLong() {
      return Long.parseLong(next());
    }

    public int nextInt() {
      return Integer.parseInt(next());
    }

    public double nextDouble() {
      return Double.parseDouble(next());
    }

    public int[] nextIntArray(int n) {
      int[] a = new int[n];
      for (int i = 0; i < n; i++)
        a[i] = nextInt();
      return a;
    }

    public long[] nextLongArray(int n) {
      long[] a = new long[n];
      for (int i = 0; i < n; i++)
        a[i] = nextLong();
      return a;
    }
  }

  public static void main(String[] args) {
    FastScanner sc = new FastScanner(System.in);
    String s = sc.next();
    if (s.endsWith("s")) System.out.println(s + "es");
    else System.out.println(s + "s");
  }
}

Measured memory_bytes: 36528
#include<stdio.h>
#include<iostream>
#include<map>

using namespace std;

int main()
{
    int n,mx=0;
    string inp;
    map<string,int> papers;
    map<string,int> out;

    scanf("%d",&n);

    for(int i=0;i<n;i++)
    {
        cin>>inp;

        if(papers.count(inp))
            papers[inp]++;
        else
            papers[inp]=1;

        if(papers[inp]>mx)
            mx=papers[inp];
    }

    map<string,int>::iterator it;

    for(it=papers.begin();it!=papers.end();it++)
    {
        //cout<<it->first<<"\n";
        if((it->second)==mx)
            out[it->first]=mx;
    }

    for(it=out.begin();it!=out.end();it++)
        cout<<it->first<<"\n";

    return 0;
}


Measured memory_bytes: 37760
#include <cstdio>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <iterator>
#include <cassert>
#include <numeric>
#include <functional>
#pragma warning(disable:4996) 

typedef long long ll;
typedef unsigned long long ull;
#define MIN(a, b) ((a)>(b)? (b): (a))
#define MAX(a, b) ((a)<(b)? (b): (a))
#define LINF  9223300000000000000
#define LINF2 1223300000000000000
#define LINF3 1000000000000
#define INF 2140000000
const long long MOD = 1000000007;
//const long long MOD = 998244353;

using namespace std;


void solve()
{
    int a;
    scanf("%d", &a);
    printf("%d\n", a + a * a + a * a*a);
    return;
}


int main(int argc, char* argv[])
{
#if 1
    solve();
#else
    int T;
    scanf("%d", &T);
    int t;
    for(t=0; t<T; t++) {
        //printf("Case #%d: ", t+1);
        solve();
    }
#endif
    return 0;
}


Measured memory_bytes: 1724
#include <bits/stdc++.h>
using namespace std;
      
int main(){
  string S;cin>>S;
  vector<int> vec(26,0);
  int size=S.size();
  for(int i=0;i<size;i++){
    vec.at((int)S.at(i)-97)++;
  }
  int std;
  for(int j=0;j<26;j++){
    if(vec.at(j)==0){
      std=j;
      break;
    }
    else{
      std=-1;
    }
  }
  if(std>=0){
    int k=std+97;
    cout<<(char)k<<endl;
  }
  else{
    cout<<"None"<<endl;
  }
  
}


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

const long long MAX = 1e18;
using namespace std;  
int main() {

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

	for (int i = 0; i < N; i++) {
		if (a[i] == 0) {
			cout << 0 << endl;
			return 0;
		}
	}
	
	long long mul = 1;
	for (int i = 0; i < N; i++) {
		if (mul > MAX / a[i]) {
			cout << -1 << endl;
			return 0;
		}
		else 
                     mul *= a[i];
	}
	
	cout << mul << endl;
	return 0;
}


Measured memory_bytes: 4052
// d_abc106.cpp
#include <iostream>
#include <vector>
#include <cstdio>
using namespace std;

#define FOR(i,a,b) for(i = a; i < b; ++i)
#define REP(i,n)   for(i = 0; i < n; ++i)

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;


vector<vector<int>> sum;
ll N, M, Q;

void makeSumTable(vector<int> L, vector<int> R)
{
    ll i, j;

    sum = vector<vector<int>> (N + 1, vector<int>(N + 1, 0));

    REP(i, M){
        ++sum[L[i]][R[i]];
    }

    FOR(i, 1, N + 1){
        FOR(j, 1, N + 1){
            sum[i][j] += sum[i - 1][j];
            sum[i][j] += sum[i][j - 1];
            sum[i][j] -= sum[i - 1][j - 1];
        }
    }
}

int getSum(int L, int R){
    int ans = sum[R][R] - sum[R][L - 1] - sum[L - 1][R] + sum[L - 1][L - 1];
    return ans;
}

int main()
{
    ll i;

    cin >> N >> M >> Q;
    // scanf("%d %d %d", N, M, Q);

    vector<int> L(M);
    vector<int> R(M);
    REP(i, M){
        // cin >> L[i] >> R[i];
        scanf("%d %d", &L[i], &R[i]);
    }

    vector<int> p(Q);
    vector<int> q(Q);
    REP(i, Q){
        // cin >> p[i] >> q[i];
        scanf("%d %d", &p[i], &q[i]);

    }

    makeSumTable(L, R);

    int ans;
    REP(i, Q){
        ans = getSum(p[i], q[i]);
        // cout << ans << endl;
        printf("%d\n", ans);
    }
}


Measured memory_bytes: 5120
#include <bits/stdc++.h>
#define For(i, a, b) for(int (i)=(a); (i)<(b); (i)++)
#define rFor(i, a, b) for(int (i)=(a)-1; (i)>=(b); (i)--)
#define rep(i, n) For((i), 0, (n))
#define rrep(i, n) rFor((i), (n), 0)
using namespace std;
typedef long long lint;
typedef vector<vector<lint>> mat;

const lint mod = 1e9 + 7;

mat mul(mat a, mat b){
    int s = a.size();
    int t = b[0].size();
    mat c(s, vector<lint>(t, 0LL));
    rep(i, s)rep(j, t)rep(k, b.size()) c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % mod;
    return c;
}

mat pow(mat a, lint x){
    int s = a.size();
    mat c(s, vector<lint>(s, 0LL));
    rep(i, s) c[i][i] = 1;
    while(x > 0){
        if(x&1) c = mul(a, c), x -= 1;
        else a = mul(a, a), x >>= 1;
    }
    return c;
}

int main(){
    int n; lint k; cin >> n >> k;
    mat a(n, vector<lint>(n, 0LL)); rep(i, n)rep(j, n) cin >> a[i][j];
    mat u(n, vector<lint>(1, 1LL));
    mat v = mul(pow(a, k), u);
    lint ans = 0;
    rep(i, n) ans = (ans + v[i][0]) % mod;
    cout << ans << endl;
}

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

using namespace std;
using ll = long long;

#define rep(i,N) for(int i=0;i<(int)N;++i)

ll GCD(ll x, ll y) {
    if (y == 0) return x;
    else return GCD(y, x % y);
}


#include <iostream>

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

    string T = S.substr(0, 3);
    T = "2018";
    T += S.substr(4, 6);

    cout << T << endl;

}


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


Measured memory_bytes: 256
import collections
 
H,W = list(map(int,input().split()))
S = [list(input()) for _ in range(H)]
copyS = [S[i][:] for i in range(H)]
que = collections.deque()
que.append([0,0])
 
d = [[float('inf') for _ in range(W)] for _ in range(H)]
d[0][0] = 0
S[0][0] = '#'
 
while len(que) != 0:
    y,x = que.popleft()
    if y == H-1 and x == W-1:
        break
    for direct in [[1,0],[-1,0],[0,1],[0,-1]]:
        if 0 <= y+direct[0] <= H-1 and 0 <= x+direct[1] <= W-1:
            if S[y+direct[0]][x+direct[1]] != '#':
                d[y+direct[0]][x+direct[1]] = d[y][x]+1
                S[y+direct[0]][x+direct[1]] = '#'
                que.append([y+direct[0], x+direct[1]])

if y != H-1 or x != W-1:
    print(-1)
    exit()

count = 0
for i in range(H):
    for j in range(W):
        if copyS[i][j] == '.':
            count += 1
print(count - (d[y][x]+1))

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

void solve(){
    long long x;
    cin>>x;
    long long res=x/500;
    long long div=x%500;
    div/=5;
    cout<<(res*1000+div*5);

}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();    
    return 0;
}

Measured memory_bytes: 256
import bisect

n=int(input())
a=list(map(int,input().split()))

b=sorted(a)

kazu=[]
shurui=[]

gen=0
for i in range(n):
    if(gen!=b[i]):
        kazu.append(1)
        shurui.append(b[i])
        gen=b[i]
    else:
        kazu[-1]+=1


gokei=0
herasi=[]

for k in kazu:
    gokei+=k*(k-1)//2


ans=[]
for i in range(n):
    basho=bisect.bisect_left(shurui,a[i])
    print(gokei-kazu[basho]+1)

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

using namespace std;

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

const ll INF=1e9+7;
int minf=INF;
int n,a[101];
int main()
{
	/*freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);*/
	cin>>n;
	rep(i,n){
		cin>>a[i];
	}
	for(int i=-100;i<=100;i++){
		int h=0;
		rep(j,n){
			h+=(i-a[j])*(i-a[j]);
		}
		minf=min(minf,h);
	}
	cout<<minf;
	return 0;
}


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

template <typename T> T gcd(T x, T y) {
  if (y == 0)
    return x;
  return gcd(y, x % y);
}

template <typename T> T lcm(T x, T y) {
  if (x == 0 || y == 0)
    return 0;
  return x / gcd(x, y) * y;
}

int ctoi(char c) {
  if (c >= '0' && c <= '9') {
    return c - '0';
  }
  return 0;
}

vector<int> p;
vector<int> r;

void init(int n) {
  p.reserve(n);
  r.reserve(n);
  for (int i = 0; i < n; i++) {
    p[i] = i;
    r[i] = 0;
  }
}

int root(int x) { return p[x] == x ? x : p[x] = root(p[x]); }

bool same(int x, int y) { return root(x) == root(y); }

void unite(int x, int y) {
  x = root(x);
  y = root(y);
  if (x == y)
    return;

  if (r[x] < r[y])
    p[x] = y;
  else {
    p[y] = x;
    if (r[x] == r[y])
      r[x]++;
  }
}

int main() {
  int S;
  cin >> S;
  int tmp = S;
  int n = 0;
  while (tmp > 0) {
    n += tmp % 10;
    tmp /= 10;
  }
  cout << (S % n == 0 ? "Yes" : "No") << endl;
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.sql.Array;
import java.util.*;

public class Main {

    static long gcd (long a, long b) {return b>0?gcd(b,a%b):a;}
    static long lcm (long a, long b) {return a*b/gcd(a,b);}

    public static void main(String[] args){
	// write your code here
        Scanner sc=new Scanner(System.in);
        Set<Long> set = new HashSet<Long>();
        int n=sc.nextInt();
        for(int i=0;i<n;i++){
            long S=sc.nextLong();
            set.add(S);
        }
        long ans=0;
        int q=sc.nextInt();
        for(int i=0;i<q;i++){
            long T = sc.nextLong();
            if (set.contains(T)) {
                ans++;
            }
        }
        System.out.println(ans);

    }
}



Measured memory_bytes: 93324
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define ld long double
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
using P=pair<long long,long long>;
#define rep(i,n) for(long long i=0; i<(long long)n; i++)
#define req(i,n) for(long long i=n-1; i>=0; i--)
#define range(i,a,b) for(long long i=a; i<b; i++)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((long long)(x).size())
#define COUT(x) cout << x << endl
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define onBoard(y,x) (y>=0 && y<h && x>=0 && x<w)
#define pri_que priority_queue
#define vint vector<int>
#define vvint vector<vector<int>>
#define vi vector<int>
#define vvi vector<vector<int>>
#define vs vector<string>
#define vvc vector<vector<char>>
#define vc vector<char>
#define vp vector<pair<int,int>>
#define vb vector<bool>
#define vvb vector<vector<bool>>
#define show(x) cout<<#x<<"="<<x<<endl;
#define SUM(x) accumulate(x.begin(),x.end(),0)
#define MAX(x) *max_element(x.begin(),x.end())
#define MIN(x) *min_element(x.begin(),x.end())
#define couty cout<<"Yes"<<endl
#define coutn cout<<"No"<<endl
#define coutY cout<<"YES"<<endl
#define coutN cout<<"NO"<<endl
#define yn(x) cout<<(x?"Yes":"No")<<endl
#define YN(x) cout<<(x?"YES":"NO")<<endl
long long gcd(long long a,long long b){return b?gcd(b,a%b):a;}
long long lcm(long long a, long long b){return a/gcd(a,b)*b;}
const long long dx[8]={1,0,-1,0,1,-1,-1,1};
const long long dy[8]={0,1,0,-1,1,1,-1,-1};
const long long INF = 1e15;
const long long MOD = 1e9+7;

signed main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout<<fixed<<setprecision(15);

    vi a(3); rep(i,3)cin>>a[i];
    sort(all(a),greater<int>());
    cout<<a[0]*10+a[1]+a[2]<<endl;
}

Measured memory_bytes: 3648
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <utility>
#include <stack>
#include <queue>
typedef long long ll;
using namespace std;

void check(string s,ll f){

}

int main(){
  ll i,j,k,n,m;
  string s;
  ll a,b,c,d;
  cin >> n >> a >> b >> c >> d;
  cin >> s;
  ll mi = min(c,d);
  ll si = s.size();
  if(s[d-1]=='#'){
    cout << "No" << endl;
    return 0;
  }
  if(s[c-1]=='#'){
    cout << "No" << endl;
    return 0;
  }
  if(c<d){
    for(i=b;i<d-1;i++){
      if(s[i]=='#' && s[i+1]=='#'){
        cout << "No" << endl;
        return 0;
      }
    }
    for(i=a;i<c-1;i++){
      if(s[i]=='#' && s[i+1]=='#'){
        cout << "No" << endl;
        return 0;
      }
    }
    cout << "Yes" << endl;
    return 0;
  }else{
    bool flag = false;
    if(s[b-2]=='#')b++;
    for(i=b-1;i<d;i++){
      if(s[i-1]=='.'&&s[i]=='.' && s[i+1]=='.'){
        s[i]='#';
        flag =true;
        break;
      }
    }
    if(!flag){
      cout << "No" << endl;
      return 0;
    }
    for(i=a;i<c-1;i++){
      if(s[i]=='#' && s[i+1]=='#'){
        cout << "No" << endl;
        return 0;
      }
    }
    cout << "Yes" << endl;
  }

  //check(s,d);
  return 0;
}


Measured memory_bytes: 640
# coding: utf-8
# Your code here!
n,k=map(int,input().split())
h=[]
for i in range(n):
    h.append(int(input()))
ans=10**10
c=0
h.sort()
for i in range(n-k+1):
    c=h[i+k-1]-h[i]
    if c<ans:
        ans=c
print(ans)

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

#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define all(v) (v).begin(),(v).end()
typedef pair<int,int> P;
int n,k;
int c,g;
vector<P> v;
int G[12];
int dp[11][2002];
vector<int> val[11];//?????£??????G???N-1????????£??????????????§
priority_queue<int> que[12];

int main(){
  cin>>n>>k;
  REP(i,n){
    cin>>c>>g;
    val[g].push_back(c);
  }
  FOR(i,1,11){
    sort(all(val[i]),greater<int>());
    REP(j,val[i].size()){
      if(j==0)continue;
      val[i][j]+=val[i][j-1]+j*2;
    }
  }
  FOR(i,1,11){
    REP(j,k+1){
      FOR(l,j,k+1){
        if(j==l)dp[i][l]=max(dp[i][l],dp[i-1][j]);
        else if(l-j-1<val[i].size()){
          dp[i][l]=max(dp[i][l],dp[i-1][j]+val[i][l-j-1]);
        }
      }
    }
  }
  cout<<dp[10][k]<<endl;
  return 0;
}

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

#define getmid(l,r) ((l) + ((r) - (l)) / 2)
#define MEM(a,b) memset(a,b,sizeof(a))
#define MP(a,b) make_pair(a,b)
#define PB push_back

typedef long long ll;
typedef pair<int,int> pii;
const double eps = 1e-8;
const int INF = (1 << 30) - 1;

int A[100010];
int n;

int main(){
	cin >> n;
	for(int i = 1; i <= n; ++i){
		cin >> A[i];
	}
	sort(A + 1,A + n + 1);
	int p = 1;
	double mid = A[n] / 2.0;
	for(int i = 1; i < n; ++i){
		if(fabs(A[i] - mid) < fabs(A[p] - mid)) p = i;
	}
	printf("%d %d\n",A[n],A[p]);
	return 0;
}

Measured memory_bytes: 768
package main
import (
    "strconv"
    "fmt"
)
func main(){
    var s string
    ans := 0
    fmt.Scan(&s)
    for i :=0; i < len(s); i++ {
        r, _ := strconv.Atoi(s[i:i+1])
        ans += r
    }
    fmt.Println(ans)
}

Measured memory_bytes: 1772
#include <iostream>
#include <bits/stdc++.h>
#include <string>
#include <math.h>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

int main(){
    double l; cin>>l;
    double a=l/3;
    double ans=pow(a,3);
    printf("%.10f\n",ans);
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <math.h>
#define ALL(a)    a.begin(), a.end() 
#define rep(i, K, N)  for(long long int i = K; i < N; i++)
#define ll long long int
using namespace std;

int main (){
ll K, Ans = 1;cin >> K;
ll n = 0;
map<ll, ll> M;

while(1){

    n*=10;n+=7;n%=K;M[n]++;

    if(n == 0){cout << Ans;exit(0);}

    if(M[n] == 2)break;

    Ans++;
}
cout << -1;
}

Measured memory_bytes: 66064
//Chat I am Trash
#include <bits/stdc++.h>
#define ll long long int
#define FASTIO std::ios::sync_with_stdio(false);
#define pb push_back
#define mp make_pair
#define ld long double
#define F first
#define S second
#define inf 1e18
#define debug(x) cout<<x<<endl
#define all(x) x.begin(),x.end()

using namespace std;
int main()
{
    FASTIO
    ll k,a,b;
    cin >>k>>a>>b;
ll ans = 0;
    if(b-a<=2||a>k+1)
    ans=1+k;
    else
    {
      ll o=0;
      k-=(a-1);

      if(k%2!=0)
      {
        o++;k--;
      }
      ll c=k/2;
      ll curr =a;


      curr+=c*(b-a);
      curr+=o;
      ans = curr;
    }
    cout<<ans;



return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {

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

    for (int i = 0; i < n; i++) {
      a[i] = sc.nextInt();
    }

    Arrays.sort(a);
    int sum = 0;
    int x = (n-1)%2;

    for (int i = n-1; i >= 0; i--) {
      if (i % 2 == x) {
        sum += a[i];
      } else {
        sum -= a[i];
      }
    }

    System.out.println(sum);
    
  }

}


Measured memory_bytes: 21460
#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()
{
    while(true){
    int ans = 0;
        int n,x;
        cin >> n >> x;
        if(n == 0 && x == 0) break;
        for(int i = 1; i <= n-2; i++){
            for(int j = i+1; j<= n-1; j++){
                for(int k = j+1; k <= n; k++){
                    if(i+j+k == x) ans++;
                }
            }
        }
        
    cout << ans << endl;
    }
    return 0;
}



Measured memory_bytes: 3056
#include<cstdio>
const int N=2*1e5+10;
int a[N],n,l=1,r=1;
long long ans,s;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	while(l<=n)
	{
		while(r<=n&&(s&a[r])==0)s^=a[r++];
		ans+=r-l;
		s^=a[l++];
	}
	printf("%lld",ans);
	return 0;
}

Measured memory_bytes: 896
#include <bits/stdc++.h>
using namespace std;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
using Int = long long;
const char newl = '\n';


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

//INSERT ABOVE HERE
signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);

  Int k;
  cin>>k;

  const Int MAX = 1e8;
  Int res=0;
  for(Int i=1;i<MAX;i++){
    res=(res*10+7)%k;
    if(res==0) drop(i);
  }

  cout<<-1<<newl;
  return 0;
}


Measured memory_bytes: 3624
import sys

N = int(input())

for i in range(1, N + 1):
    if i * (i + 1) // 2 == N:
        K = i
        break
else:
    print('No')
    sys.exit(0)

anss = [[] for _ in range(K + 1)]
x = 1
iAns = 0
for i in reversed(range(1, K + 1)):
    anss[iAns].append(x)
    anss[-1].append(x)
    for j in range(1, i):
        anss[iAns].append(x + j)
        anss[iAns + j].append(x + j)
    x += i
    iAns += 1

print('Yes')
print(K + 1)
for ans in anss:
    print(len(ans), ' '.join(map(str, ans)))


Measured memory_bytes: 12292
N,M = map(int,input().split())
A = []
for _ in range(N):
    a,b = map(int,input().split())
    A.append((a,b))
A = sorted(A,key=lambda x:x[0])
B = [A[0][1]]
if A[0][1]>=M:
    cnt = A[0][0]*M
else:
    ind = 0
    for i in range(1,N):
        B.append(B[i-1]+A[i][1])
        if B[i]>=M:
            ind = i
            break
    cnt = 0
    for i in range(ind):
        cnt += A[i][0]*A[i][1]
    cnt += A[ind][0]*(M-B[ind-1])
print(cnt)

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

int main() {
    int n, l;
    cin >> n >> l;
    string s[n];
    rep(i, n) cin >> s[i];
    sort(s, s + n);

    rep(i, n) cout << s[i];
    cout << endl;
    return 0;
}


Measured memory_bytes: 3636
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <iomanip>

//#define DEBUG
using namespace std;

int main(){
    int A, B, C;
    cin >> A >> B >> C;
    int maxmum = max(A, B);
    int minmum = min(A, B);
    for(int i = minmum; i < maxmum; i++){
        if(i == C){
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <stack>
#include <iomanip>


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 FORR(i, m, n) for(int i = m;i >= n;i--)
#define REPO(i, n) for(int i = 1;i <= n;i++)
#define ll long long
#define INF 1999999999
#define MINF -1999999999
#define INF64 1999999999999999999
#define ALL(n) n.begin(),n.end()
#define MOD 1000000007


ll i, o, t, j, l, s, z, a1 = 0, a2 = 0;
int main() {
	cin >> i >> o >> t >> j >> l >> s >> z;

	a1 += o;
	a1 += (l - l % 2);
	a1 += (j - j % 2);
	a1 += (i - i % 2);
	if (l > 0 and j > 0 and i > 0) {
		a2 += 3;
		i--;
		l--;
		j--;
	}
	a2 += o;
	a2 += (l - l % 2);
	l %= 2;
	a2 += (j - j % 2);
	j %= 2;
	
	a2 += (i - i % 2);
	i %= 2;
	
	cout << max(a1, a2) << endl;
}

Measured memory_bytes: 256
/*
*                                 Name : chaitanya
*
*                         Institute : ANITS,Visakhapatnam
*   "Don't regret anything you do, because in the end it makes you who you are."
*
*/
#include<cstdio>
#include<iostream>
#include<sstream>
#include<fstream>
#include<iomanip>
#include<algorithm>
#include<cmath>
#include<complex>
#include<cstring>
#include<vector>
#include<list>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<bitset>
#include<numeric>
#include<limits>
#include<climits>
#include<cfloat>
#include<functional>
#include<iterator>
#include <random>
#include<sstream>
#define infy  1000000000
#define all(x) begin(x),end(x)
#define ll long long int
#define ff first
#define ss second
#define pb push_back
const ll m = 1000000007;
#pragma GCC optimization ("O3")
using namespace std;

bool prime(int n)
{
  for (int i = 2; i < min(500000,n); ++i)
  {
    if(n%2 == 0)
    {
      return 0;
  }
}
return 1;
}
vector<string> vec_splitter(string s) {
  s += ',';
  vector<string> res;
  while(!s.empty()) {
    res.push_back(s.substr(0, s.find(',')));
    s = s.substr(s.find(',') + 1);
}
return res;
}
void debug_out(
    vector<string> __attribute__ ((unused)) args,
    __attribute__ ((unused)) int idx,
    __attribute__ ((unused)) int LINE_NUM) { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(vector<string> args, int idx, int LINE_NUM, Head H, Tail... T) {
  if(idx > 0) cerr << ", "; else cerr << "Line(" << LINE_NUM << ") ";
  stringstream ss; ss << H;
  cerr << args[idx] << " = " << ss.str();
  debug_out(args, idx + 1, LINE_NUM, T...);
}
#ifndef ONLINE_JUDGE
#define debug(...) debug_out(vec_splitter(#__VA_ARGS__), 0, __LINE__, __VA_ARGS__)
#else
#define debug(...) 42
#endif

// 2+3+5+7+11+13
//   consecutivePrimes = (41) is also a prime

const int  N = 1000 * 10000 + 4;
vector <bool> isPrime(N,true);
vector <int> odd;
void  oddnum()
{
    for (int i = 1; i < N; i+=2 )
    {
        odd.pb(i);
    }
}
bool pall (int n)
{
    string s = to_string(n),r = "";
    r = string(s.rbegin(),s.rend());
    if (s == r)
        return true;
    else
        return false;

}
int main()
{

	// int x = -1, y = 10000;
	// double z = 0.2;
	// string s2 = "beginner1010";
	// long long b = 1LL << 60;B
	// // debug(x, y, z, s, b);
	// double aux = 1010.0;
	// string code = "code";

	// debug(code + "forces",-aux / 10 * 2.3);
	// freopen("input.txt","r",stdin);
	// freopen("output.txt","w",stdout);
	//ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t = 5;
    while(t--) {
        int a;
        cin >> a;
        if (a == 0) {
            cout << 5 - t;
        }
    }
}

Measured memory_bytes: 4272
M, D = map(int, input().split())

count = 0
for m in range(1, M + 1):
    for d in range(22, D + 1):
        d10 = d // 10
        d1 = d % 10
        if d10 >= 2 and d1 >= 2 and d1 * d10 == m:
            count += 1

print(count)

Measured memory_bytes: 39408
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.InputMismatchException;
import java.util.List;
import java.util.Set;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		TaskX solver = new TaskX();
		solver.solve(1, in, out);
		out.close();
	}

	static int INF = 1 << 29;
	static int modP = 1000000007;

	static class TaskX {
		public void solve(int testNumber, InputReader in, PrintWriter out) {

			int n = in.nextInt();
			int t = in.nextInt();
			int[] a = in.nextIntArray(n);

			int min = Integer.MAX_VALUE;
			int max = -1;
			int profit = 0;
			Set<Long> set = new HashSet<>();
			List<P> list = new ArrayList<>();
			int maxProfit = 0;
			for (int i = 0; i < n; i++) {
				if (a[i] < min) {
					min = a[i];
					max = a[i];
				}
				if (max < a[i]) {
					max = a[i];
				}
				maxProfit = Math.max(maxProfit, max-min);
			}

			min = Integer.MAX_VALUE;
			max = -1;
			for (int i = 0; i < n; i++) {
				if (a[i] < min) {
					min = a[i];
					max = a[i];
				}
				if (max < a[i]) {
					max = a[i];
				}
				if (max-min == maxProfit) {
					set.add((long)min<<32 | max);
					list.add(new P(min, max));
				}
			}

			out.println(set.size());

		}
	}
	static class P {
		int a, b;
		P (int a, int b) {
			this.a = a;
			this.b = b;
		}
	}

	static class InputReader {
		BufferedReader in;
		StringTokenizer tok;

		public String nextString() {
			while (!tok.hasMoreTokens()) {
				try {
					tok = new StringTokenizer(in.readLine(), " ");
				} catch (IOException e) {
					throw new InputMismatchException();
				}
			}
			return tok.nextToken();
		}

		public int nextInt() {
			return Integer.parseInt(nextString());
		}

		public long nextLong() {
			return Long.parseLong(nextString());
		}

		public double nextDouble() {
			return Double.parseDouble(nextString());
		}

		public int[] nextIntArray(int n) {
			int[] res = new int[n];
			for (int i = 0; i < n; i++) {
				res[i] = nextInt();
			}
			return res;
		}

		public long[] nextLongArray(int n) {
			long[] res = new long[n];
			for (int i = 0; i < n; i++) {
				res[i] = nextLong();
			}
			return res;
		}

		public InputReader(InputStream inputStream) {
			in = new BufferedReader(new InputStreamReader(inputStream));
			tok = new StringTokenizer("");
		}

	}

}


Measured memory_bytes: 44668
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, n) for(int i = 0; i < n; i++)
#define all(a) a.begin(), a.end()
#define P pair<int, int>
#define F first
//#define S second
#define mod 1000000007
#define MOD 998244353
#define INF 40000000000000000
int dx8[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
int dy8[8] = {1, 1, 1, 0, -1, -1, -1, 0};
int dx4[4] = {-1, 0, 1, 0};
int dy4[4] = {0, -1, 0, 1};
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;
}
signed main() {
    int N;
    cin >> N;
    vector<int> V(N, 0);
    rep(i, N - 1) {
        int a;
        cin >> a;
        V[a - 1]++;
    }
    rep(i, N) cout << V[i] << endl;
}


Measured memory_bytes: 4840
#include<bits/stdc++.h>
#define eps 1e-9
#define MOD1 998244353
#define MOD2 1000000007
#define INV_10 299473306
#define INF 1000000001
#define PI 3.14159265358979323846
using namespace std;
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n, nb=0;
	cin >> n;
	long long d, x, y, cu;
	cin >> d;
	d=d*d;
	for(int i = 0; i < n; i++)
	{
		cin >> x >> y;
		x=x*x;
		y=y*y;
		cu=x+y;
		if(cu <= d)
			nb++;
	}
	cout << nb << '\n';
}

Measured memory_bytes: 3652
#include <array>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <deque>
#include <complex>
#include <stack>
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <ctime>
#include <iterator>
#include <bitset>
#include <numeric>
#include <list>
#include <iomanip>
using namespace std;


typedef long long LL;
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;

typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;

#define VV(T) vector<vector< T > >

template <class T>
void initvv(vector<vector<T> > &v, int a, int b, const T &t = T()){
	v.assign(a, vector<T>(b, t));
}

template <class F, class T>
void convert(const F &f, T &t){
	stringstream ss;
	ss << f;
	ss >> t;
}


#define REP(i,n) for(int i=0;i<int(n);++i)
#define ALL(v) (v).begin(),(v).end()
#define RALL(v) (v).rbegin(),(v).rend()
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define PB push


#define MOD 1000000007LL
#define EPS 1e-10

struct UnionFind
{
  vector< int > data;

  UnionFind(int sz)
  {
    data.assign(sz, -1);
  }

  bool unite(int x, int y)
  {
    x = find(x), y = find(y);
    if(x == y) return(false);
    if(data[x] > data[y]) swap(x, y);
    data[x] += data[y];
    data[y] = x;
    return(true);
  }

  int find(int k)
  {
    if(data[k] < 0) return(k);
    return(data[k] = find(data[k]));
  }

  int size(int k)
  {
    return(-data[find(k)]);
  }

  bool same(int x, int y)
  {
      return find(x) == find(y);
  }
};

int main()
{
    int N;
    cin >> N;
    vector<pair<int, int> > red(N);
    vector<pair<int, int> > blue(N);
    REP(i, N) cin >> red[i].first >> red[i].second;
    REP(i, N) cin >> blue[i].first >> blue[i].second;
    sort(blue.begin(), blue.end());
    int ans = 0;
    REP(b, N)
    {
        int maxY = -1;
        int matchR = -1;
        REP(r, red.size())
        {
            if (red[r].first < blue[b].first && red[r].second < blue[b].second)
            {
                if (red[r].second > maxY)
                {
                    maxY = red[r].second;
                    matchR = r;
                }
            }
        }
        if (matchR >= 0)
        {
            red.erase(red.begin() + matchR);
            ++ans;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

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

  string t = "LRUD";
  for(int i = 0; i < s.size(); i++){
    if((i+1) % 2 == 0){
      if(s[i] == 'R'){
        cout << "No" << endl;
        return 0;
      }
    }
    else if(s[i] == 'L'){
      cout << "No" << endl;
      return 0;
    }
  }

  cout << "Yes" << endl;

  return 0;
}

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

int main(){
  int n, m, b[100], a[100][100], c[100] = {};
  cin >> n >> m;
  for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++){
      cin >> a[i][j];
    }
  }
  for(int i = 0; i < m; i++){
    cin >> b[i];
  }
  for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++){
      c[i] += a[i][j] * b[j];
    }
  }
  for(int i = 0; i < n; i++){
    cout << c[i] << endl;
  }
}



Measured memory_bytes: 3124
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAX 10000
#define NIL -1

struct Node {  int parent,left,right; };

struct Node T[MAX];
int n,D[MAX],H[MAX];

void setDepth(int u,int d){
  if(u == NIL) return;
  D[u] = d;
  setDepth(T[u].left, d + 1);
  setDepth(T[u].right,d + 1);
}

int setHeight(int u){
  int h1 = 0,h2=0;
  if(T[u].left != NIL)
  h1 = setHeight(T[u].left) + 1;
  if(T[u].right != NIL)
  h2 = setHeight(T[u].right) + 1;
  return H[u] = (h1 > h2 ? h1 : h2);
}


int getSibling(int u){
  if(T[u].parent == NIL) return NIL;
  if(T[T[u].parent].left !=u && T[T[u].parent].left != NIL)
  return T[T[u].parent].left;
  if(T[T[u].parent].right !=u && T[T[u].parent].right != NIL)
  return T[T[u].parent].right;
  return NIL;
}

void print(int u){
  printf("node %d: ",u);
  printf("parent = %d, ",T[u].parent);
  printf("sibling = %d, ",getSibling(u));
  int deg = 0;
  if(T[u].left !=NIL) deg++;
  if(T[u].right !=NIL) deg++;
  printf("degree = %d, ",deg);
  printf("depth = %d, ",D[u]);
  printf("height = %d, ",H[u]);

  if(T[u].parent == NIL){
    printf("root\n");
  }else if(T[u].left == NIL && T[u].right == NIL){
    printf("leaf\n");
  }else{
    printf("internal node\n");
  }
}

int main(){
  int v,l,r,root = 0;
  scanf("%d",&n);

  for(int i = 0;i<n;i++) T[i].parent = NIL;

  for(int i = 0;i < n;i++){
    scanf("%d %d %d",&v,&l,&r);
    T[v].left = l;
    T[v].right = r;
    if(l !=NIL) T[l].parent = v;
    if(r !=NIL) T[r].parent = v;
  }

  for(int i = 0;i<n;i++)if(T[i].parent == NIL) root = i;

  setDepth(root,0);
  setHeight(root);

  for(int i = 0;i < n;i++) print(i);

  return 0;
}



Measured memory_bytes: 2148
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
const int INF = (1<<30)-1;
const long long LINF = (1LL<<62)-1;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll n, k;
  cin >> n >> k;
  vector<ll> a(n);
  rep(i, n) cin >> a[i];
  sort(a.begin(), a.end());
  ll l = -LINF, r = LINF;
  while (r-l > 1) {
    ll mid = (l+r)/2, cnt = 0;
    rep(i, n) {
      if (a[i] < 0)
        cnt += a.end()-upper_bound(a.begin(), a.end(), (long double)mid/a[i]);
      else if (a[i] > 0)
        cnt += lower_bound(a.begin(), a.end(), (long double)mid/a[i])-a.begin();
      else if (mid > 0)
        cnt += n;
      if (a[i]*a[i] < mid)
        cnt--;
    }
    cnt /= 2;
    if (cnt < k)
      l = mid;
    else
      r = mid;
  }
  cout << l << endl;
  return 0;
}

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

using namespace std;

int main()
{
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; i++)
    cin >> a[i];
  int cnt = 0;
  for (int i = 0; i < n; i++)
    if (a[i] % 2 == 1)
    {
      cout << "first" << endl;
      return 0;
    }
  cout << "second" << endl;

  return 0;
}


Measured memory_bytes: 640
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <tuple>
#include <vector>

using namespace std;
typedef long long ll;

#define rep(i, n) for (ll i = 0; i < (n); i++)
#define reps(i, f, n) for (ll i = (f); i < (n); i++)
#define repr(i, n) for (ll i = n; i >= 0; i--)
#define repv(v) for (auto it = (v).begin(); it != (v).end(); it++)
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
#define pb push_back
#define INIT    \
    cin.tie(0); \
    ios::sync_with_stdio(false);

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

ll const INF = 1LL << 60;
ll const MOD = 1000000007;

int main() {
    INIT;

    string S, T;
    cin >> S >> T;
    ll cnt = 0;
    rep(i, SZ(S)) {
        if (S[i] == T[i]) cnt++;
    }

    cout << cnt << endl;

    return 0;
}

Measured memory_bytes: 3640
/*input

*/
#include <bits/stdc++.h>
#define up(i,a,b) for(int (i) = (a);(i)<=(b);++(i))
#define down(i,b,a) for(int (i) = (b);i>=(a);--i)
#define debug(x) cerr << (x) << '\n';
#define bits(x,i) ((x >> i) & 1)
#define mid ((l+r)/2)
#define pr pair<int,int>
using namespace std;
const int N = 200005;
const int INF = 2e9;
int a[N];
int ans[N];
vector< vector<int> > G;
int n;
vector<int> dp;
void dfs(int u, int par){
	int pos = lower_bound(dp.begin(), dp.end(), a[u]) - dp.begin();
	int roll = dp[pos];
	dp[pos] = a[u];
	ans[u] = lower_bound(dp.begin(), dp.end(), INF) - dp.begin() - 1;
	for (auto v : G[u]){
		if (v == par) continue;
		dfs(v, u);
	}
	dp[pos] = roll;
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	G.assign(n+1, vector<int>());
	dp.assign(n+1, INF); dp[0] = -INF;
	up(i,1,n) cin >> a[i];
	up(i,1,n-1){
		int u,v; cin >> u >> v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs(1,1);
	up(i,1,n) cout << ans[i] << '\n';
}

Measured memory_bytes: 27904
def solve():
    import sys
    file_input = sys.stdin
    
    N, M, Q = map(int, file_input.readline().split())
    
    from collections import deque
    student = deque(range(N))
    exemption = [1] * N
    for a in map(int, file_input.readline().split()):
        if a % 2:
            student.rotate(a)
        else:
            student.rotate(-a)
        s = student.popleft()
        exemption[s] = 0
    
    question = map(int, file_input.readline().split())
    print(*map(lambda x: exemption[x], question), sep = '\n')

solve()


Measured memory_bytes: 29296
h,w=map(int,input().split())
a=[]

from collections import deque
fifo = deque()
a.append(["@"]*(w+2))
for i in range(h):
    s=input()
    temp=["@"]
    for j in range(w):
        if s[j]=="#":
            fifo.append([i+1,j+1])
            temp.append(0)
        else:
            temp.append(s[j])
    temp.append("@")
    a.append(temp)
a.append(["@"]*(w+2))

result=0
#print(a)

while len(fifo)>0:
    temp=fifo.popleft()
    y,x=temp[0],temp[1]

    for item in [[0,1],[1,0],[-1,0],[0,-1]]:
        #print(y+item[0],x+item[1])
        if a[y+item[0]][x+item[1]]==".":
            fifo.append([y+item[0],x+item[1]])
            a[y+item[0]][x+item[1]]=a[y][x]+1
            result=max(result,a[y+item[0]][x+item[1]])
    
print(result)

    



Measured memory_bytes: 166916
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cassert>
#include <iostream>
#include <cctype>
#include <sstream>
#include <string>
#include <list>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <map>
#include <utility>
#include <numeric>
#include <algorithm>
#include <iterator>
#include <bitset>
#include <complex>
#include <fstream>
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
typedef vector<int> vint;
typedef pair<int, int> pint;
#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
template<class T> T RoundOff(T a){ return int(a+.5-(a<0)); }
template<class T, class C> void chmax(T& a, C b){ if(a < b) a = b; }
template<class T, class C> void chmin(T& a, C b){ if(b < a) a = b; }
template<class T, class C> pair<T, C> mp(T a, C b){ return make_pair(a, b); }

const int INF = 1 << 30;
const int hardCost = 100000;
const int dx[] = {1, 0, 0, -1};
const int dy[] = {0, 1, -1, 0};
struct P{ int x, y; P(int x, int y) : x(x), y(y) {} };

int main()
{
    for(int n, m; cin >> n >> m && (n || m); )
	{
		P c(0, 0);
		vector<string> field(m);
		vector<vint> cost(n, vint(m, INF));
		
		rep(i, m)
		{
			cin >> field[i];
			
			int pos = field[i].find("&");
			if(pos != string::npos)
			{
				c.x = pos;
				c.y = i;
			}
		}
		
		queue<P> que;
		cost[c.x][c.y] = 0;
		for(que.push(c); !que.empty(); que.pop())
		{
			P cur = que.front();
			
			rep(i, 4)
			{
				P nxt(cur.x + dx[i], cur.y + dy[i]);
				
				if(0 <= nxt.x && nxt.x < n && 0 <= nxt.y && nxt.y < m)
				{
					int ct = cost[cur.x][cur.y] + (field[nxt.y][nxt.x] == '#' && field[cur.y][cur.x] != '#');
					
					if(ct < cost[nxt.x][nxt.y])
					{
						cost[nxt.x][nxt.y] = ct;
						que.push(nxt);
					}
				}
			}
		}
		
		int res = 1 << 30;
		
		rep(i, n) chmin(res, min(cost[i][0], cost[i][m-1]));
		rep(i, m) chmin(res, min(cost[0][i], cost[n-1][i]));
		
		
		cout << res << endl;
	}
}

Measured memory_bytes: 0
H, W = map(int, input().split())

change_costs = [list(map(int, input().split())) for _ in range(10)]
# change_costsは9*9のコスト


for k in range(10):
    for i in range(10):
        for j in range(10):
            # print(k, i, j)
            change_costs[i][j] = min(change_costs[i][j], change_costs[i][k] + change_costs[k][j])
# print(change_costs)
# nums = []
cost = 0
for _ in range(H):
    nums = list(map(int, input().split()))
    for num in nums:
        if num == -1:
            cost += 0
        else:
            cost += change_costs[num][1]
    # nums.append(list(map(int, input().split())))
print(cost)


Measured memory_bytes: 40556
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
#define  st first
#define  nd second
#define int long long

void debug_out() { cerr << endl; }
template<class T> ostream& prnt(ostream& out, T v) { out << v.size() << '\n'; for(auto e : v) out << e << ' '; return out;}
template<class T> ostream& operator<<(ostream& out, vector <T> v) { return prnt(out, v); }
template<class T> ostream& operator<<(ostream& out, set <T> v) { return prnt(out, v); }
template<class T1, class T2> ostream& operator<<(ostream& out, map <T1, T2> v) { return prnt(out, v); }
template<class T1, class T2> ostream& operator<<(ostream& out, pair<T1, T2> p) { return out << '(' << p.st << ' ' << p.nd << ')'; }
template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << " " << H; debug_out(T...);}

#define dbg(...) cerr << #__VA_ARGS__ << " ->", debug_out(__VA_ARGS__)
#define dbg_v(x, n) do{cerr<<#x"[]: ";for(int _=0;_<n;++_)cerr<<x[_]<<" ";cerr<<'\n';}while(0)
#define dbg_ok cerr<<"OK!\n"

template <typename T> using ordered_set =  tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef cc_hash_table<int, int, hash<int > > ht;
#define TIMES_PER_SEC (CLOCKS_PER_SEC)


double get_absolute_time()
{
	return (double)clock()/TIMES_PER_SEC;
}
double starttime_acrush;
void starttime()
{
	starttime_acrush=get_absolute_time();
}
double gettime()
{
	return get_absolute_time()-starttime_acrush;
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

#define M   1000000007
const int N = 10001;  // limit for array size

int32_t main(){

  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  int a  , b ;
  cin >> a >> b ;
  if(a<b){
    for ( int i =0 ; i<b ; i++)
        cout <<a;
  }
  else{
    for ( int i =0 ; i<a ; i++)
        cout <<b;
  }
//  cout << ans ;


}



Measured memory_bytes: 256