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

N,M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
l = []
for a,b in AB:
  l.extend([a]*b)
print(sum(sorted(l)[:M]))

### FIXED CODE ###

N,M = map(int, input().split())
import numpy as np
AB = np.array([list(map(int, input().split())) for _ in range(N)])
idx = np.argsort(AB[:,0],axis=0)
AB = AB[idx]
l = []
for a,b in AB:
  l.extend([a]*b)
  if len(l) > M:
    break
print(sum(l[:M]))
### BUGGY CODE ###

import sys,math
N,M = map(int,input().split())
a = [int(input()) for i in range(M)]
dp = [0] * (N+1)
mod = 10**9+7
for i in range(N,-1,-1):
    if i in a:
        continue
    elif i == N or i == N-1:
        dp[i] = 1
    else:
        dp[i] = (dp[i+1] + dp[i+2])%mod
print(dp[0])


### FIXED CODE ###

import sys,math
N,M = map(int,input().split())
a = [int(input()) for i in range(M)]
b = set(a)
dp = [0] * (N+1)
mod = 10**9+7
for i in range(N,-1,-1):
    if i in b:
        continue
    elif i == N or i == N-1:
        dp[i] = 1
    else:
        dp[i] = (dp[i+1] + dp[i+2])%mod
print(dp[0])
### BUGGY CODE ###

N = int(input())
a = [int(i) for i in input().split()]
ans = []
for i in range(min(a),max(a)+1):
    count = 0
    for j in range(N):
        if a[j]==i or a[j]+1==i or a[j]-1==i:
            count += 1
    ans.append(count)
print(max(ans))

### FIXED CODE ###

from collections import Counter
N = int(input())
a = [int(i) for i in input().split()]
ans = dict(Counter(a))
ans1 = []
for i in range(min(a),max(a)+1):
    count = 0
    if i-1 in ans:
        count += ans[i-1]
    if i in ans:
        count += ans[i]
    if i+1 in ans:
        count += ans[i+1]
    ans1.append(count)
print(max(ans1))
### BUGGY CODE ###

def luca(n):
    if n==0:
        return 2
    elif n==1:
        return 1
    else:
        return luca(n-1) + luca(n-2)

print(luca(int(input())))

### FIXED CODE ###

luca = [2,1]
for i in range(2,100):
    luca.append(luca[i-2] + luca[i-1])
print(luca[int(input())])
### BUGGY CODE ###

def main():
    """"ここに今までのコード"""

n = int(input())
A = [int(a) for a in input().split()]
mod=10**9+7

ans=0
for i in range(60):
    l=sum([a>>i & 1 for a in A])
    ans+= l*(n-l) <<i
    ans%= mod
    
print(ans) 

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    """"ここに今までのコード"""
 
n = int(input())
A = [int(a) for a in input().split()]
mod=10**9+7
 
ans=0
for i in range(60):
    l=sum([a%2 for a in A])
    ans=(ans+l*(n-l)*(2**i))%mod
    A=[a//2 for a in A]
    
 
#ans=xor[0]
#for j in range(60-1):
#    ans=((2*ans)+xor[j+1])%mod
print(int(ans)) 
 
if __name__ == '__main__':
    main()
### BUGGY CODE ###

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

ans = min(s[1:].count("E"), s[:-1].count("W"))

for i in range(1,n-1):
    ans = min(s[:i].count("W")+s[i+1:].count("E"), ans)

print(ans)

### FIXED CODE ###

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

ans = [0]*n
ans[0] = s[1:].count("E")

for i in range(1,n):
    ans[i]=ans[i-1]
    if s[i-1]=="W":
        ans[i] += 1
    if s[i]=="E":
        ans[i] -= 1

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

from _collections import deque
D = int(input())
C = list(map(int,input().split()))
S = deque([])
for _ in range(D):
    S.append(list(map(int,input().split())))

SELECT = deque([])
for i in range(D):
    SELECT.append(int(input())-1)

def score(selects):
    score = 0
    L = [0 for _ in range(26)]
    def calc(ans, select, n):
        for i, l in enumerate(L):
            if i != select:
                ans -= C[i] * (n - L[i])
            else:
                L[i] = n
        return ans

    for i,select in enumerate(selects):
        score += S[i][select]

        for j, l in enumerate(L):
            if j != select:
                score -= C[j] * (i+1 - L[j])
            else:
                L[j] = i+1
    return score

M = int(input())
for _ in range(M):
    i, s = map(int,input().split())
    SELECT[i-1]=s-1
    print(score(SELECT))


### FIXED CODE ###

def main():
    D = int(input())
    C = list(map(int,input().split()))
    S = [list(map(int,input().split()))for _ in range(D)]

    SELECT = []
    for i in range(D):
        SELECT.append(int(input())-1)

    M = int(input())
    d = []
    q = []
    for _ in range(M):
        td, tq = map(int,input().split())
        d.append(td-1)
        q.append(tq-1)

    L_ALL = [[0]*26 for _ in range(D)]
    L = [0]*26
    ans = 0
    for i in range(D):
        ans += S[i][SELECT[i]]
        L[SELECT[i]]=i+1
        if i != 0:
            L_ALL[i] = L_ALL[i-1][:]
        L_ALL[i][SELECT[i]] = i+1
        for j in range(26):
            ans -= C[j]*(i+1-L[j])

    for i in range(M):
        day = d[i]
        before = SELECT[day]
        after = q[i]
        ans -= S[day][before]
        ans += S[day][after]
        SELECT[day] = q[i]

        if day == 0:
            tmp = 0
        else:
            tmp = L_ALL[day-1][before]
        j = day
        while 0<=j<D and L_ALL[j][before]==day+1:
            L_ALL[j][before] = tmp
            ans -= C[before]*(day+1-tmp)
            j += 1

        if day == 0:
            tmp = 0
        else:
            tmp = L_ALL[day-1][after]
        j = day
        while 0<=j<D and L_ALL[j][after]==tmp:
            L_ALL[j][after]=day+1
            ans += C[after] * (day+1-tmp)
            j += 1

        print(ans)

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

import itertools
import numpy as np
import sys
input = sys.stdin.readline
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N = I()
l = IL()
setl = list(set(l))
lenl = len(setl)
ans = 0
if len(l) == 0:
	pass
else:
	for i in range(lenl):
		num = setl[i]
		tmp = l.count(num)
		if tmp < num:
			ans += tmp
		else:
			ans += tmp-num

print(ans)

### FIXED CODE ###

import collections
import numpy as np
import sys
input = sys.stdin.readline
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N = I()
l = IL()
cl = collections.Counter(l)

key = list(cl.keys())
value = list(cl.values())

ans = 0
for i in range(len(key)):
	k = int(key[i])
	v = value[i]
	if k <= v:
		ans += v-k
	else:
		ans += v

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

n, k = map(int, input().split())
h = list(map(int, input().split()))
dp = [0]*n
for i in range(1,n):
    dp[i] = min([dp[i-j]+abs(h[i]-h[i-j]) for j in range(1,min(i+1, k+1))])
print(dp[n-1])

### FIXED CODE ###

n, k = map(int, input().split())
h = [0] + list(map(int, input().split())) + [float("inf")]*(k+1)
dp = [float("inf")]*(n+k+1)
dp[0], dp[1] = 0, 0
for i in range(1,n):
    for j in range(1, k+1):
        dp[i+j] = min(dp[i+j], dp[i] + abs(h[i+j]-h[i]))
print(dp[n])
### BUGGY CODE ###

l,l2 = map(int,input().split())
x = list(map(int,input().split()))

dp = [0]
for i in range(l-1):
    dp.append(0)
    
for i in range(l-1):
    for k in range(1,l2+1):
        if i + k >= l:
            break
        if dp[i+k] !=0:
            dp[i+k] = min(dp[i] + abs(x[i]-x[i+k]),dp[i+k])
        elif dp[i+k] == 0:
            dp[i+k] = dp[i] + abs(x[i]-x[i+k])
        
print(dp[-1])

### FIXED CODE ###

import numpy as np

l,l2 = map(int,input().split())
x = np.array(list(map(int,input().split())))

dp = np.zeros(l,dtype=int)
dp[1] = abs(x[0]-x[1])

for i in range(2,l):
    y = max(i - l2,0)
    dp[i] = np.min(dp[y:i] + abs(x[y:i] - x[i]))
    
print(dp[-1])
### BUGGY CODE ###

n, a, b, c = map(int, input().split())
mod = 10 ** 9 + 7

def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    return [w[0],w[1]]

def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m

an = n
bn = n
for i in range(n):
    an = an * a * (a + b) % mod
    bn = bn * b * (a + b) % mod
sum_a = an
sum_b = bn
for i in range(1, n):
    an = an * (n + i) * mod_inv(i, mod) * b * mod_inv(a + b, mod) % mod
    bn = bn * (n + i) * mod_inv(i, mod) * a * mod_inv(a + b, mod) % mod
    sum_a += an
    sum_b += bn
total = (sum_a + sum_b) * 100
q = 1
for i in range(2 * n):
    q = q * (a + b) % mod
q *= (100 - c)
print(total * mod_inv(q, mod) % mod)

### FIXED CODE ###

n, a, b, c = map(int, input().split())
mod = 10 ** 9 + 7

def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    return [w[0],w[1]]

def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m

an = n
bn = n
for i in range(n):
    an *= a
    an *= (a + b)
    an %= mod
    bn *= b
    bn *= (a + b)
    bn %= mod
sum_a = an
sum_b = bn
inv_ab = mod_inv(a + b, mod)
for i in range(1, n):
    an *= (n + i)
    an *= mod_inv(i, mod)
    an *= b
    an *= inv_ab
    an %= mod
    bn *= (n + i)
    bn *= mod_inv(i, mod)
    bn *= a
    bn *= inv_ab
    bn %= mod
    sum_a += an
    sum_b += bn
total = (sum_a + sum_b) * 100
q = 1
for i in range(2 * n):
    q *= (a + b)
    q %= mod
q *= (100 - c)
print(total * mod_inv(q, mod) % mod)
### BUGGY CODE ###

import numpy
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    N,S=mi()
    A=list(mi())
    MOD = 998244353

    f = numpy.poly1d([1])
    zeros = [1 if x == 0 else 0 for x in range(3010)]
    for a in A:
        g = zeros[:a+1]
        g[-1] = 2
        f *= numpy.poly1d(g)
        
        h = [x % MOD for x in f]
        f = numpy.poly1d(h)


    print(f[S] % MOD)



if __name__ == "__main__":
    main()

### FIXED CODE ###

import numpy as np
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20

class Polynomial:
    def __init__(self,dim=0,const=1):
        self.values = [(dim,const)]
    def __add__(self,other):
        return self.values + other.values


class PolySolver:
    def __init__(self,size):
        self.size = size
        self.f = np.zeros(size, np.int64)
        self.f[0] = 1


    def multiple(self,polynomial,MOD): # const1 * x^dim1 + const2 * x^dim2 + ... をfにかけ合わせる
        new_F = np.zeros(self.size, np.int64)
        for dim,const in polynomial:
            if dim != 0:
                g = np.zeros(self.size, np.int64)
                g[dim:] += self.f[:-dim]
            else:
                g = const * self.f.copy()
            new_F += g

        self.f = new_F
        self.f %= MOD

    
    def get_coefficient(self,dim):
        return self.f[dim]
    
def main():
    N,S=mi()
    A=list(mi())
    MOD = 998244353

    poly = PolySolver(3010)
    for a in A:
        f = Polynomial(const=2) + Polynomial(dim=a)
        poly.multiple(f,MOD)

    print(poly.get_coefficient(S))



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

def devisor_list(x):
    result = []
    for n in range(1, x + 1):
        if x % n == 0:
            result.append(n)
    return result

def common_max_element(array1, array2):
    result = []
    for n in array1:
        if n in array2:
            result.append(n)
    return max(result)

x, y = [int(n) for n in input().split()]
print(common_max_element(devisor_list(x), devisor_list(y)))



### FIXED CODE ###

def gcd(x, y):
    if x < y:
        x, y = [y, x]

    while y > 0:
        r = x % y
        x = y
        y = r
    return x

x, y = [int(n) for n in input().split()]
print(gcd(x, y))
### BUGGY CODE ###

N,Q = map(int,input().split())
S = input()
a = [list(map(int,input().split())) for i in range(Q)]
p = []
for i in range(N-1):
    if S[i]=='A' and S[i+1]=='C':
        p.append(1)
    else:
        p.append(0)
for j in range(Q):
    print(p[a[j][0]-1:a[j][1]-1].count(1))

### FIXED CODE ###

N,Q = map(int,input().split())
S = input()
a = [list(map(int,input().split())) for i in range(Q)]
p = [0]
q=0
for i in range(N-1):
    if S[i]=='A' and S[i+1]=='C':
        q+=1
        p.append(q)
    else:
        p.append(p[i])
for j in range(Q):
    
    print(p[a[j][1]-1]-p[a[j][0]-1])
### BUGGY CODE ###

N = int(input())
A = sorted(list(map(int,input().split())))
m = A[0]
for i in range(m-1):
    for j in range(1,len(A)):
        A[j] = A[j] % A[0]
    A = [k for k in A if k != 0]
    A.sort()

print(A[0])

### FIXED CODE ###

N = int(input())
A = sorted(list(map(int,input().split())))
while len(A) > 1:
    for j in range(1,len(A)):
        A[j] = A[j] % A[0]
    A = [k for k in A if k != 0]
    A.sort()

print(A[0])
### BUGGY CODE ###

N, X, Y = map(int, input().split())
import numpy as np
from scipy.sparse.csgraph import shortest_path
from scipy.sparse import csr_matrix
inf = float("inf")

graph = np.zeros((N, N))
for i in range(N - 1):
    graph[i][i + 1] = 1
    graph[i + 1][i] = 1
graph[X - 1][Y - 1] = 1
graph[Y - 1][X - 1] = 1

shortest_paths = shortest_path(csr_matrix(graph), directed=False, method="D")
from collections import defaultdict
d = defaultdict(int)
for i in range(N):
    for j in range(N):
        if i != j:
            d[shortest_paths[i][j]] += 1
for i in range(N - 1):
    print(d[float(i + 1)] // 2)


### FIXED CODE ###

from collections import deque
N, X, Y = map(int, input().split())

# G[v]: 頂点vに隣接する頂点list
# N: 頂点数
G = [[] for i in range(N)]
G[X - 1].append(Y - 1)
for i in range(N - 1):
    G[i].append(i + 1)
    G[i + 1].append(i)
# print(G)


def bfs(start):
    dist = [-1] * N
    que = deque([start])
    dist[start] = 0
    while que:
        v = que.popleft()
        d = dist[v]
        for w in G[v]:
            if dist[w] > -1:
                continue
            dist[w] = d + 1
            que.append(w)
    return dist


ans = [0] * N

for i in range(N - 1):
    # print(bfs(i))
    for ele in bfs(i)[i + 1:]:
        ans[ele] += 1
for a in ans[1:]:
    print(a)
### BUGGY CODE ###

N=int(input())
A=[int(_) for _ in input().split(" ")]

max=max(A)
 
if A[0] == max:
  total=0
  for i in range(len(A)):
    total=total+max-A[i]
  print(total)
  exit()

ans=0
total=0
b=len(A)
a=1

while a!=0:
  max=0
  for i in range(b):
    if max < A[i]:
      a=i
      max=A[i]
  for i in range(a,b):
    total += max - A[i]
  b=a

print(total)
    


### FIXED CODE ###

N=int(input())
A=[int(_) for _ in input().split(" ")]

max=0
total=0

for i in range(len(A)):
  if max < A[i]:
    max=A[i]
  else:
    total+=max-A[i]

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

import sys
sys.setrecursionlimit(1000000)
from functools import lru_cache
N,W=map(int,input().split())
weights0,profits0 = [0]*N, [0]*N
for i in range(N):
    weights0[i],profits0[i] = map(int,input().split())
weights0 = tuple(weights0)
profits0 = tuple(profits0)
 
@lru_cache(maxsize=100)
def knapsack_recursive(weights, profits, capacity, currentIndex):
    if capacity <= 0 or currentIndex >= len(profits): return 0
    profit = 0
    if weights[currentIndex] <= capacity:
        profit = profits[currentIndex] + knapsack_recursive(weights, profits, capacity - weights[currentIndex], currentIndex + 1)
    tmp = knapsack_recursive(weights, profits, capacity, currentIndex + 1)
    if tmp > profit:
        profit = tmp  
    return profit
  
def main():
    res = knapsack_recursive(weights0, profits0, W, 0)
    print(res)
if __name__ == "__main__":
	main()

### FIXED CODE ###

def main():
  n, w = [int(e) for e in input().split()]
  t = [-1 for i in range(w + 1)]
  t[w] = 0
  for _ in range(n):
    nw, nv = [int(e) for e in input().split()]
    for i in range(nw, w + 1):
      if t[i] == -1:
        continue
      if t[i - nw] < t[i] + nv:
        t[i - nw] = t[i] + nv
  print(max(t))
main()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
N,Q=map(int,input().split())
ab=[[] for _ in range(N)]
for i in range(N-1):
  a,b=map(int,input().split())
  ab[a-1].append(b)
  ab[b-1].append(a)

P=[0 for _ in range(N)]
for i in range(Q):
  p,x=map(int,input().split())
  P[p-1]+=x

def dfs(p,par):
  for i in ab[p-1]:
    if i!=par:
      P[i-1]+=P[p-1]
      dfs(i,p)

dfs(1,-12345)
print(" ".join(map(str,P)))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
input=lambda :sys.stdin.readline()
N,Q=map(int,input().split())
ab=[[] for _ in range(N)]
for i in range(N-1):
  a,b=map(int,input().split())
  ab[a-1].append(b)
  ab[b-1].append(a)

P=[0 for _ in range(N)]
for i in range(Q):
  p,x=map(int,input().split())
  P[p-1]+=x

def dfs(p,par):
  for i in ab[p-1]:
    if i!=par:
      P[i-1]+=P[p-1]
      dfs(i,p)

dfs(1,-12345)
print(" ".join(map(str,P)))
### BUGGY CODE ###

S = input()
S = list(S)
import math
lst = []
switch = "R"
tmp = ""
for i in range(len(S)):
	if S[i]==switch:
		tmp += S[i]
		if i==len(S)-1:
			lst.append(tmp)
	else:
		lst.append(tmp)
		tmp = S[i]
		if i==len(S)-1:
			lst.append(tmp)
		if switch is "R":
			switch = "L"
		else:
			switch = "R"
ls = []
for i in range(0,len(lst),2):
	ls.append(list(lst[i]+lst[i+1]))

for l in ls:
	for i in range(len(l)):
		if l[i] == "L":
			l_num = i
			break
	r_count = math.ceil(((i+1)/2)) + (len(l)-(i+1))//2
	l_count = len(l) - r_count
	l[l_num-1] = l_count
	l[l_num] = r_count

ls = sum(ls,[])
for i in ls:
	if (i=="R") or (i=="L"):
		print("0 ",end="")
	else:
		print(i,end=" ")
print()


### FIXED CODE ###

s = input()
n = len(s)

ret = [0]*n

for i in range(n-1):
	if s[i:i+2] == "RL":
		for j in range(i,-1,-1):
			if s[j] == "R":
				ret[i + (i+j)%2] += 1
			else:
				break
		for j in range(i+1,n):
			if s[j] == "L":
				ret[i + (i+j)%2] += 1
			else:
				break

print(" ".join(map(str,ret)))
### BUGGY CODE ###

n = int(input())
s = []
ns = []

for i in range(n):
  text = input()
  if s.count(text) != 0:
    ns[s.index(text)] += 1
  else:
    s.append(text)
    ns.append(1)

maxn = max(ns)
ms = []
for i in range(len(s)):
  if ns[i] == maxn:
    ms.append(s[i])

ms.sort()

for i in range(len(ms)):
  print(ms[i])

### FIXED CODE ###

n = int(input())
s = []
for i in range(n):
  s.append(input())

import collections
c = collections.Counter(s)
values, counts = zip(*c.most_common())

maxn = counts[0]
cnt = counts.count(maxn)
l = []
for i in range(cnt):
  l.append(values[i])

l.sort()

for i in range(len(l)):
  print(l[i])
### BUGGY CODE ###

import sys
from collections import Counter
read = sys.stdin.buffer.read
n, *lst = map(int, read().split())

def convert(A):
    return [x ^ y for x, y in zip(A, A[1:])] + [A[-1] ^ A[0]]


al = lst[:n]
bl = lst[n:]
a = convert(al)
b = convert(bl)

alal, aa = al + al, a + a
k = 0
klst = []
while k < n:
    i = 0
    while i < n and aa[k + i] == b[i]:
        i += 1
    if i == n:
        klst.append(k)
        k += 1
    elif not i:
        k += 1
    else:
        k += i

for i in klst:
    print(i, al[i] ^ bl[0])

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N = int(readline())

A = list(map(int, readline().split()))
B = list(map(int, readline().split()))


def convert(A):
    return [x ^ y for x, y in zip(A, A[1:])] + [A[-1] ^ A[0]]


C = convert(A)
D = convert(B)


def Z_algorithm(S):
    # 共通接頭辞の長さを返す
    N = len(S)
    arr = [0] * N
    arr[0] = N
    i, j = 1, 0
    while i < N:
        while i + j < N and S[j] == S[i + j]:
            j += 1
        arr[i] = j
        if not j:
            i += 1
            continue
        k = 1

        while i + k < N and k + arr[k] < j:
            k += 1
        i += k
        j -= k

    return arr


Z = Z_algorithm(D + [-1] + C + C)[N + 1:N + N + 1]

K = [i for i, x in enumerate(Z) if x == N]
X = [A[k] ^ B[0] for k in K]

print('\n'.join('{} {}'.format(k, x) for k, x in zip(K, X)))
### BUGGY CODE ###

n = int(input())

ans = 0
for i in range(1,10) :
  for j in range(i,10) :
    c_a = 0
    c_b = 0
    for k in range(1,n+1) :
      if int(str(k)[0]) == i and int(str(k)[-1]) == j :
        c_a += 1
      if int(str(k)[0]) == j and int(str(k)[-1]) == i :
        c_b += 1
    if i == j :
      ans += c_a*c_b
    else :
      ans += c_a*c_b*2
print(ans)

### FIXED CODE ###

n = int(input())

ans = 0
for i in range(1,10) :
  for j in range(i,10) :
    c_a = 0
    c_b = 0
    for k in range(1,n+1) :
      kl = len(str(k))
      if k//(10**(kl-1)) == i and k%10 == j :
        c_a += 1
      if k//(10**(kl-1)) == j and k%10 == i :
        c_b += 1
    if i == j :
      ans += c_a*c_b
    else :
      ans += c_a*c_b*2
      
print(ans)
### BUGGY CODE ###

def main():
    X = input()

    ans = part(X)
    print(ans)


def test_ans():
    X_ans = [
        ("TSTTSS", 4),
        ("SSTTST", 0),
        ("TSSTTTSS", 4),
    ]
    for X, ans in X_ans:
        assert part(X) == editorial(X) == ans


def editorial(X):
    stack = [X[0]]
    ans = len(X)
    for c in X[1:]:
        if stack and stack[-1] == "S" and c == "T":
            ans -= 2
            stack.pop()
        else:
            stack.append(c)

    return ans


def part(X):
    while True:
        n = len(X)
        for i in range(n-1):
            if X[i:i+2] == "ST":
                X = X[:i] + X[i+2:]
                break

        if n == len(X):
            break

    return len(X)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    X = input()

    #ans = part(X)
    ans = editorial(X)
    print(ans)


def test_ans():
    X_ans = [
        ("TSTTSS", 4),
        ("SSTTST", 0),
        ("TSSTTTSS", 4),
    ]
    for X, ans in X_ans:
        assert part(X) == editorial(X) == ans


def editorial(X):
    stack = [X[0]]
    ans = len(X)
    for c in X[1:]:
        if stack and stack[-1] == "S" and c == "T":
            ans -= 2
            stack.pop()
        else:
            stack.append(c)

    return ans


def part(X):
    while True:
        n = len(X)
        for i in range(n-1):
            if X[i:i+2] == "ST":
                X = X[:i] + X[i+2:]
                break

        if n == len(X):
            break

    return len(X)


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

import numpy as np
N,K = map(int,input().split())
A = list(map(int,input().split()))
already_town =[1]
now_town=1
count = 0
check=False
for i in range(K):
    already_town.append(A[now_town-1])
    now_town = A[now_town-1]
    count =i+1
    if(len(set(already_town))!=len(already_town)):
        check=True
        break
if(check==False):
    print(now_town)
else:
    beark_len=len(already_town)-1
    cicle_start=already_town.index(already_town[-1])
    roop_town=already_town[cicle_start:-1]
    print(roop_town[(K-cicle_start)%(count-cicle_start)])


### FIXED CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
already_town_check =[False]*(N+1)
already_town_check[1] = True
already_town = [1]
now_town=1
check=False
my_append = already_town.append
for i in range(K):
    check_town=A[now_town-1]
    if(already_town_check[check_town]):
        cicle_start_value=check_town
        check=True
        break
    already_town_check[check_town]=True
    my_append(check_town)
    now_town = check_town

if(check==False):
    print(now_town)
else:
    cicle_start=already_town.index(cicle_start_value)
    roop_town=already_town[cicle_start:]
    print(roop_town[(K-cicle_start)%((i+1)-cicle_start)])