akhauriyash/Code-Regression huggingface dataset:
class Tree:
    def __init__(self, n):
        self.n = n
        self.nodes = [Node(i) for i in range(n)]
        self.root = -1

    def set_tree(self):
        for _ in range(self.n):
            i_str = [int(i) for i in input().split()]
            for i in range(2):
                if i_str[i+1] != -1:
                    self.nodes[i_str[0]].degree += 1
                    self.nodes[i_str[i+1]].parent = i_str[0]
                    if self.nodes[i_str[i+1]].type != "internal node":
                        self.nodes[i_str[i+1]].type = "leaf"
            if self.nodes[i_str[0]].degree == 2:
                self.nodes[i_str[1]].sibling = i_str[2]
                self.nodes[i_str[2]].sibling = i_str[1]
            if self.nodes[i_str[0]].degree > 0:
                self.nodes[i_str[0]].type = "internal node"

    def set_depth_height(self):
        self.set_root()
        self.set_depth(self.root)

        for node in self.nodes:
            if node.type == "leaf":
                self.set_height(node.id)

    def set_depth(self, parent, depth = -1):
        self.nodes[parent].depth = depth + 1
        for node in self.nodes:
            if node.parent == parent:
                self.set_depth(node.id, depth + 1)

    def set_height(self, child, height = -1):
        if self.nodes[child].height <= height + 1:
            self.nodes[child].height = height + 1
            if self.nodes[child].parent != -1:
                self.set_height(self.nodes[child].parent, height + 1)

    def set_root(self):
        for tn in self.nodes:
            if tn.parent == -1:
                self.root = tn.id
                tn.type = "root"
                break

    def show_tree_info(self):
        for node in self.nodes:
            node.show_node_info()

class Node:
    def __init__(self, id):
        self.id = id
        self.parent = -1
        self.sibling = -1
        self.degree = 0
        self.depth = 0
        self.height = 0
        self.type = "root"

    def show_node_info(self):
        print("node {0}: parent = {1}, sibling = {2}, degree = {3}, depth = {4}, height = {5}, {6}"\
        .format(self.id, self.parent, self.sibling, self.degree, self.depth, self.height, self.type))

if __name__ == '__main__':
    tree = Tree(int(input()))
    tree.set_tree()
    tree.set_depth_height()
    tree.show_tree_info()

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

int main(){
    
    int n;
    cin >> n;
    int ans = 0;
    for(int i=0; i<6; i++)
    {
        if(pow(10, i)==n)
        {
            cout << 10 << endl;
            return 0;
        }
    }
    while(n>0){
        ans += n%10;
        n = (n - n%10) / 10;
    }
    cout << ans << endl;
    return 0;
}

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

#define MP make_pair
#define PB push_back
#define ALL(x)      (x).begin(),(x).end()
#define REP(i,n)    for(int i=0;i<(n);i++)
#define REP1(i,n)   for(int i=1;i<(n);i++)
#define REP2(i,d,n) for(int i=(d);i<(n);i++)
#define RREP(i,n)   for(int i=(n);i>=0;i--)
#define CLR(a)      memset((a),0,sizeof(a))
#define MCLR(a)     memset((a),-1,sizeof(a))
#define RANGE(x,y,maxX,maxY) (0 <= (x) && 0 <= (y) && (x) < (maxX) && (y) < (maxY))
 
typedef long long LL;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef vector<VI > VVI;
typedef vector<string> VS;
typedef vector<LL> VLL;
typedef pair<int,int> PII;
 
const int INF = 0x3f3f3f3f;
const LL INFL = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-9;
 
const int DX[]={1,0,-1,0},DY[]={0,-1,0,1};

double memo[100001];

void solve(long long N, long long K){
    REP(i, K+1) memo[i] = 0;
    double score = 1.0 / N;
    REP1(i, N+1) {
        if(K <= i) memo[K] += score;
        else memo[i] += score;
    }

    REP1(i, K) {
        if(K <= i*2) memo[K] += memo[i] / 2.0;
        else memo[i*2] += memo[i] / 2.0;
    }

    printf("%.10f\n", memo[K]);
}

int main(){
    long long N;
    scanf("%lld",&N);
    long long K;
    scanf("%lld",&K);
    solve(N, K);
    return 0;
}


Measured memory_bytes: 1024
#include<iostream>
#include<cmath>
typedef long long int ll;
using namespace std;
int main(){
    ll n; cin>>n;
    ll t=sqrt(n);
    ll ans;
    bool m=true;
    for(;t>=2;t--){
        if(n%t==0) {
            m=false;
            ans=n/t+t-2;
            break;
        }
    }
    if(m) ans=n-1;
    cout<<ans;
    return 0;
}

Measured memory_bytes: 256
#pragma GCC optimize ("Ofast")
#include <iostream>
using namespace std;
 
inline void fastin(int &num) {
    int c;
    num = 0;
    c = getchar_unlocked();
    for (; (c > 47 && c < 58); c = getchar_unlocked()) num = num * 10 + c - 48;
}
 
inline void fastout(int n) {
    int N = n, rev, count = 0;
    rev = N;
    if (N == 0) { putchar_unlocked('0'); putchar_unlocked('\n'); return ;}
    while ((rev % 10) == 0) { ++count; rev /= 10;}
    rev = 0;
    while (N != 0) { rev = (rev<<3) + (rev<<1) + N % 10; N /= 10;}
    while (rev != 0) { putchar_unlocked(rev % 10 + '0'); rev /= 10;}
    while (count--) putchar_unlocked('0');
}
 
int main(){   
    int n; fastin(n);
    //int a[n];
    //for (int i = 0; i < n; ++i) fastin(a[i]);
 
    char c = 'E';  // state Up, Down, Equal
    int cnt = 1;
    
    int t1; fastin(t1);
    for (int i = 1; i < n; ++i){
        int t2; fastin(t2);
        if (t2 > t1){
            if (c == 'U'){
                t1 = t2;
            }
            else if (c == 'E'){
                c = 'U'; t1 = t2;
            }
            else if (c == 'D'){
                ++cnt; c = 'E'; t1 = t2;
            }
        }
        else if (t1 == t2){
            t1 = t2;
        }
        else if (t2 < t1){
            if (c == 'U'){
                ++cnt; c = 'E'; t1 = t2;
            }
            else if (c == 'E'){
                c = 'D'; t1 = t2;
            }
            else if (c == 'D'){
                t1 = t2;
            }
        }
    }
    
    /*
    for (int i = 1; i < n; ++i){
        if (a[i] > a[i - 1]){
            if (c == 'U'){
                continue;
            }
            else if (c == 'E'){
                c = 'U';
            }
            else if (c == 'D'){
                ++cnt; c = 'E';
            }
        }
        else if (a[i] == a[i - 1]){
            continue;
        }
        else if (a[i] < a[i - 1]){
            if (c == 'U'){
                ++cnt; c = 'E';
            }
            else if (c == 'E'){
                c = 'D';
            }
            else if (c == 'D'){
                continue;
            }
        }
    }
    */
    fastout(cnt);
    
    return 0;
}

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

int main(){
 int n,k,q;
 cin >> n >> k >> q;
 vector<int> flag(n,0);
 vector<int> ans(n, k);
 for(int i=0;i<q;i++) {
	 int a;
	 cin >> a;
	 a--;
	 flag[a]++;
 }
 for(int i=0;i<n;i++) {
	 ans[i] -= (q-flag[i]);
 }
 for(int i=0;i<n;i++) {
	 if(ans[i]<=0) cout << "No" << endl;
	 else cout << "Yes" << endl;
 }
}

Measured memory_bytes: 1408
loop do
n = gets.to_i

if n == 0 then
  break
end

from = Array.new
to = Array.new

n.times{
  (a, b) = gets.split  
  from.push(a)
  to.push(b)
}

n = gets.to_i

n.times{
  c = gets.strip
  if i = from.index(c) then
    print to[i]
  elsif
    print c
  end
}
puts ""

end

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

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

	int sum = 0;

	vector<int> c(s.size());
	for (int i = 0; i < s.size(); i++) {
		c[i] = (int)(s.at(i) - '0');
		sum += c[i];
	}
	
	int n = stoi(s);

	string ans = "No";

	if (n % sum == 0) ans = "Yes";

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main (String[] args) {
        Scanner scanner = new Scanner(System.in);
       
        while (scanner.hasNext()) {
            double a = scanner.nextDouble();
            double b = scanner.nextDouble();
            double c = scanner.nextDouble();
            double d = scanner.nextDouble();
            double e = scanner.nextDouble();
            double f = scanner.nextDouble();
            double x = 0;
            double y = 0;

            x = (c*e - b*f) / (a*e - b*d);
            y = (c*d - a*f) / (b*d - a*e);
            if (x == -0) {
                x = 0;
            }
            if (y == -0) {
                y = 0;
            }
            
            System.out.printf("%.3f %.3f\n", x, y);

        }
    }
}

Measured memory_bytes: 20488
#include<bits/stdc++.h>
 
using namespace std;
 
#define  fastio         ios:: sync_with_stdio(0);cin.tie(0);cout.tie(0);cout<<fixed;cout<<setprecision(10);
 
typedef  long long             ll;
typedef  long double           ld;
typedef  pair<ll,ll>           pll;
typedef  vector<ll>            vll;
typedef  unordered_map<ll,ll>  um;
typedef  vector<pll>           vpll;
#define  f                     first                 
#define  s                     second                
 
const ll   N     =  2e5+5;
const ll   mod   =  1e9+7;
const ll   INF   =  0x7f7f7f7f7f7f7f7f;
const ll   INFi  =  0x7f7f7f7f;
 
ll x,y,A,B,C,a[N],b[N],c[N];
multiset <ll> s;

int main(){
    cin>>x>>y>>A>>B>>C;
    for(int i = 0; i < A; i++) cin>>a[i];
    for(int i = 0; i < B; i++) cin>>b[i];
    for(int i = 0; i < C; i++){ cin>>c[i]; s.insert(c[i]); }
    sort(a,a+A);
    sort(b,b+B);
    sort(c,c+C);
    for(int i = A-1; i > A-1-x; i--) s.insert(a[i]);
    for(int i = B-1; i > B-1-y; i--) s.insert(b[i]);
    auto it = s.end();
    it--;
    ll q = x+y;
    ll ans = 0;
    while(q--){
        ans += *it;
        it--;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 16640
#include <algorithm>
#include <cmath>
#include <complex>
#include <cstdio>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <string>
#include <vector>

const long long int INF = 1e9;
typedef long long int ll;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define Rep(i, n) for(int i = 1; i <= (int)(n); i++)
#define llrep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define llRep(i, n) for(ll i = 1; i <= (ll)(n); i++)

using namespace std;

struct Point{
	int x,y;
};

bool vector_finder(std::vector<int> vec, int number) {
    auto itr = std::find(vec.begin(), vec.end(), number);
    size_t index = std::distance( vec.begin(), itr );
  if (index != vec.size()) { // 発見できたとき
    return true;
    }
  else { // 発見できなかったとき
    return false;
    }
}


vector<int> D;

bool isHateNumberIncluded(int num){
    while(num>0){
        int rest = num%10;
        if (vector_finder(D, rest)) return true;
        num -= rest;
        num /= 10;
    }
    return false;
}


int main(){
    ll N,K;
    int d;
    cin >> N >> K;
    rep(i,K){
        cin >> d;
        D.push_back(d);
    }
    while(1){
        if (isHateNumberIncluded(N)/*嫌いな数字出現*/){
            N++;
        }else{
            break;
        }
    }
    cout << N << endl;

    return 0;
}


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



void solve(long long K){

    queue<ll> q;
    for(int i=1;i<10;i++){
        q.push(i);
    }
    while(!q.empty()){
        ll v = q.front();
        q.pop();
        K--;
        if(K==0){
            cout << v << endl;
            return;
        }
        int lastN = v%10; 
        for(int i=-1;i<2;i++){
            if(lastN +i <0|| lastN +i >9){
                continue;
            }
            q.push(v*10+lastN+i);
        }
    }


    

    // 2分探索でルンルン数の桁と先頭の数字を求める、というのを繰り返す。


}

// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    long long K;
    scanf("%lld",&K);
    solve(K);
    return 0;
}


Measured memory_bytes: 1792
import sys
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    K = int(input())
    S = input()
    if len(S) <= K:
        print(S)
    else:
        ans = S[:K] + '...'
        print(ans)
if __name__ == '__main__':
    main()

Measured memory_bytes: 9208
N,M,C=[int(z) for z in input().split(" ")]
B=[int(z) for z in input().split(" ")]

A=[]
ans=0

for z in range(0,N):
  A.append([int(z) for z in input().split(" ")])

for z in A:
  buf=0
  for i,y in enumerate(z):
    buf+=y*B[i]
  buf+=C
  if buf>0:
    ans+=1

print(ans)

Measured memory_bytes: 3064
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#include <set>
#include <map>
#include <functional>
#include <cmath>
#include <cassert>
#include <string>

using namespace std;
typedef long long int ll;
typedef pair <int,int> P;

int main()
{
	int n,k;
	scanf("%d %d",&n,&k);
	printf("%d\n",k==1?0:n-k);
	return 0;
}


Measured memory_bytes: 128
"use strict";
    
const main = arg => {
    const N = arg.split("\n")[0];
    const X = arg.split("\n").slice(1,N+1);
    let total = 0;
    for(let i in X) {
        let money;
        if(X[i].split(" ")[1] == "BTC") {
            money = X[i].split(" ")[0] * 380000.0;
        } else {
            money = X[i].split(" ")[0];
        }
        total += Number(money);
    }
    console.log(total);
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));

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

int n, h[25], t;

int main() {
    cin >> n;
    for(int i=0; i<n; i++) cin >> h[i];
    for(int i=0; i<n; i++){
        int x=0;
        for(int j=0; j<i; j++){
            if(h[j] <= h[i]){
                x++;
            }
        }
        if(x==i){
            t++;
        }
    }
    cout << t;
}

Measured memory_bytes: 256
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
template<typename T> bool chmax(T &a,T b){if(a<b){a=b;return true;}return false;}
template<typename T> bool chmin(T &a,T b){if(a>b){a=b;return true;}return false;}
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(vec) vec.begin(),vec.end()
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef tuple<ll,ll,ll> tlll;
typedef tuple<int,int,int> tiii;
const ll mod=1e9+7;
const int inf=1<<30;

ll dp[200010][3];

int main(){
  int n; cin >> n;
  vector<ll> a(n);
  rep(i,n) cin >> a[i];
  if(n%2==1){
    dp[0][0]=a[0];
    dp[1][1]=a[1];
    dp[2][2]=a[2];
  }
  else{
    dp[0][0]=a[0];
    dp[1][1]=a[1];
  }
  rep(i,n){
    rep(j,3){
      if(i-2>=0) dp[i][j]=dp[i-2][j]+a[i];
      if(i-3>=0&&j-1>=0) chmax(dp[i][j],dp[i-3][j-1]+a[i]);
      if(i-4>=0&&j-2>=0) chmax(dp[i][j],dp[i-4][j-2]+a[i]);
    }
  }
  ll ans=-1e18;
  if(n%2==1){
    chmax(ans,dp[n-1][2]);
    chmax(ans,dp[n-2][1]);
    chmax(ans,dp[n-3][0]);
  }
  else{
    chmax(ans,dp[n-1][1]);
    chmax(ans,dp[n-2][0]);
  }
  cout << ans << endl;
  
}


Measured memory_bytes: 9492
n = int(input())
a = list(map(int, input().split()))

# O(N)
cnt = 0
starts = [0 for _ in range(n)]
for i, v in enumerate(a):
    next_idx = v + i + 1
    if next_idx < n:
        starts[next_idx] += 1
    if 0 <= i - v + 1 <= n-1:
        cnt += starts[i - v + 1]
print(cnt)

Measured memory_bytes: 101848
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>

using namespace std;

#define SORT(c) sort((c).begin(),(c).end())
#define ANS(ans) cout<<(ans)<<endl;
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end());
typedef vector<int> VI;


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



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

	if (s.size() == 2) {
		ANS(s);
	}
	else {
		cout << s[2] << s[1] << s[0] << endl;
	}

	return 0;
}



Measured memory_bytes: 764
import sys

s1 = input()
s2 = input()

n1 = 0
t1 = 0
t2 = -1

for i1 in range(len(s2) ):
    t1 =  s1.find(s2[i1],t2 + 1)
    if t1 == -1:
        t1 = s1.find(s2[i1], 0, t2 + 1)
        if t1 == -1:
            print(t1)
            sys.exit()
        else:
            n1 += t1 + (len(s1) - t2)
    else:
        n1 += t1 - t2
    t2 = t1

print(n1)

Measured memory_bytes: 3316
#include<stdio.h>
#include<stdlib.h>
int a[101][101];
int main()
{
	int n,h,w;
	scanf("%d%d%d", &h, &w, &n);
	int *b = NULL;
	b = (int *)malloc(sizeof(int)*n);
	int i,j;
	for (i = 0; i < n; i++)
		scanf("%d", &b[i]);
	int k = 1,m=1;
	for (i = 0; i < h; i++)
	{
		if (i%2==0)
		{
			for (j = 0; j < w; j++)
			{
				if (m <= b[k-1])
				{
					a[i][j] = k;
					m++;
					 
				}
				else
				{
					m = 1;
					k++;
					j--;
				}
			}
	   }
		else
		{
			for (j = 0; j <w; j++)
			{
				if (m <= b[k - 1])
				{
					a[i][w-j-1] = k;
					m++;
					 
				}
				else
				{
					m = 1;
					k++;
					j--;
				}
			}
		}
		 
	}
	for (i = 0; i < h; i++)
	{
		for (j = 0; j < w; j++)
		printf("%d ", a[i][j]);
			printf("\n");
	 }
	free(b);
	return 0;
}

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

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

struct UnionFind {
  vector<int> d;
  UnionFind(int n = 0) : d(n, -1) {}
  int find(int x) {
    if (d[x] < 0)
      return x;
    return d[x] = find(d[x]);
  }
  bool unite(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y)
      return false;
    if (d[x] > d[y])
      swap(x, y);
    d[x] += d[y];
    d[y] = x;
    return true;
  }
  bool same(int x, int y) { return find(x) == find(y); }
  int size(int x) { return -d[find(x)]; }
};

int main() {

  long n, m;
  cin >> n >> m;
  UnionFind uf(n);
  int a, b;
  REP(i, m) {
    cin >> a >> b;
    --a;
    --b;
    uf.unite(a, b);
  }
  int ans = 0;
  REP(i, n) { ans = max(ans, uf.size(i)); }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3956
N = int(input())
R = [int(input()) for i in range(N)]

max_diff = -1 * 10**9
min_value = R[0]
for j in range(1, N):
    # 差分のうち最大値
    max_diff = max(max_diff, R[j] - min_value)
    # 過去の最小値
    min_value = min(min_value, R[j])
print(max_diff)


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

vector<int> adjList[100010];
bool leaf[100010];
bool ipt[100010];

vector<int> ans;
vector<int> ans2;
int cnt = 1;
bool possib = true;

vector<int> iadjList[100010];
void build(int u,int p){
	for(auto v: adjList[u]) if(ipt[v]){
		iadjList[u].push_back(v);
		if(v != p) build(v,u);
	}
}

void build2(int u,int p){
	int curr = cnt,nxt = -1;
	cnt += 1;
	for(auto v: adjList[u]) if(v != p){
		if(ipt[v]){
			if(nxt == -1) nxt = v;
			else possib = false;
		}else{
			ans.push_back(cnt++);
		}
	}
	ans.push_back(curr);
	if(nxt == -1) return;
	build2(nxt,u);
}
int main(){
	int N;cin>>N;
	for(int i=0;i<N-1;i++){
		int u,v;cin>>u>>v;u--;v--;
		adjList[u].push_back(v);
		adjList[v].push_back(u);
	}
	
	for(int i=0;i<N;i++) if(adjList[i].size() == 1) leaf[i] = true;
	for(int i=0;i<N;i++) if(leaf[i] == false) ipt[i] = true;
	for(int i=0;i<N;i++) if(ipt[i]){
		build(i,-1);
		break;
	}
	for(int i=0;i<N;i++) if(ipt[i] && (iadjList[i].size() == 1 || iadjList[i].size() == 0)){
		int nxt = (iadjList[i].size() > 0?iadjList[i][0]:-1);
		for(auto v: adjList[i]) if(v != nxt){
			ipt[v] = true;
			iadjList[v].push_back(i);
			iadjList[i].push_back(v);
			if(nxt == -1){
				nxt = v;
			}else break;
		}
	}
	
	for(int i=0;i<N;i++) if(ipt[i] && (iadjList[i].size() == 1 || iadjList[i].size() == 0)){
		if(ans.size() > 0){
			swap(ans,ans2);
			cnt = 1;
		}
		build2(i,-1);
	}

	if(ans2.size() == N && ans2 < ans) swap(ans,ans2);
	if(!possib || ans.size() != N) cout<<-1<<endl;
	else {
		for(auto x: ans) cout<<x<<" ";
		cout<<endl;
	}
}

Measured memory_bytes: 19068
#include <algorithm>
#include <functional>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <bitset>
#include <climits>

#define all(c) (c).begin(), (c).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define pb(e) push_back(e)
#define mp(a, b) make_pair(a, b)
#define fr first
#define sc second

const int INF=1000000000;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
using namespace std;
typedef pair<int ,int > P;
typedef long long ll;

int n;
string a[1003];

ll toi(string s) {
    ll res;
    stringstream ss;
    ss<<s;
    ss>>res;
    return res;
}

void solve() {
    ll l=-INF*2,r=INF*2;
    rep(i,n) cin>>a[i];

    rep(i,n) {
        if(i!=0 && a[i-1]=="x"&&a[i]=="x") {
            cout<<"none"<<endl;
            return;
        }
        if(i&1) {
            if(i+1<n && a[i+1]!="x") {
                if(a[i]=="x") l=max(l,toi(a[i+1]));
                if(a[i]!="x") {
                    if(toi(a[i])<=toi(a[i+1])) {
                        cout<<"none"<<endl;
                        return;
                    }
                }
            }
            if(i-1>=0 && a[i-1]!="x") {
                if(a[i]=="x") l=max(l,toi(a[i-1]));
                if(a[i]!="x") {
                    if(toi(a[i])<=toi(a[i-1])) {
                        cout<<"none"<<endl;
                        return;
                    }
                }
            }
        }
        else {
            if(i+1<n && a[i+1]!="x") {
                if(a[i]=="x") r=min(r,toi(a[i+1]));
                if(a[i]!="x") {
                    if(toi(a[i])>=toi(a[i+1])) {
                        cout<<"none"<<endl;
                        return;
                    }
                }
            }
            if(i-1>=0 && a[i-1]!="x") {
                if(a[i]=="x") r=min(r,toi(a[i-1]));
                if(a[i]!="x") {
                    if(toi(a[i])>=toi(a[i-1])) {
                        cout<<"none"<<endl;
                        return;
                    }
                }
            }
        }
    }
    // cout<<l<<","<<r<<endl;
    //cout<<r-l<<endl;

    if(r-l>2) {
        cout<<"ambiguous"<<endl;
    }
    else if(r-l<2) {
        cout<<"none"<<endl;
    }
    else {
        cout<<l+1<<endl;
    }




}

int main() {
    while(cin>>n) {
        if(n==0) break;
        solve();
    }
    return 0;
}

Measured memory_bytes: 1312
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=405,M=998244353;
int fac[N],inv[N],a[N],b[N],n,dp[N][N][N];
int ksm(int x,int y){
	int ans=1;
	for (;y;y>>=1,x=x*x%M)
		if (y&1)(ans*=x)%=M;
	return ans;
}
signed main(){
	scanf("%lld",&n);
	int s1=0,s2=0;
	for (int i=1;i<=n;i++)scanf("%lld%lld",&a[i],&b[i]),s1+=a[i],s2+=b[i];
	fac[0]=inv[0]=1;
	for (int i=1;i<N;i++)fac[i]=fac[i-1]*i%M,inv[i]=ksm(fac[i],M-2);
	dp[0][0][0]=-1;
	for (int i=1;i<=n;i++)
		for (int j=0;j<=s1;j++)
			for (int k=0;k<=s2;k++){
				dp[i][j][k]=dp[i-1][j][k];
				if (j>=a[i])for (int l=0,v=1;l<b[i]&&l<=k;l++,(v*=a[i])%=M)
					(dp[i][j][k]+=M-dp[i-1][j-a[i]][k-l]*v%M*inv[l]%M)%=M;
			}
	int ans=0;
	for (int i=1;i<=s1;i++)
		for (int j=0;j<=s2;j++)
			(ans+=dp[n][i][j]*ksm(ksm(i,j),M-2)%M*fac[j]%M*s1%M*ksm(i,M-2))%=M;
	printf("%lld\n",ans);
}


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

int main() {
  int N;
  string S;
  int count=0;
  cin >> N >> S;
  for (int i=0; i<N-2; i++){
    if(S.at(i)=='A'&&S.at(i+1)=='B'&&S.at(i+2)=='C')
      count++;
  }
  cout << count;
}

Measured memory_bytes: 256
#pragma GCC optimize("O3", "unroll-loops")
//#pragma GCC target("avx2")
//#pragma GCC target ("sse4")
#pragma optimize("fast-math")

#include <bits/stdc++.h>
#include <stdio.h>

using namespace std;
#define endl '\n'
#define ull unsigned long long
#define si short int
#define ll long long
#define ld long double
#define pb push_back
#define pii pair<int, int>
#define pdd pair<double, double>
#define pil pair<int, ll>
#define pli pair<ll, int>
#define pll pair<ll, ll>
#define piii pair<pair<int, int>, int>
#define all(vec) (vec).begin(), (vec).end()
#define rall(vec) (vec).rbegin(), (vec).rend()
#define piiii pair<pair<int, int>, pair<int, int>>
struct kek{
    int a,b,c,d;
};




vector<kek> arr;
int ans=0;
void gogo(int n, int m, int kolvo, vector<int> &now, int last){
    if(kolvo==n){
        int sm=0;
        for(int j=0;j<arr.size();j++){
            if(now[arr[j].b-1]-now[arr[j].a-1]==arr[j].c){
                sm+=arr[j].d;
            }
        }
        ans=max(ans, sm);
        return;
    }
    for(int i=last;i<=m;i++){
        now[kolvo]=i;
        gogo(n,m,kolvo+1, now, i);
    }

}
void solve() {
    int n,k;
    cin>>n>>k;
    vector<int> ans(n+1);
    for(int i=0;i<k;i++){
        int a;
        cin>>a;
        for(int j=0;j<a;j++){
            int b;
            cin>>b;
            ans[b]++;
        }
    }
    int kek=0;
    for(int i=1;i<=n;i++){
        if(ans[i]==0) kek++;
    }
    cout<<kek;
}

void testcases(int n) {
    n = 1 - n;
    if (!n) cin >> n;
    for (int i = 0; i < n; i++) {
        solve();
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    //freopen("C:\\Users\\Maximus\\CLionProjects\\Codeforces\\BestTeam\\output.txt", "r", stdin);
    //f=fopen("C:\\Users\\Maximus\\CLionProjects\\Codeforces\\BestTeam\\output.txt", "w");
    //freopen("C:\\Users\\Maximus\\CLionProjects\\Codeforces\\BestTeam\\output.txt", "w", stdout);

    unsigned int beg_time = clock();
    testcases(0);
    // 0 - no t, 1 - with t

    unsigned int end_time = clock();
    //cout << endl << endl << end_time - beg_time;
    return 0;
}

Measured memory_bytes: 3680
/// kAAzuki Hoshino
/*
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define int long long
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef vector<pi> vpi;
#define inf 1000000000
#define mod 1000000007
#define dmp(x) cerr<<"line "<<__LINE__<<" "<<#x<<":"<<x<<endl
#define fs first
#define sc second
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define mt make_tuple
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){
	return o<<"("<<p.fs<<","<<p.sc<<")";
}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){
	o<<"{";
	for(const T& v:vc) o<<v<<",";
	o<<"}";
	return o;
}

ordered_set s;

int a,b;


signed main(){
IOS;
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);

        cin >> a >> b;
        int ans = max( a*b, a+b );
        ans = max(ans, a-b);
        cout << ans << endl;



return 0;
}
///....


Measured memory_bytes: 256
#include <algorithm>
#include <bits/stdc++.h>
#include <cstdint>
#include <iostream>
#include <iterator>
#include <vector>

// lib/util.hpp
#ifndef UTIL_HPP
#define UTIL_HPP


typedef ::std::int_fast64_t i64;
typedef ::std::uint_fast64_t u64;
typedef ::std::int_fast32_t i32;
typedef ::std::uint_fast32_t u32;

namespace tools {
  template <typename T>
  void read(::std::istream& is, ::std::vector<T>& vector, const typename ::std::vector<T>::size_type size) {
    vector.reserve(size);
    ::std::copy_n(::std::istream_iterator<T>(is), size, ::std::back_inserter(vector));
  }
  template <typename T>
  void read(::std::vector<T>& vector, const typename ::std::vector<T>::size_type size) {
    ::tools::read(::std::cin, vector, size);
  }

  template <typename T, ::std::size_t N>
  void read(::std::istream& is, ::std::array<T, N>& array) {
    ::std::copy_n(std::istream_iterator<T>(is), N, array.begin());
  }
  template <typename T, ::std::size_t N>
  void read(::std::array<T, N>& array) {
    ::tools::read(::std::cin, array);
  }
}

#endif

// main.cpp

int main() {
  i64 N, A, B;
  std::string S;
  std::cin >> N >> A >> B >> S;

  i64 passed = 0;
  i64 rank_in_international_students = 1;
  for (const char& S_i : S) {
    switch (S_i) {
    case 'a':
      if (passed < A + B) {
        std::cout << "Yes" << std::endl;
        ++passed;
      } else {
        std::cout << "No" << std::endl;
      }
      break;
    case 'b':
      if (passed < A + B && rank_in_international_students <= B) {
        std::cout << "Yes" << std::endl;
        ++passed;
      } else {
        std::cout << "No" << std::endl;
      }
      ++rank_in_international_students;
      break;
    case 'c':
      std::cout << "No" << std::endl;
      break;
    }
  }

  return 0;
}

Measured memory_bytes: 896
#include <iostream>
#include <string>
using namespace std;
const int MAX = 10000;

int main(int argc, char* argv[]) {
    int n;
    cin >> n;
    int A[n], B[n], C[MAX];
    for (int i = 0; i < MAX; i++) C[i] = 0;
    for (int i = 0; i < n; i++){
        cin >> A[i];
        C[A[i]]++;
    }
    for (int i = 1; i < MAX; i++) C[i] = C[i] + C[i-1];
    for (int i = n-1; i >= 0; i--){
        B[C[A[i]]] = A[i];
        C[A[i]]--;
    }
    for (int i = 1; i < n; i++) cout << B[i] << " ";
    cout << B[n] << "\n";
    return 0;
}



Measured memory_bytes: 18764
N = int(input())
S = input()
ans = 3 * 10 ** 5
w = S.count('W')
w_r = 0

for i, a in enumerate(S):
	if a == 'W':
		w_r += 1
		ans = min(ans, 2*w_r+N-w-i-2)
	else:
		ans = min(ans, 2*w_r+N-w-i-1)
	

print(ans)

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

const int INF = 100000000;
typedef pair<int, int> P;
const int MAX_H = 50, MAX_W = 50;
int H, W;
int sy, sx;
int gy, gx;
char maze[MAX_H][MAX_W];

int d[MAX_H][MAX_W];

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

int bfs();

int main()
{
  cin >> H >> W;
  for (int i = 0; i < H; i++)
  {
    for (int j = 0; j < W; j++)
    {
      cin >> maze[i][j];
    }
  }
  int cnt = 0;
  for (int i = 0; i < H; i++)
  {
    for (int j = 0; j < W; j++)
    {
      if (maze[i][j] == '#')
        cnt++;
    }
  }
  int res = bfs();
  if (res == INF)
    cout << -1 << endl;
  else
  {
    int ans = H * W - (cnt + res + 1);
    cout << ans << endl;
  }
}

int bfs()
{
  queue<P> que;
  for (int i = 0; i < H; i++)
  {
    for (int j = 0; j < W; j++)
    {
      d[i][j] = INF;
    }
  }
  sy = 0, sx = 0;
  gy = H - 1, gx = W - 1;
  que.push(P(sy, sx));
  d[sy][sx] = 0;
  while (que.size())
  {
    P p = que.front();
    que.pop();
    if (p.first == gy && p.second == gx)
    {
      break;
    }
    for (int i = 0; i < 4; i++)
    {
      int ny = p.first + dy[i], nx = p.second + dx[i];
      if (0 <= ny && ny < H && 0 <= nx && nx < W && maze[ny][nx] != '#' && d[ny][nx] == INF)
      {
        que.push(P(ny, nx));
        d[ny][nx] = d[p.first][p.second] + 1;
      }
    }
  }
  return d[gy][gx];
}

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
     
   // ll t;cin>>t;while(t--)
    {
        ll m,d;
        cin>>m>>d;
        if(d<=10)
        {
            cout<<0;
            exit(0);
        }
        ll ans=0;
        for(ll i=1;i<=m;i++)
        {
            for(ll j=12;j<=d;j++)
            {
                ll tmp=j;
                ll last=j%10;
                tmp/=10;
                ll first=tmp%10; 
                if(first<2 || last<2)
                    continue;
                if(first*last==i)
                    ans++;
            }
        }
        cout<<ans<<endl;
    }
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int main()

{
    int S,modulus,h,m,s;
    scanf("%d", &S);
    h=S/3600;
    modulus=S%3600;
    m=modulus/60;
    modulus=S%60;
    s=modulus;

    printf("%d:%d:%d\n",h,m,s,modulus);
    return 0;
}


Measured memory_bytes: 2104
#include <bits/stdc++.h>
#define MAXN 2010
#define pii pair<int,int>
#define ff first
#define ss second
#define ll long long
#define in_range(x, y, n) (x >= 0 and x<n and y >=0 and y<n)
using namespace std;
const ll mod = 1e9 + 7;

ll n, m, ps[MAXN][MAXN];

int main (){
    ios_base::sync_with_stdio(false);
    int a, b, c;

    cin >> a >> b >> c;

    if (a+b == c || a+c == b || b+c == a){
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
n=gets.strip.to_i
h=gets.strip.split.map(&:to_i)

result = 0
current = h.first
tmp_result = 0
(1...n).each do |i|
  next_height = h[i]
  if next_height <= current
    tmp_result+=1
  else
    result = tmp_result if tmp_result > result
    tmp_result=0
  end
  current = next_height
end
result = tmp_result if tmp_result > result

p result


Measured memory_bytes: 9732
N = int(input())
p = list(map(int, input().split()))

a = [0] * N
b = [0] * N
for i in range(N):
    a[p[i]-1] = p[i] * 22000 + 500000000
    b[p[i]-1] = -p[i] * 22000 + i + 500000000
print(*a)
print(*b)


Measured memory_bytes: 45332
#B - Digital Gifts(ABC119)
N=int(input())
X=[]
U=[]
s=0
for i in range(N):
    x,u=map(str, input().split())
    X.append(float(x))
    U.append(u)
for i in range(N):
    if U[i]=="JPY":
        s+=X[i]
    else:
        s+=X[i]*380000.0
print(s)

Measured memory_bytes: 3060
#include<stdio.h>
#include<string.h>
int main(){
	int i,j,k,m,h;
	char A[201],B[201],C[201];
	while(1){
		scanf("%s",A);
		if(strstr(A,"-")!=NULL)break;
		scanf("%d",&m);
		for(i=0;i<m;i++){
			scanf("%d",&h);
			for(j=0;j<h;j++)B[j]=A[j];
			B[h]='\0';
			for(k=0;k<strlen(A)-h;k++)C[k]=A[k+h];
			C[strlen(A)-h]='\0';
			strcat(C,B);
			strcpy(A,C);
		}
		printf("%s\n",C);
	}
	return 0;
}



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

// #define DEBUG
#ifdef DEBUG
#define debug(fmt, ...) printf(fmt, ##__VA_ARGS__)
#else
#define debug(fmt, ...)
#endif

/*
 012
0012
1101
2210


5 \in {0,1}
a b c d e
a+b,b+c,c+d,d+e
a+2b+c,b+2c+d,c+2d+e
a+3b+3c+d,b+3c+3d+e
a+4b+6c+4d+e

1
11
101
1111
10001
110011
1010101
11111111
100000001
1100000011
10100000101
111100001111
1000100010001
11001100110011
101010101010101
1111111111111111

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

	int N;
	char tmp;
	char dummy;
	scanf("%d%c", &N, &dummy);
	debug("N=%d\n", N);
	vector<int> A(N);
	vector<int> B(N - 1);
	for (int i = 0; i < N; i++) {
		scanf("%c", &tmp);
		A[i] = tmp - '0';
		debug("%d ", A[i]);
	}
	debug("\n");
	bool flag_01 = false;
	for (int i = 0; i < N - 1; i++) {
		B[i] = abs(A[i] - A[i + 1]);
		if (flag_01 == false && B[i] == 1) {
			flag_01 = true;
		}
		debug("%d ", B[i]);
	}
	debug("\n");
	if (!flag_01) {
		for (int i = 0; i < N - 1; i++) {
			B[i] /= 2;
		}
	} else {
		for (int i = 0; i < N - 1; i++) {
			B[i] %= 2;
		}
	}

	debug("----01----\n");
	int num = N - 1;  //今何要素か
	int group;
	vector<int> new_B(N - 1);
	while (num > 1) {
		for (int i = 0; i < num; i++) {
			debug("%d ", B[i]);
		}
		debug("\n");

		group = int(exp2(floor(log2(num))));
		debug("group = %d\n", group);
		new_B[0] = 0;
		for (int i = 0; i < group; i++) {
			new_B[0] ^= B[i];
		}
		// debug("%d", new_B[0]);

		for (int i = 1; i < num - group + 1; i++) {
			new_B[i] = new_B[i - 1] ^ B[i - 1] ^ B[i + group - 1];
			// debug("_%d", new_B[i]);
		}
		// debug("\n");

		for (int i = 0; i < num - group + 1; i++) {
			B[i] = new_B[i];
			debug("%d ", B[i]);
		}
		debug("\n");

		num = num - group + 1;
	}

	debug("result:");
	if (flag_01) {
		printf("%d", B[0]);
	} else {
		printf("%d", B[0] * 2);
	}

	return 0;
}

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

int main() {
  int N;
  cin >> N;
  vector<int> W(N);
  for (int i = 0; i < N; ++i) {
    cin >> W.at(i);
  }
  int mn = INT_MAX;
  for (int i = 0; i < N - 1; ++i) {
    int sum1 = accumulate(W.begin(), W.begin() + i + 1, 0);
    int sum2 = accumulate(W.begin() + i + 1, W.end(), 0);
    mn = min(mn, abs(sum1 - sum2));
  }
  cout << mn << endl;
}


Measured memory_bytes: 256
N = int(input())
a = list(map(int,input().split()))
 
res = "No"
a_set = list(set(a))
 

 
if len(a_set) == 3:
    if a_set[0] ^ a_set[1] == a_set[2]:
        if a.count(a_set[0]) == a.count(a_set[1]) and a.count(a_set[0]) == a.count(a_set[2]):
            res = "Yes"
if len(a_set) == 1:
    if a_set[0] == 0:
        res = "Yes"
if len(a_set) == 2:
    if 0 in a_set:
        if N%3 == 0 and a.count(0) == N/3:
            res = "Yes"
print(res)

Measured memory_bytes: 14120
s = str(input())
A = int(s[0:2]); B = int(s[2:4])
if 1 <= A <= 12 and 1 <= B <= 12:
    print("AMBIGUOUS")
elif 1 <= A <= 12 and 0 <= B <= 99:
    print("MMYY")
elif 1 <= B <= 12 and 0 <= A <= 99:
    print("YYMM")
else:
    print("NA")

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

int main() {
  string s;
  cin >> s;
  reverse(s.begin(), s.end());
  int d = s.size();
  vector<int> n(d);
  for (int i = 0; i < d; i++) n.at(i) = s.at(i) - '0';
  n.push_back(0);
  vector<int> dp0(d + 1), dp1(d + 1);
  dp0.at(0) = n.at(0);
  dp1.at(0) = 10 - n.at(0);
  for (int i = 1; i <= d; i++) {
    dp0.at(i) = min(dp0.at(i - 1) + n.at(i), dp1.at(i - 1) + n.at(i) + 1);
    dp1.at(i) = min(dp0.at(i - 1) + (10 - n.at(i)), dp1.at(i - 1) + (9 - n.at(i)));
  }
  cout << min(dp0.at(d), dp1.at(d)) << endl;
}


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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	long long N, K;
	cin >> N >> K;
	long long a[110000], x, y;
	for (int i = 0; i < N; i++) {
		cin >> x >> y;
		a[i] = 100000 * x + y-1;
	}
	sort(a, a + N);
	int i = 0;
	while (K > 0) {
		K -= a[i] % 100000+1;
		i++;
	}
	cout << a[i - 1] / 100000;
}

Measured memory_bytes: 1024
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<iomanip>
#include<cmath>


#define REP(i,n) for (int i = 0; (i) < (n); ++ (i))
#define FOR(i,n) for (int i = 1; (i) <= (n); ++ (i))
#define dump(x)  cout << #x << " = " << (x) << endl;
#define pb push_back
#define lint long long

const int INF = 1e9;
const int MOD = 1e9+7;
const lint LINF = 1e18;
const double eps = 0.000000001;//もとの値の10^(-16)まで


using namespace std;
int a,b,c,d;
int sosuu[2000];
int prime[2000];
int ans[2000];


void furui(){
  REP(i,1001) prime[i] = 1;
  prime[0] = 0;
  prime[1] = 0;
  int num = 0;
  for(int i=1;i<=1000;i++){
    if(prime[i]==1){
      sosuu[num] = i;
      num ++;
      for(int j=i+i;j<=1000;j += i){
        prime[j] = 0;
      }
    }
  }
  //dump(sosuu[0]);
  //dump(num);
}

int main(){
  int n;
  cin >> n;
  furui();
  for(int i=1;i<=n;i++){
    int tt = i;
    int k = 0;
    while(tt!=1){
      while(tt%sosuu[k]==0){
        tt /= sosuu[k];
        ans[k] ++;
      }
      k++;
    }
  }
  lint ans2 = 1;
  for(int i=0;i<=500;i++){
    ans2 *= ans[i]+1;
    ans2%= MOD;
  }
  cout << ans2 << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ALL(V) (V).begin(), (V).end()
#define ALLR(V) (V).rbegin(), (V).rend()
// #define DEBUGGING

template <typename T> using V = vector<T>;
template <typename T> using VV = V<V<T>>;
template <typename T, typename U> using P = pair<T, U>;
using ll = int64_t;
using PLL = P<ll, ll>;

template <typename T> const T& var_min(const T &t) { return t; }
template <typename T> const T& var_max(const T &t) { return t; }
template <typename Head, typename... Tail> const Head& var_min(const Head &head, const Tail&... tail) { return min(head, var_min(tail...)); }
template <typename Head, typename... Tail> const Head& var_max(const Head &head, const Tail&... tail) { return max(head, var_max(tail...)); }
template <typename T, typename... Tail> void chmin(T &t, const Tail&... tail) { t = var_min(t, tail...); }
template <typename T, typename... Tail> void chmax(T &t, const Tail&... tail) { t = var_max(t, tail...); }

namespace __init {

struct InitIO {
    InitIO() {
        cin.tie(nullptr);
        ios_base::sync_with_stdio(false);
        cout << fixed << setprecision(30);
    }
} init_io;

}

#ifdef DEBUGGING
#include "../debug.cpp"
#else
#define DEBUG(...) 0
#define DEBUG_SEPARATOR_LINE 0
#endif

template <typename T>
T make_v(T init) { return init; }

template <typename T, typename... Tail>
auto make_v(T init, size_t s, Tail... tail) {
#define rec make_v(init, tail...)
    return V<decltype(rec)>(s, rec);
#undef rec
}

ll dsum(ll n) {
    ll ret = 0;
    while(n) {
        ret += n % 10;
        n /= 10;
    }
    return ret;
}

int main() {
    ll K;
    ll N = 1;
    cin >> K;

    auto print = [&] {
        cout << N << endl;
        K--;
        N++;
    };

    print();

    while(K) {
        V<PLL> vec;
        ll mul = 1;
        for(ll i = 1; i <= 15; i++) {
            ll val = mul * (N / mul + 1) - 1;
            vec.emplace_back(val, dsum(val));
            mul *= 10;
        }

        sort(ALL(vec),
             [](PLL a, PLL b) {
                 ll v1 = a.first * b.second;
                 ll v2 = a.second * b.first;
                 if(v1 != v2) return v1 < v2;
                 else return a.first < b.first;
             });
        N = vec[0].first;
        print();
    }
    return 0;
}


Measured memory_bytes: 256
#!/usr/bin/env fsharpi

open System;

let ParseIntN ( str : string ) =
    str.Split(' ')
    |> Array.map System.Int32.Parse

let ParseInt1 ( str : string ) =
    ParseIntN str |> fun arr -> arr.[0]

let ParseInt2 ( str : string ) =
    ParseIntN str |> fun arr -> (arr.[0],arr.[1])

let ParseInt3 ( str : string ) =
    ParseIntN str |> fun arr -> (arr.[0],arr.[1],arr.[2])

let ReadLinesN ( n : int ) =
    fun _ -> Console.ReadLine()
    |> Seq.initInfinite
    |> Seq.take n

let ReadLines =
    fun _ -> Console.ReadLine()
    |> Seq.initInfinite
    |> Seq.takeWhile ((<>) null)

module String =
    /// Converts a string into a list of characters.
    let explode (s:string) =
        [for c in s -> c]

    /// Converts a list of characters into a string.
    let implode (xs:char list) =
        let sb = System.Text.StringBuilder(xs.Length)
        xs |> List.iter (sb.Append >> ignore)
        sb.ToString()

Console.ReadLine() |> ignore
Console.ReadLine()
|> String.explode
|> List.fold (fun (acc,mv) c -> let nacc = acc + if c = 'I' then 1 else -1
                                (nacc, max mv nacc)) (0,0)
|> fun (_,mv) -> Console.WriteLine (sprintf "%d" mv )


Measured memory_bytes: 14168
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using vec=vector<ll>;
using mat=vector<vec>;
#define For(i,a,b) for(i=a;i<b;i++)
#define rep(i,N) For(i,0,N)
#define rep1(i,N) For(i,1,N)
#define all(v) (v).begin(),(v).end()
#define allr(v) (v).rbegin(),(v).rend()
#define vsort(v) sort(all(v))
#define vrsort(v) sort(allr(v))
#define mod 1000000007
using datas=pair<ll,ll>;
using tdata=pair<datas,ll>;

long mmid(long a,long b,long c){return a<b?(b<c?b:max(a,c)):(b>c?b:min(a,c));}

ll modinv(ll a) {
  ll b=mod,u=1,v=0,t;
  while(b){
    t=a/b;
    a-=t*b; swap(a,b);
    u-=t*v; swap(u,v);
  }
  return (u+mod)%mod;
}

ll moddevide(ll a,ll b){return (a*modinv(b))%mod;}

ll modncr(ll n,ll r){
  ll i,plus=1;
  rep(i,r){
    plus=(plus*(n-i))%mod;
    plus=moddevide(plus,i+1);
  }
  return plus;
}

ll modncrlistp[200000],modncrlistm[200000];

ll modncrs(ll n,ll r){
  ll i,j;
  if(modncrlistp[n]==0){
    for(i=n;i>=0;i--){
      if(modncrlistp[i])break;
    }
    if(i<0){
      modncrlistp[0]=1;
      rep1(i,n+1){
        modncrlistp[i]=(modncrlistp[i-1]*i)%mod;
      }
    }else{
      For(j,i+1,n+1){
        modncrlistp[j]=(modncrlistp[j-1]*j)%mod;
      }
    }
  }
  if(modncrlistm[n]==0){
    for(i=n;i>=0;i--){
      if(modncrlistm[i])break;
    }
    if(i<0){
      modncrlistm[0]=1;
      rep1(i,n+1){
        modncrlistm[i]=(modncrlistm[i-1]*modinv(i))%mod;
      }
    }else{
      For(j,i+1,n+1)modncrlistm[j]=(modncrlistm[j-1]*modinv(j))%mod;
    }
  }
  return (((modncrlistp[n]*modncrlistm[r])%mod)*modncrlistm[n-r])%mod;
}

ll euclidean_gcd(ll a, ll b) {
  if(a<b) return euclidean_gcd(b, a);
  ll r;
  while ((r=a%b)){a=b;b=r;}
  return b;
}

ll countdigits(ll n){
  ll ans=0;
  while(n){n/=10;ans++;}
  return ans;
}

ll sumdigits(ll n){
  ll ans=0;
  while(n){ans+=n%10;n/=10;}
  return ans;
}

void printmap(vector<ll>& a,ll H,ll W){
  ll i,j;
  For(i,0,H+2){
    For(j,0,W+2){cout<<a[i*(W+2)+j];}
    cout<<endl;
  }
}
void inputmap(vector<ll>& a,ll H,ll W){
  ll i,j;
  string ss;
  For(i,1,H+1){
    cin>>ss;
    For(j,1,W+1){
      if(ss[j-1]=='#'){
        a[i*(W+2)+j]=1;
      }else{
        a[i*(W+2)+j]=0;
      }
    }
  }
}

int main(){
  ll i,j,N,M,K=0;
  string ss,tt;cin>>ss>>tt;
  rep(i,3){
    if(ss[i]==tt[i])K++;
  }
  cout<<K<<endl;
  return 0;
}

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

int main() {
  int n;cin>>n;
  string s;cin>>s;
  ll cnt=0;
  int an[n+1][3];
  rep(i,3) an[n][i]=0;
  string rgb = "RGB";
  rep(i,n) rep(k,3) {
    if (s[n-1-i]==rgb[k]) an[n-1-i][k] = an[n-i][k] + 1;
    else an[n-1-i][k] = an[n-i][k];
  }
  rep(i,n-2) {
    for (int j=i+1; j<n-1; j++) {
      if (s[i]==s[j]) continue;
      rep(k, 3) {
        if (s[i] != rgb[k] && s[j] != rgb[k]) {
          cnt += an[j+1][k];
          if (j+j-i < n && s[j+j-i] == rgb[k]) cnt --;
        }
      }
    }
  }
  cout << cnt;
}


Measured memory_bytes: 3668
#include <iostream>
#include <iomanip>
#include <sstream>
#include <vector>
#include <string>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <functional>
#include <iterator>
#include <limits>
#include <numeric>
#include <utility>
#include <cmath>
#include <cassert>
#include <cstdio>

using namespace std;
using namespace placeholders;

using LL = long long;
using ULL = unsigned long long;
using VI = vector< int >;
using VVI = vector< vector< int > >;
using VS = vector< string >;
using SS = stringstream;
using PII = pair< int, int >;
using VPII = vector< pair< int, int > >;
template < typename T = int > using VT = vector< T >;
template < typename T = int > using VVT = vector< vector< T > >;
template < typename T = int > using LIM = numeric_limits< T >;

template < typename T > inline istream& operator>>( istream &s, vector< T > &v ){ for ( T &t : v ) { s >> t; } return s; }
template < typename T > inline ostream& operator<<( ostream &s, const vector< T > &v ){ for ( int i = 0; i < int( v.size() ); ++i ){ s << ( " " + !i ) << v[i]; } return s; }
template < typename T > inline T fromString( const string &s ) { T res; istringstream iss( s ); iss >> res; return res; }
template < typename T > inline string toString( const T &a ) { ostringstream oss; oss << a; return oss.str(); }

#define REP2( i, n ) REP3( i, 0, n )
#define REP3( i, m, n ) for ( int i = ( int )( m ); i < ( int )( n ); ++i )
#define GET_REP( a, b, c, F, ... ) F
#define REP( ... ) GET_REP( __VA_ARGS__, REP3, REP2 )( __VA_ARGS__ )
#define FOR( e, c ) for ( auto &&e : c )
#define ALL( c ) begin( c ), end( c )
#define AALL( a, t ) ( t* )a, ( t* )a + sizeof( a ) / sizeof( t )
#define DRANGE( c, p ) ( c ).begin(), ( c ).begin() + ( p ), ( c ).end()

#define SZ( v ) ( (int)( v ).size() )
#define EXIST( c, e ) ( ( c ).find( e ) != ( c ).end() )

template < typename T > inline bool chmin( T &a, const T &b ){ if ( b < a ) { a = b; return true; } return false; }
template < typename T > inline bool chmax( T &a, const T &b ){ if ( a < b ) { a = b; return true; } return false; }

#define PB push_back
#define EM emplace
#define EB emplace_back
#define BI back_inserter

#define MP make_pair
#define fst first
#define snd second

#define DUMP( x ) cerr << #x << " = " << ( x ) << endl

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );
	cout << setprecision( 12 ) << fixed;

	string S;
	cin >> S;
	S.insert( 4, " " );
	cout << S << endl;

	return 0;
}


Measured memory_bytes: 256