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

N = int(input())
X = input()
memo = {}
X_int = int("0b"+X, 2)


def popcount(n: int):
    x = bin(n)[2:]
    return x.count("1")


pcf = popcount(int("0b"+X, 2))
pcm = pcf - 1
pcp = pcf + 1


def f(n: int, pc: int, ops: int):

    if n == 0:
        return ops
    else:
        if memo.get(n) is None:
            n %= pc
            ops += 1
            pc = popcount(n)
            return f(n, pc, ops)
        else:
            return memo[n]


def rev(x: str, i: int):
    x = list(x)
    if x[i] == "1":
        n = X_int - 2**(N-i-1)
        pc = pcm
    else:
        n = X_int + 2**(N-i-1)
        pc = pcp
    return (n, pc)


if __name__ == "__main__":
    for i in range(N):
        print(f(*rev(X, i), 0))


### FIXED CODE ###

N = int(input())
X = input()
memo = {}
X_int = int(X, 2)


def popcount(n: int):
    x = bin(n)[2:]
    return x.count("1")


pcf = popcount(int(X, 2))
pcm = pcf - 1
pcp = pcf + 1
xm = X_int % pcm if pcm != 0 else 0
xp = X_int % pcp


def f(n: int, ops: int):

    while n != 0:
        n %= popcount(n)
        ops += 1
    return ops


def rev(x: str, i: int):
    if x == "1":
        if pcm == 0:
            return -1
        n = (xm - (pow(2, N-i-1, pcm))) % pcm
    else:
        n = (xp + (pow(2, N-i-1, pcp))) % pcp
    return n


if __name__ == "__main__":
    for i, x in enumerate(X):
        n = rev(x, i)
        if n == -1:
            print(0)
        else:
            print(f(n, 1))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
mod=10**9+7
n,m=map(int,input().split())
A=[]
for i in range(m):
  a=int(input())
  A.append(a)
S=[0]*(n+1)
S[0]=1
if 1 not in A:
  S[1]=1
for i in range(2,n+1):
  if i in A:
    S[i]=0
  else:
    S[i]=(S[i-1]+S[i-2])%mod
print(S[n]%mod)


### FIXED CODE ###

import sys
input = sys.stdin.readline
mod=10**9+7
n,m=map(int,input().split())
A=set()
for i in range(m):
  A.add(int(input()))
S=[0]*(n+1)
S[0]=1
if 1 not in A:
  S[1]=1
for i in range(2,n+1):
  if i in A:
    S[i]=0
  else:
    S[i]=(S[i-1]+S[i-2])%mod
print(S[n]%mod)
### BUGGY CODE ###

import fractions
from functools import reduce

def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

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

ans = 0
for i in range(N):
    pop = A.pop(0)
    ans = max(ans, gcd(*A))
    A.append(pop)

print(ans)

### FIXED CODE ###

def gcd(x, y):
    while y != 0:
        x, y = y, x%y
    return x

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

L = [0]*(N+1)
R = [0]*(N+1)
for i in range(1, N+1):
    L[i] = gcd(L[i-1], A[i-1])
    R[N-i] = gcd(R[N-i+1], A[N-i])

ans = 0
for i in range(N):
    ans = max(ans, gcd(L[i],R[i+1]))

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

a,b,c,d=map(int,input().split())
mod=998244353
dp=[(d+1)*[0]for _ in range(c+1)]
for i in range(a,c+1):
  for j in range(b,d+1):
    if i==a and j==b:
      dp[i][j]=1
      continue
    if i==a:
      dp[i][j]=dp[i][j-1]*i%mod
      continue
    if j==b:
      dp[i][j]=dp[i-1][j]*j%mod
      continue
    dp[i][j]=(dp[i-1][j]*j+dp[i][j-1]*i-dp[i-1][j-1]*(i-1)*(j-1))%mod
print(dp[c][d])


### FIXED CODE ###

a,b,c,d=map(int,input().split())
mod=998244353
dp=[(d+1)*[0]for _ in range(c+1)]
for i in range(a,c+1):
  for j in range(b,d+1):
    if i==a and j==b:
      dp[i][j]=1
      continue
    if i==a:
      dp[i][j]=dp[i][j-1]*i%mod
      continue
    if j==b:
      dp[i][j]=dp[i-1][j]*j%mod
      continue
    dp[i][j]=(dp[i-1][j]*j+dp[i][j-1]*i-dp[i-1][j-1]*(i-1)*(j-1))%mod
print(dp[c][d])
### BUGGY CODE ###

def quiz(N,K,Q):
    if K>Q:
        for ans in range(N):
            print('Yes')
    else:
        an=[]
        for qui in range(Q):
            an.append(int(input()))
        po=(Q+1)-K
        for su in range(1,N+1):
            if an.count(su) >=po:
                print('Yes')
            else:
                print('No')
N,K,Q=map(int,input().split())
quiz(N,K,Q)

### FIXED CODE ###

n, k, q = map(int, input().split())
b = [k - q] * n

for i in range(q):
    ai = int(input())
    b[ai - 1] += 1

for j in range(n):
    if b[j] > 0:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

dp = [[[0]*(N+3) for _ in range(N+3)] for _ in range(N+3)]

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




### FIXED CODE ###

import sys
input = sys.stdin.readline

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

dp = [[[0.0]*(N+3) for _ in range(N+3)] for _ in range(N+3)]

for k in range(N+1):
    for j in range(N+1):
        for i in range(N+1):
            if i+j+k > N: continue
            if i+j+k == 0: continue
            tmp = 1.0*N
            if i>0: tmp += i*dp[i-1][j][k]
            if j>0: tmp += j*dp[i+1][j-1][k]
            if k>0: tmp += k*dp[i][j+1][k-1]
            dp[i][j][k] = tmp/(i+j+k)
print(dp[IJK[0]][IJK[1]][IJK[2]])
### BUGGY CODE ###

from collections import defaultdict


def factorize(n: int) -> dict:
    f = defaultdict(int)
    while n % 2 == 0:
        f[2] += 1
        n //= 2
    p = 3
    while p * p <= n:
        while n % p == 0:
            f[p] += 1
            n //= p
        p += 2
    if n != 1:
        f[n] += 1
    return f


MOD = 10**9 + 7
n = int(input())
a = tuple(map(int, input().split()))

a_fac = []
lcm_fac = defaultdict(int)
for i in range(n):
    a_fac.append(factorize(a[i]))
    for k, v in a_fac[i].items():
        lcm_fac[k] = max(lcm_fac[k], v)

# print(lcm_fac)
ans = 0
for a_fac_i in a_fac:
    b_i = 1
    for k, v in lcm_fac.items():
        b_i *= pow(k, v - a_fac_i[k], MOD)
        b_i %= MOD
    # print(i, a[i], b_i)
    ans += b_i
    ans %= MOD

print(ans)


### FIXED CODE ###

def GCD(a: int, b: int) -> int:
    return a if b == 0 else GCD(b, a % b)


def LCM(a: int, b: int) -> int:
    return a * b // GCD(a, b)


MOD = 10**9 + 7
n = int(input())
a = tuple(map(int, input().split()))

MAX_a = max(a)
iinv = [1] * (MAX_a + 1)
for i in range(2, MAX_a + 1):
    iinv[i] = MOD - iinv[MOD % i] * (MOD // i) % MOD

lcm = 1
for i in range(n):
    lcm = LCM(lcm, a[i])

lcm %= MOD

ans = 0
for i in range(n):
    ans += lcm * iinv[a[i]]
    ans %= MOD

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

def main():
    n = int(input())
    ans = [0]*(n+1)
    for p in range(1,n+1):
        for i in range(1,p):
            for j in range(1,p):
                if (i+j)**2-4*(i**2+j**2+i*j-p)<0:
                    continue
                k = (((i+j)**2-4*(i**2+j**2+i*j-p))**0.5-i-j)/2
                if k.is_integer() and k>0:
                    ans[p] +=1

    for a in ans[1:]:
        print(a)
if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    n = int(input())
    ans = [0]*(n+1)
    for i in range(1,int(n**0.5+1)):
        for j in range(1,int(n**0.5+1)):
            for k in range(1,int(n**0.5+1)):
                t = i**2+j**2+k**2+i*j+j*k+k*i
                if t<=n:
                    ans[t] += 1
    for a in ans[1:]:
        print(a)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

N = int(input())
s = input()
mn=N
for i in range(N):
    lw=s[:i].count("W")
    re=s[i+1:].count("E")
    sm=lw+re
    if mn>sm:
        mn=sm
print(mn)

### FIXED CODE ###

N = int(input())
s = input()
mn=N
lw=0
re=s[1:].count("E")
for i in range(N):
    if i-1>=0 and s[i-1]=="W":
        lw+=1
    if i-1>=0 and s[i]=="E":
        re-=1
    
    sm=lw+re
    if mn>sm:
        mn=sm
print(mn)
### BUGGY CODE ###

import sys


def _s(): return sys.stdin.readline().strip()


def _ia(): return map(int, sys.stdin.readline().strip().split())


def walk(s, w1, h1, x, y, cur, v):
    if s[y][x] is not None:
        return
    s[y][x] = cur
    for hi in range(max(0, y - 2), min(h1, y + 2) + 1):
        for wi in range(max(0, x - 2), min(w1, x + 2) + 1):
            v[hi][wi] = True

    if x > 0:
        walk(s, w1, h1, x-1, y, cur, v)
    if x < w1:
        walk(s, w1, h1, x+1, y, cur, v)
    if y > 0:
        walk(s, w1, h1, x, y-1, cur, v)
    if y < h1:
        walk(s, w1, h1, x, y+1, cur, v)


def main():
    h, w = _ia()
    sh, sw = map(lambda x: x-1, _ia())
    gh, gw = map(lambda x: x-1, _ia())
    s = [[0]*w for _ in range(h)]
    for hi in range(h):
        for wi, c in enumerate(_s()):
            if c == '.':
                s[hi][wi] = None
            else:
                s[hi][wi] = -1

    v = [[False]*w for _ in range(h)]
    p = [(sw, sh)]
    c = 0
    h1, w1 = h-1, w-1
    while len(p) > 0:
        for pi in p:
            walk(s, w1, h1, *pi, c, v)
        p = []
        for j, sv in enumerate(zip(s, v)):
            sj, vj = sv
            for i, svj in enumerate(zip(sj, vj)):
                sij, vij = svj
                if sij is not None or (not vij):
                    continue
                p.append((i, j))
        c += 1
    ans = s[gh][gw]
    return ans if ans is not None else -1


if __name__ == "__main__":
    print(main())


### FIXED CODE ###

import sys


def _s(): return sys.stdin.readline().strip()


def _ia(): return map(int, sys.stdin.readline().strip().split())


def walk(s, w1, h1, x, y, cur, v1, v2):
    if s[y][x] is not None:
        return
    s[y][x] = cur
    v1.add((x, y))
    for hi in range(max(0, y - 2), min(h1, y + 2) + 1):
        for wi in range(max(0, x - 2), min(w1, x + 2) + 1):
            if s[hi][wi] is None:
                v2.add((wi, hi))

    if x > 0:
        walk(s, w1, h1, x-1, y, cur, v1, v2)
    if x < w1:
        walk(s, w1, h1, x+1, y, cur, v1, v2)
    if y > 0:
        walk(s, w1, h1, x, y-1, cur, v1, v2)
    if y < h1:
        walk(s, w1, h1, x, y+1, cur, v1, v2)


def main():
    h, w = _ia()
    sh, sw = map(lambda x: x-1, _ia())
    gh, gw = map(lambda x: x-1, _ia())
    s = [[0]*w for _ in range(h)]
    for hi in range(h):
        for wi, c in enumerate(_s()):
            if c == '.':
                s[hi][wi] = None
            else:
                s[hi][wi] = -1

    p = [(sw, sh)]
    c = 0
    h1, w1 = h-1, w-1
    while len(p) > 0:
        v1 = set()
        v2 = set()
        for pi in p:
            walk(s, w1, h1, *pi, c, v1, v2)
        p = v2 - v1
        c += 1
    ans = s[gh][gw]
    return ans if ans is not None else -1


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

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

cnt = 0
while s >= 1 and c >= 2:
    s -= 1
    c -= 2
    cnt += 1
    
if c > 3:
    cnt += c // 4
    
print(cnt)

### FIXED CODE ###

s, c = map(int, input().split())
if s >= c // 2:
    print(c // 2)
else:
    print(s + (c - 2 * s) // 4)
### BUGGY CODE ###

n = int(input())
t=0
for i in range(1,n):
    t+=i
print(t)

### FIXED CODE ###

n = int(input())
t=(n-1)*n//2
print(t)
### BUGGY CODE ###

s = input()[::-1]
num = len(s)

cnts = [1] + [0] * (2019 - 1)
for i in range(1, num+1):
    tmp = s[:i][::-1]
    cnts[int(''.join(tmp))%2019] += 1

ans = 0
for cnt in cnts:
    ans += (cnt-1)*cnt//2

print(ans)


### FIXED CODE ###

s = input()[::-1]

cnts = [1] + [0] * (2019 - 1)
tmp = 0
d = 1

for i in s:
    tmp += int(i) * d
    cnts[tmp % 2019] += 1
    d = d * 10 % 2019 # 桁数が大きくなりすぎる → 10と2019が素だから可能

ans = 0
for cnt in cnts:
    ans += (cnt - 1) * cnt // 2

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

n = input()
a_list = [int(a) for a in input().split(" ")]

max = 10**9 + 7

sum = 0
for i in range(0, len(a_list)-1):
  for j in range(i+1, len(a_list)):
    sum += a_list[i] * a_list[j]
    sum = sum % max
print(sum)


### FIXED CODE ###

n = input()
 
max = 10**9 + 7
 
a_list = [int(a) % max for a in input().split(" ")]
a_sum = sum(a_list)

total = 0
for i in range(0, len(a_list)-1):
    a_sum -= a_list[i]
    total += a_list[i] * a_sum
total = total % max
print(total)
### BUGGY CODE ###

n = int(input())


l, r = 0, n

re = input(0)
if re=="Vacant": exit()

for i in range(10):
    mid = (l+r)//2
    tmp = input(mid)
    if tmp=="Vacant": exit()

    if re==tmp:
        l = mid
        re = tmp
    else:
        if abs(l-mid) in [1, n-1]:
            l = mid
            re = tmp
        else: r = mid

### FIXED CODE ###

n = int(input())


l, r = 0, n

print(0, flush=True)
re = input()
if re=="Vacant": exit()

for i in range(19):
    mid = (l+r)//2
    print(mid, flush=True)
    tmp = input()
    if tmp=="Vacant": exit()

    p = abs(l-mid)%2

    if (re!=tmp and p) or (re==tmp and p-1):
        l = mid
        re = tmp
    else:
        if abs(l-mid) in [1, n-1]:
            l = mid
            re = tmp
        else: r = mid
### BUGGY CODE ###

n = int(input())
stones = [0] + [0 if x == "." else 1 for x in list(input())] + [1]

min_num = 10 ** 6

for i in range(1, n + 2):
	tmp = sum(stones[:i]) + (len(stones[i:]) - sum(stones[i:]))
	#print(tmp, sum(stones[:i]), (len(stones[i:]) - sum(stones[i:])))
	min_num = min(min_num, tmp)

print(min_num)

### FIXED CODE ###

n = int(input())
#n = 10 ** 5
stones = [0 if x == "." else 1 for x in list(input())]
#stones = [0] + [0 for _ in range(n)] + [1]

bf = 0
af = n - sum(stones)
min_num = bf + af

for i in range(n):
	bf += stones[i]
	af -= 1 - stones[i]
	min_num = min(min_num, bf + af)

print(min_num)
### BUGGY CODE ###

S = list(input())

mod = [0] * (2019+1)

tmp = ""
for i in range(1, len(S)+1):
    tmp = S[-i] + str(tmp)
    mod[int(tmp) % 2019] += 1

ans = mod[0]
for i in range(1, 2020):
    if mod[i] >= 2:
        ans += (mod[i] * (mod[i]-1)) // 2
print(ans)

### FIXED CODE ###

S = input()

n_i_to_j_mod = [0] * (2019+1) # 2019で割った余りがiになるようなSの部分連続文字列の個数
i_to_end_mod = [0] * (len(S)+1) # S[-i:](Sの後方i文字)を2019で割ったときの余り

for i in range(1, len(S)+1):
    if i == 1:
        i_to_end_mod[1] = int(S[-1]) % 2019
    else:
        i_to_end_mod[i] = (i_to_end_mod[i-1] + int(S[-i]) * pow(10, i-1, 2019)) % 2019
    n_i_to_j_mod[i_to_end_mod[i]] += 1

ans = n_i_to_j_mod[0] + (n_i_to_j_mod[0] * (n_i_to_j_mod[0]-1))//2
for i in range(1, 2019):
    if n_i_to_j_mod[i] >= 2:
        ans += (n_i_to_j_mod[i] * (n_i_to_j_mod[i]-1)) // 2
print(ans)
### BUGGY CODE ###

import sys
from queue import Queue


def print_costs(costs):
    for c in costs:
        print(c)


def solve(inp):
    (H, W) = map(int, inp.readline().strip().split(' '))
    S = [list(inp.readline().strip()) for i in range(H)]

    max_cost = 0
    for start_y in range(H):
        for start_x in range(W):
            if S[start_y][start_x] == '#':
                continue
            costs = [[0 for w in range(W)] for h in range(H)]
            queue = Queue()
            queue.put((start_y, start_x, 1))
            cost = 1
            while not queue.empty():
                (y, x, c) = queue.get()
                if costs[y][x] != 0:
                    continue
                # print("({},{}): {}".format(y, x, c))
                costs[y][x] = c
                cost = c
                for (next_y, next_x) in [(y - 1, x), (y, x + 1), (y + 1, x), (y, x - 1)]:
                    if 0 <= next_y < H and 0 <= next_x < W and S[next_y][next_x] == '.':
                        queue.put((next_y, next_x, c + 1))
            if cost > max_cost:
                max_cost = cost
            # print("--- cost={}".format(max_cost))
            # print_costs(costs)
            # print()

    return str(max_cost - 1)


def main():
    result = solve(sys.stdin)
    if result:
        print(result)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from queue import Queue


def print_costs(costs):
    for c in costs:
        print(c)


def solve(inp):
    (H, W) = map(int, inp.readline().strip().split(' '))
    S = [list(inp.readline().strip()) for i in range(H)]

    max_cost = 0
    for start_y in range(H):
        for start_x in range(W):
            if S[start_y][start_x] == '#':
                continue
            costs = [[0 for w in range(W)] for h in range(H)]
            costs[start_y][start_x] = 1
            queue = Queue()
            queue.put((start_y, start_x))
            cost = 1
            while not queue.empty():
                (y, x) = queue.get()
                # print("({},{}): {}".format(y, x, c))
                for (next_y, next_x) in [(y - 1, x), (y, x + 1), (y + 1, x), (y, x - 1)]:
                    if 0 <= next_y < H and 0 <= next_x < W and S[next_y][next_x] == '.' and costs[next_y][next_x] == 0:
                        costs[next_y][next_x] = costs[y][x] + 1
                        if cost < costs[next_y][next_x]:
                            cost = costs[next_y][next_x]
                        queue.put((next_y, next_x))
            if cost > max_cost:
                max_cost = cost
            # print("--- cost={}".format(max_cost))
            # print_costs(costs)
            # print()

    return str(max_cost - 1)


def main():
    result = solve(sys.stdin)
    if result:
        print(result)


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

from collections import deque


H, W = map(int, input().split())
CH, CW = map(int, input().split())
DH, DW = map(int, input().split())
S = ['#' * (W+4)] * 2
for i in range(H):
    S.append('##' + input() + '##')
S.append('#' * (W+4))
S.append('#' * (W+4))

CH += 2
CW += 2
DH += 2
DW += 2

dist = [[-1 for i in range(W + 4)] for j in range(H + 4)]
dist[CH - 1][CW - 1] = 0
q = deque()
q.append([CH, CW])

while len(q) != 0:
    current_pos = q.popleft()
    y = current_pos[0]
    x = current_pos[1]
    for i in range(-2, 3):
        for j in range(-2, 3):
            if i == j == 0:
                continue
            next_y = y + i
            next_x = x + j

            if S[next_y - 1][next_x - 1] == '#':
                continue
            if dist[next_y - 1][next_x - 1] == dist[y - 1][x - 1]:
                continue

            if dist[next_y - 1][next_x - 1] == -1 or dist[next_y - 1][next_x - 1] > dist[y - 1][x - 1]:
                q.append([next_y, next_x])
                if (i == 0 and j in (-1, 1)) or (j == 0 and i in (-1, 1)):
                    dist[next_y - 1][next_x - 1] = dist[y - 1][x - 1]
                else:
                    if dist[next_y - 1][next_x - 1] == -1:
                        dist[next_y - 1][next_x - 1] = dist[y - 1][x - 1] + 1

print(dist[DH - 1][DW - 1])


### FIXED CODE ###

from collections import deque


H, W = map(int, input().split())
CH, CW = map(int, input().split())
DH, DW = map(int, input().split())
S = ['#' * (W+4)] * 2
for i in range(H):
    S.append('##' + input() + '##')
S.append('#' * (W+4))
S.append('#' * (W+4))

CH += 2
CW += 2
DH += 2
DW += 2

dist = [[-1 for i in range(W + 4)] for j in range(H + 4)]
dist[CH - 1][CW - 1] = 0
q = deque()
q.append([CH, CW])

while len(q) != 0:
    current_pos = q.popleft()
    y = current_pos[0]
    x = current_pos[1]
    if (y, x) == (DH, DW):
        print(dist[DH - 1][DW - 1])
        exit()

    for i in range(-2, 3):
        for j in range(-2, 3):
            if i == j == 0:
                continue
            next_y = y + i
            next_x = x + j

            if S[next_y - 1][next_x - 1] == '#':
                continue
            if dist[next_y - 1][next_x - 1] == dist[y - 1][x - 1]:
                continue

            if dist[next_y - 1][next_x - 1] == -1 or dist[next_y - 1][next_x - 1] > dist[y - 1][x - 1]:
                if (i == 0 and j in (-1, 1)) or (j == 0 and i in (-1, 1)):
                    q.appendleft([next_y, next_x])
                    dist[next_y - 1][next_x - 1] = dist[y - 1][x - 1]
                else:
                    if dist[next_y - 1][next_x - 1] == -1:
                        q.append([next_y, next_x])
                        dist[next_y - 1][next_x - 1] = dist[y - 1][x - 1] + 1

print(-1)
### BUGGY CODE ###

h,n = map(int,input().split())

ls = [list(map(int,input().split())) for _ in range(n)]

amax = max(a for a,b in ls)

dp = [0]*(h+amax)

for i in range(1,h+amax):
  dp[i] = min(dp[i-a]+b+ 0*max(1,2) for a,b in ls)

print(min(dp[h:]))

### FIXED CODE ###

n,m=map(int, input().split())
s=[list(map(int, input().split())) for i in range(m)]
x=max(a for a,b in s)
dp=[0]*(n+x)
for i in range(0,n+x):
  if i>0:
    dp[i]=min(dp[i-a]+b for a,b in s)
print(min(dp[n:]))
### BUGGY CODE ###

from itertools import chain
import bisect
N, M = map(int, input().split())
ABs = [list(map(int, input().split())) for _ in range(N)]

lists = [[] for _ in range(10**5 + 1)]
availables = []
for A, B in ABs:
    bisect.insort(lists[A], B)

ans = 0
for i in range(1, M + 1):
    availables = sorted(chain(availables, lists[i]))
    if availables:
        ans += availables.pop()

print(ans)

### FIXED CODE ###

import heapq
N, M = map(int, input().split())
ABs = [list(map(int, input().split())) for _ in range(N)]

heapq.heapify(ABs)
availables = []
ans = 0
for i in range(1, M + 1):
    while ABs:
        a = heapq.heappop(ABs)
        if a[0] == i:
            heapq.heappush(availables, -a[1])
        else:
            heapq.heappush(ABs, a)
            break
    if availables:
        ans -= heapq.heappop(availables)

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

def main():
    n, m, *py = map(int, open(0).read().split())
    d = [[] for _ in range(n+1)]
    for i,j in zip(*[iter(py)]*2):
        d[i].append(j)
        d[i].sort()

    ans = ''
    for i, j in zip(*[iter(py)] * 2):
        k = d[i].index(j) + 1
        id = str(i).zfill(6) + str(k).zfill(6)
        ans += id + '\n'

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    import bisect
    n, m, *py = map(int, open(0).read().split())
    d = [[] for _ in range(n + 1)]
    for i, j in zip(*[iter(py)] * 2):
        d[i].append(j)

    for i in d:
        i.sort()

    ans = ''
    for i, j in zip(*[iter(py)] * 2):
        k = bisect.bisect_right(d[i], j)
        id = str(i).zfill(6) + str(k).zfill(6)
        ans += id + '\n'

    print(ans)


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

N,K = map(int,input().split())
A = list(map(int,input().split()))
A.insert(0,0)
cur = A[1]
T = 1
while cur!=1:
    cur = A[cur]
    T += 1
K = K%T
cnt = 0
while cnt<K:
    cur = A[cur]
    cnt += 1
print(cur)

### FIXED CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
A.insert(0,0)
B = {1:1}
x = A[1]
st = 0
while True:
    if x not in B:
        B[x] = 1
        x = A[x]
    else:
        st = x
        break
x = 1
t = 0
while x!=st:
    x = A[x]
    t += 1
x = st
x = A[x]
T = 1
while x!=st:
    x = A[x]
    T += 1
if K<=t:
    x = 1
    cnt = 0
    while cnt<K:
        x = A[x]
        cnt += 1
    print(x)
else:
    K -= t
    K = K%T
    x = st
    cnt = 0
    while cnt<K:
        x = A[x]
        cnt += 1
    print(x)