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

k = int(input())
def last2digit(a):
    sevens = True
    i = 0
    while i < 2 and a > 0:
        #print (a, i)
        if a % 10 != 7:
            sevens = False
        a //= 10
        i += 1
    return sevens
impossible = True
for i in range(20):
    a = k * i
    if last2digit(a):
        impossible = False

if k % 2 == 0 or impossible:
    print(-1)
else:
    ans = 1
    seven = 7
    while seven % k != 0:
        seven = seven * 10 + 7
        ans += 1
        if ans >= 999982:
            print (ans, seven)
            break
    print(ans)

### FIXED CODE ###

k = int(input())
ans = 1
seven = 7
for i in range(k):
    if seven % k == 0:
        print(ans)
        exit()
    seven = (seven * 10 + 7) % k
    ans += 1
print(-1)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
A.sort()
for i in range(N):
    print(A.count(i+1))

### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int, input().split()))
counter = Counter(A)
for i in range(N):
    print(counter[i+1])
### BUGGY CODE ###

import sys
# input処理を高速化する
input = sys.stdin.readline
# 入力
N, W = map(int, input().split())
array = [list(map(int, input().split())) for _ in range(N)]  # [重さ、価値]
# sum_vの取りうる上限値
# MAX_V = (10**3 + 1) * N
MAX_V = 0
for line in array:
    MAX_V += line[1]
MAX_V += 1
# 最小値を求めるので無限大の値
f_inf = float('inf')


def chmin(a, b):
    if a <= b:
        return a
    else:
        return b


def knapsack(n, w):
    # dpの初期化　dp[i][sum_v]は重さの総和の最小値
    dp = [[f_inf] * MAX_V for j in range(N + 1)]
    # 初期条件
    dp[0][0] = 0
    # forは全て関数の中で回す。
    # 入力
    for i in range(N):
        # w, v = map(int, input().split())
        for sum_v in range(MAX_V):
            # i番目の品物を選ぶ場合
            if sum_v - array[i][1] >= 0:
                dp[i + 1][sum_v] = chmin(dp[i + 1][sum_v],
                                         dp[i][sum_v - array[i][1]] + array[i][0])
            # i番目の品物を選ばない場合
            dp[i + 1][sum_v] = chmin(dp[i + 1][sum_v], dp[i][sum_v])
    # dp[N][sum_v]の値が、W以下であるsum_vの値の最大値
    ans = 0
    for sum_v in range(MAX_V):
        if dp[N][sum_v] <= W:
            ans = sum_v
    print(ans)


knapsack(N, W)


### FIXED CODE ###

import sys
# input処理を高速化する
input = sys.stdin.readline
# 入力
N, W = map(int, input().split())
array = [list(map(int, input().split())) for _ in range(N)]  # [重さ、価値]
# sum_vの取りうる上限値
# MAX_V = (10**3 + 1) * N
MAX_V = 0
for line in array:
    MAX_V += line[1]
MAX_V += 1
# 最小値を求めるので無限大の値
f_inf = float('inf')


def chmin(a, b):
    if a <= b:
        return a
    else:
        return b


def knapsack(n, w):
    # dpの初期化　dp[i][sum_v]は重さの総和の最小値
    dp = [[f_inf] * MAX_V for j in range(N + 1)]
    # 初期条件
    dp[0][0] = 0
    # forは全て関数の中で回す。
    # 入力
    for i in range(N):
        # w, v = map(int, input().split())
        for sum_v in range(MAX_V):
            # i番目の品物を選ぶ場合
            if sum_v - array[i][1] >= 0:
                dp[i + 1][sum_v] = chmin(dp[i + 1][sum_v],
                                         dp[i][sum_v - array[i][1]] + array[i][0])
            # i番目の品物を選ばない場合
            dp[i + 1][sum_v] = chmin(dp[i + 1][sum_v], dp[i][sum_v])
    # dp[N][sum_v]の値が、W以下であるsum_vの値の最大値
    ans = 0
    for sum_v in range(MAX_V):
        if dp[N][sum_v] <= W:
            ans = sum_v
    print(ans)


knapsack(N, W)
### BUGGY CODE ###

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

G = [0]*(H+1)
G_old = [1000000000]*(H+1)

for i in range(1,N+1):
    for j in range(1,H+1):
        if j-A[i-1]<0:
            G[j] = min(G_old[j], B[i-1])
        else:
            G[j] = min(G_old[j], G[j-A[i-1]]+B[i-1])
        G_old[j] = G[j]

print(G[H])

### FIXED CODE ###

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

G = [0]*(H+1)

for i in range(1,N+1):
    for j in range(1,H+1):
        if i == 1:
            if j-A[i-1]<0:
                G[j] = B[i-1]
            else:
                G[j] = G[j-A[i-1]]+B[i-1]
        elif j-A[i-1]<0:
            G[j] = min(G[j], B[i-1])
        else:
            G[j] = min(G[j], G[j-A[i-1]]+B[i-1])
        
print(G[H])
### BUGGY CODE ###

n = int(input())
l = list(map(int, input().split()))
l.sort()

def check(x, a):
    if a < x:
        return True
    else:
        return False

def bin_search(x, ok, ng, l):
    while ng - ok > 1:
        mid = (ng + ok) // 2
        if check(x, l[mid]):
            ok = mid
        else:
            ng = mid
    return ok + 1

ans = 0
for i in range(n - 2):
    for j in range(i + 1, n - 1):
        ans += bin_search(l[i] + l[j], -1, n - j - 1, l[j + 1:])
print(ans)

### FIXED CODE ###

n = int(input())
l = list(map(int, input().split()))
l.sort()

def check(x, a):
    if a < x:
        return True
    else:
        return False

def bin_search(x, ok, ng, l):
    while ng - ok > 1:
        mid = (ng + ok) // 2
        if check(x, l[mid]):
            ok = mid
        else:
            ng = mid
    return ok + 1

ans = 0
for i in range(n - 2):
    for j in range(i + 1, n - 1):
        ans += bin_search(l[i] + l[j], -1, n - j - 1, l[j + 1:])
print(ans)
### BUGGY CODE ###

N,K=map(int,input().split())
lmnk=(2*N//K)
ans=0
for h in range(1,lmnk+1):
    a=h*K//2
    if 1<=a<=N:
        for i in range(1,lmnk+1):
            b=i*K-a
            if 1<=b<=N:
                for j in range(1,lmnk+1):
                    c=j*K-b
                    if 1<=c<=N:
                        if (a+b)%K==0 and (b+c)%K==0 and (c+a)%K==0:
                            ans+=1
print(ans)


### FIXED CODE ###

N,K=map(int,input().split())
if K%2==1:
    print((N//K)**3)
else:
    print((N//K)**3+(2*N//K-N//K)**3)
### BUGGY CODE ###

import numpy as np
def main():
    N,K = map(int, input().split())
    p = np.array(list(map(int,input().split())))
    p = (p+1)/2
    ans = 0.0
    for i in range(N-K+1):
        buf = sum(p[i:i+K])
        if ans < buf:
            ans = buf
    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import numpy as np
N,K = map(int, input().split())
p = [(int(i)+1)/2 for i in input().split()]
s = [0]*N
s[0] = p[0]
if N==K:
    print(sum(p))
else:
    for i in range(N-1):
        s[i+1] = s[i]+p[i+1]
    ans=max(s[i+K]-s[i] for i in range(N-K))
    print(ans)
### BUGGY CODE ###

N, M = list(map(int, input().split()))
if N >= M:
    print(M // 2)
else:
    while N * 2 < M:
        N += 1
        M -= 2
    print(M // 2)

### FIXED CODE ###

N, M = list(map(int, input().split()))
count = 0
if N >= (M // 2):
    count += (M // 2)
else:
    count += N
    M -= (2 * N)
    count += (M // 4)
print(count)
### BUGGY CODE ###

def main():
    s = input()
    K = int(input())
    code = [ord(c) - ord("a") for c in s]
    for i in range(len(s)):
        a = code[i]
        x = 26 - a % 26
        if x <= K:
            code[i] = 0
            K -= x
    code[-1] = code[-1] + K % 26
    ans = ""
    for c in code:
        ans += chr(ord("a") + c)
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    s = input()
    K = int(input())
    a = ord("a")
    code = [ord(c) - a for c in s]
    for i in range(len(s)):
        x = (26 - code[i]) % 26
        if x <= K:
            code[i] = 0
            K -= x
    code[-1] = code[-1] + K % 26
    ans = "".join([chr(a + x) for x in code])
    print(ans)


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

N,K=map(int,input().split())
a=list(map(int,input().split()))
dp=[[0]*(K+1) for i in range(N)]
for j in range(a[0]+1):
  dp[0][j]=1
  
for i in range(1,N):
  for j in range(K+1):
    if j==0:
      dp[i][j]=1
    else:
      dp[i][j]=dp[i][j-1]+dp[i-1][j]
      if j>=a[i]+1:
        dp[i][j]-=dp[i-1][j-1-a[i]]
      dp[i][j]=dp[i][j]%(10**9+7)
      
print(dp[-1][-1])


### FIXED CODE ###

N,K=map(int,input().split())
a=list(map(int,input().split()))
dp=[[0]*(K+1) for i in range(N)]
for j in range(a[0]+1):
  dp[0][j]=1
  
for i in range(1,N):
  for j in range(K+1):
    if j==0:
      dp[i][j]=1
    else:
      dp[i][j]=dp[i][j-1]+dp[i-1][j]
      if j>=a[i]+1:
        dp[i][j]-=dp[i-1][j-1-a[i]]
      dp[i][j]=dp[i][j]%(10**9+7)
      
print(dp[-1][-1])
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N = int(input())
edges = []
# edges = [[] for _ in range(N)]
sum_w = 0
for i in range(N-1):
    u, v, w = map(int, input().split())
    edges.append([u-1,v-1,w])

    # edges[u-1].append([v-1,w])
    # edges[v-1].append([u-1,w])


dist = [None]*N
dist[0] = 0
cnt = 0
while len(edges) > 0:
    for edge in edges:
        if dist[edge[0]] == None and dist[edge[1]] != None:
            dist[edge[0]] = dist[edge[1]] + edge[2]
            edges.remove(edge)
        elif dist[edge[1]] == None and dist[edge[0]] != None:
            dist[edge[1]] = dist[edge[0]] + edge[2]
            edges.remove(edge)
    cnt += 1
    if cnt > N: break

for item in dist:
    print(item%2)

### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())
tree = [[] for _ in range(N)]
for i in range(N-1):
    u, v, w = map(int, input().split())
    tree[u-1].append([v-1,w])
    tree[v-1].append([u-1,w])

dist = [None]*N
dist[0] = 0
comp = [0]*N
next_ptr = [0]
for ptr in next_ptr:
    comp[ptr] = 1
    edges = tree[ptr]
    for edge in edges:
        if comp[edge[0]] == 0:
            dist[edge[0]] = dist[ptr] + edge[1]
            next_ptr.append(edge[0])

for item in dist:
    print(item%2)
### BUGGY CODE ###

N = int(input())
count = 0
for i in range(0,10):
    for j in range(0,10):
        countij = 0
        countji = 0
        for k in range(1,N+1):
            if str(k)[0] == str(i) and str(k)[-1] == str(j):
                countij += 1
            if str(k)[0] == str(j) and str(k)[-1] == str(i):
                countji += 1
        count += countij*countji

            
print(count)

### FIXED CODE ###

N = int(input())
rem = [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]
for i in range(1,N+1):
    sti = str(i)
    rem[int(sti[0])][int(sti[-1])] += 1
count = 0
for k in range(10):
    for j in range(10):
        count += rem[k][j]*rem[j][k]
        
print(count)
### BUGGY CODE ###

from math import trunc, sqrt

def p(x,y,z):
    return x**2+y**2+z**2+x*y+y*z+z*x

def perm(x,y,z):
    if x==y and y==z and z==x:
        return 1
    if x!=y and y!=z and z!=x:
        return 6
    return 3

def f(n):
    mn=n
    k=0
    for x in range(1,mn+1):
        for y in range(x,mn+1):
            for z in range(y,mn+1):
                if p(x,y,z)==n:
                    k += perm(x,y,z)
    return k

N=int(input())

for n in range(1,N+1):
    print(f(n))
    


### FIXED CODE ###

N=int(input())

a=[0]*N

x=1
while x*x<=N:
    y=1
    while x*x+y*y+x*y<=N:
        z=1
        while z*z+x*x+y*y+x*y+z*y+z*x<=N:
            a[z*z+x*x+y*y+x*y+z*y+z*x-1]+=1
            z+=1
        y+=1
    x+=1

for n in a:
    print(n)
### BUGGY CODE ###

def LI(): return list(map(int, input().split()))
inf = float('inf')

n, k = LI()
h = LI()

# init
dp = [inf] * k + [0] * n

# calc
for i in range(1, n):
    d_i = [(dp[i+k-(j+1)] + abs(h[i] - h[i-(j+1)]) if j < i else inf) for j in range(k)]
    # print(i, d_i, dp)
    dp[i+k] = min(d_i)

print(dp[-1])


"""
"""


### FIXED CODE ###

import numpy as np
def LI(): return list(map(int, input().split()))


N, K = LI()
h = np.array(LI(), dtype='int32')
dp = np.zeros(N, dtype='int32')
 
for i in range(1, N):
  start = 0 if i < K else i-K
  dp[i] = np.min(dp[start:i] + np.abs(h[i]-h[start:i]))
 
print(dp[-1])


"""
"""
### BUGGY CODE ###

x, y, a, b, c = [int(i) for i in input().split()]
pa = [int(i) for i in input().split()]
pb = [int(i) for i in input().split()]
pc = [int(i) for i in input().split()]

pa = sorted(pa, reverse=True)
pa = pa[:x]
pb = sorted(pb, reverse=True)
pb = pb[:y]
pc = sorted(pc, reverse=True)

l = pa + pb
l = sorted(l, reverse=True)

for i in range(len(pc)):
  for j in range(len(l)):
    if pc[i] > l[j]:
      l[j] = pc[i]
    if j == len(l)-1:
      break
      
print(sum(l))
  

### FIXED CODE ###

x, y, a, b, c = [int(i) for i in input().split()]
pa = [int(i) for i in input().split()]
pb = [int(i) for i in input().split()]
pc = [int(i) for i in input().split()]

pa = sorted(pa, reverse=True)
pa = pa[:x]
pb = sorted(pb, reverse=True)
pb = pb[:y]
pc = sorted(pc, reverse=True)

l = pa + pb + pc
l = sorted(l, reverse=True)
l = l[:int(x+y)]
print(sum(l))
### BUGGY CODE ###

A,B,N=map(int,input().split())
ans=0
if N<B:
    for i in range(1,N+1):
        if ((A*i)//B)-A*(i//B)>ans:
            ans=((A*i)//B)-A*(i//B)
else:
    if ((A*(B-1))//B)-A*((B-1)//B)>ans:
            ans=((A*(B-1))//B)-A*((B-1)//B)
print(ans)


### FIXED CODE ###

A,B,N=map(int,input().split())
ans=0
if N<B:
    for i in range(N,N+1):
        if ((A*i)//B)-A*(i//B)>ans:
            ans=((A*i)//B)-A*(i//B)
else:
    if ((A*(B-1))//B)-A*((B-1)//B)>ans:
            ans=((A*(B-1))//B)-A*((B-1)//B)
print(ans)
### BUGGY CODE ###

def main():
    import sys
    sys.setrecursionlimit(10**5)
    N = int(input())
    a = list(map(int, input().split()))
    A = [0]*4
    for x in a:
        A[x] += 1

    dp = [[[0]*(N+1) for i in range(N+1)] for j in range(N+1)]

    for k in range(A[3]+1):
        for j in range(A[2]+A[3] + 1 - k):
            for i in range(A[1]+A[2]+A[3] + 1 - k - j):
                if i + j+k == 0:
                    continue
                P = N
                if i > 0:
                    P += dp[i-1][j][k] * i
                if j > 0:
                    P += dp[i+1][j-1][k] * j
                if k > 0:
                    P += dp[i][j+1][k-1] * k
                dp[i][j][k] = P/(i+j+k)

    print(dp[A[1]][A[2]][A[3]])


main()


### FIXED CODE ###

def main():
    N = int(input())
    A = list(map(int, input().split()))
    a = A.count(1)
    b = A.count(2)
    c = A.count(3)
    floatN = N*1.0
    dp = [[[.0]*(N+1) for i in range(N+1)] for j in range(N+1)]

    for k in range(c+1):
        for j in range(b+c + 1 - k):
            for i in range(N + 1 - k - j):
                if i + j+k == 0:
                    continue
                dp[i][j][k] = floatN
                if i > 0:
                    dp[i][j][k] += dp[i-1][j][k] * i
                if j > 0:
                    dp[i][j][k] += dp[i+1][j-1][k] * j
                if k > 0:
                    dp[i][j][k] += dp[i][j+1][k-1] * k
                dp[i][j][k] /= (i+j+k)
    print(dp[a][b][c])


main()
### BUGGY CODE ###

from heapq import heapify, heappush, heappop
N = 4
m = {0: {1, 4}, 1: {0, 2, 5}, 2: {1, 3, 6}, 3: {2, 7},
     4: {0, 5, 8}, 5: {1, 4, 6, 9}, 6: {2, 5, 7, 10}, 7: {3, 6, 11},
     8: {4, 9, 12}, 9: {5, 8, 10, 13}, 10: {6, 9, 11, 14}, 11: {7, 10, 15},
     12: {8, 13}, 13: {9, 12, 14}, 14: {10, 13, 15}, 15: {11, 14}}
goal = 0x123456789abcdef0
manhattan = (0, 1, 2, 3,
             1, 2, 3, 4,
             2, 3, 4, 5,
             3, 4, 5, 6)
def solve():
    MAP = sum((input().split() for _ in range(N)), [])
    start = int("".join(f"{int(i):x}" for i in MAP), base=16)
    if start == goal:
        return 0
    zero = 15 - MAP.index("0")
    dp = [(0, start, zero)]
    TABLE = {start}
    while dp:
        cnt, M, yx = heappop(dp)
        cnt += 1
        for nyx in m[yx]:
            num = (M >> 4 * nyx) & 15
            key = M - (num << 4 * nyx) + (num << 4 * yx)
            if key == goal:
                return cnt
            if key in TABLE:
                continue
            TABLE.add(key)
            new_cnt = cnt + manhattan[nyx]
            if new_cnt > 45:
                continue
            heappush(dp, (cnt, key, nyx))
def MAIN():
    print(solve())
MAIN()



### FIXED CODE ###

from heapq import heappop, heappush
manhattan = tuple(tuple(abs((i % 4) - (j % 4)) + abs((i // 4) - (j // 4)) for j in range(16)) for i in range(16))
movables = ((1, 4), (0, 2, 5), (1, 3, 6), (2, 7), (0, 5, 8), (1, 4, 6, 9), (2, 5, 7, 10), (3, 6, 11),
            (4, 9, 12), (5, 8, 10, 13), (6, 9, 11, 14), (7, 10, 15), (8, 13), (9, 12, 14), (10, 13, 15), (11, 14))
swap_mul = tuple(tuple((1 << mf) - (1 << mt) for mt in range(0, 64, 4)) for mf in range(0, 64, 4))
destination = 0xfedcba9876543210
i = 0
board_init = 0
blank_init = 0
for _ in range(4):
    for n in map(int, input().split()):
        if n:
            n -= 1
        else:
            n = 15
            blank_init = i
        board_init += n * 16 ** i
        i += 1
estimation_init = sum(manhattan[i][((board_init >> (4 * i)) & 15)] for i in range(16) if i != blank_init)
queue = [(estimation_init, board_init, blank_init)]
visited = set()
while True:
    estimation, board, blank = heappop(queue)
    if board in visited:
        continue
    elif board == destination:
        print(estimation)
        break
    visited.add(board)
    for new_blank in movables[blank]:
        num = (board >> (4 * new_blank)) & 15
        new_board = board + swap_mul[new_blank][blank] * (15 - num)
        if new_board in visited:
            continue
        new_estimation = estimation + 1 - manhattan[new_blank][num] + manhattan[blank][num]
        if new_estimation > 45:
            continue
        heappush(queue, (new_estimation, new_board, new_blank))
### BUGGY CODE ###

N = int(input())
a = [''.join(sorted(input())) for i in range(N)]
a_unique = set(a)
b = 0
for i in a_unique:
    c = a.count(i)
    b = b + c * (c - 1) / 2
print(int(b))


### FIXED CODE ###

from collections import Counter

N = int(input())
a = [''.join(sorted(input())) for i in range(N)]
count = Counter(a).values()
b = 0
for i in count:
    b = b + i * (i-1)
b=int(b/2)
print(b)
### BUGGY CODE ###


S = input()
Q = int(input())
Front_flag = 1

for i in range(Q):
    Query = tuple(input().split())
    if len(Query) == 1:
        Front_flag = 1 - Front_flag
    else:
        a, b, c = Query
        if (Front_flag + int(b)) % 2 == 1:
            S += c
        else:
            S = c + S
if Front_flag:
    print(S)
else:
    print(S[::-1])


### FIXED CODE ###

from collections import deque
S = input()
que = deque()
que.append(S)
Q = int(input())
Front_flag = 1

for i in range(Q):
    Query = tuple(input().split())
    if len(Query) == 1:
        Front_flag = 1 - Front_flag
    else:
        a, b, c = Query
        if (Front_flag + int(b)) % 2 == 1:
            que.append(c)
        else:
            que.appendleft(c)

ans = ''.join(que)
if Front_flag:
    print(ans)
else:
    print(ans[::-1])
### BUGGY CODE ###

# coding: utf-8

def sIsland(slist):
    b1, b0 = slist[0][1], slist[0][1]-1
    slist = slist[1:]
    
    rest = []
    for i in range(len(slist)):
        if not(slist[i][0] <= b0 and b1 <= slist[i][1]):
            rest.append(slist[i])
    return rest

def solve(matrix):
    n_call = 1
    deleted = sIsland(sorted(matrix, key=lambda x:x[1]))
    while True:
        if len(deleted) == 0:
            return n_call
        deleted = sIsland(deleted)
        n_call += 1
    
if __name__ == "__main__":
    
    N, M = map(int, input().split())
    matrix = []
    for i in range(M):
        matrix.append([int(x) for x in  input().split(" ")])
    print(solve(matrix))


### FIXED CODE ###

# coding: utf-8

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

    return G

def solve(G, N):
    ans = 0
    index = -1

    for i in range(1, N):
        for p in G[i]:
            if index < p < i:
                ans += 1
                index = i - 1
    return ans

if __name__ == "__main__":
    N, M = map(int, input().split())
    G = getG(N, M)
    print(solve(G, N))
### BUGGY CODE ###

import math
n,d,a = map(int,input().split())
L = []
s = 0
for i in range(n):
    t = list(map(int,input().split()))
    s += t[1]
    L.append(t)
L.sort()
ans = 0
temp = 0
while s != 0:
    if L[temp][1] != 0:
        times = int(math.ceil(L[temp][1]/a))
        ans += times
        s -= L[temp][1]
        damage = a*times
        ran = L[temp][0]+2*d
        next = temp+1
        for i in range(temp+1, n):
            if L[i][0] <= ran:
                if L[i][1] > damage:
                    L[i][1] -= damage
                    s -= damage
                    next = min(next, i)
                else:
                    s -= L[i][1]
                    L[i][1] = 0
            else:
                break
        temp = next
    else:
        for i in range(temp+1, n):
            if L[i] != 0:
                temp = i
                break
print(ans)


### FIXED CODE ###

import math
import bisect
n,d,a = map(int,input().split())
L = []
kyo = []
for i in range(n):
    x,h = map(int,input().split())
    L.append([x,h])
    kyo.append(x)
L.sort()
kyo.sort()
ans = 0
imos = [0]*(n+1)
cur = 0
ran = 2*d
for i in range(n):
    if imos[cur] < L[cur][1]:
        t = int(math.ceil((L[cur][1]-imos[cur])/a))
        ans += t
        imos[cur] += t*a
        lim = bisect.bisect_right(kyo, kyo[cur]+ran)
        imos[lim] -= t*a
    imos[i+1] += imos[i]
    cur += 1
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
A = [int(s) for s in input().split()]

a = [0] * N
flg = 0

for k in range(K):
    if a[0] == N:
        break
    a = [0] * N
    for i in range(N):
        a[max(0, i - A[i])] += 1
        if N - 1 >= (A[i] + i + 1):
            a[A[i] + i + 1] -= 1
    for j in range(N):
        A[j] = A[j - 1] if j > 0 else 0
        A[j] += a[j]
    # print("k=", k, A)


for i in range(N):
    print(A[i], end="")
    if i < N - 1:
        print(" ", end="")
print()


### FIXED CODE ###

N, K = map(int, input().split())
A = [int(s) for s in input().split()]

a = [0] * N
for k in range(K):
    for i in range(N):
        a[max(0, i - A[i])] += 1
        if N - 1 >= (A[i] + i + 1):
            a[A[i] + i + 1] -= 1

    if a[0] == N:
        A = [N] * N
        break
    for j in range(N):
        A[j] = A[j - 1] if j > 0 else 0
        A[j] += a[j]
        a[j] = 0
    # print("k=", k, A)


for i in range(N):
    print(A[i], end="")
    if i < N - 1:
        print(" ", end="")
print()
### BUGGY CODE ###

n = int (input())
ln = []
ln2 = []
for _ in range(n):
    ln.append( int (input()))
for _  in ln:
    if _ in ln2:
        ln2.remove(_)
    else:
        ln2.append(_)
print(len(ln2))

### FIXED CODE ###

import collections
n = int (input())
ln = []
ln2 = []
for _ in range(n):
    ln.append( int (input()))

C = collections.Counter(ln)
 
ans = 0
for k, v in C.items():
    if (v%2 != 0):
        ans += 1

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

S=list(input())
#print(S)
D={}
ans=0
for i in range(len(S)):
    d={}
    d[int(S[i])]=1
    for k,v in D.items():
        if (k*10+int(S[i]))%2019 not in d:
            d[(k*10+int(S[i]))%2019]=v
        else:
            d[(k*10+int(S[i]))%2019]+=v
    if 0 in d:
        ans+=d[0]
    D=d
print(ans)

### FIXED CODE ###

S=input()

mod=2019
D={}
S=S[::-1]
now=0

for i in range(len(S)):
    if (int(S[i])*pow(10,i,mod)+now)%mod not in D:
        D[(int(S[i])*pow(10,i,mod)+now)%mod]=1
    else:
        D[(int(S[i])*pow(10,i,mod)+now)%mod]+=1
    now=(int(S[i])*pow(10,i,mod)+now)%mod
#print(D)
ans=0
for k,v in D.items():
    if k==0:
        v+=1
    ans+=v*(v-1)//2
print(ans)
### BUGGY CODE ###

n,k = map(int, input().split())
to = [[0] * n for i in range(60)]
to[0] = list(map(int, input().split()))

# ダブリング
for i in range(n):
    to[0][i] -= 1
DOUBLING = 60
for i in range(DOUBLING-1):
    for j in range(n):
        to[i+1][j] = to[i][to[i][j]]
v = 0
for d in range(DOUBLING, -1, -1):
    l = (1 << d)
    if l <= k:
        v = to[d][v]
        k -= l

print(v + 1)

### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))

visit = []
step = [-1] * (n + 1)
v = 1
while step[v] == -1:
    step[v] = len(visit)
    visit.append(v)
    v = a[v - 1]
cycle = len(visit) - step[v]
nonCycle = step[v]

if k < nonCycle:
    print(visit[k])
else:
    k -= nonCycle
    k %= cycle
    print(visit[nonCycle + k])