Harryxun/stf_run huggingface dataset:
#!/usr/bin/env python3
import sys
import bisect

inf = float('inf')

def solve(A: int, B: int, Q: int, s: "List[int]", t: "List[int]", x: "List[int]"):
    s.sort()
    t.sort()
    for q in x:
        i_s = bisect.bisect(s, q)
        i_t = bisect.bisect(t, q)
        s_l = inf
        if i_s > 0:
            s_l = q - s[i_s-1]
        s_r = inf
        if i_s < A:
            s_r = s[i_s] - q
        t_l = inf
        if i_t > 0:
            t_l = q - t[i_t-1]
        t_r = inf
        if i_t < A:
            t_r = t[i_t] - q
        # 同じ方向に行く場合
        sltl = max([s_l, t_l])
        srtr = max([s_r, t_r])

        # 違う方向に行く場合
        sltr = min([s_l, t_r]) * 2 + max([s_l, t_r])
        srtl = min([s_r, t_l]) * 2 + max([s_r, t_l])

        min_d = min([sltl, srtr, sltr, srtl])

        print(min_d)
        
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    s = [ int(next(tokens)) for _ in range(A) ]  # type: "List[int]"
    t = [ int(next(tokens)) for _ in range(B) ]  # type: "List[int]"
    x = [ int(next(tokens)) for _ in range(Q) ]  # type: "List[int]"
    solve(A, B, Q, s, t, x)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import bisect

inf = float('inf')

def solve(A: int, B: int, Q: int, s: "List[int]", t: "List[int]", x: "List[int]"):
    for q in x:
        i_s = bisect.bisect(s, q)
        i_t = bisect.bisect(t, q)

        s_l = q - s[i_s-1] if i_s > 0 else inf
        s_r = s[i_s] - q if i_s < A else inf
        t_l = q - t[i_t-1] if i_t > 0 else inf
        t_r = t[i_t] - q if i_t < B else inf

        # 同じ方向に行く場合
        sltl = max([s_l, t_l])
        srtr = max([s_r, t_r])

        # 違う方向に行く場合
        sltr = min([s_l, t_r]) + sum([s_l, t_r])
        srtl = min([s_r, t_l]) + sum([s_r, t_l])

        min_d = min([sltl, srtr, sltr, srtl])

        print(min_d)
        
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    s = [ int(next(tokens)) for _ in range(A) ]  # type: "List[int]"
    t = [ int(next(tokens)) for _ in range(B) ]  # type: "List[int]"
    x = [ int(next(tokens)) for _ in range(Q) ]  # type: "List[int]"
    solve(A, B, Q, s, t, x)

if __name__ == '__main__':
    main()
N = int(input())
def dfs(s): # 文字列 s で始まる七五三数の個数
if int(s) > N:
  return 0
  ret = 1 if all(s.count(c) > 0 for c in '753') else 0 # s 自体が七五三数なら +1
  for c in '753':
    ret += dfs(s + c)
    return ret
print(dfs('0'))

### FIXED CODE ###

N = int(input())
def shichi(n):
    if int(n) > N:
        return 0
    ret=1 if all(n.count(c)>0 for c in "753") else 0
    for c in "753":
        ret += shichi(n+c)
    return ret
print(shichi("0"))
N = int(input())

S = [50]*26

for i in range(N):
    s = [0]*26
    for item in input():
        s[ord(item)-97] += 1
    for i in range(26):
        S[i] = min(S[i], s[i])

ans = ""
for i in range(N):
    ans += chr(97+i)*S[i]
print(ans)



### FIXED CODE ###

N = int(input())

S = [50]*26

for i in range(N):
    s = [0]*26
    for item in input():
        s[ord(item)-97] += 1
    for i in range(26):
        S[i] = min(S[i], s[i])

ans = ""
for i in range(26):
    ans += chr(97+i)*S[i]
print(ans)
def main():
    N=int(input())
    c=list(input())[::-1]
    
    #x...WR
    #o...RR, RW, WW
    #Wが来たらそれ以降はW
    #R(0個以上)+W(0個以上)
    
    res=0
    cR=c.count('R')
    cW=c.count('W')
    
    l,r=0,N-1
    while True:
        if c[l]=='W':
            if c[r]=='R':
                c[l],c[r]='R','W'
                res+=1
            else:
                r-=1
        else:
            l+=1
        
    print(min(cR,cW,res))
    
 
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    N=int(input())
    c=list(input())
    
    #x...WR
    #o...RR, RW, WW
    #Wが来たらそれ以降はW
    #R(0個以上)+W(0個以上)
    
    res=0
    cR=c.count('R')
    cW=c.count('W')
    
    l,r=0,N-1
    while l!=r:
        if c[l]=='W':
            if c[r]=='R':
                c[l],c[r]='R','W'
                res+=1
            else:
                r-=1
        else:
            l+=1
        
    print(min(cR,cW,res))
    
 
if __name__ == '__main__':
    main()
import bisect
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A.sort()
B.sort()
C.sort()
BoverA = [0] * N
CoverB = [0] * N
for i in range(N):
    BoverA[i] = N - bisect.bisect_right(B, A[i])
    CoverB[i] = N - bisect.bisect_right(C, B[i])
cumBC = [0] * N
cumBC[N-1] = CoverB[N-1]
for i in range(N-2, -1, -1):
    cumBC[i] = cumBC[i+1] + CoverB[i]
ans = 0
for i in range(N):
    ans += cumBC[N - BoverA[i]]
print(ans)

### FIXED CODE ###

import bisect
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A.sort()
B.sort()
C.sort()
BoverA = [0] * N
CoverB = [0] * N
for i in range(N):
    BoverA[i] = N - bisect.bisect_right(B, A[i])
    CoverB[i] = N - bisect.bisect_right(C, B[i])
cumBC = [0] * N
cumBC[N-1] = CoverB[N-1]
for i in range(N-2, -1, -1):
    cumBC[i] = cumBC[i+1] + CoverB[i]
ans = 0
for i in range(N):
    if N - BoverA[i] >= 0 and N - BoverA[i] < N:
        ans += cumBC[N - BoverA[i]]
print(ans)
a,b = map(int, raw_input().split());

print2*(a+b) a*b;

### FIXED CODE ###

a, b = map(int, raw_input().split())

print a*b, 2*(a+b)
n=int(input())
s=input()
k=int(input())
for i in range(n):
    if s[i] == s[k]:
        print(s[i],end="")
    else:
        print("*",end="")

### FIXED CODE ###

n=int(input())
s=input()
k=int(input())
for i in range(n):
    if s[i] == s[k-1]:
        print(s[i],end="")
    else:
        print("*",end="")
N = int(input())
S = input()

num = 0
for i in range(len(S)-2):
  if S[i:i+2] = "ABC":
    num += 1
  else:
    num = num

print(num)

### FIXED CODE ###

N = int(input())
S = str(input())

num = 0
for i in range(N-2):
  if S[i:i+3] == "ABC":
    num += 1
  else:
    num += 0
print(num)
N, K = map(int, input().split())
S = str(input())

s1 = S[:K-1]
smid = S[K-1:K].lower()
s1 = S[K:]

print(s0 + smid + s1)

### FIXED CODE ###

N, K = map(int, input().split())
S = str(input())

s0 = S[:K-1]
smid = S[K-1:K].lower()
s1 = S[K:]

print(s0 + smid + s1)
h,w = int(input())
Array = [list(map(int, input().split())) for _ in range(h)]
dx = [1,1,0,-1,-1,-1,0,1]
dy = [0,1,1,1,0,-1,-1,-1]
for i in range(h):
  for j in range(w):
    if Array[i][j]='#':
      continue
      
    num=0
    for d in range(8):
      ni = i+dy[d]
      nj = j+dx[d]
      if ni<0 or h<=ni:
        continue
      if nj<0 or w<=nj:
        continue
      if Array[ni][nj]=='#':
        num=num+1
        
    Array[i][j]=char(num + '0')
    
for i in Array:
  print(*Array)

### FIXED CODE ###

h,w = map(int,input().split())
Array = [list(map(str,input())) for _ in range(h)]
dx = [1,1,0,-1,-1,-1,0,1]
dy = [0,1,1,1,0,-1,-1,-1]
for i in range(h):
  for j in range(w):
    if Array[i][j]=='#':
      continue
    num=0
    for d in range(8):
      ni = i+dy[d]
      nj = j+dx[d]
      if ni<0 or h<=ni:
        continue
      if nj<0 or w<=nj:
        continue
      if Array[ni][nj]=='#':
        num=num+1
    Array[i][j]=str(num)
    
for i in Array:
  print(*i, sep='')
N = int(input())
T = []

while len(input())>0:
    t = int(input())
    T_temp=[]
    for t_ in range(t) :
        temp = list(map(int,input().split()))
        T_temp.append(temp)
    T.append(T_temp)
    
def check_Contradiction(true_list):
    S = {}
    for n in range(N):
        if n in true_list:
            S[n]=set([1])
        else:
            S[n]=set([0])

    for t in true_list:
        for T_ in T[t]:
            S[T_[0]-1].add(T_[1])
    ok=True
    for s in S.keys():
        if len(S[s])!=1:
            ok='False'
            break

    return ok

ok_max = -1
for i in range(2**N):
#     print('=====',i)
    true_list=[]
    for j in range(N):
        if i>>j&1 ==True:
            true_list.append(j)
#     print(true_list)
#     print(check_Contradiction(true_list))
            
    if check_Contradiction(true_list)==True:
        if ok_max < len(true_list):
            ok_max=len(true_list)
            
print(ok_max)

### FIXED CODE ###

N = int(input())
T = []
try:
	while True:
		t = input()
		t=int(t)
		T_temp=[]
		for t_ in range(t) :
			temp = list(map(int,input().split()))
			T_temp.append(temp)
		T.append(T_temp)
except EOFError:
	pass
    
def check_Contradiction(true_list):
    S = {}
    for n in range(N):
        if n in true_list:
            S[n]=set([1])
        else:
            S[n]=set([0])

    for t in true_list:
        for T_ in T[t]:
            S[T_[0]-1].add(T_[1])
    ok=True
    for s in S.keys():
        if len(S[s])!=1:
            ok='False'
            break

    return ok

ok_max = -1
for i in range(2**N):
#     print('=====',i)
    true_list=[]
    for j in range(N):
        if i>>j&1 ==True:
            true_list.append(j)
#     print(true_list)
#     print(check_Contradiction(true_list))
            
    if check_Contradiction(true_list)==True:
        if ok_max < len(true_list):
            ok_max=len(true_list)
            
print(ok_max)
S = input()
cnt = 0
for i in s:
    if i == "o":
    cnt += 1
print(cnt * 100 + 700)


### FIXED CODE ###

S = input()
cnt = 0
for i in S:
    if i == "o":
        cnt += 1
print(cnt * 100 + 700)
while True:
    a,op,b=input().split()
    if(op==+) print(f"{a+b}")
    else if(op==-) print(f"{a-b}")
    else if(op==*) print(f"{a*b}")
    else if(op==/) print(f"{a//b}")
    else if(op==?) break



### FIXED CODE ###

while True:
    a,op,b=input().split()
    a=int(a)
    b=int(b)
    if op=='+':
        print(f"{a+b}")
    elif op=='-':
        print(f"{a-b}")
    elif op=='*':
        print(f"{a*b}")
    elif op=='/':
        print(f"{a//b}")
    elif op=='?':
        break
s = map(int, input().split())
return (s[0] == s[1] == 5 and s[2] == 7 or s[2] == s[1] == 5 and s[0] == 7 or s[0] == s[2] == 5 and s[1] == 7)



### FIXED CODE ###

a, b, c = map(int, input().split())
if (a==b == 5 and c ==7) or (a==c == 5 and b ==7) or (c== b == 5 and a ==7):
  print("YES")
else:
  print("NO")
a,b=input().split()
c,d=int(a),int(b)
l=[int(input()) for i in range(c)]
L=sorted(l)
x=L[d]-L[0]
for i in range(c-d+1):
    if L[d+i]-L[i]<x:
        x=L[d+i]-L[i]
print(x)

### FIXED CODE ###

a,b=input().split()
c,d=int(a),int(b)
l=[int(input()) for i in range(c)]
L=sorted(l)
x=L[d-1]-L[0]
for i in range(c-d+1):
    if L[d+i-1]-L[i]<x:
        x=L[d+i-1]-L[i]
print(x)
length = 0
max_length=0
for i in range(N-1):
    if H[i+1] - H[i] >= 0:
        length +=1
    else:
        max_length = length
        length = 0
print(length)
        

### FIXED CODE ###

import numpy as np
N = int(input())
H = np.array([int(i) for i in input().split(' ')])
length = 0
max_length=0
for i in range(N-1):
    if H[i+1] - H[i] <= 0:
        length +=1
    else:
        length = 0
        if max_length < length:
            max_length = length
    if max_length < length:
        max_length = length
print(max_length)
n = int(input())
d = {}
k = 0
for _ in range(n-1):
    a, b = map(int, input().split())
    if a not in d:
        d[a] = [b]
    else:
        d[a].append(b)
for i in d.keys():
    tmp_k = len(d[i]) if i == 1 else len(d[i]) + 1
    k = max(k, tmp_k)
print(k)
dd = {1: 0}
for i, v in d.items():
    cnt = 1
    for j in v:
        if cnt != dd[i]:
            c = cnt
            cnt += 1
        else:
            c = cnt + 1
            cnt += 2
        print(c)
        dd[j] = c


### FIXED CODE ###

n = int(input())
L = []
d = {}
for _ in range(n-1):
    a, b = map(int, input().split())
    L.append((a, b))
    if a not in d:
        d[a] = [b]
    else:
        d[a].append(b)
k = 0
for i in d.keys():
    tmp_k = len(d[i]) if i == 1 else len(d[i]) + 1
    k = max(k, tmp_k)
print(k)
key = sorted(d.keys())
dd = {1: 0}
ans = {}
for i in key:
    v = d[i]
    cnt = 1
    for j in v:
        if cnt != dd[i]:
            c = cnt
            cnt += 1
        else:
            c = cnt + 1
            cnt += 2
        ans[(i, j)] = c
        dd[j] = c
for a, b in L:
    print(ans[(a, b)])
N, M = map(int, input().split())

graph = [[] for _ in range(110000)]

for _ in range(M):
    x, y = map(int, input().split())

    graph[x].append(y)

dp_memo = [-1] * 110000

def dp(v):
    if dp_memo[v] != -1:
        return dp_memo[v]

    ret = 0
    for item in graph[v]:
        ret = max(ret, dp(item) + 1)

    dp_memo[v] = ret
    return ret

ans = 0

for i in range(1, N+1):
    ans = max(ans, dp(i))

print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(110000) #再帰上限はデフォルトで1000回までなので，増やす。

N, M = map(int, input().split())

graph = [[] for _ in range(110000)]

for _ in range(M):
    x, y = map(int, input().split())

    graph[x].append(y)

dp_memo = [-1] * 110000

def dp(v):
    if dp_memo[v] != -1:
        return dp_memo[v]

    ret = 0
    for item in graph[v]:
        ret = max(ret, dp(item) + 1)

    dp_memo[v] = ret
    return ret

ans = 0

for i in range(1, N+1):
    ans = max(ans, dp(i))

print(ans)
n=int(input())
p=sorted(list(map(int,input().split())))
s=[]
m = 10**6+1
a=[True for _ in range(m)]
prev = 0
flag = True
for x in p:
    if prev == x:
        if flag and s[-1] == x:
            s.pop()
            flag = False
        continue
    if a[x]:
        s.append(x)
    i = 2
    y = i*x
    while y<m:
        a[y] = False
        i+=1
        y = i*x
    prev=x
    flag = True

print(len(s))

### FIXED CODE ###

n=int(input())
p=sorted(list(map(int,input().split())))
s=set()
m = 10**6+1
a=[True for _ in range(m)]
prev = 0
for x in p:
    if prev == x:
        s.discard(x)
        continue
    if a[x]:
        s.add(x)
    i = 2
    y = i*x
    while y<m:
        a[y] = False
        i+=1
        y = i*x
    prev=x

print(len(s))
from math import gcd 
from functools import reduce
n=int(input())
a=list(map(int,input().split()))
ans=0
for i in range(n):
    ans=max(ans,reduce(gcd,a[:i]+a[i+1:]))
print(ans)

### FIXED CODE ###

from fractions import gcd
n=int(input())
a=list(map(int,input().split()))
L=[0]
R=[0]
for i in range(n-1):
    L.append(gcd(L[i],a[i]))
    R.append(gcd(R[i],a[-1-i]))
MAX=0
for i in range(n):
    MAX=max(MAX,gcd(L[i],R[-1-i]))
print(MAX)
l = input().split()
n = int(l[0])
x = int(l[1])
l = input().split()
cnt = 1
d = 0

while(True):
    d = d + int(l[cnt-1])
    if(d<=x):
        cnt = cnt + 1
    else:
        break

print(cnt)

### FIXED CODE ###

l = input().split()
n = int(l[0])
x = int(l[1])
l = input().split()
cnt = 1
d = 0

while(cnt -1 < len(l)):
    d = d + int(l[cnt-1])
    if(d<=x):
        cnt = cnt + 1
    else:
        break

if(cnt > n+1):
    cnt = n+1
print(cnt)
# input
N, M = map(int, input().split())
G = [list(map(int, input().split())) for _ in range(M)]
edges = [set() for _ in range(N)]

for a, b in G:
    edges[a - 1].add((b - 1, 1))
    edges[b - 1].add((a - 1, 1))

def dfs(start, edges, path):
    path.append(start)
    if len(path) == n:
        path.pop()
        return 1
    ans = 0
    for u in edges[start]:
        if u in path:
            continue
        ans += dfs(u, path)
    path.pop()
    return ans    

print(dfs(0, []))


### FIXED CODE ###

# input
N, M = map(int, input().split())
G = [list(map(int, input().split())) for _ in range(M)]
edges = [set() for _ in range(N)]

for a, b in G:
    edges[a - 1].add(b - 1)
    edges[b - 1].add(a - 1)

def dfs(start, edges, path):
    path.append(start)
    if len(path) == N:
        path.pop()
        return 1
    ans = 0
    for u in edges[start]:
        if u in path:
            continue
        ans += dfs(u, edges, path)
    path.pop()
    return ans    

print(dfs(0, edges, []))
N, K, X, Y=[int(input()) for i in range(4)]
if n=<K:
  print(K*X)
else:
print(K*X+Y*(N-K))

### FIXED CODE ###

N, K, X, Y=[int(input()) for i in range(4)]
if N<=K:
  print(N*X)
else:
  print(K*X+Y*(N-K))
a,b,k = map(int,input().split())
x = []
for i in range(1,a):
    if a%i == 0 and b%i == 0:
        x.append(i)
print(x[-k])

### FIXED CODE ###

a,b,k = map(int,input().split())
x = []
for i in range(1,a+1):
    if a%i == 0 and b%i == 0:
        x.append(i)
print(x[-k])
r = input()
print(3 * r * r)

### FIXED CODE ###

r = int(input())
print(3 * r * r)
def func(n):
    return (n * (n - 1)) // 2


node_size, input_size = [int(i) for i in input().split()]

br = [func(node_size)]
for _ in range(input_size):
    br.append([int(i) for i in input().split()])

cnt_list = [func(node_size)]

index = 0
node_to_group = {}
group_to_index = {}
index_size = {}

for j in range(1, input_size + 1):
    flag1, flag2 = br[-j][0] in node_to_group, br[-j][1] in node_to_group

    if flag1 and flag2:
        if group_to_index[node_to_group[br[-j][0]]] == group_to_index[node_to_group[br[-j][1]]]:
            tmp = cnt_list[0]
        else:
            tmp = cnt_list[0] + func(index_size[group_to_index[node_to_group[br[-j][0]]]]) + \
                  func(index_size[group_to_index[node_to_group[br[-j][1]]]]) - \
                  func(index_size[group_to_index[node_to_group[br[-j][0]]]] +
                       index_size[group_to_index[node_to_group[br[-j][1]]]])
            index_size[group_to_index[node_to_group[br[-j][0]]]] += index_size[group_to_index[node_to_group[br[-j][1]]]]
            del index_size[group_to_index[node_to_group[br[-j][1]]]]
            group_to_index[node_to_group[br[-j][1]]] = group_to_index[node_to_group[br[-j][0]]]

    elif flag1:
        tmp = cnt_list[0] - index_size[group_to_index[node_to_group[br[-j][0]]]]
        node_to_group[br[-j][1]] = node_to_group[br[-j][0]]
        index_size[group_to_index[node_to_group[br[-j][0]]]] += 1
    elif flag2:
        tmp = cnt_list[0] - index_size[group_to_index[node_to_group[br[-j][1]]]]
        node_to_group[br[-j][0]] = node_to_group[br[-j][1]]
        index_size[group_to_index[node_to_group[br[-j][1]]]] += 1
    else:
        tmp = cnt_list[0] - 1
        node_to_group[br[-j][0]] = br[-j][0]
        node_to_group[br[-j][1]] = br[-j][0]
        group_to_index[br[-j][0]] = index
        index_size[index] = 2
        index += 1
    
    if tmp == 0:
        for _ in range(input_size - j):
            print(0)
        break
    cnt_list.insert(0, tmp)

for i in cnt_list:
    print(i)

### FIXED CODE ###

def search_root(l, n):
    i = n
    while l[i] != i:
        i = l[i]
    return i


def set_root(l, root_index, start_index):
    i = start_index
    while l[i] != root_index:
        tmp = i
        i = l[i]
        l[tmp] = root_index


def func(n):
    return (n * (n - 1)) // 2


node_size, input_size = [int(i) for i in input().split()]

br = []
for _ in range(input_size):
    br.append([int(i) for i in input().split()])

cnt_list = [0]
size_list = [1 for _ in range(node_size + 1)]
node_list = [i for i in range(node_size + 1)]

for i in range(1, input_size + 1):
    node1, node2 = br[-i]

    root1, root2 = search_root(node_list, node1), search_root(node_list, node2)

    if root1 == root2:
        cnt_list.append(cnt_list[-1])
    else:
        cnt_list.append(cnt_list[-1] + (size_list[root1] * size_list[root2]))
        if size_list[root1] < size_list[root2]:
            node_list[root1] = root2
            size_list[root2] += size_list[root1]
        else:
            node_list[root2] = root1
            size_list[root1] += size_list[root2]

val = func(node_size)
for i in cnt_list[::-1][1:]:
    print(val - i)
a,b,c,d = map(int,input().split())

if abs(a-c) =< d:
  print("Yes")
elif abs(a-b) =< d and abs(c-b) =< d:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

a,b,c,d = map(int,input().split())

if abs(a-c) <= d:
  print("Yes")
elif abs(a-b) <= d and abs(c-b) <= d:
  print("Yes")
else:
  print("No")
a = input()
n = len(a)
if (a[n-1]==3):
  print(bon)
elif(a[n-1] in [0,1,6,8]):
  print(hon)
else:
  print(pon)

### FIXED CODE ###

a = input()
n = len(a)
if (int(a[n-1])==3):
  print("bon")
elif(int(a[n-1]) in [0,1,6,8]):
  print("pon")
elif(int(a[n-1]) in [2,4,5,7,9]):
  print("hon")
a,b,x=map(int,input().split())
if a+b>x:
  print(0)
  exit()
k=(x-b)//a+1

while k>0:
  n=a*k+len(str(k))*b

  if n<=x:
    if n>10**9:
      print(10**9)
      exit()
    print(k)
    exit()
  k-=1


### FIXED CODE ###

s = input()
if s=="SUN":
  print(7)
elif s=="MON":
  print(6)
elif s=="TUE":
  print(5)
elif s=="WED":
  print(4)
elif s=="THU":
  print(3)
elif s=="FRI":
  print(2)
else:
  print(1)
a,b=map(int,input().split())
ans=0
flag=False
for i in range(b*10,(b+1)*10+1):
    x=i*8
    if 100*(a+1>x>=100*a:
        flag=True
        ans=i
        break
print(ans if flag else -1)

### FIXED CODE ###

a,b=map(int,input().split())
ans=0
flag=False
for i in range(b*10,(b+1)*10):
    x=i*8
    if 100*(a+1)>x>=100*a:
        flag=True
        ans=i
        break
print(ans if flag else -1)
n, k = map(int, input().split()) 
a_list = list(map(int, input().split())) 

rireki = [0] * (n+10)
curr_c = 1
rireki[1] = 0

no_loop_count = k
loop_cnt = 1

mugen = False
for i in range(n):
    next_c = a_list[curr_c-1]
    # print(i, curr_c, next_c)
    # if next_c == curr_c:
    #     mugen = True
    if next_c == 1:
        no_loop_count = 0
        loop_cnt = i + 1
        break
    elif rireki[next_c] == 0:
        rireki[next_c] = i+1
    else:
        # print(next_c)
        no_loop_count = rireki[next_c] -1
        loop_cnt = i - no_loop_count
        break
    curr_c = next_c


# if not mugen:
if k <= no_loop_count:
    ans = rireki.index(k)
else:
    # print('k',k)
    # print('no', no_loop_count)
    # print('lo', loop_cnt)
    ind = (k-1-no_loop_count)%loop_cnt +1
    rireki_fix = [i-no_loop_count for i in rireki]
    # print(ind, 'ind')
    ans = rireki_fix.index(ind)
    # print(rireki_fix)
    print(ans)

### FIXED CODE ###

def main():
    n, k = map(int, input().split()) 
    al = list(map(int, input().split())) 
    city_l = [1]
    city_s = set([1])
    loop_city_l = []
    curr_city = 1
    cnt = 0
    for i in range(1,k+1):
        next_c = al[curr_city-1]
        if next_c in city_s:
            cnt = i
            first_city = city_l.index(next_c)
            loop_city_l = city_l[first_city:]
            break
        else:
            city_s.add(next_c)
            city_l.append(next_c)
        curr_city = next_c
    else:
        print(curr_city)
        return

    # print(loop_city_l)
    remained = k-cnt
    last_pos = remained%len(loop_city_l)
    print(loop_city_l[last_pos])

if __name__ == "__main__":
    main()
n, m = map(int, input().split())

ans = [0]*n 

for i in range(m):
    s, c = map(int, input().split())
    if ans[s-1] == 0:
        ans[s-1] = c 
    elif not ans[s-1] == c:
        print(-1)
        break
    if i == m-1:
        if ans[0] == 0:
            print(-1)
        else:
            for j in range(n):
                a = a+ans[j]*(10**(n-j-1))
            print(a)

### FIXED CODE ###

n, m = map(int, input().split())
x = [-1]*n
ans = 0
count = 0
for i in range(m):
    s, c = map(int, input().split())
    if (s==1) and (c==0) and(n!=1):
        count = 1
    if x[s-1]!=-1 and x[s-1]!=c:
        count = 1
    if x[s-1] != c:
        ans += c*(10**(n-s))
    x[s-1] = c

if count==1:
    print(-1)
elif n==1 and ans==0:
    print(0)
elif ans>=10**(n-1):
    print(ans)
else:
    print(ans+10**(n-1))