akhauriyash/Code-Regression huggingface dataset:
import bisect
import heapq 

Q=int(input())

que=list(map(int,input().split()))
b=que[2]
l,r=[-que[1]],[que[1]]
heapq.heapify(l)
heapq.heapify(r)
a=0
tmp=que[1]
j=1
for i in range(Q-1):
    que=list(map(int,input().split()))
    if que[0]==1:
        j+=1
        b+=que[2]
        q1=que[1]
        if j%2==0:
            if q1<-l[0]:
                heapq.heappushpop(l,-q1)
            else:
                heapq.heappushpop(r,q1)

        else:
            if q1<-l[0]:
                heapq.heappush(l,-q1)
                heapq.heappush(r,-l[0])
            else:
                heapq.heappush(r,q1)
                heapq.heappush(l,-r[0])
        

        if -l[0]!=r[0]: a+=abs(tmp-q1)
        else: a+=abs(tmp-q1)-abs(-l[0]-tmp)
        tmp=-l[0]

    elif que[0]==2:
        print(tmp,a+b)

Measured memory_bytes: 11168
#include <algorithm>
#include <cstdint>
#include <iostream>
#include <vector>

using namespace std;

int main() {
  int x, y, z, k;
  cin >> x >> y >> z >> k;
  vector<int64_t> a(x);
  vector<int64_t> b(y);
  vector<int64_t> c(z);
  for (int i = 0; i < x; i++) cin >> a[i];
  for (int i = 0; i < y; i++) cin >> b[i];
  for (int i = 0; i < z; i++) cin >> c[i];

  sort(a.begin(), a.end(), greater<int64_t>());
  sort(b.begin(), b.end(), greater<int64_t>());
  sort(c.begin(), c.end(), greater<int64_t>());

  vector<int64_t> abc;  // a + b + c

  for (int i = 0; i < x; i++) {
    for (int j = 0; j < y; j++) {
      if ((i + 1) * (j + 1) > k) break;
      for (int m = 0; m < z; m++) {
        if ((i + 1) * (j + 1) * (m + 1) > k) break;

        abc.push_back(a[i] + b[j] + c[m]);
      }
    }
  }
  sort(abc.begin(), abc.end(), greater<int64_t>());
  for (int i = 0; i < k; i++) {
    cout << abc[i] << endl;
  }

  return 0;
}


Measured memory_bytes: 1404
#include <string>
#include <vector>
#include <map>
#include <iostream>
#define ll long long
using namespace std;

int main() {
    int N,K;
    cin>>N>>K;
    // 1,3,5...,2*k-1
    if (2*K-1 <= N) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }
}

Measured memory_bytes: 256
import sys

N,M=map(int, sys.stdin.readline().split())
A=map(int, sys.stdin.readline().split())
A.sort()

B=[ map(int, sys.stdin.readline().split()) for _ in range(M)] 
B.sort(key=lambda x: x[1], reverse=True)

i=0

for b,c in B:
	for i in range(i,N):
		if A[i]<c and 0<b:
			A[i]=c
			b-=1
		if b==0:
			break
	i+=1

print sum(A)


Measured memory_bytes: 53476
#include <stdio.h>

int main(void)
{
	int X;
	int Y;
	int s;
	int i;
	
	scanf("%d", &X);
	scanf("%d", &Y);
	s = 0;
	
	for (i = 0; i < 2; i++){
		
		if (X < Y){
			s += Y--;
		}
		else {
			s += X--;
		}
	}
	
	printf("%d\n", s);
	
	return (0);
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#include <stdio.h>
int n,m,j,k,i;
int cou = 0;
int a[10000],b[10000],c[10000] = {0,1};

int main()
{
    while(1)
    {
        int c[10000] = {0,1};
        scanf("%d %d",&n,&m);
        if(n == 0 && m == 0)break;
        for(i = 0; i < m; i++)
        {
            scanf("%d %d",&a[i],&b[i]);
        }
        for( j = 0; j < m; j++)
        {
            if(a[j] == 1)
            {
                cou++;
                c[b[j]] = 1;
            }
        }
        for(k = 0; k < m; k++)
        {
            if(c[a[k]] == 1 && c[b[k]] == 0)
            {
                cou++;
                c[b[k]] = 2;
            }
            if(c[a[k]] == 0 && c[b[k]] == 1)
            {
                cou++;
                c[a[k]] = 2;
            }
        }
        printf("%d\n",cou);
        cou = 0;
    }
    return 0;

}

Measured memory_bytes: 1316
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] l = new int[n];		
		int[] r = new int[n];
		for (int i=0; i<n; i++){
			l[i] = sc.nextInt();
			r[i] = sc.nextInt();
		}
		int sum = 0;
		for (int i=0; i<n; i++){
			sum += r[i] - l[i] + 1;
		}
		System.out.println(sum);
	}
}

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

int main(){
  int n;
  cin>>n;
  int mini=1e8;
  for(int i=0;i<n;i++){
      int a;
      cin>>a;
      int cnt=0;
      while(a%2==0){
          cnt++;
          a/=2;
      }
      mini=min(mini,cnt);
    }
    cout<<mini<<endl;
}

Measured memory_bytes: 3628
n,m = map(int, input().split())
# x,y,z=[],[],[]
xyz = []
for _ in range(n):
    a,b,c = map(int, input().split())
    xyz.append((a,b,c))

ans = 0
for i in range(8):
    a,b,c = (-1)**(i&4 > 0), (-1)**(i&2 > 0), (-1)**(i&1 > 0)
    xyz.sort(key=lambda x:a*x[0] + b*x[1] + c*x[2], reverse=True)
    x,y,z=0,0,0
    for i in range(m):
        a,b,c = xyz[i]
        x += a
        y += b
        z += c
    tmp = abs(x) + abs(y) + abs(z)
    #print(tmp, ans)
    if ans < tmp:
        ans = tmp
print(ans)


Measured memory_bytes: 39792
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<n; i++)
#define cans cout << ans << endl
#define cyes cout << "Yes" << endl
#define cno cout << "No" << endl
typedef long long ll;


int main(){
    int n,m;
    cin >> n >> m;
    vector<int> l(m),r(m);
    rep(i,m) cin >> l[i] >> r[i];
    int lim=0,rim=100001;
    rep(i,m){
        lim = max(l[i],lim);
        rim = min(r[i],rim);
    }
    cout << max(rim-lim+1,0) << endl;
    return 0;
}

Measured memory_bytes: 4012
import java.util.*;
import java.util.Arrays;
public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		
		int c[][] = new int[3][3];

		for(int i= 0;i<3;i++){
			for(int j = 0; j<3; j++){
				c[i][j] = sc.nextInt();
			}
		}
		
		int w = 0;
		
		int a[] = new int[3];
		int b[] = new int[3];

		for(w = 0;w<=100;w++){
	
			a[0] = w;
			b[0] = c[0][0] - a[0];
			b[1] = c[0][1] - a[0];
			b[2] = c[0][2] - a[0];

			for(int i=0;i<3;i++){
				if(b[i] < 0){
					System.out.println("No");
					return;
				}
			}
			
			int aa[][] = new int[3][3];

			for(int i = 1;i<3;i++){
				for(int j=0;j<3;j++){
					aa[i][j] = c[i][j] - b[j];
				}
			}

			if(aa[1][0] != aa[1][1] || aa[1][0] != aa[1][2] || aa[2][0] != aa[2][1] || aa[2][0] != aa[2][2]){
				continue;
			}
			
		System.out.println("Yes");
		return;
		}
			System.out.println("No");	
	}
}




Measured memory_bytes: 22996
import sys
input = sys.stdin.readline
N, A, B = [int(x) for x in input().split()]
a = max(A, B) - 1
b = N - min(A, B)
c = 10 ** 19
d = 10 ** 19
e = 10 ** 19
if abs(A - B) % 2 == 0:
    c = abs(A - B) // 2
else:
    d = min(A, B) - 1 + 1 + (abs(A - B) - 1) // 2
    e = N - max(A, B) + 1 + (abs(A - B) - 1) // 2
print(min(a, b, c, d, e))  

Measured memory_bytes: 3064
#include <iostream>
#include <string>
#include <sstream>
#include <iomanip>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <queue>
#include <cmath>

using namespace std;
using ll = long long;

void ABC060C()
{
	int N;
	ll T;
	cin >> N >> T;
	vector<ll> t(N);
	for (auto& x : t)
		cin >> x;

	ll start = 0;
	ll end = 0;
	ll sum = 0;
	for (const auto& x : t)
	{
		ll start1 = x;
		ll end1 = x + T;

		if (start1 > end)
		{
			sum += end - start;
			start = start1;
		}
		end = end1;
	}
	sum += end - start;
	cout << sum << endl;
}
int main()
{
	ABC060C();
	return 0;
}


Measured memory_bytes: 1792
"""
dp[i][j] => 下からi桁目まで見る。あまりがjになるような数。
"""
mod = 10**9 +7
S = input()
S = S[::-1]
N = len(S)
dp = [[0]*13 for _ in range(N+1)]
dp[0][0] = 1
by = 1
for i in range(N):
    s = S[i]
    for j in range(13):
        if s == "?":
            for k in range(10):
                rest = k*by%13
                dp[i+1][(j+rest)%13] += dp[i][j]
                dp[i+1][(j+rest)%13] %= mod
        else:
            rest = int(s)*by%13
            dp[i+1][(j+rest)%13] += dp[i][j]
            dp[i+1][(j+rest)%13] %= mod
    by = by*10%13
print(dp[-1][5])

Measured memory_bytes: 96108
#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 all(v) v.begin(),v.end()
typedef long long ll;

int main(){
    string S;
    cin >> S;
    int len = S.size();
    int count_0 = 0;
    int count_1 = 0;
    rep(i,len){
        if (S[i] == '0'){
            count_0++;
        }
        else if (S[i] == '1'){
            count_1++;
        }
    }
    cout << 2 * min(count_0,count_1) << endl;
}


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

struct node{
	int a;int b;
}q[100005];

inline
bool cmp(node a,node b){
	return (a.a==b.a)?a.b<b.b:a.a<b.a;
}

int n,m;
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i){
		scanf("%d%d",&q[i].a,&q[i].b);
		if(q[i].a>q[i].b)swap(q[i].a,q[i].b);
	}
	sort(q+1,q+m+1,cmp);
	int now=q[1].b;
	int ans=1;
	for(int  i=2;i<=m;++i){
		if(q[i].a<now){
			if(q[i].b<now)now=q[i].b;
			continue;
		}
		now=q[i].b;
		++ans;
	}
	cout<<ans;
	return 0;
}

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

int main() {

    int x1, x2, x3, x4, x5;
    cin >> x1 >> x2 >> x3 >> x4 >> x5;

    if (x1 == 0) cout << 1 << endl;
    else if (x2 == 0) cout << 2 << endl;
    else if (x3 == 0) cout << 3 << endl;
    else if (x4 == 0) cout << 4 << endl;
    else if (x5 == 0) cout << 5 << endl;

    return 0;
}

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


#define _USE_MATH_DEFINES_
#define ll long long
#define ld long double
#define Accepted 0
#define pb push_back
#define mp make_pair
#define sz(x) (int)(x.size())
#define every(x) x.begin(),x.end()
#define F first
#define S second
#define For(i,x,y)  for (int i = x; i <= y; i ++) 
#define FOr(i,x,y)  for (int i = x; i >= y; i --)
#define SpeedForce ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
// ROAD to...                                                                                                                                                                                                                Red

using namespace std;
inline double Time() {return (clock() * 1.0) / CLOCKS_PER_SEC; } 
inline bool isvowel (char c) {
	c = tolower(c);
    if (c == 'a' || c == 'e' || c == 'i' || c == 'y' || c == 'o' || c == 'u') return 1;
    return 0;
}

const double eps = 0.000001;
const ld pi = acos(-1);
const int maxn = 1e7 + 9;
const int mod = 1e9 + 7;
const ll MOD = 1e18 + 9;
const ll INF = 1e18 + 123;
const int inf = 2e9 + 11;
const int mxn = 1e6 + 9;
const int N = 6e5 + 123;                                          
const int M = 22;
const int pri = 997;
const int Magic = 2101;

const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};
 
int n, m, k;
int cnt[N];
string s;
int a[N];
vector < int > g[N];
int u[N];
int ans, res;
int cur;

int main () {
	SpeedForce;     
    cin >> n >> m;
    cin >> s;
    s = '#' + s;
    for (int i = 1; i <= n; i ++) {
    	a[i] = a[i - 1];
    	if (s[i] == 'C' && s[i - 1] == 'A') a[i] ++;
    }
    for (int i = 1; i <= m; i ++) {
    	int l, r;
    	cin >> l >> r;
    	cout << a[r] - a[l] << '\n';
    }
    return Accepted;
}

// B...a D....

Measured memory_bytes: 19436
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll mod = 1000000007;
const ll INF = (ll)1000000007 * 1000000007;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef long double ld;
typedef complex<ld> Point;
const ld eps = 1e-11;
const ld pi = acos(-1.0);
typedef pair<ll, ll> LP;
typedef pair<ld, ld> LDP;
int price[20][20001];
struct edge { int to, cost; };
int wfd[20][100][100];
vector<edge> G[100];
int d[100];
void init() {
	rep(i, 100) {
		G[i].clear();
	}
	rep(i, 20) {
		rep(j, 100) {
			rep(k, 100) {
				if (j != k) {
					wfd[i][j][k] = (int)mod;
				}
				else wfd[i][j][k] = 0;
			}
		}
	}
	fill(d, d + 100, (int)mod);
}
int main() {
	int n, m, c, s, g;
	queue<int> outt;
	while (cin >> n >> m >> c >> s >> g,n) {
		init();
		s--; g--;
		rep(i, m) {
			int u, v, dd, cc; cin >> u >> v >> dd >> cc; u--; v--; cc--;
			wfd[cc][u][v] = wfd[cc][v][u] = min(wfd[cc][u][v], dd);
		}
		int l[20];
		rep(i, c) {
			cin >> l[i];
		}
		rep(i, c) {
		    queue<int> q,r;
			rep(j, l[i]-1) {
				int qq; cin >> qq; q.push(qq);
			}
			rep(j, l[i]) {
				int rr; cin >> rr; r.push(rr);
			}
			price[i][0] = 0;
			rep1(j, 20000) {
				price[i][j] = price[i][j - 1] + r.front();
				if (!q.empty()&&j == q.front()) {
					q.pop(); r.pop();
				}
			}
			rep(z, 100) {
				rep(x, 100) {
					rep(y, 100) {
						wfd[i][x][y] = min(wfd[i][x][y], wfd[i][x][z] + wfd[i][z][y]);
					}
				}
			}
			rep(x, 100) {
				rep(y, 100) {
					if (wfd[i][x][y] < (int)mod) {
						G[x].push_back({ y,price[i][wfd[i][x][y]] });
					}
				}
			}
		}
		priority_queue<P, vector<P>, greater<P>> que;
		que.push({ 0,s });
		while (!que.empty()) {
			P x = que.top(); que.pop();
			int id = x.second;
			if (x.first > d[id])continue;
			int len = G[id].size();
			rep(j, len) {
				int v = G[id][j].to;
				int cc = G[id][j].cost;
				if(d[v] > x.first + cc) {
					d[v] = x.first + cc;
					que.push({ d[v],v });
				}
			}
		}
		if (d[g] == (int)mod)d[g] = -1;
		outt.push(d[g]);
	}
	while (!outt.empty()) {
		cout << outt.front() << endl; outt.pop();
	}
	return 0;
}


Measured memory_bytes: 7028
#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;

int main(void){
    double r;
    cin>>r;
    
    double pi=acos(-1);
    cout<<fixed<<setprecision(6);
    double area=r*r*pi;
    double cir=(r+r)*pi;
    cout<<area<<" "<<cir<<endl;
    
    
}


Measured memory_bytes: 3256
#include <bits/stdc++.h>
#define ll long long int
#define F first
#define S second
const ll mod = 1e9 + 7;
const ll INF = 10000000000000;
#define pb push_back
#define deb(x) cout << '>' << #x << ':' << x << endl;
#define fastio ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
int main()
{
    fastio;
    string s;
    ll n=0,a=0,b=0;
    cin>>n>>a>>b;
    ll q=n/(a+b);
    ll r=n%(a+b);
    ll ans=0;
    ans+=q*a;
    ans+=min(r,a);
    cout<<ans;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
struct Node{
	int parent,left,right;
} T[100000];

int getDepth(int u){
	return (T[u].parent!=-1)?(1+getDepth(T[u].parent)):0;
}
int print(int u){
	u = T[u].left;
	printf("[");
	while(u!=-1){
		printf("%d",u);
		u = T[u].right;
		if(u!=-1) printf(", ");
	}
	printf("]\n");
}
int main()
{
	int n,du,in; cin>>n;
	for(int i=0;i<n;i++)
		T[i].parent = T[i].left = T[i].right = -1;
	for(int i=0;i<n;i++){
		scanf("%d%d",&in,&du);
		int son,bro;
		for(int j=0;j<du;j++){
			scanf("%d",&son);
			if(j==0) T[in].left = son;
			else T[bro].right = son;
			T[son].parent = in;
			bro = son;
		}
	}
	int root;
	for(int i=0;i<n;i++)
		if(T[i].parent==0) root = i,i = n;
	for(int i=0;i<n;i++){
		printf("node %d: parent = %d, ",i,T[i].parent);
		printf("depth = %d, ",getDepth(i));
		if(T[i].parent==-1) printf("root, ");
		else if(T[i].left==-1) printf("leaf, ");
		else printf("internal node, ");
		print(i);
	}
	return 0;
}



Measured memory_bytes: 4300
#include<bits/stdc++.h>
using namespace std;
#define ALL(obj) (obj).begin(), (obj).end()
#define REP(i, n) for(int i = 0;i < (n);++i)

#define endl '\n'
#define pb push_back
#define mp make_pair
#define MOD 1000000007LL
#define INF 2000000000
#define PI 3.1415926

const int dx[]={1,0,-1,0}, dy[]={0,-1,0,1};
const int dx_8[]={1,1,0,-1,-1,-1,0,1}, dy_8[]={0,-1,-1,-1,0,1,1,1};

typedef long long ll;

template <typename T> inline T GCD(T a,T b){T c;while(b!=0){c=a%b;a=b;b=c;}return a;}
template <typename T> inline T LCM(T a,T b){T c=GCD(a,b);a/=c;return a*b;}
template <typename T> inline T nCr(T a,T b){T i,r=1;for(i=1;i<=b;i++){r*=(a+1-i);r/=i;}return r;}
template <typename T> inline T nHr(T a,T b){return nCr(a+b-1,b);}
template <typename T> inline T POW(T a,T b){int i,r=1;for(i=1;i<=b;i++){r*=a;}return r;}

signed main(void){
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	string s; cin >> s;
	int a=0, b=0;
	REP(i, s.size()){
		if(s[i]=='0') a++;
		else b++;
	}
	cout << min(a, b)*2 << endl;

	return 0;
}

Measured memory_bytes: 512
# /usr/bin/python3
# -*- coding: utf-8 -*-
from queue import Queue
from queue import LifoQueue as Stack
from math import sqrt
from fractions import gcd
from itertools import permutations, combinations

def lcm(a, b):
    return (a*b) // gcd(a,b)

def intinput():
    return int(input())

def mulinputs():
    return map(int,input().split())

def lineinputs(func=intinput):
    datas = []
    while True:
        try:
            datas.append(func())
        except EOFError:
            break
    return datas



N, K = mulinputs()
Hs = list(mulinputs())


Hs.sort(reverse=True)
Hs = Hs[K:]

# 出力
print(sum(Hs))




Measured memory_bytes: 27516
#include<iostream>

int dp[100001];
int h[100001];
int func(int a) {
	if (dp[a] != -1) {
		return dp[a];
	}
	if (func(a-1)+abs(h[a]-h[a-1]) < func(a-2)+abs(h[a]-h[a-2])) {
		return dp[a] = func(a - 1) + abs(h[a] - h[a - 1]);
	}
	else {
		return dp[a] = func(a - 2) + abs(h[a] - h[a - 2]);
	}
}
int main() {
	int n;
	std::cin >> n;
	for (int i = 0; i <= n; i++) {
		dp[i] = -1;
	};
	for (int i = 1; i <= n; i++) {
		std::cin >> h[i];
	}
	dp[1] = 0;
	dp[2] = abs(h[2] - h[1]);
	std::cout << func(n) << std::endl;
} 


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

int main() {
  int n;
  cin >> n;
  int a[n + 1];
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  int cnt = 0;
  for (int i = 1; i < n; i++) {
    if (a[i] == i) {
      swap(a[i], a[i + 1]);
      cnt++;
    }
  }
  if (n == a[n]) {
    swap(a[n], a[n - 1]);
    cnt++;
  }
  cout << cnt << endl;
  return 0;
}


Measured memory_bytes: 640
// AOJ ALDS1_8_B Binary Search Tree II
// 2018.5.1 bal4u

#include <stdio.h>

#if 1
#define gc() getchar_unlocked()
#define pc(c) putchar_unlocked(c)
#else
#define gc() getchar()
#define pc(c) putchar(c)
#endif

int in()
{
	int n = 0, c = gc();
	if (c == '-') { c = gc();
		do n = 10*n + (c & 0xf), c = gc(); while (c >= '0');
		return -n;
	}
	do n = 10*n + (c & 0xf), c = gc(); while (c >= '0');
	return n;
}

void skip(int k) { while (k--) gc(); }

void out(int n)
{
	int i;
	char ob[20];

	if (!n) { pc('0'); return; }
	if (n < 0) pc('-'), n = -n;
	i = 0; while (n) ob[i++] = n%10 + '0', n/=10;
	while (i--) pc(ob[i]); 
}

void sout(char *s) { while (*s) pc(*s++); }

typedef struct { int key; int parent; int left, right; } BT;
BT bt[500005]; int sz;
int root;

void preorder(int node)
{
	pc(' '), out(bt[node].key);
	if (bt[node].left  > 0) preorder(bt[node].left);
	if (bt[node].right > 0) preorder(bt[node].right);
}

void inorder(int node)
{
	if (bt[node].left  > 0) inorder(bt[node].left);
	pc(' '), out(bt[node].key);
	if (bt[node].right > 0) inorder(bt[node].right);
}

void insert(int z)
{
	int x, y;

	y = 0, x = root;
	while (x) {
		y = x;
		if (bt[z].key < bt[x].key) x = bt[x].left;
		else                       x = bt[x].right;
	}
	bt[z].parent = y;

	if (!y) root = z;
	else if (bt[z].key < bt[y].key) bt[y].left  = z;
	else                            bt[y].right = z;
}

int find(int node, int key)
{
	int t;

	t = key - bt[node].key;
	if (!t) return 1;
	if (t < 0) {
		if (bt[node].left > 0) return find(bt[node].left, key);
	} else {
		if (bt[node].right > 0) return find(bt[node].right, key);
	}
	return 0;
}

int main()
{
	int n, i;
	char op;

	n = in(), root = 0, sz = 1;
	for (i = 0; i < n; i++) {
		op = gc();
		if (op == 'p') {            // print
			skip(5);
			inorder(root), pc('\n');
			preorder(root), pc('\n');
		} else if (op == 'i') {     // insert
			skip(6);
			bt[sz].key = in();
			insert(sz++);
		} else {                    // find
			skip(4);
			sout(find(root, in())? "yes": "no"), pc('\n');
		}
	}
	return 0;
}


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

#define int long long
#define endl "\n"
#define REP(i,a,n) for(int i=a;i<n;++i)
#define REPR(i,a,n) for(int i=a;i>n;--i)
#define RUP(a,b) ((a+b-1)/(b))
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define MOD 1000000007
#define INF LLONG_MAX/2

typedef long long ll;
typedef pair<int,int> Pii;
typedef tuple<int,int,int> Tiii;
typedef vector<int> Vi;
typedef vector<Vi> VVi;
typedef vector<Pii> VPii;
typedef vector<string> Vs;

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;}
template<class T> void YesNo(T a) {cout<<(a?"Yes":"No")<<endl;}
template<class T> void YESNO(T a) {cout<<(a?"YES":"NO")<<endl;}
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a/gcd(a,b)*b;}
void uniq(Vi &v){sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end());}
int ctoi(char c){if(c>='0'&&c<='9'){return c-'0';}return 0;}
bool comp(Pii a,Pii b){
    if(a.second != b.second) return a.second<b.second;
    else return a.first<b.first;
}

void cntfill(Vi x,int n){
    REP(i,0,n){
        if(i==0) x[i]=n;
        else x[i]=x[i-1]+(n-2*i);
    }
}


signed main(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
    int h,w,a,b;
    cin>>h>>w>>a>>b;
    Vs ans(h);
    REP(i,0,h){
        REP(j,0,w){
            if((j<a && i<b) || (j>=a && i>=b)) ans[i] += "0";
            else ans[i] += "1";
        }
    }
    REP(i,0,h) cout<<ans[i]<<endl;
    return 0;
}

Measured memory_bytes: 2304
#include <bits/stdc++.h>
#define gcd(m,n) __gcd(m,n)
#define lcm(m,n) m*(n/gcd(m,n))
#define fast std::ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pi acos(-1.0)
#define endl '\n'
#define MOD 1000000007
#define ull unsigned long long
#define ll long long
#define ld long double
#define pb push_back
#define dbg(x) cout << #x << "  " << x << endl;

ll power(ll base, ll exp) 
{ll res=1;while(exp>0) {if(exp%2==1) res=(res*base);base=(base*base);exp/=2;}return res;}
ll mod(ll a, ll b) {return (a % b + b) % b;}
using namespace std;

int main() 
{
	fast;
	ll H,W; cin>>H>>W;
	char dp[H][W];
	for(ll i = 0; i < H; i++)
	{
		for(ll j = 0; j < W; j++)
		{
			cin>>dp[i][j];
		}
	}
	for(ll i = 0; i < W+2; i++)
	{
		cout << "#";
	}
	cout << endl;
	for(ll i = 0; i < H; i++)
	{
		cout << "#";
		for(ll j = 0; j < W; j++)
		{
			cout << dp[i][j];
		}
		cout << "#";
		cout << endl;
	}
	for(ll i = 0; i < W+2; i++)
	{
		cout << "#";
	}
 	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <string>
#include <numeric>
#include <cmath>
#include <bitset>

#define rep(i, n) for (int i = 0; i < n; i++)
using namespace std;
typedef long long ll;
using P = pair<ll, ll>;

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 ll MOD = 1000000007;
const int INF = 1<<30;
//const ll INF = (ll)1e18 + 1;

int main(){
  vector<int> a = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
  int K; cin >> K;
  cout << a[K - 1] << endl;
}


Measured memory_bytes: 256
/*
  _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
 |                                                                 |
 |   author : thanos1399     Language : C ++                         | 
 |   college : MSIT                                                | 
 | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |  
*/
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cctype>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <functional>
#include <bits/stdc++.h>
using namespace std ;
#define TEST            int t ; cin>>t; while(t--)
#define line            cout<<endl;
#define loop(i,a,b)     for(long long int i=a;i<b;i++)
#define loopIn(i,a,b)   for(long long int i=a;i<=b;i++)
#define MAX_SIZE        1000000
#define ff              first
#define ss              second
#define pb              push_back
#define ll              long long int  
#define mp              make_pair
#define vt              vector<tup>
#define vtt             vector<vt >
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
void Sieve( int *prime , int n){for(int i=0;i<n;i++){prime[i] = 0;}for(int i=2;i<n;i++){prime[i] = 1 ;}for(int i=4;i<n;i+=2){prime[i] = 0;}for(int i=3;i<n;i++){if(prime[i]==1){for(int j=i*i;j<n;j+=i){prime[j] = 0;}}}return ;}
void input(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #ifndef ONLINE_JUDGE
    freopen("/home/yash/Desktop/CPP/input.txt","r",stdin);
    freopen("/home/yash/Desktop/CPP/output.txt","w",stdout);
    #endif
}
ll inp;
int parent[101];
bool sortbysec(const pair<int,int> &a,const pair<int,int> &b) {return (a.second < b.second); } 
/*int find(int a)
{
    while(parent[a] > 0)
        a = parent[a];
 
    return a;
} */
 
void Union(int a , int b)
{
    parent[a] += parent[b];     //adding size of set b to set a
    parent[b] = a;              //making a , parent of new set
}
int find ( int node )
{
    if ( parent[node] < 0 )
        return node ;
 
    parent[node] = find( parent[node] ) ;
    return parent[node] ;
}
 
int main() {
   // input();
    int n,k;
    cin>>n>>k;
    vi V;
    loop(i,0,n){
        cin>>inp;
        V.pb(inp);
    }
    int dp[n];
    dp[0] = 0 ;
    //dp[1] = abs(V[0] - V[1]);
    loop(i,1,n){
        int ans = INT_MAX;
        loop(j,0,k){
        int temp ;
        if( (i-j)-1 >= 0 ) {
            temp = dp[(i-j) - 1] + abs(V[i] - V[(i-j)-1]);
           // cout<<i<<" "<<j<<" "<<temp<<endl;
        }
        dp[i] = min (ans , temp); 
        ans = min(ans, temp);
        //cout<<dp[i]<<endl;
        }
    }

    cout<<dp[n-1]<<endl;


    return 0;
}

Measured memory_bytes: 1144
#pragma region template
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vld = vector<ld>;
using vvld = vector<vld>;
using vvvld = vector<vvld>;
using vs = vector<string>;
using pll = pair<ll, ll>;
using vp = vector<pll>;
template <typename T>
using pqrev = priority_queue<T, vector<T>, greater<T>>;
#define rep(i, n) for (ll i = 0, i##_end = (n); i < i##_end; i++)
#define repb(i, n) for (ll i = (n)-1; i >= 0; i--)
#define repr(i, a, b) for (ll i = (a), i##_end = (b); i < i##_end; i++)
#define reprb(i, a, b) for (ll i = (b)-1, i##_end = (a); i >= i##_end; i--)
#define ALL(a) (a).begin(), (a).end()
#define SZ(x) ((ll)(x).size())
//
constexpr ll MOD = 1e9 + 7;
/*/
const ll MOD = 998244353;
//*/
constexpr ll INF = 1e+18;
constexpr ld EPS = 1e-12L;
constexpr ld PI = 3.14159265358979323846L;
constexpr ll GCD(ll a, ll b) { return b ? GCD(b, a % b) : a; }
constexpr ll LCM(ll a, ll b) { return a / GCD(a, b) * b; }
template <typename S, typename T>
inline bool chmax(S &a, const T &b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <typename S, typename T>
inline bool chmin(S &a, const T &b) {
  if (b < a) {
    a = b;
    return 1;
  }
  return 0;
}
#ifdef OJ_LOCAL
#include "dump.hpp"
#else
#define dump(...) ((void)0)
#endif
template <typename T>
bool print_(const T &a) {
  cout << a;
  return true;
}
template <typename T>
bool print_(const vector<T> &vec) {
  for (auto &a : vec) {
    cout << a;
    if (&a != &vec.back()) {
      cout << " ";
    }
  }
  return false;
}
template <typename T>
bool print_(const vector<vector<T>> &vv) {
  for (auto &v : vv) {
    for (auto &a : v) {
      cout << a;
      if (&a != &v.back()) {
        cout << " ";
      }
    }
    if (&v != &vv.back()) {
      cout << "\n";
    }
  }
  return false;
}
void print() { cout << "\n"; }
template <typename Head, typename... Tail>
void print(Head &&head, Tail &&... tail) {
  bool f = print_(head);
  if (sizeof...(tail) != 0) {
    cout << (f ? " " : "\n");
  }
  print(forward<Tail>(tail)...);
}
#pragma endregion

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(20);
  string s;
  cin >> s;
  string t;
  cin >> t;
  cout << t << s << endl;
}


Measured memory_bytes: 256
n,h=map(int,input().split());a=[0]*n;b=[0]*n
for i in range(n):a[i],b[i]=map(int,input().split())
m=max(a);b.sort();c=0
while h>0:
 if b and b[-1]>m:c+=1;h-=b.pop()
 else:c-=h//-m;h=0
print(c)

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

int main() {
	int X, Y, Z;
	cin >> X >> Y >> Z;

	//int A = Y * Z + Z;

	cout << (X - Z) / (Y + Z) << endl;
	

}

Measured memory_bytes: 256
def gcd(a, b):
    if a < b:
        a, b = b, a
    return b if (a % b == 0) else gcd(b, a%b)

def solve(a):
    n = len(a)
    if n == 1:
        return a[0]
    b = []
    for i in range(0, n, 2):
        if i+1 < n:
            z = gcd(a[i], a[i+1])
        else:
            z = a[i]
        b.append(z)
    return solve(b)

assert solve([2,10,8,40]) == 2
assert solve([5,13,8,1000000000]) == 1
assert solve([1000000000,1000000000,1000000000]) == 1000000000
n = input()
a = list(map(int, input().split()))
print(solve(a))

Measured memory_bytes: 14480
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <ctime>
#include <cstring>
#include <functional>
#include <iostream>
#include <iomanip>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

#define fix(n)          cout<<fixed<<setprecision(n)
#define rep(i,n)        for (int i = 0; i < (n); ++i)
#define sort(a)         sort((a).begin(), (a).end())
#define uniq(a)         SORT(a);(a).erase(unique((a).begin(), (a).end()), (a).end())
#define reverse(a)      reverse((a).begin(), (a).end())
#define ctos(c)         string(1, (c))
#define out(d)          cout << (d)
#define outl(d)         std::cout<<(d)<<"\n"
#define Yes()           printf("Yes\n")
#define No()            printf("No\n")
#define YES()           printf("YES\n")
#define NO()            printf("NO\n")
#define ceil(x, y)      ((x + y - 1) / (y))
#define debug(x)        cerr << #x << ": " << (x) << '\n'
#define debug2(x, y)    cerr << #x << ": " << (x) << ", " << #y << ": " << (y) << '\n'
#define debug3(x, y, z) cerr << #x << ": " << (x) << ", " << #y << ": " << (y) << ", " << #z << ": " << (z) << '\n'
#define dbg(v)          for (size_t _ = 0; _ < v.size(); ++_){ cerr << #v << "[" << _ << "] : " << v[_] << '\n'; }

using namespace std;
using ll = long long;
using P = pair<ll,ll>;

const ll MOD = 1000000007; // 10^9 + 7

void solve() {
  string s; cin >> s;
  s.insert(4, " ");
  outl(s);
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  srand((unsigned)time(NULL));
  fix(12);

  solve();
}


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

int main(){
  int A,B,C,X,Y;
  cin>>A>>B>>C>>X>>Y;
  
  int sum=0;
  if(X<Y){
    if(A+B>=2*C){
      sum+=X*2*C;
      if(B>=2*C) sum+=(Y-X)*2*C;
      else sum+=(Y-X)*B;
    }
    else sum+=X*A+Y*B;
  }
  else{
    if(A+B>=2*C){
      sum+=Y*2*C;
      if(A>=2*C) sum+=(X-Y)*2*C;
      else sum+=(X-Y)*A;
    }
    else sum+=X*A+Y*B;
  }
  cout<<sum<<endl;
}

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

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define endl '\n';
#define FASTER ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
const ll POSITIVE_INFINITY = 9223372036854775807;
const ll NEGATIVE_INFINITY = -9223372036854775807;
const ll MOD = 1000000007;
const ld PI = acos(-1.0);

template <typename T> inline T bigMod(T A,T B,T M = MOD){A %= M;T ret = 1;while(B){if(B & 1) ret = (ret * A) % M;A = (A * A) % M;B = B >> 1;}return ret;}
template <typename T> inline T invMod (T A,T M = MOD){return bigMod(A,M-2,M);}

const int N = 200005;

int main(){
  FASTER;
  int n;
  cin >> n;
  ll sum = 0;
  for (int i = 1; i <= n; i++){
    if (i % 3 == 0 || i % 5 == 0){

    } else {
      sum += i;
    }
  }
  cout << sum << "\n";
  return 0;
}


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

using namespace std;

struct _in {
	const _in operator , (int&a) const {
		a = 0;
		int f = 1;
		char k = getchar ();
		while (k > '9' || k < '0') {
			if (k == '-')
				f = -1;
			k = getchar ();	
		}
		while (k >= '0' && k <= '9')
		{
			a = a * 10 + k - '0';
			k = getchar ();
		}
		a *= f;
		return*this;
	}
}in;

const int N = 1000 + 5;
int info[N][N], h, w, a, b, x1, x2, cntl[N], cur[N];

int main () {
	scanf ("%d%d%d%d", &h, &w, &a, &b);
	x1 = b, x2 = a;
	for (int i = 1; i <= b; ++i)
	{
		for (int j = 1; j <= a; ++j)
		{
			info[i][j] = 1;
			cntl[j]++;
		}
	}
	for (int i = b + 1; i <= h; ++i)
	{
		for (int j = 1; j <= w - a; ++j)
		{
			info[i][j] = 1;
			cntl[j]++;
		}
	}
	for (int i = 1; i <= h; ++i)
		cur[i] = w;
	for (int i = 1; i <= w; ++i)
	{
		int c1 = i > a ? h - b : b, tcnt = 0, curx;
		for (curx = 1; curx <= h; ++curx)
		{
			if (info[curx][i]) tcnt++;
			if (c1 == tcnt) break;
		}
		for (int j = curx + 1; j <= h; ++j)
		{
			if (!info[j][i]) continue;
			swap (info[j][i], info[j][ cur[j] ]);
			cntl[i]--;
			cntl[ cur[j] ]--;
			cur[j]--;
		}
	}
	for (int i = 1; i <= h; ++i)
	{
		for (int j = 1; j <= w; ++j)
		{
			printf ("%d", info[i][j]);
		}
		puts ("");
	}
	return 0;
}






























Measured memory_bytes: 5248
#include <iostream>
#include <cstdint>
#include <vector>

constexpr std::int64_t Mod = 1e9 + 7;

int main() {
	std::int64_t n, k;
	std::cin >> n >> k;

	std::vector<int> vec(n);
	std::vector<std::int64_t> count(2001);
	for (auto&& e : vec) {
		std::cin >> e;
		++count[e];
	}
	for (int i = 1; i <= 2000; ++i)
		count[i] += count[i - 1];

	std::int64_t ans = 0;
	
	for (int i = 0; i < n; ++i)
		ans += ((count[2000] - count[vec[i]]) * (k * (k - 1) / 2 % Mod)) % Mod;

	for (int i = 0; i < n; ++i) {
		std:int64_t rev = 0;

		for (int j = 0; j < i; ++j)
			if (vec[i] < vec[j])
				++rev;

		ans = (ans + k * rev) % Mod;
	}

	std::cout << ans << std::endl;
}

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

int asc(const void *a, const void *b) {
  return *(int *)a - *(int *)b;
}

int main() {
	string s;
	cin >> s;
	string ans = "yes";
	for(int i = 0; i < s.size(); i++){
		for(int j = i+1; j < s.size(); j++){
			if(s[i] == s[j]){
				ans = "no";
			}
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); ++i)
#define MOD 1000000007

using namespace std;
using ll = long long;

int main() {
	int x, n, ans;
	cin >> x >> n;
	int p[102] = {};
	rep(i,n) {
		int s;
		cin >> s;
		p[s] = 1;;
	}
	int i = 0;
	while(1) {
		if (p[x - i] == 0) {
			ans = x - i;
			break;
		}
		if (p[x + i] == 0) {
			ans = x + i;
			break;
		}
		i++;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3616
import java.util.Scanner;

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

	int cn=0;
	int[] num = new int[31];
	for(int i=1; i<29; i++){
		int n = stdIn.nextInt();
		num[n]++;
		}
	for(int i=1; i<31; i++){
		if(num[i]==0){
			System.out.println(i);
			cn++;
			}
		if(cn == 2)break;	
		}	
	}
}

Measured memory_bytes: 17252
import java.io._
import java.util.StringTokenizer
import scala.util.control.Breaks.{breakable,break}

object Main extends App {
  val in = new InputReader(System.in)
  val pw = new PrintWriter(System.out)

  // val a = new Array[Int](N)

  val N, M = in.next().toInt

  val uf = new UnionFind(N+1)
  for (_ <- 1 to M) {
    val X, Y, Z = in.next().toInt
    uf.connect(X, Y)
  }

  val dp = new Array[Boolean](N+1)
  var ans = 0
  for(i <- 1 to N) {
    if(!dp(uf.root(i))) {
      ans += 1
      dp(uf.root(i)) = true
    }
  }
  println(ans)
}


class InputReader(stream: InputStream) {
  private val reader = new BufferedReader(new InputStreamReader(stream))
  private var tokenizer: StringTokenizer = new StringTokenizer(reader.readLine())
  def next(): String = {
    while (!tokenizer.hasMoreTokens()) {
      tokenizer = new StringTokenizer(reader.readLine())
    }
    tokenizer.nextToken()
  }
}

// O(α(n)) << O(log(n))
// v は頂点数

class UnionFind(v: Int){
  // 根であれば *そのグループの要素数(負)* が、子であれば親の番号が入る。
  val uni = Array.fill(v)(-1)

  // 頂点 v の所属するグループを調べる
  def root(v: Int): Int =
    uni(v) < 0 match{
      case true  =>  // v が親の場合
        return v
      case false =>  // v が子の場合
        uni(v) = root(uni(v))  // 親のrootを調べる
        return uni(v)
    }

  // 頂点 a と頂点 b をつなぐ。もともと同じグループのとき、False を返す
  def connect(a: Int, b: Int): Boolean = {
    // まずはそれぞれ根の番号に置き換える
    var ra = root(a)
    var rb = root(b)
    if(ra == rb)
      return false  // a と b がそもそも同じグループに属しているなら即終了

    // ra を大きなグループにしたいので、逆であれば入れ替える
    if(uni(ra) > uni(rb)) {  // rbの方が要素数が多ければ
      var tmp = ra
      ra = rb
      rb = tmp
    }

    // ra と rb を結合し、rb の親を ra とする
    uni(ra) += uni(rb)
    uni(rb) = ra
    return true
  }

  // 頂点 a, b が同じグループであるかを調べる
  def isConnect(a: Int, b: Int): Boolean =
    root(a) == root(b)

  // 頂点 a を含むグループの頂点数を調べる
  def size(a: Int): Int = -uni(root(a))
}


Measured memory_bytes: 39184
/*input
15
123 119
129 120
132 112
126 109
118 103
115 109
102 100
130 120
105 105
132 115
104 102
107 107
127 116
121 104
121 115
8
8 234
9 244
10 226
11 227
12 240
13 237
14 206
15 227
*/
/*

**************************
*						 *
* AUTHOR :: knight_coder *
*						 *
**************************

*/
#include<bits/stdc++.h>
#define lld          long long int
#define pb          push_back
#define ppb         pop_back
#define	endl		'\n'
#define mii         map<lld,lld>
#define msi         map<string,lld>
#define mis         map<lld, string>
#define mpi         map<pair<lld ,lld >,lld >
#define pii         pair<lld,lld>
#define vi          vector<lld>
#define vpi 		vector<pii>
#define vs          vector<string>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (lld)x.size()
#define hell        1000000007
#define rrep(i,m,n)	for(lld i=m;i>=n;i--)
#define rep(i,m,n)	for(lld i=m;i<n;i++)
#define lbnd        lower_bound
#define ubnd        upper_bound
#define bs          binary_search
#define mp          make_pair
#define what_is(x)  cerr << #x << " is " << x << endl;
#define pr(x) 		cout<< x << " ";
#define pre(x)		cout<< x << endl ;
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T>
using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>; 
//change null_type to get ordered_map
#define N  100005
int dp[1024][100001],v[323456],w[323456];
int n,q;
 
int f(int a,int l) {
  if(l<0) return -1e9;
  if(!a) return 0;
  if(a>1023) return max(f(a/2,l),f(a/2,l-w[a])+v[a]);
  if(~dp[a][l]) return dp[a][l];
  return dp[a][l]=max({f(a/2,l),f(a,l-1),f(a/2,l-w[a])+v[a]});
}
 void solve()
{
  cin >> n;
  memset(dp,-1,sizeof(dp));
  for(int i=1;i<=n;i++) cin >> v[i] >> w[i];
  cin >> q;
 
  while(q--) {
    int a,l;
    cin >> a >> l;
    cout << f(a,l) << endl;
  }
	 
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int tests=1;
	//cin>>tests;
	while(tests--)
	{
		solve();
	}
}

Measured memory_bytes: 413460
#include <iostream>
#include <cstdio>
#include <cctype>
#include <string>
#include <algorithm>
using std::string;

string s, s1;
int len = 0;

int main() {
	std::cin >> s;
	s1 = s;
	len = s.size();
	for (int i = 0, j = len - 1; i < j; ++i, --j) {
		std::swap(s[i], s[j]);
	}
	for(int i = 0; i < len; ++i) {
		if (s[i] == 'd') {
			s[i] = 'b';
		}
		else if (s[i] == 'b') {
			s[i] = 'd';
		}
		else if (s[i] == 'q') {
			s[i] = 'p';
		}
		else if (s[i] == 'p') {
			s[i] = 'q';
		}
	}
	if (s1 == s) {
		printf("Yes\n");
	}
	else {
		printf("No\n");
	}
	return 0;
}

Measured memory_bytes: 512
#include <iostream>

using namespace std;
int sq[17] = {1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289};

void solve()
{
	int dp[301];
	dp[0] = 1;
	for(int i = 1; i < 301; ++i)
	{
		dp[i] = 1;
	}
	for(int a = 1; a < 17; ++a)
	{
		for(int i = sq[a]; i < 301; ++i)
		{
			dp[i] += dp[i - sq[a]];
		}
	}
	int n;
	while(cin >> n, n)
	{
		cout << dp[n] << endl;
	}
}

int main()
{
	solve();
	return(0);
}

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

int main(){
  int n;
  string s;
  cin >> n >> s;
  
  int ans = 0; 

  rep(i,1000){
    int x = n-1, y = n-1;
    string p = to_string(i);
    if(p.size() == 1) p= "00" + p;
    if(p.size() == 2) p = "0" + p;
    
    rep(j,n){
      if(s[j] == p[0]){
        x = j;
        break;
      }
    }
    if(x-n+1){
      for(int j = x + 1;j < n; j++){
        if(s[j] == p[1]){
          y = j;
          break;
        }
      }
    }
    if(y-n+1){
      for(int j = y + 1; j < n; j++){
        if(s[j] == p[2]){
          ans++;
          break;
        }
      }
    }   
    
  }
  
  cout << ans << endl;
}



Measured memory_bytes: 256
#include <iostream>

using namespace std;

typedef long long ll;

int main()
{
    ios_base::sync_with_stdio(0);
    ll a, b, n;
    cin >> a >> b >> n;
    n = min(n, b - 1);
    cout << (a * n) / b - (a * (n / b));
    return 0;
}


Measured memory_bytes: 3652
n = int(input())
x = list(map(int, input().split()))

mod = 10**9 + 7

fac = [1, 1]
inv = [1, 1]
finv = [1, 1]
for i in range(2, n+5):
    fac.append(fac[i-1] * i % mod)
    inv.append(mod - inv[mod%i] * (mod//i) % mod)
    finv.append(finv[i-1] * inv[i] % mod)

ans = 0
j_inv = []
num = 0
for j in range(1, n):
    num += inv[j]
    num %= mod
    j_inv.append(num)

for i in range(n-1):
    ans += j_inv[i] * (x[i+1] - x[i])
    ans %= mod

ans *=fac[n-1]
ans %= mod

print(ans)



Measured memory_bytes: 76312
#include <iostream>
#include <vector>
#include <array>
#include <set>
#include <cmath>
#include <string>
#include <queue>
#include <list>
#include <stack>
#include <unordered_map>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cassert>
#include <cctype>  // std::islower(), std::isupper(), std::tolower, std::toupper
#include <iomanip> // std::std::setprecision(X)
#include <limits>  //std::numeric_limits<int>::max(), min()

typedef long long ll;

int main (void) {

  int N; std::cin >> N;
  std::cout << std::floor((float)N/3) << std::endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
/*#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_int.hpp>
*/#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")    
using namespace std;
/*namespace mp = boost::multiprecision;
using Bint = mp::cpp_int;
using Real = mp::number<mp::cpp_dec_float<1024>>;
*/#define lli long long int
#define uli unsigned long long int
#define INF 999999999999
#define rep(i,m,n) for(lli i = m;i < n;i++)
#define rrep(i,m,n) for(lli i=m-1;i>=n;i--)
#define pb(n) push_back(n)
#define UE(N) N.erase(unique(N.begin(),N.end()),N.end());
#define Sort(n) sort(n.begin(), n.end())
#define Rev(n) reverse(n.begin(),n.end())
#define Out(S) cout << S << endl
#define NeOut(S) cout << S
#define HpOut(S) cout << setprecision(50) << S << endl
#define Vec(K,L,N,S) vector<L> K(N,S)
#define DV(K,L,N,M,S) vector<vector<L>> K(N,vector<L>(M,S))
#define TV(K,L,N,M,R,S) vector<vector<vector<L>>> K(N,vector<vector<L>>(M,vector<L>(R,S)))
#define pint pair<lli,lli>
#define paf(L,R) pair<L,R>
#define mod 998244353
#define MAX 10000000
#define ALL(a)  a.begin(),a.end()
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  lli A,B,C,D,E,H,W,M,K,L,R,N,num=0,sum=0,flag=0;string S,T;
  cin >> S >> T;
  rep(i,0,S.size())if(S[i]!=T[i])sum++;
  Out(sum);
}

Measured memory_bytes: 3800
#include <bits/stdc++.h>
#define FOR(i, m, n) for (int i = m; i < (n); i++)
#define RFOR(i, m, n) for (int i = (m - 1); i >= 0; i--)
#define REP(i, n) FOR(i, 0, n)
#define RREP(i, n) RFOR(i, n, 0)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;

int main()
{
  int n;
  cin >> n;
  bool flag = false;
  REP(i, n)
  {
    char s;
    cin >> s;
    if (s == 'Y')
      flag = true;
  }
  cout << (flag ? "Four" : "Three") << endl;
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main()
{
    int N,M,i,sum=0;
    cin>>N>>M;
    int A[M];
    for(i=0;i<M;i++)
    {
        cin>>A[i];
        sum=sum+A[i];
    }
    int r=N-sum;
    if(r>=0)
        cout<<r<<endl;
    else
        cout<<"-1"<<endl;

}


Measured memory_bytes: 3196
import java.util.*;


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

        int N = sc.nextInt();
        int K = sc.nextInt();
        int keta = 1;
        while(N >= K){
            
            N = N/K;
            keta++;

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

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

int main()
{
	string s;
	cin >> s;
	
	for (int i = 0; i < s.length(); ++i)
	{
		if (s == "hi" or s == "hihi" or s == "hihihi" or s == "hihihihi" or s == "hihihihihi")
		{
			cout << "Yes" << endl;
			return 0;
		}
	}
	
	cout << "No" << endl;
	
	return 0;
}


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

#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
#define ALL(x) x.begin(),x.end()
#define EPS (1e-8)
#define equals(a,b) (fabs((a)-(b))<EPS)

using namespace std;

typedef long long ll;
const int IINF = INT_MAX;
const ll LLINF = LLONG_MAX;

bool LT(double a,double b) { return !equals(a,b) && a < b; }
bool LTE(double a,double b) { return equals(a,b) || a < b; }

void compute() {

}

const string YES = "POSSIBLE";
const string NO  = "IMPOSSIBLE";
int main() {
  int N,K;
  cin >> N >> K;
  vector<int> A(N);
  bool exist = false;
  rep(i,N) {
    cin >> A[i];
    if( A[i] == K ) exist = true;
  }
  if( exist ) { puts(YES.c_str()); return 0; }
  sort(ALL(A));
  if( K > A[N-1] ) { puts(NO.c_str()); return 0; }
  int gcj = A[0];
  REP(i,1,N) gcj = __gcd(gcj,A[i]);
  if( K % gcj == 0 ) puts(YES.c_str());
  else               puts(NO.c_str());
  compute();
  return 0;
}


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

public class Hello {
  
 static int counter =0;
static  int[] loop;
static  int[] num;
    public static void Main() {
        //使わないのはコメントアウトしないとエラー
      
      loop = NumInput();
      num = NumInput();
//        var text = StringInput();
Loop();

        Result(counter);
        
    }
  static void Loop(){
    while(true){
      for(int i = 0; i < loop[0]; i++){
        if(num[i]%2 != 0) return;
          num[i] = num[i]/2;
        }
        counter++;
      } 
  }
  
    static int[] NumInput(){
        var input_line = Console.ReadLine().Split(' ');
        return input_line.Select(int.Parse).ToArray();
    }
    static string[] StringInput(){
        return Console.ReadLine().Split(' ');
    }
    
    static void Result(string text){
        Console.WriteLine( text );
    }   
    static void Result(int num){
        Console.WriteLine( num );
    }
    static void Result(float num){
        Console.WriteLine( num );
    }
}

Measured memory_bytes: 13396