Harryxun/stf_run huggingface dataset:
M,N,P = map(int, input().split())

edges = []
for _ in range(N):
    edges.append(map(int, input().split()))

neg_inf = float("-Inf")
no_answer = False

start = 1
end = M

distance = {}
distance[start] = 0
previous = {}

for i in range(M-1):
    for f,t,w in edges:
        if distance.get(f,neg_inf) + w - P > distance.get(t,neg_inf):
            distance[t] = distance[f] + w - P
            previous[t] = f

path = []
node = end
if node in previous:
    while node != start:
        path.append(node)
        node = previous[node]
        if node in path:
            no_answer = True
            break
    path.append(start)

for f,t,w in edges:
    if distance.get(f,neg_inf) + w - P > distance.get(t,neg_inf) and t in path:
        no_answer = True
        break

if no_answer:
    print(-1)
else:
    print(max(0,distance[end]))


### FIXED CODE ###

def is_reachable(edges,start,end):
  g = {}
  for f,t,w in edges:
    if f in g: g[f].append(t)
    else: g[f] = [t]
  visiting = [start]
  visited = {}
  while visiting:
    v = visiting.pop()
    if v in visited: continue
    if v == end: return True
    visited[v] = True
    for v2 in g.get(v, ()):
      if v2 in visited or v2 in visiting: continue
      visiting.append(v2)
  return False

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

edges = []
for _ in range(M):
    a,b,c = map(int, input().split())
    edges.append((a,b,c))

neg_inf = float("-Inf")
no_answer = False

start = 1
end = N

distance = {}
for i in range(1,N+1):
  distance[i] = neg_inf
distance[start] = 0

for i in range(N-1):
    for f,t,w in edges:
        if distance[f] + w - P > distance[t]:
            distance[t] = distance[f] + w - P

for f,t,w in edges:
    if distance[f] + w - P > distance[t] and is_reachable(edges,t,end):
        no_answer = True
        break

if no_answer:
    print(-1)
else:
    print(max(0,distance[end]))
INF = 2000000000
n ,limit_w = map(int, input().split())
w = [0]*n
v = [0]*n
for i in range(n):
    w[i], v[i] = map(int, input().split())
sum_v = sum(v)
dp = [INF for i in range(sum_v + 1)]
dp[0] = 0
for i in range(n):
    for j in range(sum_v ,-1,-1):
        if j >= v[i]:
            dp[j] = min(dp[j], dp[j - v[i]] + w[i])
for i in range(sum_v ,-1,-1):
    if dp[i] <= limit_w:
		print(i)

### FIXED CODE ###

"""
重さと価値がそれぞれw_i,v_iであるようなn個の品物がある.
これらの品物の中から, 重さの総和がWを超えないように選んだ時の,
価値の総和の最大値を求めよ.
1<=n<=100, 1<=w_i<=10^7, 1<=v_i<=100, 1<=W<=10^9
"""
#-------------------------------------------------------------------------------

#入力
INF=2*10**9
n,W = map(int,input().split())
w=[0]*n
v=[0]*n
for i in range(n):
    x,y = map(int, input().split())
    w[i] = x
    v[i] = y
max_v=max(v)
dp = [[INF for i in range(n*max_v+1)] for j in range(n+1)]

#ここからメイン
dp[0][0]=0
for i in range(n):
    for j in range(n*max_v+1):
        if j<v[i]:
            dp[i+1][j]=dp[i][j]
        else:
            dp[i+1][j]=min(dp[i][j],dp[i][j-v[i]]+w[i])
ans=0
for i in range(n*max_v+1):
    if dp[n][i]<=W:
        ans=i
print(ans)
H,W = map(int,input().split())
List=[input() for i in range(H)]
A =[[[1]*(W) for i in range(H)]
B =[[] for i in range(W)]
for i in range(H):
    k = 0
    a = 0
    while k < W:
        if List[i][k]==".":
            a += 1
            k = k+1
        else:
            for j in range(a):
                A[i][k-j-1]=a
            A[i][k]=a
            a = 0
            k = k+1
    for j in range(a):
                A[i][k-j-1]=a
for i in range(W):
    k = 0
    a = 0
    while k < H:
        if List[k][i]==".":
            a += 1
            k = k+1
        else:
            for j in range(a):
                B[i][k-j-1]=a
            B[i][k] = 0
            a = 0
            k = k+1
    for j in range(a):
                B[i][k-j-1]= a
max = 0
for i in range(H):
    for j in range(W):
        if max < A[i][j] + B[j][i]:
            max = A[i][j] + B[j][i]
print(max-1)
        

### FIXED CODE ###

H,W = map(int,input().split())
List=[input() for i in range(H)]
A =[[1]*(W) for i in range(H)]
B =[[1]*(H) for i in range(W)]
for i in range(H):
    k = 0
    a = 0
    while k < W:
        if List[i][k]==".":
            a += 1
            k = k+1
        else:
            for j in range(a):
                A[i][k-j-1]=a
            A[i][k]=a
            a = 0
            k = k+1
    for j in range(a):
                A[i][k-j-1]=a
for i in range(W):
    k = 0
    a = 0
    while k < H:
        if List[k][i]==".":
            a += 1
            k = k+1
        else:
            for j in range(a):
                B[i][k-j-1]=a
            B[i][k] = 0
            a = 0
            k = k+1
    for j in range(a):
                B[i][k-j-1]= a
max = 0
for i in range(H):
    for j in range(W):
        if max < A[i][j] + B[j][i]:
            max = A[i][j] + B[j][i]
print(max-1)
ab_str = input()
a_str, b_str = ab_str.split()
a = int(a_str)
b = int(b_str)
if a%2 == 0 or b%2 == 0:
  print(Even)
else:
  print(Odd)

### FIXED CODE ###

ab_str = input()
a_str, b_str = ab_str.split()
a = int(a_str)
b = int(b_str)
if a%2 == 0 or b%2 == 0:
    print('Even')
else:
    print('Odd')
a = int(input().split())
if a < 1200:
    print("ABC")
elif a < 2800:
    print("ARC")
else:
    print("AGC")

### FIXED CODE ###

a = int(input())
if a < 1200:
    print("ABC")
elif a < 2800:
    print("ARC")
else:
    print("AGC")
a,b = map(int, input().split())
  
  if a*b % 2 == 0:
    print("Even")
  else:
    print("Odd")
    
 

### FIXED CODE ###

a, b = map(int, input().split())
if (a*b) % 2:
    print("Odd")
else:
    print("Even")
import math
 
n = int(input())
answers = []

if n == 0:
  print(':(')
else:
  for i in range(1, n):
    if math.floor(i * 1.08) == n:
      answers.append(i)
  if len(answers) == 0:
    print(':(')
  if len(answers) == 1:
    print(answers[0])
  else:
    print(answers[len(answers) // 2])

### FIXED CODE ###

n = int(input())
 
ans = -1
for i in range(1, n+1):
  if int(i  * 1.08) == n:
    ans = i
if ans == -1:
  print(':(')
else:
  print(ans)
import math
H, W, M = map(int, input().split())

if H <= W:
    for i in range(1, H + 1):
    if W * i => M:
        print(i)

elif:
    for k in range(1, W + 1):
    if H * k => M:
        print(k)

### FIXED CODE ###

H = int(input())
W = int(input())
M = int(input())

if H <= W:
    for i in range(1, H + 1):
        if W * i >= M:
            print(i)
            break
            
else:
    for k in range(1, W + 1):
        if H * k >= M:
            print(k)
            break
import numpy as np
def main():
  ttt = []
  n = int(input())
  e = [[int(i) for i in input().split()] for i in range(int(input()))]
  for i in range(n):
    t = e[0][0] - e[1][i]*0.006
    tt = abs(e[0][1] - t)
    ttt.append(tt)
  ttt = np.array(ttt)
  print(np.argmin(ttt)+1)
main()

### FIXED CODE ###

import numpy as np
def main():
    ttt = []
    n = int(input())
    N, M = map(int, input().split())
    e = list(map(int, input().split()))
    #e = [[int(i) for i in input().split()] for i in range(int(input()))]
    #n = 3
    #e = [[21,-11],[81234,94124,52141
    for j in range(n):
        t = N - e[j]*0.006
        tt = abs(M - t)
        ttt.append(tt)
    ttt = np.array(ttt)
    print(np.argmin(ttt)+1)
main()
n = int(input())
def c(x,y):
    if 0 <= x < n and 0 <= y < 2:
        if cache[y][x] != " ":
            return cache[y][x]

        if x == 0 and y == 0:
            total = matrice[0][0]
        else:
            if x > 0:
                tt1 = c(x-1,y)
            else:
                tt1 = 0
            if y > 0:
                tt2 = c(x,y-1)
            else:
                tt2 = 0
            total = max(tt1,tt2) + matrice[y][x]
        cache[y][x] = total
        return total

    
matrice = []
cache = [ [" " for i in range(n)] for a in range(2) ] 
for i in range(2):
    matrice.append( [ int(i) for i in input().split() ] )

print( c(n-1,1) )


### FIXED CODE ###

argent = int(input())
gateau = int(input())
donut = int(input())

argent -= gateau
argent %= donut
print(argent)
print((int(input())**3)

### FIXED CODE ###

print((int(input()))**3)
s=input()
if s='A':
  print('T')
elif s='T':
  print('A')
elif s='C':
  print('G')
else:
  print('C')

### FIXED CODE ###

s=input()
if s=='A':
  print('T')
elif s=='T':
  print('A')
elif s=='C':
  print('G')
else:
  print('C')
kekka = ""
num = []
hantei = "OK"
INF = input().split()
gyosu = int(INF[1])
keta = int(INF[0])
out = []
for l in range(keta):
  out.append(0)


for i in range(gyosu):
  num.append([int(j) for j in input().split()])

for j in range(gyosu - 1):
  for k in range(gyosu - 1):
    if num[j][0] == num[k + 1][0]:
      if num[j][1] != num[k + 1][1]:
        hantei = "NG"
          
  if num[j][0] == keta:
    if num[j][1] == 0:
      hantei ="NG"

if hantei == "NG":
  print("-1")
else:
  for m in range(gyosu):
    out[(num[m][0] - 1)] = num[m][1]
    #print(out)





### FIXED CODE ###

import math

N = int(input())
P = math.floor(N / 2)
P = P + N % 2
print(P)
a,b,c,d=map(int, input().split())
while
	b -= c
	if c<=0
		print"Yes"
 		break
	a -=d
	if a<=0
      	print"No"
        break

### FIXED CODE ###


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

while True:
  c -= b
  if c <= 0:
    print('Yes')
    break
  
  a -= d
  if a <= 0:
    print('No')
    break
n = int(input())
for i in range(n):
  x1, y1, x2, y2, x3, y3, x4, y4 = [float(j) for j in input().split()]
  if x2 - x1 == 0.0:
    if x4 - x3 == 0.0:
      print("YES")
    else:
      print("NO")
  elif x4 - x3 == 0.0:
    print("NO") 
  print("YES" if (y2 - y1) / (x2 - x1) == (y4 - y3) / (x4 - x3) else "NO")

### FIXED CODE ###

n = int(input())
for i in range(n):
  x1, y1, x2, y2, x3, y3, x4, y4 = [float(j) * 10**10 for j in input().split()]
  if x2 == x1:
    if x4 == x3:
      print("YES")
    else:
      print("NO")
  elif x4 == x3:
    print("NO")
  else:
    print("YES" if (y2 - y1) / (x2 - x1) == (y4 - y3) / (x4 - x3) else "NO")
a,b = [int(input()).split()]

if a >=13:
  print(b)
elif a >= 6:
  print(int(b/2))
else:
  print('0')

### FIXED CODE ###

a,b = [int(i) for i in input().split()]

if a >= 13:
  print(b)
elif a >= 6:
  print(int(b/2))
else:
  print(0)
N, M = map(int, input().split())
A = [input() for _ in range(N)]
B = [input() for _ in range(M)]

flag = 'No'
for i in range(N-M):
    for j in range(N-M):
        check = []
        for k in range(M):
            if A[i+k][j:j+M] == B[i+k]:
                check.append(1)
            else:
                check.append(-1)
        if sum(check) == M:
            flag = 'Yes'
print(flag)			


### FIXED CODE ###

N, M = map(int, input().split())
A = [input() for _ in range(N)]
B = [input() for _ in range(M)]

flag = 'No'
for i in range(N-M+1):
    for j in range(N-M+1):
        check = []
        for k in range(M):
            if A[i+k][j:j+M] == B[k]:
                check.append(1)
            else:
                check.append(-1)
        if sum(check) == M:
            flag = 'Yes'
print(flag)
N, K, *H = map(int, open(0).read().split())
H.sort()
a=float('inf')
for i in range(N-K+1):
    a=min(a,H[i+k-1]-H[i])
print(a)

### FIXED CODE ###

N, K = map(int, input().split())
h = sorted([int(input()) for _ in range(N)])
print(min([h[i+K-1]-h[i] for i in range(N - K + 1)]))
import heapq
N,K = map(int, input().split())
*V, = map(int, input().split())
#N, K = 6, 4
#V = [-10, 8, 2, 1, 2, 6]
motimono = []
ans = []

if K >= N: # 操作回数のほうが大きいなら、全部取り出してから何個戻すかを考える
    K -= N
    heapq.heapify(V)
    ans.append(sum(V))
    for i in range(K):
        if len(V)>0:
            heapq.heappop(V)
        ans.append(sum(V))
    print(max(ans))

else:
    V *= 2 # 前後からの取り出しを楽にするためにこうしておく
    #print(V)
    for j in range(1,K+1): # 取り出す個数
        for i in range(N-j, N+1): # 何番目から取り出すか
            motimono = V[i:i+j]
            #print(str(j), str(i), motimono)
            ans.append(sum(motimono))
            #print(ans)
            heapify(motimono)
            for i in range(K-j): # 戻す個数
                if len(motimono)>0:
                    heappop(motimono)
                ans.append(sum(motimono))
    print(max(ans))

### FIXED CODE ###

import heapq
N,K = map(int, input().split())
*V, = map(int, input().split())
#N, K = 6, 4
#V = [-10, 8, 2, 1, 2, 6]
motimono = []
ans = []

if K >= N: # 操作回数のほうが大きいなら、全部取り出してから何個戻すかを考える
    K -= N
    heapq.heapify(V)
    ans.append(sum(V))
    for i in range(K):
        if len(V)>0:
            heapq.heappop(V)
        ans.append(sum(V))
    print(max(ans))

else:
    V *= 2 # 前後からの取り出しを楽にするためにこうしておく
    #print(V)
    for j in range(1,K+1): # 取り出す個数
        for i in range(N-j, N+1): # 何番目から取り出すか
            motimono = V[i:i+j]
            #print(str(j), str(i), motimono)
            ans.append(sum(motimono))
            #print(ans)
            heapq.heapify(motimono)
            for i in range(K-j): # 戻す個数
                if len(motimono)>0:
                    heapq.heappop(motimono)
                ans.append(sum(motimono))
    print(max(ans))
n = int(input())
d,x = map(int,input().split())
count = x
for i in range(n):
  a[i] = int(input())
  count += d//a + 1
print(count)

### FIXED CODE ###

n = int(input())
d,x = map(int,input().split())
count = x
a = [int(input()) for i in range(n)]
for i in range(n):
  j = 0
  while j * a[i] + 1 <= d:
    count += 1
    j += 1
print(count)
nab = input().split()
n = nab[0]
a = nab[1]
b = nab[2]

if n*a > b:
  print(n*a)
else:
  print(b)

### FIXED CODE ###

nab = input().split()
n = int(nab[0])
a = int(nab[1])
b = int(nab[2])

if n*a > b:
  print(b)
else:
  print(n*a)
import math
n=int(input())
for i in range(1,n+1):
  max = int(math.sqrt(i))
  result = 0
  for x in range(1,max+1):
    for y in range(1,max+1):
      for z in range(1,max+1):
        if x * x + y * y + z * z + x * y + y * z + x * z == i:
          result += 1
  print(result)

### FIXED CODE ###

l,r,d = map(int,input().split())
result = 0
for i in range(l, r+1):
  if i % d == 0:
    result+= 1
print(result)
N = int(input())
 
for i in range(1,10):
  for j in range(1,10):
    if i*j=N:
      break
  if i*j=N:
    print("Yes")
    break
  elif i==9 and i*j!=N:
    print("No")

### FIXED CODE ###

A,B = map(int,input().split())
if A>=10 or B>=10:
   print(-1)
else:
   print(A*B)
N, M, R = map(int, input().split())
rs = permutations(map(lambda x: int(x) - 1, input().split()))
dist = [[10**9 for _ in range(N)] for _ in range(N)]
for _ in range(M):
    v1, v2, d = map(int, input().split())
    dist[v1-1][v2-1] = dist[v2-1][v1-1] = d
for i in range(N):
    dist[i][i] = 0
for k in range(N):
    for i in range(N):
        for j in range(N):
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
ans = 10**9
for r in rs:
    t = 0
    for i in range(R-1):
        t += dist[r[i]][r[i+1]]
        if t > 10**9:
            break
    ans = min(t, ans)
print(ans)

### FIXED CODE ###

from itertools import permutations
N, M, R = map(int, input().split())
rs = map(lambda x: int(x) - 1, input().split())
dist = [[10**9 for _ in range(N)] for _ in range(N)]
for _ in range(M):
    v1, v2, d = map(int, input().split())
    dist[v1-1][v2-1] = dist[v2-1][v1-1] = d
for i in range(N):
    dist[i][i] = 0
for k in range(N):
    for i in range(N):
        for j in range(N):
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
ans = 10**9
for r in permutations(rs):
    t = 0
    for i in range(R-1):
        t += dist[r[i]][r[i+1]]
        if t > 10**9:
            break
    ans = min(t, ans)
print(ans)
a,b = list(map(int, input().split()))
r=[300000, 200000, 100000]
ra=0
if a+b==2:
  print('1000000')
  exit()
if a<3:
  rb += r[a]
if b<3:
  ra += r[b]
 
print(ra)

### FIXED CODE ###

a,b = list(map(int, input().split()))
r=[300000, 200000, 100000]
ra=0
if a+b==2:
  print('1000000')
else:
    if a<4:
      ra += r[a-1]
    if b<4:
      ra += r[b-1]
    print(ra)
h,a = map(int, input().split())
print(h//a if !h%a else h//a + 1)

### FIXED CODE ###

h,a = map(int, input().split())
print(-(-h//a))
y, x = map(int, input().split())
    image = ["#" * (x+2)]
    for y in range(0,y):
        image.append("#"  + input() + "#")
    image.append("#" * (x+2))
    for img in image:
        print(img)


### FIXED CODE ###

y, x = map(int, input().split())
image = ["#" * (x+2)]
for y in range(0,y):
    image.append("#"  + input() + "#")
image.append("#" * (x+2))
for img in image:
    print(img)
a, b = map(int, input().split()
if (a + b) % 2 == 0:
           print((a + b) // 2)
else:
           print((a + b) // 2 + 1)

### FIXED CODE ###

a, b = map(int, input().split())
if (a + b) % 2 == 0:
    print((a + b) // 2)
else:
    print((a + b) // 2 + 1)
n, a, b = map(int, input().split())
blue='b'*a
red='r'*b
s = str(blue+red)*100
ss=s[:n]
print(ss.count('b'))

### FIXED CODE ###

n, a, b = map(int, input().split())
c = n//(a+b)
ans = c*a+min(n%(a+b), a)
print(ans)
a, b = [int(i) in input().split(" ")]
c = a/b
print(int(a/b), a%b, "{0:.6f}.format(c), sep = " ")

### FIXED CODE ###

a, b = [int(i) for i in input().split(" ")]
num1 = a // b
num2 = a % b
num3 = "{:.8f}".format(a / b)

print(num1, num2, num3)
n, m = map(int, input().split(' '))
a = [0]*m
b = [0]*m
for i in range(m):
    a[i], b[i] = list(map(int, input().split(' ')))

c = [-1]*(m+1)

def find(num):
    if c[num] < 0:
        return num
    else:
        k = find(c[num])
        c[num] = k
        return k

result = [int(n*(n-1)/2)]
for i in range(m-1, 0,-1):
    x = find(a[i])
    y = find(b[i])

    if x != y:
        result.append(result[-1]-c[x]*c[y])
        x, y = sorted([x,y])
        c[x] += c[y]
        c[y] = x
    else:
        result.append(result[-1])

for i in result[::-1]:
    print(int(i))


### FIXED CODE ###

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

c = [-1]*(m+2)

def find(num):
    if c[num] < 0:
        return num
    else:
        k = find(c[num])
        c[num] = k
        return k

result = [int(n*(n-1)/2)]
for i in range(m-1, 0,-1):
    x = find(a[i])
    y = find(b[i])

    if x != y:
        result.append(result[-1]-c[x]*c[y])
        x, y = sorted([x,y])
        c[x] += c[y]
        c[y] = x
    else:
        result.append(result[-1])

for i in result[::-1]:
    print(int(i))
n = int(input())
words = []
for i in range(n):
	a = int(input())
	w = []
	for _ in range(a):
		x, y = map(int, input().split())
		w.append([x-1, y])
	words.append(w)


ans = 0
for bit in range(1<<n):　#2のn乗まで捜査
	ok = True
	is_honest = [(bit>>i) & 1 for i in range(n)]
	#bitをiずらして末尾が1のひとは正直
	for i in range(n):
		if not is_honest[i]:
			continue
		for x, y in words[i]:
			if is_honest[x] != y:
				ok = False
	if ok:
		ans = max(ans, sum(is_honest))
print(ans)


### FIXED CODE ###

n = int(input())
words = []
for i in range(n):
	a = int(input())
	w = []
	for _ in range(a):
		x, y = map(int, input().split())
		w.append([x-1, y])
	words.append(w)


ans = 0
for bit in range(1<<n):
  #2のn乗まで捜査
	ok = True
	is_honest = [(bit>>i) & 1 for i in range(n)]
	#bitをiずらして末尾が1のひとは正直
	for i in range(n):
		if not is_honest[i]:
			continue
		for x, y in words[i]:
			if is_honest[x] != y:
				ok = False
	if ok:
		ans = max(ans, sum(is_honest))
print(ans)
N = int(input())
a = list(map(int, input().split()))
cnt1 = 0
li1 = []
for i in range(1,N):
    M = max(a)
    num = 0
    for j in range(N):
        if a[j] == M:
            n = j
    if a[i] < a[i-1]:
        num += -((-a[i-1]+a[i])//M)
        if num < 0:
            cnt1 = -1
            break
        a[i] += num*M
        for j in range(num):
            li1.append([n+1, i+1])
        cnt1 += num
cnt2 = 0
li2 = []
for i in range(1,N):
    M = min(a)
    num = 0
    for j in range(N):
        if a[j] == M:
            n = j
    if a[N-i] < a[N-i-1]:
        num += -((-a[N-i-1]+a[N-i])//(-M))
        if num < 0:
            cnt2 = -1
            break
        a[N-i-1] += num *M
        for j in range(num):
            li2.append([n+1, N-i])
        cnt2 += num
if cnt1 <= 2*N and cnt1 >= 0:
    print(cnt1)
    for x in li1:
        print(*x)
else:
    print(cnt2)
    for x in li2:
        print(*x)

### FIXED CODE ###

N = int(input())
a = list(map(int, input().split()))
cnt1 = 0
li1 = []
for i in range(1,N):
    M = max(a)
    num = 0
    for j in range(N):
        if a[j] == M:
            n = j
    if a[i] < a[i-1]:
        if M <= 0:
            cnt1= -1
            break
        num += -((-a[i-1]+a[i])//M)
        if num < 0 or num > 2*N:
            cnt1 = -1
            break
        a[i] += num*M
        for j in range(num):
            li1.append([n+1, i+1])
        cnt1 += num
cnt2 = 0
li2 = []
for i in range(1,N):
    M = min(a)
    num = 0
    for j in range(N):
        if a[j] == M:
            n = j
    if a[N-i] < a[N-i-1]:
        if M >= 0:
            cnt2 = -1
            break
        num += -((-a[N-i-1]+a[N-i])//(-M))
        if num < 0 or num > 2*N:
            cnt2 = -1
            break
        a[N-i-1] += num *M
        for j in range(num):
            li2.append([n+1, N-i])
        cnt2 += num
if cnt1 <= 2*N and cnt1 >= 0:
    print(cnt1)
    for x in li1:
        print(*x)
else:
    print(cnt2)
    for x in li2:
        print(*x)
n, m, x = map(int,input().split())
a = list(map(int,input().split())

#leftto0
cost_left = 0
b = range(x-1,0,-1)
for i in b:
    if i in a:
        cost_left+= 1
    
#right_to_N
cost_right = 0
for i in range(x+1, N):
    if i in a:
        cost_right+= 1
    
print(min(cost_left, cost_right))

### FIXED CODE ###

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

#leftto0
cost_left = 0
for i in range(x-1,0,-1):
    if i in a:
        cost_left+= 1
    
#right_to_N
cost_right = 0
for i in range(x+1, n):
    if i in a:
        cost_right+= 1
    
print(min(cost_left, cost_right))
n, m = map(int, input().split())
py = [[int(i) for i in input().split()] for _ in range(m)]
py_ = [[] for _ in range(m)]
for pi, yi in py:
    py_[pi-1].append(yi)
for i in range(m):
    py_[i].sort()
for pi, yi in py:
    print(str(pi).zfill(6) + str(py_[pi-1].index(yi) + 1).zfill(6))

### FIXED CODE ###

import bisect as bis
n, m = map(int, input().split())
idx = lambda x: x-1
p, y = [], []
for _ in range(m):
    p_, y_ = map(int, input().split())
    p.append(p_)
    y.append(y_)
val = [[] for _ in range(n)]
for i, j in zip(p, y):
    val[idx(i)].append(j)
for i in range(n):
    val[i].sort()
for i in range(m):
    v = p[i]
    id = bis.bisect_right(val[idx(v)], y[i])
    print(str(v).zfill(6) + str(id).zfill(6))