Harryxun/stf_run huggingface dataset:
import array

class UnionFind :
    def __init__(self, n):
        self.par = array.array('i', range(n))


    def root(self, i):
        if i == self.par[i]:
            return i
        else:
            r = self.root(self.par[i])
            self.par[i] = r
            return r


    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if(rx == ry):
            return
        self.par[rx] = ry
        self.root(x)

    def same(self, x, y) :
        return self.root(x) == self.root(y)

    def debug(self):
        print(self.par)

if __name__ == '__main__':
    main()

def main():
    (n,m) = map(int, input().split())
    ab = []
    for i in range(m):
        (a,b) = map(int, input().split())
        ab.append((a-1,b-1))
    ab = ab[::-1]
    uf = UnionFind(n)
    res = []
    for (a,b) in ab:
        res.append(calcScore(uf, n))
        uf.unite(a,b)
    for i in range(m):
        res[i] = ((n*(n-1)) // 2) - res[i]
    res = res[::-1]
    for r in res:
        print(r)

def calcScore(uf, n):
    nroots = array.array('i', [0] * n)
    for i in range(n):
        root = uf.root(i)
        nroots[root] = nroots[root] + 1
    res = 0
    for r in nroots:
        res = res + (r * (r-1)) // 2
    return res


### FIXED CODE ###

import array
import time

class UnionFind :
    def __init__(self, n):
        self.par = array.array('i', range(n))
        self.sizes = array.array('i', [1]*n)
        self.rank = array.array('i', [0]*n)


    def root(self, i):
        if i == self.par[i]:
            return i
        else:
            r = self.root(self.par[i])
            self.par[i] = r
            return r

    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        srx = self.sized(x)
        sry = self.sized(y)
        if rx != ry:
            if self.rank[rx] < self.rank[ry]:
                self.par[rx] = ry
            else:
                self.par[ry] = rx
                if self.rank[rx] == self.rank[ry]:
                    self.rank[rx] = self.rank[rx] + 1
            self.sizes[self.root(rx)] = srx + sry

    def same(self, x, y) :
        return self.root(x) == self.root(y)

    def sized(self, x):
        return self.sizes[self.root(x)]

    def debug(self):
        print(self.par)
        print(self.sizes)

def calsc(x):
    return (x * (x-1)) // 2

def main():
    (n,m) = map(int, input().split())
    ab = []
    for _ in range(m):
        (p,q) = map(int, input().split())
        ab.append((p-1,q-1))
    uf = UnionFind(n)
    res = []
    prev = 0
    while len(ab) > 0:
        (a,b) = ab.pop()
        #uf.debug()
        res.append(prev)
        score = prev
        if not uf.same(a,b):
            score = score - calsc(uf.sized(a)) - calsc(uf.sized(b))
            uf.unite(a,b)
            score = score + calsc(uf.sized(a))
        prev = score
    for i in range(len(res)):
        res[i] = calsc(n) - res[i]
    res = res[::-1]
    for r in res:
        print(r)

if __name__ == '__main__':
    main()
c = 0
while True:
    x == int(input())
    if x == 0:
        break;
    c += 1
    print('Case', str(c) + ':', x)

### FIXED CODE ###

c = 0
while True:
    x = int(input())
    if x == 0:
        break;

    c += 1
    print('Case', str(c) + ':',  x)
a,b = map(int(input().split()))
if a <= 0 <= b:
    print('Zero')
elif b < 0 and b%2 == a%2:
    print('Negative')
else:
    print("Positive")

### FIXED CODE ###

a,b = map(int,input().split())
if a <= 0 <= b:
        print("Zero")

elif b < 0 and (b-a)%2 == 0:
        print("Negative")
else:
        print("Positive")
N = int(input())
M = [0]*N
for i in range(N-1):
    M[i+1] = M[i] + i + 1
print(M[-1])

### FIXED CODE ###

from decimal import *
N = int(input())

print(int(Decimal(Decimal(N-1)/2*Decimal(N))))
visited=[False]*(10**6+1)

N=int(input())
A=list(map(int,input().split()))
A.sort()

if A[1]==1:
  print(0)
  exit()
if A[0]==1:
  print(1)
  exit()
ans=0
for i in range(N):
  if visited[A[i]]:
    continue
  if i < N-1 and A[i]==A[i+1]:
    continue
  ans+=1
  index=1
  while A[i]*index<=10**6:
    visited[A[i]*index]=True
    index+=1
    
print(ans)

### FIXED CODE ###

visited=[False]*(10**6+1)

N=int(input())
A=list(map(int,input().split()))
A.sort()

if N>=2 and A[1]==1:
  print(0)
  exit()
if A[0]==1 or N == 1:
  print(1)
  exit()
  
ans=0
for i in range(N):
  if visited[A[i]]:
    continue
  if i < N-1 and A[i]==A[i+1]:
    index = 1
    while A[i]*index<=10**6:
      visited[A[i]*index]=True
      index+=1
    continue
  ans+=1
  index=1
  while A[i]*index<=10**6:
    visited[A[i]*index]=True
    index+=1
    
print(ans)
l,n=map(int,input().split())
tree=[]
for i in range(n):
  k=int(input())
  tree.append(k)

reverse_tree=[l-i for i in tree]
position=0
ans=0

while len(tree)>0:
  if (tree[0]-position >= reverse_tree[0]+position):
  ans+= tree[0]-position
  position=tree.pop(tree[0])
  reverse_tree.pop(reverse_tree[-1])
else:
  ans+= reverse_tree[0]+position
  position=l-reverse_tree.pop(reverse_tree[0])
  tree.pop(tree[-1])
  
print(ans)


### FIXED CODE ###

import sys
from collections import deque
l,n=map(int,input().split())
c=n
tree1=[int(i) for i in sys.stdin]
reversed_tree1=[l-i for i in reversed(tree1)]
tree=deque(tree1)
reversed_tree=deque(reversed_tree1)
if n%2 == 0:
  ans= sum(tree1)*2 + l*(n-1) +tree1[n//2] - sum(tree1[n//2:])*4
  ans2= sum(reversed_tree1)*2 + l*(n-1) +reversed_tree1[n//2] - sum(reversed_tree1[n//2:])*4
  n-=1
  c-=1
  ans3= ans-tree.popleft()*2-l+tree[n//2]*2
  ans= max(ans,ans3)
  ans4= ans2-reversed_tree.popleft()*2-l+(reversed_tree[n//2])*2
  ans2= max(ans2,ans4)
else:
  ans= sum(tree1)*2 + l*(n-1) - tree1[n//2] - sum(tree1[((n//2)+1):])*4
  ans3=ans
  ans2= sum(reversed_tree1)*2 + l*(n-1) - reversed_tree1[n//2] - sum(reversed_tree1[((n//2)+1):])*4
  ans4=ans2
for i in range(n//2):
  n-=1
  ans_stack= ans3-tree.popleft()*2-l+tree[(n-1)//2]+tree[(n+1)//2]
  ans= max(ans_stack,ans)
  ans3=ans_stack
  n-=1
  ans_stack= ans3-tree.popleft()*2-l+tree[n//2]*2
  ans=max(ans_stack,ans)
  ans3=ans_stack
n=c
for i in range(n//2):
  n-=1
  ans_stack= ans4-reversed_tree.popleft()*2-l+reversed_tree[(n-1)//2]+reversed_tree[(n+1)//2]
  ans2=max(ans_stack,ans2)
  ans4=ans_stack
  n-=1
  ans_stack= ans4-reversed_tree.popleft()*2-l+reversed_tree[n//2]*2
  ans2=max(ans2,ans_stack)
  ans4=ans_stack
print(max(ans,ans2))
H,W = map(int, input().split())
List = []
queue = [(0,0)]
shape = 0
for i in range(H):
    x = input()
    shape += x.count('#')
    List.append(x)
while(len(queue) != 0):
    x,y = queue[0]
    queue.pop(0)
    if(x == H-1 and y == W-1):
        flag = 1
        break
    if(x < H-1):
        if(List[x+1][y] == '.'):
            queue.append((x+1,y))
    if(y < W-1):
        if(List[x][y+1] == '.'):
            queue.append((x,y+1))
if(flag == 1):
    print(H*W - (H-1 + W-1 + 1) - shape)
else:
    print(-1)


### FIXED CODE ###

H,W = map(int, input().split())
List = []
queue = [(0,0,1)]
shape = 0
used ={(0,0)}
for i in range(H):
    x = input()
    shape += x.count('#')
    List.append(x)

def check(x,y,c):
    if(x>W-1 or y>H-1 or x<0 or y<0):
        return
    if(List[y][x] == '#'):
        return
    if(x,y) in used:
        return
    queue.append((x,y,c+1))
    used.add((x,y))

flag = -1
while(len(queue) != 0):
    x,y,c = queue[0]
    if x==W-1 and y==H-1:
        flag = 1
        break
    queue.pop(0)
    check(x+1,y,c)
    check(x, y+1,c)
    check(x-1,y,c)
    check(x, y-1,c)
if(flag == 1):
    print(H*W - c - shape)
else:
    print(-1)
N = int(input())
h = [i for i in map(int, input().split())]    
def jump(point):
    if point <= 0:
        return 0
    if memo[point] != inf:
        return memo[point]
    memo[point] = min(jump(point-1)+abs(h[point-1]-h[point]), jump(point-2)+abs(h[point-2]-h[point]))
    return min(jump(point-1)+abs(h[point-1]-h[point]), jump(point-2)+abs(h[point-2]-h[point]))
    
inf = 10**10
memo = [inf]*(N+2)

print(jump(N-2))

### FIXED CODE ###

N = int(input())
h = [i for i in map(int, input().split())]    
memo = [0] * (N+1)
for i in range(N):
    if i == 0:
        pass
    elif i == 1:
        memo[1] = abs(h[1]-h[0])
    else:
        memo[i] = min(memo[i-1]+abs(h[i]-h[i-1]),  memo[i-2]+abs(h[i]-h[i-2]))
print(memo[N-1])
from math import sqrt
n, k = map(int, input().split())
a = list(map(int, input().split()))
s = sum(a)
div = []
for i in range(1, int(sqrt(s)+1)):
	if s%i == 0:
		if i*i != s:
			div.append(s//i)
		div.append(i)
div.sort(reverse=True)
#print(div)

for d in div:
	plus, minus = [], []
	for x in a:
		if x%d == 0:
			continue
		plus.append(d-(x%d))
		minus.append(x%d)
	if min(sum(plus)-max(plus), sum(minus)-max(minus)) <= k:
		print(d)
		break

### FIXED CODE ###

from math import sqrt
n, k = map(int, input().split())
a = list(map(int, input().split()))
s = sum(a)
div = []
for i in range(1, int(sqrt(s)+1)):
	if s%i == 0:
		if i*i != s:
			div.append(s//i)
		div.append(i)
div.sort(reverse=True)
#print(div)

for d in div:
	b = [x%d for x in a if x%d != 0]
	if not b:
		print(d)
		break
	b.sort(key=lambda x: x%d)
	y, z = 0, d*len(b)-sum(b)
	res = 10**30
	for x in b:
		y += x
		z -= d-x
		res = min(res, max(y, z))
	if res <= k:
		print(d)
		break
n = int(input())
for i in range(int(n**0.5))[::-1]:
    if n%i == 0:
        print(i + n//i - 2)
        break

### FIXED CODE ###

import math
n = int(input())
ans = float('inf')
for i in range(1,10**6 + 1)[::-1]:
    if n%i == 0:
        ans = min(ans,i + n//i - 2)

print(ans)
n  = []
while True:
    try:
        n.append(int(raw_input()))
    except:
        break

R = max(n)+1
p = [1]*R
p[0] = p[1] = 0
i = 2
while i <= R**0.5:
    if p[i]:
        p[2*i::i] = [0]*((R-2*i)/i)
    i += p[i+1:].index(1)+1
for i in n:
    print sum(p[:i+1])

### FIXED CODE ###

import math
n = []
while True:
    try:
        n.append(int(raw_input()))
    except:
        break
  
r = max(n)+1
sqrt = int(math.sqrt(r))
p = [1]*r
p[0] = 0
p[3::2] = [0 for x in range(3,r,2)]
for i in range(2,sqrt,2):
    if p[i]:
        p[2*i+1::i+1] = [0 for x in range(2*i+1,r,i+1)] 
  
for i in n:
     print sum(p[:i])
import sys
from functools import reduce
from math import gcd

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def eratosthenes(n):
    prime = [2]
    if n == 2:
        return prime
    limit = int(n ** 0.5)
    data = [i + 1 for i in range(2, n, 2)]
    res = [0] * (n + 1)
    res[1] = 1
    for i in range(2, n + 1, 2):
        res[i] = 2
    while True:
        p = data[0]
        if limit <= p:
            return res
        prime.append(p)
        res[p] = p
        for e in data:
            if e % p == 0:
                res[e] = p
        data = [e for e in data if e % p != 0]


def solve():
    _ = int(rl())
    A = list(map(int, rl().split()))
    
    prime_fact = eratosthenes(10 ** 6)
    p_flg = True
    prime_fact_set = set()
    for ai in A:
        num = ai
        prime_fact_ai = set()
        while num != 1:
            prime_fact_ai.add(prime_fact[num])
            num //= prime_fact[num]
        for p in prime_fact_ai:
            if p in prime_fact_set:
                p_flg = False
                break
            prime_fact_set.add(p)
        if not p_flg:
            break
    
    if p_flg:
        print('pairwise coprime')
        return
    
    gcd_a = reduce(gcd, A)
    if gcd_a == 1:
        print('setwise coprime')
        return
    
    print('not coprime')


if __name__ == '__main__':
    solve()


### FIXED CODE ###

import sys
from functools import reduce
from math import gcd

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def eratosthenes(n):
    prime = [2]
    if n == 2:
        return prime
    limit = int(n ** 0.5)
    data = [i + 1 for i in range(2, n, 2)]
    res = [0] * (n + 1)
    res[1] = 1
    for i in range(2, n + 1, 2):
        res[i] = 2
    while True:
        p = data[0]
        if limit <= p:
            for e in data:
                res[e] = e
            return res
        prime.append(p)
        res[p] = p
        for e in data:
            if e % p == 0:
                res[e] = p
        data = [e for e in data if e % p != 0]


def solve():
    _ = int(rl())
    A = list(map(int, rl().split()))
    
    prime_fact = eratosthenes(10 ** 6)
    p_flg = True
    prime_fact_set = set()
    for ai in A:
        num = ai
        prime_fact_ai = set()
        while num != 1:
            prime_fact_ai.add(prime_fact[num])
            num //= prime_fact[num]
        for p in prime_fact_ai:
            if p in prime_fact_set:
                p_flg = False
                break
            prime_fact_set.add(p)
        if not p_flg:
            break
    
    if p_flg:
        print('pairwise coprime')
        return
    
    gcd_a = reduce(gcd, A)
    if gcd_a == 1:
        print('setwise coprime')
        return
    
    print('not coprime')


if __name__ == '__main__':
    solve()
a, b, c, d=map(int,input().split)
k1=abs(a-b)
k2=abs(a-c)
k3=abs(b-c)
if k2<=d:
  print("Yes")
elif k1<=d || k2<=d:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

a, b, c, d=map(int,input().split())
k1=abs(a-b)
k2=abs(a-c)
k3=abs(b-c)
if k2<=d:
  print("Yes")
elif k1<=d and k3<=d:
  print("Yes")
else:
  print("No")
FILE = open("coderData.txt", 'r')

def raw_input():
    return FILE.readline()

N,C,K = map(int, raw_input().split(" "))
timelist = []
for i in range(0, N):
    timelist.append(int(raw_input()))
timelist.sort()


class Foo:

    timelist = []
    buslist = []
    firstId = 0
    capacity = 0

    def __init__(self, timelist):
        self.timelist = timelist

    def addBus(self, i):
        self.buslist.append(self.timelist[i])
        self.firstId  = i + 1
        self.capacity = 0

    def calc(self):
        for i in range(0, N):

            if i == N - 1:
                self.addBus(i)
                break

            nexttime = self.timelist[i + 1]

            self.capacity += 1
            # timeover
            if nexttime > timelist[self.firstId] + K:
                self.addBus(i)
                continue

            # capacity over
            if self.capacity >= C:
                self.addBus(i)
                continue


    def printBusList(self):
        for bus in self.buslist:
            print(bus)

    def printTotalBusNum(self):
        print(len(self.buslist))


foo = Foo(timelist)
foo.calc()
foo.printTotalBusNum()


### FIXED CODE ###

N,C,K = map(int, raw_input().split(" "))
timelist = []
for i in range(0, N):
    timelist.append(int(raw_input()))
timelist.sort()


class Foo:

    timelist = []
    buslist = []
    firstId = 0
    capacity = 0

    def __init__(self, timelist):
        self.timelist = timelist

    def addBus(self, i):
        self.buslist.append(self.timelist[i])
        self.firstId  = i + 1
        self.capacity = 0

    def calc(self):
        for i in range(0, N):

            if i == N - 1:
                self.addBus(i)
                break

            nexttime = self.timelist[i + 1]

            self.capacity += 1
            # timeover
            if nexttime > timelist[self.firstId] + K:
                self.addBus(i)
                continue

            # capacity over
            if self.capacity >= C:
                self.addBus(i)
                continue


    def printBusList(self):
        for bus in self.buslist:
            print(bus)

    def printTotalBusNum(self):
        print(len(self.buslist))


foo = Foo(timelist)
foo.calc()
foo.printTotalBusNum()
N,A = map(int,input().split())
if N%500>A:
  print('No')
else:
  print('Yes')

### FIXED CODE ###

N=int(input())
A=int(input())
if N%500>A:
  print('No')
else:
  print('Yes')
s=input()
t=input()
# 
#print("#")

# minimize
mnmz={ch for ch in s} & {ch for ch in t}
if len(mnmz)==0:
    print("")
    exit()
s="".join([ z for z in s if z in mnmz])
t="".join([ z for z in t if z in mnmz])
if len(s)>len(t): s, t = t, s
#print(s)
#print(t)
# init
dp=[0]*len(s)
res={}
#dp
for i in range(len(t)):
    #print(dp)
    prev=dp[0]
    if dp[0]==0 and t[i]==s[0]:
        dp[0]=1
        res[1]=[s[0]]
    for j in range(1, len(s)):
        temp = max(dp[j-1], dp[j])
        if s[j]==t[i]:
            if temp<prev+1:
                temp=prev+1
                res[temp]=res[prev]+[s[j]]
        prev, dp[j] = dp[j], temp
    if dp[len(s)-1]==len(s): break

#print(dp)

print("".join(res[dp[len(s)-1]]))

### FIXED CODE ###

s=[ord(ch)-97 for ch in input()]
t=[ord(ch)-97 for ch in input()]

# minimize
mnmz={ch for ch in s} & {ch for ch in t}
if len(mnmz)==0:
    print("")
    exit()
s=[ z for z in s if z in mnmz ]
t=[ z for z in t if z in mnmz ]
if len(s)>len(t): s, t = t, s

# init
dp=[[0]*len(s) for _ in range(len(t))]

#dp frame init
for i in range(len(s)): 
    if s[i]==t[0]:
        for j in range(i, len(s)):
            dp[0][j]=1
        break
for i in range(len(t)): 
    if s[0]==t[i]:
        for j in range(i, len(t)):
            dp[j][0]=1
        break
#dp
for i in range(1,len(t)):
    for j in range(1, len(s)):
        if s[j]==t[i]:
            dp[i][j]=dp[i-1][j-1]+1
        else: dp[i][j]=(dp[i][j-1] if dp[i][j-1]>dp[i-1][j] else dp[i-1][j])

#recover string
res=[]
j=len(s)-1
i=len(t)-1
while i>=0 and j>=0:
    if s[j]==t[i]: #and dp[i][j]==dp[i-1][j-1]+1:
        res.append(s[j])
        i=i-1
        j=j-1
        continue
    if i==0 and j==0: break
    if j>0 and dp[i][j]==dp[i][j-1]:
        j=j-1
    else: i=i-1
# last letter (first acually)


print("".join(chr(i+97) for i in reversed(res)))
import numpy as np
n = int(input())
a = list(map(int,input().split()))
mat = np.matrix([np.zeros(n) for i in range(n)])
for i in range(n-1):
    mat[i,i] = 1/2
    mat[i,i + 1] = 1/2
mat[n-1,0] = 1/2
mat[n-1,n-1] = 1/2

ans = np.linalg.inv(mat) @ np.matrix(a).T
anss = []
for i in range(n):
    anss.append(int(ans[i,0]))
print(*anss)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
 
m = [0]*n
m[0] = sum(a)
 
for i in range((n-1)//2):
	m[0] -= 2*(a[1+i*2])
 
for i in range(1,n):
	m[i] = 2*a[i-1] - m[i-1]
 
print(' '.join(map(str, m)))
S = input()
ARR = ['A', 'C', 'G', 'T']

results = []
count = 0
for i in range(len(S)):
    if S[i] in ARR:
        count+=1
    else:
        results.append(count)
        count = 0
print(max(results))

### FIXED CODE ###


S = input()
ARR = ['A', 'C', 'G', 'T']

results = []
count = 0
for i in range(len(S)):
    if S[i] in ARR:
        count+=1
        results.append(count)
    else:
        results.append(count)
        count = 0

print(max(results))
if 1 <= s_1 <=12 and 1 <= s_2 <= 12:
    print("AMBIGUOUS")
elif 1 <= s_1 <= 12:
    print("MMYY")
elif 1 <= s_2 <= 12:
    print("YYMM")
else:
    print("NA")

### FIXED CODE ###

s = int(input())
s_1 = s // 100 #4桁の数字列の上2桁を取り出す
s_2 = s % 100  #4桁の数字列の下2桁を取り出す

if 1 <= s_1 <=12 and 1 <= s_2 <= 12:
    print("AMBIGUOUS")
elif 1 <= s_1 <= 12:
    print("MMYY")
elif 1 <= s_2 <= 12:
    print("YYMM")
else:
    print("NA")
N = int(input())
xyh = [list(map(int,input().split())) for i in range(N)]

xyh_hNonzero = sorted(xyh, reverse=True, key=lambda x:x[2])[0]

for cx in range(101):
  for cy in range(101):
    h = abs(xyh_hNonzero[0] - cx) + abs(xyh_hNonzero[1] - cy) + xyh_hNonzero[2]
    for i in range(N):
      if xyh[i][2] == 0 and abs(xyh[i][0] - cx) + abs(xyh[i][1] - cy) < h:
        break
      if abs(xyh[i][0] - cx) + abs(xyh[i][1] - cy) + xyh[i][2] != h:
        break
    else:
      print(' '.join(map(str, [cx,cy,h])))
      exit()
else:
  raise Exception('aaa!!!')

### FIXED CODE ###

N = int(input())
xyh = [list(map(int,input().split())) for i in range(N)]

xyh_hNonzero = sorted(xyh, reverse=True, key=lambda x:x[2])[0]

for cx in range(101):
  for cy in range(101):
    h = abs(xyh_hNonzero[0] - cx) + abs(xyh_hNonzero[1] - cy) + xyh_hNonzero[2]
    for i in range(N):
      if xyh[i][2] == 0:
        if abs(xyh[i][0] - cx) + abs(xyh[i][1] - cy) < h:
          break
      elif abs(xyh[i][0] - cx) + abs(xyh[i][1] - cy) + xyh[i][2] != h:
        break
    else:
      print(' '.join(map(str, [cx,cy,h])))
      exit()
else:
  raise Exception('aaa!!!')
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

k = ni()
que = deque()
for i in range(1, 10):
    que.append(i)
ct = 0
while True:
    x = que.popleft()
    ct += 1
    if ct == k:
        print(x)
        exit(1)
    if x % 10 != 0:
        que.append(10*x+x%10-1)
    que.append(10*x+x%10)
    if x % 10 != 9:
        que.append(10*x+x%10+1)

### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

k = ni()
que = deque()
for i in range(1, 10):
    que.append(i)
ct = 0
for i in range(k):
    x = que.popleft()
    if x % 10 != 0:
        que.append(10*x+x%10-1)
    que.append(10*x+x%10)
    if x % 10 != 9:
        que.append(10*x+x%10+1)
print(x)
import math
n = int(input())
a = list(map(int,input().split()))
# def lcm(a,b):
#     return(a*b//math.gcd(a,b))
ans = a[0]
for i in range(1,n):
    ans = min(ans,math.gcd(ans,a[i]))
    
print(ans)

### FIXED CODE ###

import fractions
n = int(input())
a = list(map(int,input().split()))
ans = a[0]
for i in range(1,n):
    ans = min(ans,fractions.gcd(ans,a[i]))
print(ans)
n=int(input())
a1=list(map(int,input().split()))
a2=list(map(int,input().split()))
total=0
i=0
frag=True
while frag:
    total+=a1[i]
    sum1=sum(a1[i+1:])
    sum2=sum(a2[i:])
    if sum1>=sum2:
        i+=1
    else:
        if a1[i+1]>a2[i]:
            i+=1
        else:
            frag=False
total+=sum(a2[i:])
print(total)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
maxi=0
for i in range(n):
    total=0
    x=sum(a[:i+1])
    y=sum(b[i:])
    total=x+y
    maxi=max(total,maxi)
print(maxi)
# DP practice
# https://atcoder.jp/contests/dp/tasks/dp_b

# 入力方法としてはこれが手軽
N, K = list(map(int, input().split()))
h = list(map(int, input().split()))

dp = list()

# N = 0, 1 の時の処理も必要。だが省く
dp.append(0)

# dp_a を改造した方法で単純にやってみる。
for i in range(1, N):

	min_cost_sum = 99999999
	for k in range(1, K+1):
		if(i-k) < 0:
			break

		tmp = dp[i-k] + abs(h[i] - h[i-k])
		if(tmp < min_cost_sum):
			min_cost_sum = tmp

	dp.append(min_cost_sum)


print(dp[N-1])

# Failure
# 1.初期値を dp[0] = h[0] の方が正しいと思ってしまった
#   → dpの意味を誤解
#
# 2.abs をつけていなかった
#   → コストの全てのパターン意識していなかった。正の場合しか考えていない
#

### FIXED CODE ###

# DP practice
# https://atcoder.jp/contests/dp/tasks/dp_a

# 入力方法としてはこれが手軽
N = int(input())
h = list(map(int, input().split()))

dp = list()

# N = 0, 1 の時の処理も必要。だが省く
dp.append(0)
dp.append(dp[0] + abs(h[1] - h[0]))

for i in range(2, N):
	dp.append(min(dp[i-2] + abs(h[i] - h[i-2]), dp[i-1] + abs(h[i] - h[i-1])))


print(dp[N-1])
n, k = map(int, input().split())
s = input()
l = [0]
for i in range(n - 1):
    if s[i] != s[i + 1]:
        l.append(i + 1)
l += [n]
le = len(l)
ans = 0
for i in range(le - 1):
    if s[l[i]] == "0":
        ans = max(ans, l[min(le, k * 2 + i)] - l[i])
    else:
        ans = max(ans, l[min(le, k * 2 + i + 1)] - l[i])
print(ans)

### FIXED CODE ###

n, k = map(int, input().split())
s = input()
l = [0]
for i in range(n - 1):
    if s[i] != s[i + 1]:
        l.append(i + 1)
l += [n]
le = len(l)
ans = 0
for i in range(le - 1):
    if s[l[i]] == "0":
        ans = max(ans, l[min(le - 1, k * 2 + i)] - l[i])
    else:
        ans = max(ans, l[min(le - 1, k * 2 + i + 1)] - l[i])
print(ans)
from math import gcd
N, X = map(int, input().split())
kotae = list(map(int, input().split()))
kotae.append(X)
kotae.sort()
t = kotae[1]-kotae[0]
for i in range(len(kotae)-1):
    t = gcd(t, abs(kotae[i + 1] - kotae[i]))
print(t)

### FIXED CODE ###

from fractions import gcd
N, X = map(int, input().split())
kotae = list(map(int, input().split()))
kotae.append(X)
kotae.sort()
t = kotae[1]-kotae[0]
for i in range(len(kotae)-1):
    t = gcd(t, abs(kotae[i + 1] - kotae[i]))
print(t)