Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

from operator import itemgetter
from collections import deque
import sys

def main():
    n = int(input())  
    keys = map(lambda i:(map(int,raw_input().split())+[i]),xrange(n))

    T = Tree()
    T.recursive_add_Node(keys,0)

    q = int(input())
    for i in xrange(q):
        sx, tx, sy, ty = map(int,raw_input().split())
        nums = deque()
        find(T.root,[sx,sy],[tx,ty],0,nums)
        nums = list(nums)
        nums.sort()
        map(lambda i:sys.stdout.write("{}\n".format(i)), nums)
        print ("")

        

def find(z,s,t,d,nums):
    if(s[0]<=z.key[0]<=t[0])and(s[1]<=z.key[1]<=t[1]):
        nums.append(z.num)
    d += 1
    xy = d%2
    if (z.left != None)and(z.key[xy]>=s[xy]):
        find(z.left,s,t,d,nums)    
    if (z.right != None)and(z.key[xy]<=t[xy]):
        find(z.right,s,t,d,nums)


class Tree():
    def __init__(self):
        self.root = None

    def add_Node(self,k,n):
        y = None
        x = self.root
        d = 0
        xy = 0
        while(x != None):
            d += 1
            xy = d%2
            y = x
            if x.key[xy] > k[xy]:
                x = x.left
            else:
                x = x.right
        
        z = Node(k,n)
        z.parent = y
        z.depth  = d

        if y == None:
            self.root = z
        elif y.key[xy] > k[xy]:
            y.left = z
        else:
            y.right = z
        
    def recursive_add_Node(self,keys,depth):
        keys.sort(key=itemgetter(depth%2))
        id_mean = len(keys)/2
        self.add_Node(keys[id_mean][:2],keys[id_mean][2])
       
        if id_mean != 0:
            self.recursive_add_Node(keys[:id_mean],depth+1)
        if id_mean+1 != len(keys):
            self.recursive_add_Node(keys[id_mean+1:],depth+1)

class Node():
    def __init__(self,k,n):
        self.key    = k
        self.num    = n
        self.depth  = None
        self.parent = None
        self.left   = None
        self.right  = None
    


if __name__ == "__main__":
    main()

### FIXED CODE ###

from sys import stdin,stdout
import math
from operator import itemgetter
from bisect import bisect_left, bisect_right
readline = stdin.readline
 
def main():
    n = int(input())
    keys = map(lambda i: map(int,readline().split())+[i], xrange(n))
    keys.sort()

    root = int(math.sqrt(len(keys)))
 
    low = [x for x, y, i in keys[::root]]
    high = [x for x, y, i in keys[root - 1::root]] + [float('inf')]
 
    keys = [sorted(keys[i:i+root], key=itemgetter(1)) for i in range(0,len(keys),root)]
    keys_y = map(lambda k:[y for x,y,i in k], keys)

    q = int(input())
    for i in xrange(q):
        sx,tx,sy,ty = map(int,readline().split())
        
        nums = []
        for i in range(bisect_left(high, sx), bisect_right(low, tx)):
            y = keys_y[i]
            for j in range(bisect_left(y, sy), bisect_right(y, ty)):
                if sx <= keys[i][j][0] <= tx:
                    nums.append(keys[i][j][2])
        if nums:
            nums.sort()
            map(lambda n:stdout.write("{}\n".format(n)), nums)
        print("")

if __name__ == "__main__":
    main()
### BUGGY CODE ###

s = list(map(len, input().split("T")))
*x, = map(int,input().split())
x[0] -= s[0]
s = s[1:]

ans = True
for j in range(2):
    dp = [False]*(8000*2+1)
    dp[8000] = True
    MAX, MIN = 8000, 8000
    for i in range(j, len(s), 2):
        dp_new = [False]*(8000*2+1)
        MIN_ = 8000*2+1
        MAX_ = -1
        for k in range(MIN, MAX+1):
            if dp[k]:
                dp_new[k-s[i]] = True
                MIN_ = min(MIN_, k-s[i])
                dp_new[k+s[i]] = True
                MAX_ = max(MAX_, k+s[i])
        dp = dp_new
        MIN, MAX = MIN_, MAX_
    ans = ans and dp[x[1-j]+8000]
print(["No","Yes"][ans])


### FIXED CODE ###

s = list(map(len, input().split("T")))
*x, = map(int,input().split())
x[0] -= s[0]
s = s[1:]

moveX, moveY = [], []
for i in range(len(s)):
    if i%2 == 0:
        moveY.append(s[i])
    else:
        moveX.append(s[i])
X = [x[0]]
Y = [x[1]]
for x in moveX:
    X_ = []
    for cx in X:
        X_.append(cx+x)
        X_.append(cx-x)
    X = list(set(X_))
for y in moveY:
    Y_ = []
    for cy in Y:
        Y_.append(cy+y)
        Y_.append(cy-y)
    Y = list(set(Y_))
print(["No","Yes"][0 in X and 0 in Y])
### BUGGY CODE ###

num=int(input())
line=input()
line=line.split()
count1=0
for i in range(num):
    num1=200000
    for j in range(i+1):
        if num1>=int(line[j]):
            num1=int(line[j])
    if num1==int(line[i]):
        count1+=1
print(count1)

### FIXED CODE ###

num=int(input())
line=input()
line=line.split()
#b=list(map(int,input().split()))
count1=0
num1=200000
for i in range(num):
    if num1>=int(line[i]):
        num1=int(line[i])
        count1+=1
print(count1)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
import random

def main():
	Q = int(input())
	maps = []
	r_max = 0
	for _ in range(Q):
		l, r = map(int, input().split(" "))
		maps.append((l, r))
		if r_max < r:
			r_max = r
			
	#marix = getPrimeNumList(r_max)
				
	base = [0] * (r_max+1)
	counts = 0
	for i in range(r_max+1):
		if i == 0:
			continue
		if (i+1) % 2 == 0 and is_prime3(i) == True:
			tmp = (i+1) / 2
			tmp = int(tmp)
			if is_prime3(tmp) == True:
				counts += 1
		base[i] = counts
			
	
	for i in maps:
		l, r = i
		#print(base)
		print(base[r] - base[l-1])
			
				
		
def getPrimeNumList(n):
	is_prime = [True] * (n + 1)
	is_prime[0] = False
	is_prime[1] = False
	for i in range(2, int(n**0.5) + 1):
		if not is_prime[i]:
			continue
		for j in range(i * 2, n + 1, i):
			is_prime[j] = False
	return [i for i in range(n + 1) if is_prime[i]]
	
def is_prime3(q,k=50):
    q = abs(q)
    #計算するまでもなく判定できるものははじく
    if q == 2: return True
    if q < 2 or q&1 == 0: return False

    #n-1=2^s*dとし（但しaは整数、dは奇数)、dを求める
    d = (q-1)>>1
    while d&1 == 0:
        d >>= 1
    
    #判定をk回繰り返す
    for i in range(k):
        a = random.randint(1,q-1)
        t = d
        y = pow(a,t,q)
        #[0,s-1]の範囲すべてをチェック
        while t != q-1 and y != 1 and y != q-1: 
            y = pow(y,2,q)
            t <<= 1
        if y != q-1 and t&1 == 0:
            return False
    return True
	
if __name__ == "__main__":
	main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
import random

def main():
	Q = int(input())
	maps = []
	r_max = 0
	for _ in range(Q):
		l, r = map(int, input().split(" "))
		maps.append((l, r))
		if r_max < r:
			r_max = r
			
	#marix = getPrimeNumList(r_max)
				
	base = [0] * (r_max+1)
	counts = 0
	for i in range(r_max+1):
		if i == 0 or i == 1:
			continue
		if (i+1) % 2 == 0 and is_prime(i) == True:
			tmp = (i+1) / 2
			if is_prime(tmp) == True:
				counts += 1
		base[i] = counts
			
	
	for i in maps:
		l, r = i
		print(base[r] - base[l-1])
			
		
def getPrimeNumList(n):
	is_prime = [True] * (n + 1)
	is_prime[0] = False
	is_prime[1] = False
	for i in range(2, int(n**0.5) + 1):
		if not is_prime[i]:
			continue
		for j in range(i * 2, n + 1, i):
			is_prime[j] = False
	return [i for i in range(n + 1) if is_prime[i]]
	
def is_prime(n): 
  i = 2
  while i * i <=n:
    if n % i == 0:
      return False
    i += 1
  return True
	
if __name__ == "__main__":
	main()
### BUGGY CODE ###

k, s = map(int, input().split())
ans = 0
for x in range(k + 1):
  for y in range(k + 1):
    if x + y > s:
      break
    for z in range(k + 1):
      if x + y + z == s:
        ans += 1
        break
      
print(ans)

### FIXED CODE ###

k, s = map(int, input().split())
ans = 0
for x in range(k + 1):
  for y in range(k + 1):
    if x + y > s:
      break
    z = s - x - y
    if 0 <= z <= k:
      ans += 1
      
print(ans)
### BUGGY CODE ###

N = int(input())
h = list(map(int, input().split()))
c = 1
for i in range(0, len(h)):
    c *= h[i]
if c > 10**18:
    print(-1)
else:
    print(c)

### FIXED CODE ###

import sys

N = int(input())
h = list(map(int, input().split()))
c = 1
if 0 in h:
    print(0)
    sys.exit()
for i in range(0, len(h)):
    c *= h[i]
    if c > 10**18:
        print(-1)
        sys.exit()
print(c)
### BUGGY CODE ###

n = int(input())
A = list(map(int, input().split()))        
D = {}
C = lambda x: x*(x-1)//2

for i in set(A):
  D[i] = A.count(i)
  
for i in A:
  res = 0
  for j,k in D.items():
    if i==j:
      res += C(k-1)
      continue
    res += C(k)
  print(res)

### FIXED CODE ###

from collections import Counter
n = int(input())
A = list(map(int, input().split()))        
C = lambda x: x*(x-1)//2
s = 0
D = Counter(A)
for i,j in D.items():
  s += C(j)
for i in A:
  print(s-D[i]+1)
### BUGGY CODE ###

N,A,B = map(int, input().split())
H = [int(input()) for i in range(N)]

def check(X):
    """ X回以下の爆発で全滅するか """
    ans = 0
    for h in H:
        cnt = ((h - B * X) + (A - B) - 1) // (A - B)
        ans += max(0, cnt)
    return ans <= X

ng = 0
ok = 10 ** 18
while ok - ng > 1:
    mid = (ok + ng) // 2
    if check(mid):
        ok = mid
    else:
        ng = mid
print(ok)

### FIXED CODE ###

from math import ceil

N,A,B = map(int,input().split())
h = sorted([int(input()) for _ in range(N)], reverse=True)

# C回以下の爆発で倒せるか
def is_all_kill(C:int):
    cnt = 0
    for HP in h:
        # あるモンスターに中心ダメージを何回与えるか
        tmp = ceil((HP-B*C)/(A-B))
        # オーバーキルの場合
        if tmp <= 0:
            break
        cnt += tmp
    return cnt <= C

ok = 10 ** 18
ng = 0
while ok - ng > 1:
    mid = (ok + ng) // 2
    if is_all_kill(mid):
        ok = mid
    else:
        ng = mid

print(ok)
### BUGGY CODE ###

n,k = map(int,input().split())         # n=町の個数 , k=テレポート回数
a_list = list(map(int,input().split()))         # 各町のテレポート先リスト
dum = a_list[0]                        # dum=次のテレポート先
k = k - 1                              # テレポート回数をデクリメント
ans_list = [1]                         # 訪れた町を ans_list に格納
while(1):
    #print(dum,ans_list)
    if ans_list.count(dum) == 1:
        ind = ans_list.index(dum)
        loop = ans_list[ind:]
        len_loop = len(loop)
        k = k % len_loop
        ans_list = []
        #print("ok")

    if k == 0:
        print(int(dum))
        break
    ans_list.append(dum)
    dum = a_list[int(dum)-1]
    k = k - 1



### FIXED CODE ###

n,k = map(int,input().split())         # n=町の個数 , k=テレポート回数
a_list = list(map(int,input().split()))     # 各町のテレポート先リスト
dum = a_list[0]                        # dum=次のテレポート先
k = k - 1                              # テレポート回数をデクリメント
ans_list = [1]                         # 訪れた町を ans_list に格納
ok = True
check_list = n*[0]
check_list[0] = 1
for i in range(k+1):
    if ok and check_list[dum-1] == 1:
        #print(dum,111)
        ind = ans_list.index(dum)
        loop = ans_list[ind:]
        len_loop = len(loop)
        k = k % len_loop
        ans_list = []
        ok = False
    else:
        check_list[dum-1] = 1

    if k == 0:
        print(int(dum))
        break
    ans_list.append(dum)
    dum = a_list[int(dum)-1]
    k = k - 1
### BUGGY CODE ###

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import bisect_right
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
from decimal import Decimal
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
N,M = map(int,input().split())
count = [[0]*N for _ in range(N)]
fr = [[] for _ in range(N)]
for _ in range(M):
    a,b = map(int,input().split())
    a,b = a-1,b-1
    if count[a][b] == 1:
        continue
    count[a][b] = 1
    count[b][a] = 1
    fr[a].append(b)
    fr[b].append(a)
used = [-1]*N 
MAX = 0
def dfs(fr,cur,parent):
    global cnt
    children = fr[cur]
    for chi in children:
        if used[chi] != -1:
            continue
        if chi == parent:
            continue
        used[chi] = 0
        cnt += 1
        dfs(fr,chi,cur)
    return

for i in range(N):
    cnt = 1
    if used[i] != -1:
        continue
    used[i] = 0
    dfs(fr,i,-1)
    MAX = max(MAX, cnt)
print(MAX)

            








### FIXED CODE ###

# Union Find
#0オリジン以下注意

#xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
    
def unite(x, y):
    x = find(x)
    y = find(y)
    
    if x == y:
        return False
    else:
        #sizeの大きい方がx
        if par[x] > par[y]:
            x, y = y, x
        par[x] += par[y] #ここで集合の個数を更新している
        par[y] = x
        return True
    
#xとyが同じ集合に含まれているかどうかを判定(同じ集合にあればTrue)
def same(x, y):
    return find(x) == find(y)

#xが属する集合の個数
def size(x):
    return -par[find(x)]

#初期化
#根なら-size, 子なら親の頂点
n, m = map(int, input().split())
par = [-1]*n
for i in range(m):
    a, b = map(int, input().split())
    unite(a-1, b-1)
M = 0
for i in range(n):
    M = max(M, size(i))
print(M)

################以下にコードを書く
######2次元配列が与えられたら１次元に直す必要あり
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n,k = [int(i) for i in input().split()]
p = [int(i) for i in input().split()]
p = tuple(p)

chk = 0
for i in range(n-k+1):
  m = sum(p[i:k+i])
  chk = max(chk,m)
  if chk == m:
    a = p[i:k+i]

ans = [(j+1)/2 for j in a]
print(sum(ans))

### FIXED CODE ###

def main():  
  import sys
  read = sys.stdin.buffer.read
  readline = sys.stdin.buffer.readline
  readlines = sys.stdin.buffer.readlines
  import numpy as np #pypy不可
  n,k = map(int,readline().split())
  p =  np.array(read().split(),np.int32)
  np.cumsum(p,out=p)
  chk = p[k-1]
  for i in range(n-k):
    c = p[i+k]-p[i]
    chk = max(c,chk)
  print((chk+k)/2)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import heapq

N = int(input())
N2 = 2**N
S = list(map(int, input().split()))
S = [-s for s in S]
heapq.heapify(S)

slimes = [heapq.heappop(S)]
num = 1
for i in range(N):
  slimes.sort(reverse=True)
  n = num
  temp = []
  while n and S:
    s = heapq.heappop(S)
    if s > slimes[n-1]:
      slimes.append(s)
      n -= 1
    else:
      temp.append(s)
  
  if n:
    print('No')
    quit()
  
  num *= 2
  for t in temp:
    heapq.heappush(S, t)


print('Yes')

### FIXED CODE ###

N = int(input())
N2 = 2**N
S = list(map(int, input().split()))
S.sort(reverse=True)

slimes = [S[0]]
S[0] = float('inf')
num = 1
for i in range(N):
  slimes.sort()
  n = num
  idx = 0
  while n and idx<=N2-1:
    if S[idx] < slimes[n-1]:
      slimes.append(S[idx])
      S[idx] = float('inf')
      idx += 1
      n -= 1
    else:
      idx += 1
  
  if n:
    print('No')
    quit()
  
  num *= 2

print('Yes')
### BUGGY CODE ###

import sys
from heapq import *

input = sys.stdin.readline

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

dif = [x-y for (x,y) in zip(A,B)]
difh = []
for i, d in enumerate(dif):
	heappush(difh, (d,i))

ans = 0
while difh[0][0]!=0:
	tv, ti = difh[0]
	if ti==0:
		ll, rr = B[-1], B[1]
	elif ti==N-1:
		ll, rr = B[N-2], B[0]
	else:
		ll, rr = B[ti-1], B[ti+1]

	tv += ll+rr
	if tv>0:
		ans=-1
		break
	else:
		ans += 1
		B[ti] = A[ti]-tv
		heappushpop(difh, (tv, ti))

print(ans)

### FIXED CODE ###

import sys
from heapq import *

input = sys.stdin.readline

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

dif = [x-y for (x,y) in zip(A,B)]
difh = []
for i, d in enumerate(dif):
	heappush(difh, (d,i))

ans = 0
while difh[0][0]!=0:
	tv, ti = difh[0]
	if ti==0:
		ll, rr = B[-1], B[1]
	elif ti==N-1:
		ll, rr = B[N-2], B[0]
	else:
		ll, rr = B[ti-1], B[ti+1]

	plus = int((-tv)/(ll+rr))
	if plus==0:
		ans=-1
		break
	else:
		tv += (ll+rr)*plus
		ans += plus
		B[ti] = A[ti]-tv
		heappushpop(difh, (tv, ti))

print(ans)
### BUGGY CODE ###

n,k = map(int, input().split())
A = list(map(int, input().split()))
a = 1
for i in range(k):
    a *= A[i]
ans = a
for i in range(k,n):
    a = a//A[i-k] * A[i]
    if ans < a: print("Yes")
    else: print("No")
    ans = a

### FIXED CODE ###

n,k = map(int, input().split())
A = list(map(int, input().split()))
a = 0
for i in range(k):
    a += A[i]
ans = a
for i in range(k,n):
    a = a-A[i-k] + A[i]
    if ans < a: print("Yes")
    else: print("No")
    ans = a
### BUGGY CODE ###

import sys; input = sys.stdin.buffer.readline
import numpy as np
sys.setrecursionlimit(10**7)
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N, K = getlist()
	h = np.array(getlist() + [0] * K, dtype = np.int64)
	
	DP = [INF for i in range(N + K)]
	DP[0] = 0

	for i in range(N):
		for j in range(1, K + 1):
			DP[i + j] = min(DP[i + j], DP[i] + abs(h[i] - h[i + j]))

	print(DP[N - 1])

if __name__ == '__main__':
	main()

### FIXED CODE ###

import sys; input = sys.stdin.buffer.readline
import numpy as np
sys.setrecursionlimit(10**7)
from collections import defaultdict
con = 10 ** 9 + 7; INF = 2 ** 63 - 1

def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N, K = getlist()
	h = np.array(getlist() + [0] * K, dtype = np.int64)
	
	DP = np.full(N + K, INF, dtype = np.int64)
	DP[0] = 0
	for i in range(N):
		DP[i + 1:i + K + 1] = np.minimum(DP[i + 1:i + K + 1],
			DP[i] + np.abs(h[i] - h[i + 1:i + K + 1]))

	print(DP[N - 1])

if __name__ == '__main__':
	main()
### BUGGY CODE ###

from collections import defaultdict
from numpy import array


def solve(row, col, d):
    x_map = defaultdict()

    for i in range(row):
        a_i = list(map(int, input().split()))
        for j in range(col):
            x_map[a_i[j]-1] = (i, j)

#    print(x_map)

    q = int(input())

    mp = 0
    ans = []
    for _ in range(q):
        l, r = map(int, input().split())
        for current_pos in range(l+d-1, r, d):
            cp = x_map[current_pos]
            pp = x_map[current_pos-d]
#            print("curre_pos : {0}".format(current_pos))
#            print("cp : {0}".format(cp))
#            print("pp : {0}".format(pp))
            mp += abs(cp[1] - pp[1]) + abs(cp[0] - pp[0])
        ans.append(mp)
        mp = 0

    ans = array(ans)

    for k in range(q):
        print(ans[k])


if __name__ == '__main__':
    row, col, d = map(int, input().split())
    solve(row, col, d)


### FIXED CODE ###

from collections import defaultdict


def solve(row, col, d):
    x_map = defaultdict()

    for i in range(row):
        a_i = list(map(int, input().split()))
        for j in range(col):
            x_map[a_i[j]] = (i, j)

    q = int(input())

    dp = [0]*(row*col+1)
    for j in range(d+1, row*col+1):
        x_map_y = abs(x_map[j][0] - x_map[j-d][0])
        x_map_x = abs(x_map[j][1] - x_map[j-d][1])
        dp[j] = dp[j-d]+x_map_y+x_map_x
#        print("j {0} x_map_y : {1} x_map_x : {2} dp[j] : {3}".format(
#            j, x_map_y, x_map_x, dp[j]))

    for _ in range(q):
        l, r = map(int, input().split())
        print(dp[r]-dp[l])


if __name__ == '__main__':
    row, col, d = map(int, input().split())
    solve(row, col, d)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n,m = map(int,input().split())
arr = []
for i in range(m):
	ls = list(map(int,input().split()))
	arr.append(ls)

def st(a):
	b = list(str(a))
	while len(b) <= 5:
		b.insert(0,'0')
	c= ''.join(b)
	return c

for y in arr:
	k = 1
	for j in arr:
		if y[0] == j[0] and y[1] > j[1]:
			k += 1
	print('{}{}'.format(st(y[0]), st(k)))




### FIXED CODE ###


n,m = map(int,input().split())
arr = []
for i in range(m):
	ls = list(map(int,input().split()))+[i]
	arr.append(ls)

arr.sort(key=lambda x:x[1])

def st(a):
	b = list(str(a))
	while len(b) <= 5:
		b.insert(0,'0')
	c= ''.join(b)
	return c

dic = {}
for j in range(m):
	if arr[j][0] in dic:
		dic[arr[j][0]] += 1
		arr[j] += [dic[arr[j][0]]]
	else:
		dic[arr[j][0]] = 1
		arr[j] += [dic[arr[j][0]]]

arr.sort(key=lambda x:x[2])

for y in range(m):
	print('{}{}'.format(st(arr[y][0]), st(arr[y][3])))
### BUGGY CODE ###

in_s = input().rstrip()
s_old = in_s
while True:
    s_new = s_old.replace("10","")
    s_new = s_new.replace("01","")
    if s_new == s_old:
        break
    s_old = s_new
print(len(in_s) - len(s_new))

### FIXED CODE ###

in_s = input().rstrip()
lst = list(in_s)
cur=0
while True:
    if cur+1 >= len(lst):
        break
    if lst[cur]!=lst[cur+1]:
        del lst[cur+1]
        del lst[cur]
        cur = max(0,cur-1)
    else:
        cur+=1
 
print(len(in_s) - len(lst))
### BUGGY CODE ###

import sys
from math import sqrt
from collections import Counter, defaultdict

input = sys.stdin.readline


def I():
    return int(input())


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


def LI():
    return list(MI())


def LIN(n: int):
    return [I() for _ in range(n)]


inf = float("inf")
mod = 10 ** 9 + 7


def main():
    k = I()

    c = 0
    for i in range(99999999999):
        string = str(i)
        s0 = int(string[0])
        flag = True
        for s in string:
            ints = int(s)
            if abs(ints - s0) > 1:
                flag = False
                break
            s0 = ints
        if flag:
            c += 1
        if c == k:
            print(i)

    pass


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
from math import sqrt
from collections import Counter, defaultdict, deque

input = sys.stdin.readline


def I():
    return int(input())


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


def LI():
    return list(MI())


def LIN(n: int):
    return [I() for _ in range(n)]


inf = float("inf")
mod = 10 ** 9 + 7


def main():
    k = I()

    q = deque([1, 2, 3, 4, 5, 6, 7, 8, 9])
    for i in range(1, 10 ** 5 + 1):
        ln = q.popleft()

        if i == k:
            print(ln)
            break

        r = ln % 10
        new_ln = ln * 10 + r
        if r != 0:
            q.append(new_ln - 1)
        q.append(new_ln)
        if r != 9:
            q.append(new_ln + 1)


if __name__ == "__main__":
    main()
### BUGGY CODE ###

N=int(input())
A=[int(input()) for i in range(N)]
count=0
nowN=0
while A:
    #print(A)
    nowN=0
    m=1
    deleteFlag=0
    maxA=max(A)
    while m<len(A):
        #print(A[nowN],A[m])
        if A[m]==maxA and A[nowN]<A[m]:
            #print(A[nowN],A[m],"MAX")
            A.pop(m)
            A.pop(nowN)
            deleteFlag=1
            break
        if A[nowN]<A[m]:
            #print( A[nowN],A[m],"hutuu")
            A.pop(nowN)
            nowN=m-1
            deleteFlag=1
        else:
            m+=1
    count+=1
    if not deleteFlag:A.pop(0)

print(count)


### FIXED CODE ###

import bisect
import collections

N=int(input())
A=[int(input()) for i in range(N)]
B=[0 for i in range(N)]
C=sorted(A)
count=0
lst=collections.deque([])
for i in range(N):
    if A[i]==C[-1]:
        C.pop()
        if lst:
            lst.pop()
        else:
            count+=1
        continue
    idx=bisect.bisect_left(lst,A[i])-1
    #print(idx,lst,A[i])
    if idx<0:
        lst.appendleft(A[i])
        count+=1
    else:
        lst[idx]=A[i]

print(count)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = A[0]
for i in range(N-1):
  ans = ans * A[i+1]

if ans > 10**18:
    ans = -1  
print(ans)

### FIXED CODE ###

import numpy as np
N = int(input())
A = list(map(int, input().split()))
ans = A[0]
if 0 in A:
  ans = 0
for i in range(N-1):
  ans = ans * A[i+1]
  if ans > 10**18 or ans < -1:
    ans = -1  

print(ans)