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

#16:15
n = int(input())
xyi = []
for i in range(n):
  xyi.append(list(map(int,input().split())) + [i])
xyi.sort()
road = []
for j in range(n-1):
  road.append([xyi[j+1][0]-xyi[j][0],xyi[j][2],xyi[j+1][2]])
xyi.sort(key = lambda x: x[1])
for j in range(n-1):
  road.append([xyi[j+1][1]-xyi[j][1],xyi[j][2],xyi[j+1][2]])
road.sort()
pre = [i for i in range(n)]
ans = 0
for k in range(2*n-2):
  d,I,J = road[k]
  ii = []
  ic = 0
  jj = []
  jc = 0
  while pre[I] != I:
    ii.append(I)
    ic += 1
    I = pre[I]
  while pre[J] != J:
    jj.append(J)
    jc += 1
    J = pre[J]
  if I != J:
    ans += d
    if ic >= jc:
      for Js in jj:
        pre[Js] = I
      pre[J] = I
    else:
      for Is in ii:
        pre[Is] = J
      pre[I] = J
print(ans)

### FIXED CODE ###

#16:15
n = int(input())
xyi = []
for i in range(n):
  xyi.append(list(map(int,input().split())) + [i])
xyi.sort()
road = []
for j in range(n-1):
  road.append([xyi[j+1][0]-xyi[j][0],xyi[j][2],xyi[j+1][2]])
xyi.sort(key = lambda x: x[1])
for j in range(n-1):
  road.append([xyi[j+1][1]-xyi[j][1],xyi[j][2],xyi[j+1][2]])
road.sort()
pre = [i for i in range(n)]
ans = 0
for k in range(2*n-2):
  d,I,J = road[k]
  ii = []
  jj = []
  while pre[I] != I:
    ii.append(I)
    I = pre[I]
  for Is in ii:
    pre[Is] = I
  while pre[J] != J:
    jj.append(J)
    J = pre[J]
  for Js in jj:
    pre[Js] = J
  if I != J:
    pre[J] = I
    ans += d
print(ans)
### BUGGY CODE ###

def gcd(x,y):
    if x<y:
        x,y=y,x
    if y==0:
        return x
    return gcd(y,x%y)
def lcm(x,y):
    return x*y//gcd(x,y)

def main():
    mod=1000000007
    n=int(input())
    A=tuple(map(int,input().split()))
    l=1
    for a in A:
        l=lcm(l,a)
    ans=0
    for a in A:
        ans+=l//a
        ans%=mod
    print(ans)
    
if __name__=='__main__':
    main()

### FIXED CODE ###

def gcd(x,y):
    if x<y:
        x,y=y,x
    if y==0:
        return x
    return gcd(y,x%y)
def lcm(x,y):
    return x*y//gcd(x,y)
def modinv(k,mod):
    return pow(k,mod-2,mod)

def main():
    mod=1000000007
    n=int(input())
    A=tuple(map(int,input().split()))
    l=1
    for a in A:
        l=lcm(l,a)
    l%=mod
    ans=0
    for a in A:
        ans+=l*modinv(a,mod)
        ans%=mod
    print(ans)
    
if __name__=='__main__':
    main()
### BUGGY CODE ###

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

def mygcd(a, b):
    if a < b:
        return mygcd(b, a)
    elif b == 0:
        return a
    else:
        return mygcd(b, a % b)

gcd = mygcd(A, B)

pfac = {}
gcd_tmp = gcd
for p in range(2, gcd + 1):
    if gcd_tmp < 2: break
    if gcd_tmp % p == 0:
        i_p = 0
        while gcd_tmp % p == 0:
            gcd_tmp //= p
            i_p += 1
        #
        pfac[str(p)] = i_p

# print("#", pfac)
        
print(1 + len(pfac))

### FIXED CODE ###

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

def mygcd(a, b):
    if a < b:
        return mygcd(b, a)
    elif b == 0:
        return a
    else:
        return mygcd(b, a % b)

gcd = mygcd(A, B)

import math

pfac = {}
gcd_tmp = gcd
for p in range(2, int(math.sqrt(gcd)) + 1):
    if gcd_tmp < 2: break
    if gcd_tmp % p == 0:
        i_p = 0
        while gcd_tmp % p == 0:
            gcd_tmp //= p
            i_p += 1
        #
        pfac[str(p)] = i_p
else:
    if gcd_tmp > 1: pfac[str(gcd_tmp)] = 1
    
# print("#", pfac)
        
print(1 + len(pfac))
### BUGGY CODE ###

import sys
from fractions import gcd
def main(a, b):
    #a, b = [int(i) for i in sys.stdin.readline().split()]
    _gcd = gcd(a,b)
    #memo_ls = [0 for i in range(_gcd)]
    #memo_set = set()
    cnt = 0
    if _gcd == 1:
        print(1)
    else:
        div = 2
        while _gcd > 1:
            if _gcd % div == 0:
                while _gcd % div == 0:
                    _gcd /= div
                cnt += 1
            if div > 2:
              div += 2
            else:
              div += 1
        #print(memo_set)
        print(cnt + 1)

if __name__ == "__main__":
    a, b = [int(i) for i in sys.stdin.readline().split()]
    main(a, b)

### FIXED CODE ###

import sys
from fractions import gcd
def prime_factorize(n):
    a = set()
    while n % 2 == 0:
        a.add(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.add(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.add(n)
    return a

def main(a, b):
    #a, b = [int(i) for i in sys.stdin.readline().split()]
    _gcd = gcd(a,b)
    #memo_ls = [0 for i in range(_gcd)]
    #memo_set = set()
    cnt = 0
    if _gcd == 1:
        print(1)
    else:
        res = prime_factorize(_gcd)
        print(len(res) + 1)
if __name__ == "__main__":
    a, b = [int(i) for i in sys.stdin.readline().split()]
    main(a, b)
### BUGGY CODE ###

N,Q=map(int,input().split())
S=str(input())
AC_list=[]
for i in range(1,N):
  if S[i]=='C' and S[i-1]=='A':
    AC_list.append([i,i+1])
ans=0
for i in range(Q):
  ans=0
  l,r=map(int,input().split())
  for j in AC_list:
    if l<=j[0] and j[1]<=r:
      ans+=1
  print(ans)

### FIXED CODE ###

N,Q=map(int,input().split())
S=str(input())
AC_list=[0]*N
t=0
for i in range(1,N):
  if S[i]=='C' and S[i-1]=='A':
    t+=1
  AC_list[i]=t
ans=0
for i in range(Q):
  l,r=map(int,input().split())
  print(AC_list[r-1]-AC_list[l-1])
### BUGGY CODE ###

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**7)

def grid(y,x):
    global dp
    if mp[y][x]!='#' and dp[y][x]==0:
        dp[y][x]=grid(y-1,x)+grid(y,x-1)
    return dp[y][x]

H,W=map(int,input().split())
mp=[['#']*(W+1)]
for _ in range(H):
    mp.append(['#']+list(input()))
mp.append(['#']*(W+1))

dp=[[0]*(W+1)for _ in range(H+1)]
dp[1][1]=1
grid(H,W)
print(dp[H][W]%(10**9+7))


### FIXED CODE ###

import sys
input=sys.stdin.readline

def grid(y,x,mp):
    mod=10**9+7
    dp=[[0]*x for _ in range(y)]
    dp[0][0]=1
    for h in range(y):
        for w in range(x):
            if mp[h][w]=='.':
                if 1<=h<y and 1<=w<x:
                    dp[h][w]=((dp[h][w-1]+dp[h-1][w])%mod)
                elif h==0 and 1<=w<x:
                    dp[h][w]=(dp[h][w-1]%mod)
                elif 1<=h<y and w==0:
                    dp[h][w]=(dp[h-1][w]%mod)
    return dp[y-1][x-1]


H,W=map(int,input().split())
mp=[list(input()) for _ in range(H)]
print(grid(H,W,mp))
### BUGGY CODE ###

s=input()
n=len(s)
c=0
for i in range(n):
    for j in range(i+1,n+1):
        if int(s[i:j])%2019==0:
            c+=1
print(c)

### FIXED CODE ###

from collections import Counter
s=input()
n=len(s)
M=[0]
mod=2019
for i in range(n):
	m=(M[-1]+int(s[n-1-i])%mod*pow(10,i,mod))%mod
	M.append(m)
MC=Counter(M)
r=0
for v in MC.values():
	if v>1:
		r+=v*(v-1)//2
print(r)
### BUGGY CODE ###

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

w=sorted(w)
#print(w)

total=0
for i in range(m,-1,-1):
#  print("i:"+str(i))
  max=0
  max_j=0
  found=False
  for j in range(len(w)):
    if (m-i)<w[j][0]: #残り日数(m-i)よりも大きい
#      print("残り日数:"+str(m-i) + "　仕事日数:"+str(w[j][0]))
      break
    elif max < w[j][1]:
#      print("最大値:"+str(w[j][1]) + " 添え字:"+str(j))
      max=w[j][1]
      max_j=j
      found=True
#  print(str(max) + "の仕事をやる")
  total = total + max
  if found:
#    print(str(max_j)+"番目の仕事を削除")
    w.pop(max_j)
#    print(w)
      
      
print(total)

### FIXED CODE ###

n,m=map(int,input().split())
tasks=[None]*n
for i in range(n):
  a,b=map(int,input().split())
  tasks[i]=[a,b]

tasks=sorted(tasks,key=lambda x:x[0])
import heapq
que=[]
ans=0
heapq.heapify(que)
j=0
for i in range(m,-1,-1):
  left=m-i
  while j<len(tasks):
    if tasks[j][0]<=left:
      heapq.heappush(que, tasks[j][1]*(-1))
    else:
      break
    j+=1
  if len(que)>0:
    val=heapq.heappop(que)*(-1)
    ans+=val
      
print(ans)
### BUGGY CODE ###

from fractions import gcd
from itertools import product
from functools import reduce

def gcd1(*numbers):
    return reduce(gcd, numbers)

k = int(input())

a = product([int(i) for i in range(1,k+1)], repeat=3)
ans = 0

for i in list(a):
  ans += gcd1(i[0], i[1], i[2])

print(ans)


### FIXED CODE ###

from math import gcd

k=int(input())
ans=0
for i in range(1,k+1):
  for j in range(1,k+1):
    for g in range(1,k+1):
      ans += gcd(gcd(i,j), g)

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

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

MOD = 10 ** 9 + 7

A.sort()

ans = A[K-1] - A[-K]

tmp2 = 1
tmp3 = K

a = 1

for k in range(K, N):
    a = a * tmp3 // tmp2
    ans += a * (A[k] - A[N-k-1])
    if ans > MOD:
        ans %= MOD
    tmp2 += 1
    tmp3 += 1

print(int(ans))


### FIXED CODE ###

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

mod = 10 ** 9 + 7

f = [i for i in range(N+1)]
for i in range(2, N+1):
    f[i] *= f[i-1]
    f[i] %= mod
f[0] = 1

q = K - 1
fk = pow(f[q], mod - 2, mod)

total = 0

for i in range(N - K + 1):
    p = N - i - 1

    c = (f[p] * fk * pow(f[p-q], mod-2, mod)) % mod
    total += c * (A[-1 - i] - A[i])
    total %= mod

print(total)
### BUGGY CODE ###

import math
import numpy as np
x = int(input())
height = list(map(lambda x: int(x), input().split()))  
cands = []


count = 0
for i in range(len(height)):
  tmp = []
  cands.append(tmp)
  
  
for i in range(len(height)):
  if i-height[i] >= 0:
    for j in cands[i-height[i]]:
      count += 1
      
  if i+height[i] < len(height):
    cands[i+height[i]].append(i)

print(count)
	    


### FIXED CODE ###

import math
import numpy as np
x = int(input())
height = list(map(lambda x: int(x), input().split()))  
cands = [0 for i in range(len(height))]


count = 0
  
for i in range(len(height)):
  if i-height[i] >= 0:
    count += cands[i-height[i]]
      
  if i+height[i] < len(height):
    cands[i+height[i]] += 1

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

import math
K=int(input())
sum=0
for i in range(1, K+1):
    for j in range(1, K+1):
        for k in range(1, K+1):
            sum+=math.gcd(math.gcd(i, j), k)
print(sum)

### FIXED CODE ###

import math
K=int(input())
sum=int(0.5*K*(K+1))

for i in range(1, K):
    for j in range(i+1, K+1):
        sum+=6*math.gcd(i, j)

for i in range(1, K-1):
    for j in range(i+1, K):
        for k in range(j+1, K+1):
            sum+=6*math.gcd(math.gcd(i, j), k)

print(sum)
### BUGGY CODE ###

import bisect
import sys
input = sys.stdin.readline

N,M = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]

l = [[] for _ in range(M)]
for j in range(M):
    b,c = [int(i) for i in input().split()]
    l[j] = [c,b]
l.sort(reverse=True)
A.sort()
ans = 0
for i,j in l:
    insert_index = min(bisect.bisect_left(A,i), j)
    ans += insert_index*i
    A = A[insert_index:]
print(ans+sum(A))


### FIXED CODE ###

N,M = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
bc = [tuple(int(i) for i in input().split()) for _ in range(M)]

A.sort()
bc.sort(key=lambda t: t[1], reverse=True)

index = 0
count = 0
for i in range(N):
    if index >= M or A[i] >= bc[index][1]:
        break
    A[i] = bc[index][1]
    count += 1
    if bc[index][0] <= count:
        index += 1
        count = 0

print(sum(A))
### BUGGY CODE ###

#二分探索
from bisect import bisect_left
#input
N = int(input())
#print(N)

A = sorted(list(map(int, input().split()))) #この表記について...
B = sorted(list(map(int, input().split())))
C = sorted(list(map(int, input().split())))
#print(A,B,C)

#sort 昇順に並び替え
#A.sort()
#B.sort()
#C.sort()
Bis_B = []
for i in range(N):
    Bis_B.append(bisect_left(A,B[i]))

#print(Bis_B)

ans = 0
for i in range(N):
    M = bisect_left(B, C[i])
    if M == 0: #この文で余分な動作を少し減らせる
        continue
    ans += sum(Bis_B[:M]) #この探索を複数回やってしまっている？
print(ans)


### FIXED CODE ###

from bisect import bisect_left
from bisect import bisect_right
#input
N = int(input())
#print(N)

A = sorted(list(map(int, input().split()))) #この表記について...
B = sorted(list(map(int, input().split())))
C = sorted(list(map(int, input().split())))
#print(A,B,C)

#sort 昇順に並び替え
#A.sort()
#B.sort()
#C.sort()
ans = 0
for i in range(N):
    ab = bisect_left(A,B[i])
    bc = N-bisect_right(C,B[i])
    #print(ab, end='  ')
    #print(bc)
    ans += ab*bc
print(ans)
### BUGGY CODE ###

n,k = map(int,input().split())
x = []
y = []
for i in range(n):
	a,b = map(int,input().split())
	x.append(a)
	y.append(b)
ans = 10 ** 100
for j in range(n):
	for f in range(n):
		for h in range(n):
			for g in range(n):
				cou = 0
				ri_x = x[j]
				le_x = x[f]
				up_y = y[h]
				do_y = y[g]
				for t in range(n):
					if le_x <= x[t] <= ri_x and do_y <= y[t] <= up_y:
						cou += 1
				if cou >= k:
					ans = min(ans,(ri_x - le_x) * (up_y - do_y))
print(ans)

### FIXED CODE ###

n,k = map(int,input().split())
x = []
y = []
xx = []
yy = []
for i in range(n):
    a,b = map(int,input().split())
    x.append(a)
    y.append(b)
    xx.append(a)
    yy.append(b)
ans = 10 ** 40
x.sort()
y.sort()
for i in range(n):
    for j in range(i+1,n):
        for l in range(n):
            for h in range(l+1,n):
                lx = x[i]
                rx = x[j]
                uy = y[h]
                dy = y[l]
                cnt = 0
                for ii in range(n):
                    if lx <= xx[ii] <= rx and dy <= yy[ii] <= uy:
                        cnt += 1
                if cnt >= k:
                    if (rx-lx) * (uy-dy) != 0:
                        ans = min(ans,(rx-lx)*(uy-dy))
print(ans)
### BUGGY CODE ###

while 1:
    n = input()
    if n == 0: break
    p = [map(int, raw_input().split()) for i in range(n)]
    ans = 0
    for i in range(n):
        for j in range(i,n):
            x  = p[j][0]
            y  = p[j][1]
            mx = x - p[i][0]
            my = y - p[i][1]
            if [x+my, y-mx] in p:
                if [x+my-mx, y-mx-my] in p:        
                    ans = max(ans, mx**2 + my**2)
    print ans

### FIXED CODE ###

while 1:
    n = input()
    if n == 0: break
    p = set([tuple(map(int, raw_input().split())) for i in range(n)])
    ans = 0
    for x1, y1 in p:
        for x2, y2 in p:
            mx = x2 - x1
            my = y2 - y1
            if mx==0 and my==0: continue
            if (x2+my, y2-mx) in p:
                if(x2+my-mx, y2-mx-my) in p:
                    ans = max(ans, mx**2 + my**2)
    print ans
### BUGGY CODE ###

import sys
import math
import itertools
import collections
from collections import deque
from collections import defaultdict

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
MOD2 = 998244353
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()

def main():
    N, K = NMI()
    A = list(sorted([NLI() for _ in range(K)]))
    
    ls = [0 for _ in range(N)]
    ls[0] = 1

    for n in range(1,N):
        for k in range(K):
            for x in range(A[k][0],A[k][1]+1):
                if 0 <= n-x and n-x <= N:
                    ls[n] += ls[n-x]
                    ls[n] = ls[n]%MOD2
    print(ls[-1])
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
import math
import itertools
import collections
from collections import deque
from collections import defaultdict

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
MOD2 = 998244353
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()

def main():
    N, K = NMI()
    LR = list(sorted([NLI() for _ in range(K)]))
    
    dp = [0 for _ in range(N)]
    dp[0] = 1
    
    cumsum = [0 for _ in range(N+1)]
    cumsum[0] = 0
    cumsum[1] = 1
    
    for n in range(1,N):
        for k in range(K):
            r = n-LR[k][0]
            l = n-LR[k][1]
            if r < 0:
                continue
            else:
                l = max(0,l)
            dp[n] += cumsum[r+1]-cumsum[l]
        dp[n] = dp[n]%MOD2
        cumsum[n+1] = (dp[n] + cumsum[n])%MOD2
    print(dp[-1])
if __name__ == '__main__':
    main()
### BUGGY CODE ###

# def main():
#     N, Q = list(map(int, input().split()))
#     parents = [[] for i in range(N+1)]
#     ans = [0] * (N+1)

#     for i in range(N-1):
#         a, b = list(map(int, input().split()))
#         parents[b].append(a)

#     for i in range(Q):
#         p, x = list(map(int, input().split()))
#         ans[p] += x

#     print(parents[1:])

#     for i in range(1, N+1):
#         for p in parents[i]:
#             ans[i] += ans[p]

#     print(*ans[1:])

import queue


def main():
    N, Q = list(map(int, input().split()))
    tree = [[] for i in range(N+1)]
    ans = [0] * (N+1)
    visit = [False]*(N+1)

    for i in range(N-1):
        a, b = list(map(int, input().split()))
        tree[a].append(b)
        tree[b].append(a)

    for i in range(Q):
        p, x = list(map(int, input().split()))
        ans[p] += x

    q = queue.Queue()
    q.put(1)
    visit[1] = True

    while (not q.empty()):
        n = q.get()
        # print(tree[n])
        for i in tree[n]:
            if visit[i] is False:
                ans[i] += ans[n]
                # print(i, '+=', n)
                visit[i] = True
                q.put(i)

    print(*ans[1:])


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import queue
input = sys.stdin.readline
N, Q = map(int, input().split())
 
tree = [[] for i in range(N+1)]
values = [0] * (N+1)
visit = [False]*(N+1)
for _ in range(N-1):
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)
 
for _ in range(Q):
    p, x = map(int, input().split())
    values[p] += x
 
 
q = queue.Queue()
q.put(1)
visit[1] = True
while (not q.empty()):
    now = q.get()
    for next in tree[now]:
        if not visit[next]:
            values[next] += values[now]
            visit[next] = True
            q.put(next)
 
values = values[1:]
print(" ".join(map(str, values)))
### BUGGY CODE ###

# coding: utf-8
a, b = map(int, input().split())
c = [i for i in range(a, b+1)]

if a <= 0 and b >= 0:
    print("Zero")
elif b < 0 and (a - b) % 2 == 0:
    print("Negative")
else:
    print("Positive")

### FIXED CODE ###

# coding: utf-8
a, b = map(int, input().split())

if a <= 0 and b >= 0:
    print("Zero")
elif b < 0 and (a - b) % 2 == 0:
    print("Negative")
else:
    print("Positive")
### BUGGY CODE ###

k, s = map(int, input().split())

count=0
for i in range(k+1):
  for j in range(k+1):
    for h in range(k+1):
      if i+j+h ==s:
        count+=1
print(count)

### FIXED CODE ###

k, s = map(int, input().split())

count=0
for i in range(k+1):
  for j in range(k+1):
    if (s-(i+j)<=k)&(s-(i+j)>=0):
      count+=1
print(count)
### BUGGY CODE ###

#!/usr/bin/env python3
import collections
import itertools as it
import math
#import numpy as np
 
s  = input()
n  = int(input())
#  = map(int, input().split())
#  = list(map(int, input().split()))
#  = [int(input()) for i in range(N)]
#
# c = collections.Counter()

is_seiichi = True

for _ in range(n):
    ipt = input()

    if ipt[0] == '1':
        is_seiichi = not is_seiichi
    else:
        _, id_, s_ = ipt.split()
        is_head = True if id_ == '1' else False
        if is_seiichi ^ is_head:
            s = s + s_
        else:
            s = s_ + s

print(s if is_seiichi else s[::-1])


### FIXED CODE ###

s  = input()
n  = int(input())

s_mae = ''
s_ato = s

for _ in range(n):
    ipt = input()

    if ipt[0] == '1':
        s_mae, s_ato = s_ato, s_mae
    else:
        _, id_, s_ = ipt.split()
        is_head = True if id_ == '1' else False
        if is_head:
            s_mae += s_
        else:
            s_ato += s_

print(s_mae[::-1] + s_ato)
### BUGGY CODE ###

from collections import defaultdict, deque

v, n = map(int, input().split())
n += v -1
es = [[int(x) for x in input().split()] for _ in range(n)]
f = [[]for _ in range(v+1)]
for a, b in es:
    f[b] += [a]

outs = defaultdict(list)
ins = defaultdict(int)
for v1, v2 in es:
    outs[v1].append(v2)
    ins[v2] += 1

q = deque(v1 for v1 in range(v) if ins[v1] == 0)
res = []
while q:
    v1 = q.popleft()
    res.append(v1)
    for v2 in outs[v1]:
        ins[v2] -= 1
        if ins[v2] == 0:
            q.append(v2)

for i in range(1, v+1):
    j = res.index(i) - 1
    if res[j] and not res[j] in f[i]:j -= 1
    print(res[j])

### FIXED CODE ###

from collections import defaultdict, deque

v, n = map(int, input().split())
n += v -1
es = [[int(x) for x in input().split()] for _ in range(n)]

outs = defaultdict(list)
ins = defaultdict(int)
for v1, v2 in es:
    outs[v1].append(v2)
    ins[v2] += 1

q = deque(v1 for v1 in range(v) if ins[v1] == 0)
res = []
f = [0]*(v+1)
while q:
    v1 = q.popleft()
    res.append(v1)
    for v2 in outs[v1]:
        ins[v2] -= 1
        if ins[v2] == 0:
            q.append(v2)
            f[v2] = v1
for t in f[1:]:
    print(t)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from sys import stdin
from operator import itemgetter
import math
# stdin = open("sample.txt")

def keta(kazu):
    kazu_str = str(kazu)
    kazu_list = [int(kazu_str[i]) for i in range(0, len(kazu_str))]
    return kazu_list

K = int(stdin.readline().rstrip())
a = list(range(1,10))
b = []

for i in range(100000):
    go = a.pop(0)
    ue = go*10
    shimo = go%10
    b.append(go)
    if shimo == 0:
        a += (ue,ue+1)
    elif shimo == 9:
        a += (ue+shimo-1,ue+shimo)
    else:
        a += (ue+shimo-1,ue+shimo,ue+shimo+1)

print(b[K-1])

### FIXED CODE ###

# -*- coding: utf-8 -*-
from sys import stdin
from operator import itemgetter
from collections import deque
import math
# stdin = open("sample.txt")

K = int(stdin.readline().rstrip())
a = deque(range(1,10))
ans_list = []
attack = 100000
while attack > 0:
    ans = a.popleft()
    ue = ans*10
    shimo = ans%10
    ans_list.append(ans)
    if shimo == 0:
        a.append(ue)
        a.append(ue+1)
    elif shimo == 9:
        a.append(ue+shimo-1)
        a.append(ue+shimo)
    else:
        a.append(ue+shimo-1)
        a.append(ue+shimo)
        a.append(ue+shimo+1)
    attack -= 1

print(ans_list[K-1])
### BUGGY CODE ###

N = int(input())
s = [sorted(input()) for i in range(N)]
s.sort()
ans = 0
for i in range(N-1):
    for j in range(i+1,N):
        if s[i] == s[j]:
            ans += 1
        else:
            break
print(ans)

### FIXED CODE ###

N = int(input())
s = [sorted(input()) for i in range(N)]
s.sort()
ans = 0
for i in range(N-1):
    if s[i] == s[i+1]:
        start = i
        end = N-1
        while start != end:
            center = (start + end) // 2
            if s[center] == s[i]:
                if s[center+1] == s[i]:
                    start = center+1
                else:
                    start = end = center
            else:
                end = center
        ans += start - i
print(ans)
### BUGGY CODE ###

N,K = (int(a) for a in input().split())
p = list(map(int,input().split()))
p = list(map(lambda x : (x+1)/2 , p))
ans = 0
for i in range(N-K+1) :
    b = sum(p[i:i+K])
    ans = max(ans,b)
print(ans)


### FIXED CODE ###

N,K = (int(a) for a in input().split())
p = list((int(a) + 1)/2 for a in input().split())
s = [sum(p[:K])]

for i in range(N-K) :
    s.append(s[-1] - p[i] + p[i+K])
print(max(s))