Harryxun/stf_run huggingface dataset:
from sys import stdin


class DFS():
    def __init__(self,A_B_arr,N,M):
        self.N = N
        self.M = M
        self.route = {i:[] for i in range(N+1)}
        for A, B in A_B_arr:
            self.route[A].append(B)
            self.route[B].append(A)

        self.dp = [[None,self.N] for i in range(N+1)]
        self.dp[1] = [1,0]

    def dfs(self,i,rank):
        for r in self.route[i]:
            if rank<self.dp[r][1]:
                self.dp[r] = [i,rank]
                self.dfs(r,rank+1)
        return


if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    N, M = list(map(int,_in[0].split(' ')))  # type:list(int)
    A_B_arr = []
    for i in range(M):
        _ = list(map(int,_in[i+1].split(' ')))  # type:list(int)
        A_B_arr.append(_)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    dfs = DFS(A_B_arr,N,M)
    dfs.dfs(1,1)

    ans = []
    TF = 'Yes'
    for (i,_) in enumerate(dfs.dp):
        if i>1:
            if _[0] == None:
                TF = 'No'
                break
            else:
                ans.append(_[0])
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    if TF == 'Yes':
        print(TF)
        for _ in ans:
            print(_)
    else:
        print(TF)


### FIXED CODE ###

from sys import stdin
from collections import deque


class BFS():
    def __init__(self, con, val=None):
        # 隣接リスト表現
        self.con = con
        self.val = val
        self.N = len(self.con)
        # 1つ前の部屋(1-indexed)
        self.dist = [-1]*self.N
        self.que = deque()

        # 初期条件(0-indexed)
        self.dist[0] = 0
        self.que.append(0)

    def bfs(self):
        while self.que:
            v = self.que.popleft()
            for next_v in self.con[v]:
                if self.dist[next_v] != -1:
                    continue
                self.dist[next_v] = v+1
                self.que.append(next_v)


if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    N, M = list(map(int,_in[0].split(' ')))  # type:list(int)
    A_B_arr = []
    for i in range(M):
        _ = list(map(int,_in[i+1].split(' ')))  # type:list(int)
        A_B_arr.append(_)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    con = [[] for i in range(N)]
    for A,B in A_B_arr:
        A -= 1
        B -= 1
        con[A].append(B)
        con[B].append(A)

    bfs = BFS(con)
    bfs.bfs()
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    if -1 in bfs.dist[1:]:
        print('No')
    else:
        print('Yes')
        for _ in bfs.dist[1:]:
            print(_)
import sys
sys.setrecursionlimit(100000)

N, M = map(int, input().split())
adj = [[] for _ in range(M)]
visited = [0] * N

for i in range(M):
  a, b = map(int, input().split())
  adj[a-1].append(b)
  adj[b-1].append(a)

ans = []

def dfs(x):
  visited[x-1] = 1
  if visited == [1] * N:
    ans.append(1)
  for i in range(len(adj[x-1])):
    if visited[adj[x-1][i] - 1] == 0:
      dfs(adj[x-1][i])
  visited[x-1] = 0
      
dfs(1)
print(sum(ans))

### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)

N, M = map(int, input().split())
adj = [[] for _ in range(N)]
visited = [0] * N

for i in range(M):
  a, b = map(int, input().split())
  adj[a-1].append(b)
  adj[b-1].append(a)

ans = []

def dfs(x):
  visited[x-1] = 1
  if visited == [1] * N:
    ans.append(1)
  for i in range(len(adj[x-1])):
    if visited[adj[x-1][i] - 1] == 0:
      dfs(adj[x-1][i])
  visited[x-1] = 0
      
dfs(1)
if ans == []:
  print(0)
else:
  print(sum(ans))
a, b, m = map(int, input().split())
A = [map(int, input().split())]
B = [map(int, input().split())]
C = sorted(A)
D = sorted(B)
l = C[0] + D[0]

for i in range(m):
  x, y, c = map(int, input().split())
  k = A[x-1] + B[y-1] -c
  if l > k:
    l = k
  else:
    continue
print(l)
  

### FIXED CODE ###

a, b, m = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = sorted(A)
D = sorted(B)
l = C[0] + D[0]
for i in range(m):
  x, y, c = map(int, input().split())
  k = A[x-1] + B[y-1] -c
  if l > k:
    l = k
print(l)
N = int(input())

nums = [int(input()) for x in range(N)]

a = sorted(nums)[-1]#max(nums)
b = sorted(nums)[-2]#max(nums.remove(max_num))



if a == b:
    for _ in range(nums):
        print(a)
else:
    for x in [b if x == a else a for x in nums]:
        print(x)

### FIXED CODE ###

N = int(input())

nums = [int(input()) for x in range(N)]

a = sorted(nums)[-1]#max(nums)
b = sorted(nums)[-2]#max(nums.remove(max_num))



if a == b:
    for _ in nums:
        print(a)
else:
    for x in [b if x == a else a for x in nums]:
        print(x)
from bisect import bisect_right

s = input()
t = input()

char_list = [[] for i in range(26)]

for i in range(2*len(s)):
        if i<len(s):
                char_list[ord(s[i])-97].append(i)
        else:
                char_list[ord(s[i-len(s)])-97].append(i)

INF = 10**27

for i in range(26):
        char_list[i].append(INF)

next_list = [[char_list[j][bisect_right(char_list[j],i)] for j in range(26)] for i in range(len(s))]

flag = False
for i in range(len(s)):
        if t[0]==s[i]:
                flag=True
                x = i
                y = i
                break
if flag:
        flag2 = True
        for i ina range(1,len(t)):
                n = next_list[x][ord(t[i])-97]
                y += n - x
                x = n%(len(s))
                if y >= INF:
                        flag2=False
                        break
        if flag2:
                print(y+1)
        else:
                print(-1)
else:
        print(-1)

### FIXED CODE ###

from bisect import bisect_right

s = input()
t = input()

char_list = [[] for i in range(26)]

for i in range(2*len(s)):
        if i<len(s):
                char_list[ord(s[i])-97].append(i)
        else:
                char_list[ord(s[i-len(s)])-97].append(i)

INF = 10**27

for i in range(26):
        char_list[i].append(INF)

next_list = [[char_list[j][bisect_right(char_list[j],i)] for j in range(26)] for i in range(len(s))]

flag = False
for i in range(len(s)):
        if t[0]==s[i]:
                flag=True
                x = i
                y = i
                break
if flag:
        flag2 = True
        for i in range(1,len(t)):
                n = next_list[x][ord(t[i])-97]
                y += n - x
                x = n%(len(s))
                if y >= INF:
                        flag2=False
                        break
        if flag2:
                print(y+1)
        else:
                print(-1)
else:
        print(-1)
N = int(input())
A = input()
X = 1000000000
count = 0
for i in range(N):
  while A[i] % 2 ==0:
    A[i] = A[i]//2
    count +=1
  if count < X:
    X = count
    count = 0
print(X)

### FIXED CODE ###

N = int(input())
A = input().split()
X = 1000000000
count = 0
for i in range(N):
  t = int(A[i])
  while t % 2 == 0:
    t = t//2
    count +=1
  if count < X:
    X = count
  count =0
print(X)
N, T = [int(s) for s in input().split()]

c = []
t = []
for n in N:
    inputs = input().split()
    c.append(int(inputs[0]))
    t.append(int(inputs[1]))

min_cost = None
for i in range(N):
    if t[i] <= T and (min_cost is None or c[i] <= min_cost):
        min_cost = c[i]
        result = i

return i

### FIXED CODE ###

x = input()
if x is "1":
    print("Hello World")
elif x is "2":
    a = int(input())
    b = int(input())
    print(a+b)
import collections
def main():

    X, Y, A, B, C = map(int, input().split())
    p = list(map(int, input().split()))
    q = list(map(int, input().split()))
    r = list(map(int, input().split()))
    p.sort(reverse = True)
    q.sort(reverse = True)
    r.sort(reverse = True)
    countA = 0
    countB = 0
    countC = 0
    ans = 0
    i = 0
    j = 0
    k = 0
    while countA < X and countB < Y and countC < C:
        v = max([p[i], q[j], r[k]])
        if p[i] == v:
            ans += p[i]
            countA += 1
            i += 1
        elif q[j] == v:
            ans += q[j]
            countB += 1
            j += 1
        else:
            ans += r[k]
            countC += 1
            k += 1

    if countA == X:
        targ = q[j:] + r[k:]
        targ.sort(reverse = True)
        return ans + sum(targ[:Y-countB-countC])
    if countB == Y:
        targ = p[i:] + r[k:]
        targ.sort(reverse = True)
        return ans + sum(targ[:X-countA-countC])

    pp = [0]
    qq = [0]
    p = p[i:]
    q = q[j:]
    for i in range(len(p)):
        pp.append(pp[-1] + p[i])
    for i in range(len(q)):
        qq.appendO(qq[-1] + q[i])

    out = ans
    for k in range(countC+1):
        m = X - k
        n = Y - (countC - k)
        if 0<= m < len(pp) and 0<=n < len(qq):
            out = max(out, ans + pp[m] + qq[n])
    return ans



if __name__ == '__main__':
    # main()
    print(main())

### FIXED CODE ###

import collections
def main():

    X, Y, A, B, C = map(int, input().split())
    p = list(map(int, input().split()))
    q = list(map(int, input().split()))
    r = list(map(int, input().split()))
    p.sort(reverse = True)
    q.sort(reverse = True)
    r.sort(reverse = True)

    p = p[:X]
    q = q[:Y]
    pqr = p + q + r
    pqr.sort(reverse = True)
    return sum(pqr[:X+Y])




if __name__ == '__main__':
    # main()
    print(main())
s = input()
k = int(input())

ans = 0

def f(text):
    ret = 0
    if len(set(text))==1:
        return len(text)//2
    else:
        for i in range(len(text)):
            if i==0:
                n=1
                tmp = text[i]
            elif text[i] == tmp:
                n += 1
            else:
                if n!=1:
                    ret += n//2
                tmp = text[i]
                n = 1
        return ret

if len(set(s))==1:
    s = s*k
    print(len(s)//2)
else:
    if s[0] != s[-1]:
        ans = f(s)
        print(ans*k)
    else:
        c = s[0]
        a, b = 0,0
        ite = 0
        if len(set(s))!=0:
            while s[a] == c:
                a += 1
            while s[len(s)-b-1] == c:
                b += 1
        s1 = s[:a]
        s2 = s[a:len(s)-b]
        s3 = s[len(s)-b:]
        
        A = f(s1)
        B = f(s3)
        C = f(s1+s3)
        X = f(s2)
        
        print(A+B+X*k+C*(k-1))

### FIXED CODE ###

s = input()
k = int(input())

if len(set(list(s)))==1:
    print(len(s)*k//2)

elif s[0] != s[-1]:
    cnt = 0
    for i in range(1, len(s)):
        if s[i] == s[i-1]:
            s = s[:i]+'.'+s[i+1:]
    print(s.count('.')*k)
else:
    a,b = 0,0
    c = s[0]
    rev_s = s[::-1]
    for i in range(len(s)):
        if s[i]==c:
            a += 1
        else:
            break
    for i in range(len(s)):
        if rev_s[i]==c:
            b += 1
        else:
            break
    cnt = 0
    for i in range(1, len(s)):
        if s[i] == s[i-1]:
            s = s[:i]+'.'+s[i+1:]
    print(s.count('.')*k - (a//2 + b//2 - (a+b)//2)*(k-1))
s = inpput()
while True:
	S = s
	if len(S) < 5:
		print('NO')
		break
	if S == 'dream' or S == 'erase':
		print('YES')
		break
	else:
		if S[0] == 'd':
			if S[7] == 'a':
				T ='dream'
				if S[:5] == T:
					S = S[5:]
					T = ""
					if S == "":
						print('YES')
						break
					s = S
				else:
					print('NO')
					break
			else:
				T = 'dreamer'
				if S[:7] == T:
					S = S[7:]
					T = ""
					if S == "":
						print('YES')
						break
					s = S
				else:
					print('NO')
					break
		if S[0] == 'e':
			if len(S) >= 6 and S[5] == 'r':
				T = 'eraser'
				if S[:6] == T:
					S = S[6:]
					T = ""
					if S == "":
						print('YES')
						break
					s = S
				else:
					print('NO')
					break
			else:
				T = 'erase'
				if S[:5] == T:
					S = S[5:]
					T = ""
					if S == "":
						print('YES')
						break
					s = S
				else:
					print('NO')
					break
		else:
			print('NO')
			break

### FIXED CODE ###

S=input()
 
S=S.replace('eraser','')
S=S.replace('erase','')
S=S.replace('dreamer','')
S=S.replace('dream','')
 
if S=='':
    print('YES')
else:
    print('NO')
s = list(input())
for i in range(len(s)):
  if i % 2 == 0:
    if not s[i] in "RUD":
      print ("No") 
      exit() 
  else: 
    if nit s[i] in "LUD":
      print("No")
      exit()
print("Yes")


### FIXED CODE ###

s = list(input())
for i in range(len(s)):
  if i % 2 == 0:
    if not s[i] in "RUD":
      print ("No") 
      exit() 
  else: 
    if not s[i] in "LUD":
      print("No")
      exit()
print("Yes")
n,k = map(int,input().split())
ans = 0
a = list[map(int,input().split())]
for i in range(n):
  if a[i] >= k:
    ans += 1
print(ans)

### FIXED CODE ###

n,k = map(int,input().split())
ans = 0
a = list(map(int,input().split()))
for i in range(n):
  if a[i] >= k:
    ans += 1
print(ans)
import sys
sys.setrecursionlimit(100000)

n = int(input())
edge = [[] for _ in range(n)]
for _ in range(n-1):
    a,b = map(int,input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)

def dfs(v,d,dist):
    dist[v] = d
    for ve in edge[v]:
        if dist[ve] is None:
            dist = dfs(ve, d+1, dist)
    return dist
    
    
f_dist = dfs(0,0,[None]*n)
s_dist = dfs(n-1,0,[None]*n)

fget = sum(1 for f,s in zip(f_dist,s_dist) if f<=s)
print("Fennec" if fget*2>n else "Snuke")

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)

n = int(input())
edge = [[] for _ in range(n)]
for _ in range(n-1):
    a,b = map(int,input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)

def dfs(v,d,dist):
    dist[v] = d
    for ve in edge[v]:
        if dist[ve] is None:
            dist = dfs(ve, d+1, dist)
    return dist
    
    
f_dist = dfs(0,0,[None]*n)
s_dist = dfs(n-1,0,[None]*n)

fget = sum(1 for f,s in zip(f_dist,s_dist) if f<=s)
print("Fennec" if fget*2>n else "Snuke")
N,M,C=map(int,input().split())
b=list(map(int,input().split()))
a=list(map(int,input().split()) for _ in range(N))
ab=list(range(N))
count=0

for i in range(N):
    for j in range(M):
        ab[i]+=a[i][j]*b[j]
    if ab[i]+C>0:
        count+=1

print(count)


### FIXED CODE ###

N,M,C=map(int,input().split())
b=list(map(int,input().split()))
a=list(range(N))
for i in range(N):
    a[i]=list(map(int,input().split()))
ab=list(range(N))
count=0

for i in range(N):
    ab[i]=0
    for j in range(M):
        ab[i]+=a[i][j]*b[j]
    if ab[i]+C>0:
        count+=1

print(count)
n=int(input())
f=lambda x:sum(map(int,str(x)))
v=1e9
for i in range(1,n//2+3):
  a=i
  b=n-i
  v=min(v,f(a)+f(b))
print(v)

### FIXED CODE ###

n=int(input())
f=lambda x:sum(map(int,str(x)))
v=1e9
for i in range(1,n//2+1):
  a=i
  b=n-i
  v=min(v,f(a)+f(b))
print(v)
import math

r = float(input())
s = math.pai * r ** 2
l = 4 * math.pai * r ** 3 / 3
print(s, l)



### FIXED CODE ###

pai = 3.141592653589793

r = float(input())
s = pai * r ** 2
l = 2 * pai * r
print(s, l)
P, Q, R = int(input()), int(input()), int(input())

if P < Q < R:
    t1 = P
    t2 = Q
elif P < R < Q:
    t1 = P
    t2 = R
else:
    t1 = Q
    t2 = R

print(t1+t2)

### FIXED CODE ###

P, Q, R = map(int, input().split())

times = []
times.append(P+Q)
times.append(P+R)
times.append(Q+R)

print(min(times))
n,m,c = map(int, input().split())
b = list(map(int, input().split()))
res = 0
for i in range(n):
  a = list(map(int, input().split()))
  if sum(a * b) + c > 0:
    res += 1
print(res)

### FIXED CODE ###

import numpy as np
n,m,c = map(int, input().split())
b = np.array(list(map(int, input().split())))
res = 0
for i in range(n):
  a = np.array(list(map(int, input().split())))
  if sum(a * b) + c > 0:
    res += 1
print(res)
import math


def digit_sum(b, n):
    if b > n:
        return n
    else:
        return digit_sum(b=b, n=n // b) + n % b


def main(n, s):
    if s > n:
        return -1
    elif n == s:
        return n + 1
    else:
        sqrt_n = int(math.sqrt(n))
        for b in range(2, sqrt_n + 1):
            if digit_sum(b, n) == s:
                return b
        b_min = 1L << 55
        for p in range(1, sqrt_n):
            if (n - s) % p == 0:
                b = int((n - s) / p + 1)
                if digit_sum(b, n) == s:
                    b_min = min(b_min, b)
            p += 1
    if b_min == 1L << 55:
        return -1
    else:
        return b_min


if __name__ == '__main__':
    N = int(input())
    S = int(input())
    print(main(n=N, s=S))


### FIXED CODE ###

import math


def digit_sum(b, n):
    if b > n:
        return n
    else:
        return digit_sum(b=b, n=n // b) + n % b


def main(n, s):
    if s > n:
        return -1
    elif n == s:
        return n + 1
    else:
        b = 2
        while b * b <= n:
            if digit_sum(b, n) == s:
                return b
            b += 1

        p = 1
        b_min = -1
        while p * p <= n:
            if (n - s) % p == 0:
                b = (n - s) // p + 1
                if digit_sum(b, n) == s:
                    b_min = min(b_min, b) if b_min != -1 else b
            p += 1
        return b_min


if __name__ == '__main__':
    N = int(input())
    S = int(input())
    print(main(n=N, s=S))
N,M = map(int,input().split())
L = list(map(int,input().split()))
L = sorted(L)
S = []
if N >= M:
	print(0)
	exit()

for i in range(M-1):
	S.append(abs(L[i+1]-L[i]))
S=sorted(S)
print(sum(S[0:M-N]))



### FIXED CODE ###

N = int(input())
a = list(map(int, input().split()))
ans = 0

for i in a:
    while True:
        if i % 2 == 0:
            ans += 1
            i //= 2
        else:
            break
print(ans)
N,K=map(int,input().split())
A=list(map(int,input().split()))
MOD=10**9+7
ans=1
p=[]
n=[]
for i in range(N):
    if A[i]<0:
        n.append(A[i])
    else:
        p.append(A[i])
p.sort(reverse=True)
n.sort()
numplus=len(p)
if N==K:
    for i in range(N):
        ans=(ans*A[i])%MOD
elif numplus==0 and K%2==1:
    for i in range(1,K+1):
        ans=(ans*n[i*(-1)])%MOD
else:
    minus=0
    A.sort(reverse=True,key=lambda x:abs(x))
    for i in range(K):
        ans=(ans*A[i])%MOD
        if A[i]<0:
            minus+=1
    if minus%2==1:
        B=A[:K]
        for i in range(K-1,-1,-1):
            if B[i]<0:
                waru=B[i]
                break
        for i in range(K,N):
            if A[i]>=0:
                kakeru=A[i]
                break
        ans=(ans*A[i]*pow(B[i],MOD-2,MOD))%MOD
print(ans)


### FIXED CODE ###

N,K=map(int,input().split())
A=list(map(int,input().split()))
MOD=10**9+7
p=[]
n=[]
for i in range(N):
    if A[i]<=0:
        n.append(A[i])
    else:
        p.append(A[i])
p.sort(reverse=True)
n.sort()
numplus=len(p)
if numplus==0:
    ans=1
    if K%2==1:
        for i in range(1,K+1):
            ans=(ans*n[i*(-1)])%MOD
    else:
        for i in range(K):
            ans=(ans*n[i])%MOD
elif N==K:
    ans=1
    for i in range(N):
        ans=(ans*A[i])%MOD
else:
    if numplus>=K:
        x=K
        if 0 in p:
            zero=p.index(0)
            len(p)-zero-1
    else:
        if (K-numplus)%2==1:
            x=numplus-1
        else:
            x=numplus
    ans=1
    for i in range(x):
        ans=(ans*p[i])%MOD
    for i in range(K-x):
        ans=(ans*n[i])%MOD
    temp=ans
    while x>1:
        if len(n)<(K-x+2):
            break
        if n[K-x]*n[K-x+1]<p[x-1]*p[x-2]:
            break
        temp=(temp*n[K-x]*n[K-x+1])%MOD
        temp=(temp*pow(p[x-1]*p[x-2],MOD-2,MOD))%MOD
        ans=temp
        x-=2
print(ans)
while true:
H,W = map(int,raw_input().split())

 if W==0 and H==0 :
    break

 print '#' * W + '\n'

 print ('#'+ '.'*(W-2)+ '#'+'\n')*(H-2)
 print '#'*W + '\n'

### FIXED CODE ###

while 1:
    H, W = map(int,raw_input().split())
    if H + W == 0: break
    print ('#' * W)
    for h in range(H-2):
        print ('#' + '.' * (W - 2) + '#')
    print ('#' * W + '\n')
n = int(input())
list_A = list(map(int, input().split()))

ans = 0
min_value = max(list_A)
for s in list_A:
    if s % 2 == 1:
        ans = 1
        break
    if s <= min_value:
        min_value = s
        ans = s
if max(list_A) == min(list_A)
    ans = list_A[0]
print(ans)


### FIXED CODE ###

import fractions

n = int(input())
list_A = list(map(int, input().split()))
ans = fractions.gcd(list_A[0], list_A[1])
for i in range(2, n):
    ans = fractions.gcd(ans, list_A[i])

print(ans)
N = int(input())
a = list(map(int,input().split(' ')))
a.sort(True)
 
 
fathers = [a.pop()]
for _ in range(N):
    sons = list()
    b = list()

    for father in fathers:
        while a:
            x = a.pop()
            if father > x:
                sons.append(x)
                break
            else:
                b.append(x)
                
    a = a + b[::-1]
    fathers.extend(sons)
    fathers.sort(reverse = True)
    


if len(fathers) == 2**N:
    print('Yes')
else:
    print('No')


### FIXED CODE ###

N = int(input())
A = sorted((int(x) for x in input().split()))
 
parent = [A[-1]]
rest = A[:-1]
bl = True
for _ in range(N):
    next_parent = []
    next_rest = []
    for p in parent[::-1]:
        while rest:
            x = rest.pop()
            if x < p:
                next_parent.append(x)
                break
            else:
                next_rest.append(x)
                continue
    parent += next_parent
    parent.sort()
    rest = rest + next_rest[::-1]
 
bl = len(parent) == (2**N)
answer = 'Yes' if bl else 'No'
print(answer)
N = int(input())
S = input()
count = 0
ans = 1
m = 10**9 + 7
 
for i, s in enumerate(S):
  if ((s == "W") & (i%2 == 0)) or ((s == "B") & (i%2 == 1)):
    ans *= (i - (count*2))
    count += 1
if count != N:
  print(0)
else:
  for o in range(1, N+1):
    ans *= o
    ans %= m
  print(ans %= m)

### FIXED CODE ###

N = int(input())
S = input()
count = 0
ans = 1
m = 10**9 + 7
 
for i in range(N):
  if S[2*i] == "W":
    ans = ans * ((2*i) - (count*2))%m
    count += 1
  if S[2*i + 1] == "B":
    ans = ans * ((2*i + 1) - (count*2))%m
    count += 1
 
if count != N:
  print(0)
else:
  for o in range(1, N+1):
    ans *= o
    ans %= m
  print(ans % m)
n,m = map(int,input().split())
city = [[] for _ in range(n+1)]
ret = ["" for _ in range(m)]
def createSix(s):
    while len(s) != 6:
        s = "0" + s
    return s
for i in range(m):
    a,b = map(int, input().split())
    city[a].append((b, i))
for i in range(m):
    city[i].sort()
print(city)
for i in range(n+1):
    for j in range(len(city[i])):
        ret[city[i][j][1]] = createSix(str(i)) + createSix(str(j+1))
for i in ret:
    print(i)
    

    


### FIXED CODE ###

a,b = map(int, input().split())
print(a+b//2)
N = int(input().strip())
A = list(map(int,input().strip().split(' ')))

import numpy as np
sortA = np.array(sorted(A))
a_large = sortA[-1]
sortA = np.delete(sortA,-1,0)
half_of_a_large = np.array([a_large/2 for i in range(N-1)])
a_small = sortA[np.argmin(abs(sortA-half_of_a_large))]
print(a_large,a_small)a

### FIXED CODE ###

import numpy as np

n = int(input().strip())
A = list(map(int,input().strip().split(' ')))
sorted_A = sorted(A)
ai=sorted_A[-1]
print(ai)
del sorted_A[-1]
tmplist=np.array([min(i,ai-i) for i in sorted_A])
maxidx = np.argmax(tmplist)

print(sorted_A[int(maxidx)])