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

import sys
input = sys.stdin.readline

N_ken,M_si = map(int,input().split())
ken_year_map = {}
for i in range(1,N_ken+1):ken_year_map[i]=[]

ken_list = [0]*M_si
year_list = [0]*M_si

for si in range(M_si):
    ken_list[si],year_list[si] = map(int,input().split())
    ken_year_map[ken_list[si]] += [year_list[si]]
        
for i in ken_year_map:
    ken_year_map[i].sort()

for ken,year in zip(ken_list,year_list):
    print((str(ken*1000000 + ken_year_map[ken].index(year)+1)).zfill(12))


### FIXED CODE ###

import sys
input = sys.stdin.readline
import bisect

N_ken,M_si = map(int,input().split())
ken_year_map = {}
for i in range(1,N_ken+1):ken_year_map[i]=[]

ken_list = [0]*M_si
year_list = [0]*M_si

for si in range(M_si):
    ken_list[si],year_list[si] = map(int,input().split())
    ken_year_map[ken_list[si]] += [year_list[si]]
        
for i in ken_year_map:
    ken_year_map[i].sort()

for ken,year in zip(ken_list,year_list):
    print('{:06}{:06}'.format(ken,bisect.bisect_right(ken_year_map[ken], year)))
### BUGGY CODE ###

import math, sys

def erastos(n):
    n += 1
    try:
        v = [0 if i % 2 == 0 or i % 3 == 0 or i % 5 == 0 else 1 for i in range(n)]
        v[0] = v[1] = 0
        v[2] = v[3] = v[5] = 1
    except IndexError:
        return [0, 0, 1, 1, 0, 1][:n]
    sqrt = math.sqrt(n)
    for serial in range(3, n, 2):
        if serial > sqrt:
            return v
        for s in range(serial ** 2, n, serial):
            v[s] = 0
if __name__ == '__main__':
    while True:
        try:
            n = int(input())
            v = erastos(n)
            primes = [i for i, b in enumerate(v) if b == True]
            print(len(primes))
        except:
            break

### FIXED CODE ###

import sys

primes = [1] * 500000
primes[0] = 0

for i in range(3, 1000, 2):
    if primes[i // 2]:
        primes[(i * i) // 2::i] = [0] * len(primes[(i * i) // 2::i])

for i in sys.stdin:
    n = int(i)
    if n < 4:
        print(n - 1)
    else:
        print(sum(primes[:(n + 1) // 2]) + 1)
### BUGGY CODE ###

import numpy as np

def main():
    N, K = map(int, input().split(" "))
    P = np.array(list(map(int, input().split(" "))))

    e = (P + 1) / 2

    t = np.ones((K))

    print(np.max(
        np.convolve(
            e,
            t
        )
    ))

if __name__ == "__main__":
    main()

### FIXED CODE ###

import numpy as np
from scipy import signal

def main():
    N, K = map(int, input().split(" "))
    P = np.array(list(map(int, input().split(" "))))

    e = (P + 1) / 2

    t = np.ones((K))

    print(np.amax(
        signal.fftconvolve(
            e,
            t
        )
    ))

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

N=int(input())
S=list(map(int,list(input())))

A=[0]*1000

for i in range(10):
  for ii in range(N):
    if i==S[ii]:
      for j in range(10):
        for jj in range(ii+1,N):
          if j==S[jj]:
            for k in range(10):
              for kk in range(jj+1,N):
                if k==S[kk]:
                  A[i*100+j*10+k]=1
                  break
print(sum(A))

### FIXED CODE ###

N=int(input())
S=list(map(int,list(input())))
#print(S)

A=[[] for i in range(10)]

for i in range(N):
  A[S[i]].append(i)
#print(A)

cnt=0
for a in range(10):
  if len(A[a])==0:
    continue
  for c in range(10):
    if len(A[c])==0:
      continue
    cnt+=len(set(S[A[a][0]+1:A[c][-1]]))
print(cnt)
### BUGGY CODE ###

class Node(object):
	def __init__(self, key):
		self.key = key
		self.prev = None
		self.next = None

nil = Node(None)
nil.prev = nil
nil.next = nil

def insert(key):
	node = Node(key)
	node.next = nil.next
	nil.next.prev = node
	nil.next = node
	node.prev = nil;

def search(key):
	cur = nil.next
	while ((cur != nil) and (cur.key != key)):
		cur = cur.next
	return cur

def delete(t):
	if t!=nil:
		t.prev.next = t.next
		t.next.prev = t.prev

def deleteFirst():
	delete(nil.next)

def deleteLast():
	delete(nil.prev)

n = input()
for _ in range(int(n)):
	command = input()
	if command[0] == 'i':
		insert(command[7:])
	else:
		if command[6] == " ":
			delete(search(command[7:]))
		else:
			if command[6] == 'L':
				deleteLast()
			else:
				deleteFirst()

cur = nil.next
while(1):
	if cur.next == nil:
		break;
	print(cur.key, end=" ")
	cur = cur.next
print(cur.key)

### FIXED CODE ###

from collections import deque
n = input()
d = deque()
for i in range(int(n)):
	command = input()
	if command[0] == 'i':
		d.appendleft(command[7:])
	else:
		if command[6] == " ":
			if  command[7:] in d:
				d.remove(command[7:])
		else:
			if command[6] == 'L':
				d.pop()
			else:
				d.popleft()
for _ in range(len(d)-1):
	print(d.popleft(), end=" ")
print(d.pop())
### BUGGY CODE ###

import sys

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

for i in range(N):
    A_list[i] = A_list[i] - i - 1

min_A = min(A_list)
max_A = max(A_list)

sadness = sys.maxsize
for b in range(min_A, max_A + 1):
    tmp_sadness = 0
    for A in A_list:
        tmp_sadness += abs(A - b)
    if(sadness > tmp_sadness):
        sadness = tmp_sadness

print(sadness)

### FIXED CODE ###

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

for i in range(N):
    A_list[i] = A_list[i] - i - 1

A_list = sorted(A_list)
if(N % 2 == 0):
    key = N // 2
else:
    key = (N - 1) // 2
b = A_list[key]
sadness = 0

for A in A_list:
    sadness += abs(A - b)

print(sadness)
### BUGGY CODE ###

s = input().strip()
q = int(input().strip())
queries = []
one_count = 0
one_counts = []
for i in range(q):
    inp = input().split()
    queries.append(inp)
    if inp[0] == "1":
        one_count += 1
    one_counts.append(one_count)
one_counts = list(map(lambda x: (one_count - x), one_counts))
if one_count % 2 == 1:
    s = s[::-1]
for i in range(q):
    if queries[i][0] == "1":
        continue
    elif queries[i][0] == "2":
        if queries[i][1] == "1":
            if one_counts[i] % 2 == 0:
                s = queries[i][2] + s
            else:
                s += queries[i][2]
        elif queries[i][1] == "2":
            if one_counts[i] % 2 == 0:
                s += queries[i][2]
            else:
                s = queries[i][2] + s
print(s)


### FIXED CODE ###

s = list(input().strip())
q = int(input().strip())
queries = []
one_count = 0
one_counts = []
for i in range(q):
    inp = input().split()
    queries.append(inp)
    if inp[0] == "1":
        one_count += 1
    one_counts.append(one_count)
one_counts = list(map(lambda x: (one_count - x), one_counts))
if one_count % 2 == 1:
    s = s[::-1]
pre = []
suf = []
for i in range(q):
    if queries[i][0] == "1":
        continue
    elif queries[i][0] == "2":
        if queries[i][1] == "1":
            if one_counts[i] % 2 == 0:
                pre.append(queries[i][2])
            else:
                suf.append(queries[i][2])
        elif queries[i][1] == "2":
            if one_counts[i] % 2 == 0:
                suf.append(queries[i][2])
            else:
                pre.append(queries[i][2])
print("".join(pre[::-1] + s + suf))
### BUGGY CODE ###

n = int(input())
l = sorted(list(map(int,input().split())))

check_i = 0
check_j = 0
count = 0 

for i in reversed(range(0,n)):
    if l[i] == check_i:
        check_i = l[i]
        continue
    
    for j in reversed(range(1,i)):
        
        if l[j] == check_j:
            check_j = l[j]
            continue
        
        
        
        if l[i] - l[j] >= l[j-1]:
            continue
        
        low = 0
        high = j-1
        
        while low < high:
            
            mid = (low + high)//2
            
            if l[i] - l[j] >= l[mid]:
                
                low = mid +1
            
            else:    
                
                high = mid
        else:
            
            count += len(set(l[low:j]))
print(count)            

### FIXED CODE ###

from bisect import bisect_left

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

L.sort()
result = 0
for i in range(N - 2):
    for j in range(i + 1, N - 1):
        result += bisect_left(L, L[i] + L[j]) - j - 1
print(result)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(99999)

def find_index_by_value(a, val):
    for i, items in enumerate(a):
        if val in items:
            return i
    return -1


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


n, m = map(int, input().split())
edges = []

for _ in range(m):
    a, b = map(int, input().split())
    edges.append((a, b))

size = [1 for _ in range(n + 1)]
group = [i for i in range(n + 1)]

find_group = lambda x: x if x == group[x] else find_group(group[x])

ans = []
not_reachable = n * (n - 1) // 2
reachable_node = []
ans.append(not_reachable)

count = not_reachable
reachable = 0
for _ in range(m - 1):
    a, b = edges.pop()
    if count > 0:
        ra = find_group(a)
        rb = find_group(b)
        if rb != ra:
            s_ra = size[ra]
            s_rb = size[rb]
            new_size = s_ra + s_rb
            reachable += num_reachable(new_size) - num_reachable(s_ra) - num_reachable(s_rb)
            size[ra] = new_size
            group[rb] = ra
        count = not_reachable - reachable
    ans.append(count)

for _ in range(len(ans)):
    print(ans.pop())




### FIXED CODE ###

def find_index_by_value(a, val):
    for i, items in enumerate(a):
        if val in items:
            return i
    return -1


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


n, m = map(int, input().split())
edges = []

for _ in range(m):
    a, b = map(int, input().split())
    edges.append((a, b))

size = [1 for _ in range(n + 1)]
group = [i for i in range(n + 1)]


def find_group(x):
    c = []
    p = x
    while True:
        pp = group[p]
        if pp == p:
            break
        else:
            c.append(p)
            p = pp
    for i in c:
        group[i] = pp
    return pp

# find_group = lambda x: x if x == group[x] else find_group(group[x])

ans = []
not_reachable = n * (n - 1) // 2
reachable_node = []
ans.append(not_reachable)

count = not_reachable
reachable = 0
for _ in range(m - 1):
    a, b = edges.pop()
    if count > 0:
        ra = find_group(a)
        rb = find_group(b)
        if rb != ra:
            s_ra = size[ra]
            s_rb = size[rb]
            new_size = s_ra + s_rb
            reachable += num_reachable(new_size) - num_reachable(s_ra) - num_reachable(s_rb)
            size[ra] = new_size
            group[rb] = ra
        count = not_reachable - reachable
    ans.append(count)

for _ in range(len(ans)):
    print(ans.pop())
### BUGGY CODE ###

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

sumA = [A[0]%M] + [0]*(N-1)
for i in range(1,N):
  sumA[i] = (sumA[i-1]+A[i]%M)%M

ans = 0
for i in range(N):
  ans += sumA[i+1:].count(sumA[i])
  if sumA[i] == 0: ans += 1
print(ans)

### FIXED CODE ###

from collections import Counter
N,M = map(int,input().split())
A = list(map(int,input().split()))

sumA = [0] + [0]*N
for i in range(N):
  sumA[i] = (sumA[i-1]+A[i])%M

cnt = Counter(sumA).values()
ans = sum(i*(i-1)//2 for i in cnt)

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

import sys
N = int(input())
words = []
cnts = []
for i in range(N):
    S = input()
    if S not in words:
        words.append(S)
        cnts.append(1)
    else:
        cnts[words.index(S)] += 1
max_words = []
for j in range(len(words)):
    if cnts[j] == max(cnts):
        max_words.append(words[j])
max_words = sorted(max_words)
print(*max_words, sep ="\n")

### FIXED CODE ###

from collections import Counter
N = int(input())
S =[input() for i in range(N)]
cnts = Counter(S)
mx = 0
for v in cnts.values():
    mx = max(mx, v)
    
max_words = [k for k, v in cnts.items() if v == mx]
max_words = sorted(max_words)
print(*max_words, sep ="\n")
### BUGGY CODE ###

from collections import deque
n,m,k=map(int,input().split())
fr=[{}]
for i in range(n-1):
  fr.append({})
for i in range(m):
  a,b=map(int,input().split())
  fr[a-1][b]=1
  fr[b-1][a]=1
for i in range(k):
  a,b=map(int,input().split())
  fr[a-1][b]=0
  fr[b-1][a]=0

def bfs(k):
  use=deque()
  use.append(k)
  ans=0
  aldic={}
  for i in range(0,10**100):
    if not bool(use):
      if k!=n:
        print(ans-1,end=" ")
      else:
        print(ans-1)
      break
    else:
      check=use.popleft()
      if check not in aldic:
        aldic[check]=1
        for x in fr[check-1]:
          if fr[check-1][x]==1:
            use.append(x)
        try:
          if fr[k-1][check]==0:
            pass
          else:
            pass
        except KeyError:
          ans+=1

for i in range(1,n+1):
  bfs(i)

### FIXED CODE ###

from collections import deque
n,m,k=map(int,input().split())
fr=[[]]
for i in range(n-1):
  fr.append([])
for i in range(m):
  a,b=map(int,input().split())
  fr[a-1].append(b)
  fr[b-1].append(a)

belong=[0]*n
anslist=[0]*n
count=0
def bfs(k):
  global count
  if belong[k-1]==0:
    count+=1
    use=deque()
    use.append(k)
    ans=0
    aldic={}
    while use:
      if not bool(use):
        break
      else:
        check=use.popleft()
        if check not in aldic:
          aldic[check]=1
          for x in fr[check-1]:
            use.append(x)
    for x in aldic:
      belong[x-1]=count
      anslist[x-1]=len(aldic)-len(fr[x-1])-1

for i in range(1,n+1):
  bfs(i)
for i in range(k):
  a,b=map(int,input().split())
  if belong[a-1]==belong[b-1]:
    anslist[a-1]-=1
    anslist[b-1]-=1
for i in range(0,len(anslist)):
  if i!=len(anslist)-1:
    print(anslist[i],end=" ")
  else:
    print(anslist[i])
### BUGGY CODE ###

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

ans=int(P**(1/N))+1
while ans>0:
    if P%(ans**N)==0:
        break
    ans-=1

print(ans)

### FIXED CODE ###

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

if N>=10**4:
    print(1)
else:
    ans=int(P**(1/N))
    ans+=1
    while ans>0:
        if P%(ans**N)==0:
            break
        ans-=1

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

s = input()
n = len(s)
k = int(input())

dp = [[[0] * (n + 1) for i in range(n + 1)] for i in range(k + 1)]

# 長さ1のときの初期化
for i in range(n):
    dp[0][i][i + 1] = 1

# 長さ2~nのときのDP
for length in range(2, n + 1):
    for l in range(n + 1):
        for ki in range(k + 1):
            r = l + length
            if r > n:
                break
            if s[l] == s[r - 1]:
                dp[ki][l][r] = max(2 + dp[ki][l + 1][r - 1], dp[ki][l][r])
            else:
                dp[ki][l][r] = max(dp[ki][l + 1][r], dp[ki][l][r - 1], dp[ki][l][r])
                if ki - 1 >= 0:
                    dp[ki][l][r] = max(dp[ki - 1][l + 1][r - 1] + 2, dp[ki - 1][l + 1][r - 1] + 2, dp[ki][l][r])

ans = 0
for i in range(k + 1):
    ans = max(ans, dp[i][0][-1])
print(ans)

### FIXED CODE ###

def get_ind(l, r):
    mod = 3
    return OFFSET * (l % mod) + r

s = input()
n = len(s)
k = int(input())

dp = [[0] * ((n + 1) * 3) for i in range(k + 1)]
OFFSET = n + 1

# 長さ1のときの初期化
for i in range(n):
    dp[0][get_ind(i, i + 1)] = 1

# 長さ2~nのときのDP
for length in range(2, n + 1):
    for l in range(n + 1):
        for ki in range(k + 1):
            r = l + length
            if r > n:
                break
            if s[l] == s[r - 1]:
                dp[ki][get_ind(l, r)] = max(2 + dp[ki][get_ind(l + 1, r - 1)], dp[ki][get_ind(l, r)])
            else:
                dp[ki][get_ind(l, r)] = max(dp[ki][get_ind(l + 1, r)], dp[ki][get_ind(l, r - 1)], dp[ki][get_ind(l, r)])
                if ki - 1 >= 0:
                    dp[ki][get_ind(l, r)] = max(dp[ki - 1][get_ind(l + 1, r - 1)] + 2, dp[ki][get_ind(l, r)])

ans = 0
for i in range(k + 1):
    for j in range(3 * (n + 1)):
        ans = max(ans, dp[i][j])
print(ans)
### BUGGY CODE ###

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

if N == 1:
    print(P)
else:
    ans = 1
    x = 1
    while 1:
        k = x**N
        if k > P:
            break
        if P % k == 0:
            ans = max(ans, x)
        x += 1
    print(ans)

### FIXED CODE ###

from collections import Counter

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

# n以下の全ての素数のセットを返す関数
def prime_set(n):
    primes = set(range(2, n+1))
    for i in range(2, int(n**0.5) + 1):
        primes.difference_update(range(i*2, n+1, i))
    return primes

# nを素因数分解して素因数の全リストを返す関数
def prime_factors(n):
    f = []
    for i in prime_set(int(n**0.5) + 1):
        while n % i == 0:
            f.append(i)
            n //= i
    if n > 1:
        f.append(n)
    return f

c = Counter(prime_factors(P))
ans = 1

for x in c.keys():
    ans *= pow(x, int(c[x]//N))

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

from collections import deque

h, w = map(int, input().split())
sy, sx = map(int, input().split())
gy, gx = map(int, input().split())
map = []
move = [[0, 1], [1, 0], [0, -1], [-1, 0]]
visit = [[-1]*w for i in range(h)]
visit[sy - 1][sx - 1] = 0
warp = []
cnt = 0

for i in range(-2, 3):
    for j in range(-2, 3):
        warp.append([i, j])

for i in range(h):
    s = input()
    map.append(s)

route = deque([[sy - 1, sx - 1]])

while route:
    while route:
        y, x = route.popleft()
        for i, j in move:
            k = y + i
            l = x + j
            if 0 <= k < h and 0 <= l < w:
                if map[k][l] == ".":
                    if visit[k][l] == visit[y][x]:
                        continue
                    visit[k][l] = visit[y][x]
                    route.append([k, l])
    wroute = deque([])
    for i in range(w):
        for j in range(h):
            if visit[j][i] == cnt:
                wroute.append([j, i])
    while wroute:
        y, x = wroute.popleft()
        for i, j in warp:
            k = y + i
            l = x + j
            if 0 <= k < h and 0 <= l < w:
                if map[k][l] == ".":
                    if visit[k][l] != -1:
                        continue
                    visit[k][l] = visit[y][x] + 1
                    route.append([k, l])
    cnt += 1

print(visit[gy - 1][gx - 1])

### FIXED CODE ###

from collections import deque

h, w = map(int, input().split())
sy, sx = map(int, input().split())
gy, gx = map(int, input().split())
map = []
move = [[0, 1], [1, 0], [0, -1], [-1, 0]]
visit = [[-1]*w for i in range(h)]
visit[sy - 1][sx - 1] = 0
warp = []
cnt = 0

for i in range(-2, 3):
    for j in range(-2, 3):
        if i == 0 and j == 0:
            continue
        else:
            warp.append([i, j])

for i in range(h):
    s = input()
    map.append(s)

route = deque([[sy - 1, sx - 1]])
wroute = deque()

while route:
    while route:
        y, x = route.popleft()
        wroute.append([y, x])
        for i, j in move:
            k = y + i
            l = x + j
            if 0 <= k < h and 0 <= l < w:
                if map[k][l] == ".":
                    if visit[k][l] == visit[y][x]:
                        continue
                    visit[k][l] = visit[y][x]
                    route.append([k, l])
    while wroute:
        y, x = wroute.popleft()
        for i, j in warp:
            k = y + i
            l = x + j
            if 0 <= k < h and 0 <= l < w:
                if map[k][l] == ".":
                    if visit[k][l] != -1:
                        continue
                    visit[k][l] = visit[y][x] + 1
                    route.append([k, l])
    cnt += 1

print(visit[gy - 1][gx - 1])
### BUGGY CODE ###

n,m = map(int,input().split())
A = [int(i) for i in input().split()]
 
A.sort(reverse=True)
 
def bisect(A,x):
  lo = -1
  hi = len(A)
  while lo+1 < hi:
    idx = (lo+hi)//2
    if A[idx] > x:
      lo = idx
    else:
      hi = idx
  return lo
 
for i in range(m):
  v = A.pop(0)//2
  idx = bisect(A,v)+1
  A = A[:idx] + [v] + A[idx:]

print(sum(A))

### FIXED CODE ###

from heapq import heappop, heappush, heapify
n, m = map(int, input().split())
a = [-int(i) for i in input().split()]

heapify(a)
for _ in range(m):
  l = heappop(a)
  heappush(a, -((-l)//2))

print(-sum(a))
### BUGGY CODE ###

import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    N,M=map(int,input().split())
    edge=[[] for _ in range(N)]
    s=set(range(N))
    for _ in range(M):
        x,y=map(lambda x: int(x)-1,input().split())
        edge[x].append(y)
        try:
            s.remove(y)
        except:
            pass
    que=deque(s)
    memo=[0]*N
    ans=0
    while que:
        v=que.popleft()
        for nv in edge[v]:
            memo[nv]=max(memo[nv],memo[v]+1)
            ans=max(ans,memo[nv])
            que.append(nv)
    print(ans)
    
    

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    N,M=map(int,input().split())
    edge=[[] for _ in range(N)]
    s=set(range(N))
    for _ in range(M):
        x,y=map(lambda x: int(x)-1,input().split())
        edge[x].append(y)
        try:
            s.remove(y)
        except:
            pass
    que=list(s)
    memo=[0]*N
    def saiki(v):
        if memo[v]:
            return memo[v]
        tmp=0
        for nv in edge[v]:
            memo[v]=max(memo[v],saiki(nv)+1)
            tmp=max(tmp,memo[v])
        return tmp
    ans=0
    for v in que:
        ans=max(ans,saiki(v))
    print(ans)
    
    

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

from functools import reduce
import fractions


def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)


def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)


def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)


n = int(input())
a = list(map(int, input().split()))
l = lcm_list(a)
ans = sum([l // x for x in a]) % (10**9+7)
print(ans)


### FIXED CODE ###

from functools import reduce
import fractions


def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)


def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)


def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)


n = int(input())
a = list(map(int, input().split()))
l = lcm_list(a)
ans = sum([l // x for x in a]) % int(1e9+7)
print(ans)
# print(l)
# print(a)