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

S = list(input())
S.reverse()
N = len(S)
mod = 10 ** 9 + 7
ans = [0 for r in range(13)]
if S[0] == '?':
    ans = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0]
else:
    ans[int(S[0])] = 1
for n in range(1, N):
    ans_new = []
    if S[n] == '?':
        for r in range(13):
            count = 0
            for d in range(10):
                r1 = d * (10 ** n) % 13
                r0 = (r - r1) % 13
                count += ans[r0] % mod
            ans_new.append(count % mod)
    else:
        for r in range(13):
            d = int(S[n])
            r1 = d * (10 ** n) % 13
            r0 = (r - r1) % 13
            ans_new.append(ans[r0] % mod)
    ans = ans_new
print(ans[5])


### FIXED CODE ###

S = list(input())
S.reverse()
N = len(S)
mod = 10**9+7
dp = [[0 for r in range(13)] for n in range(N+1)]
dp[0][0] = 1
lookup = [[0 for d in range(10)] for n in range(N)]
for n in range(N):
    for d in range(10):
        lookup[n][d] = d*pow(10, n, 13) % 13
for n in range(1, N+1):
    if S[n-1] == '?':
        for d in range(10):
            for r in range(13):
                dp[n][(r+lookup[n-1][d]) % 13] += dp[n-1][r] % mod
    else:
        for r in range(13):
            dp[n][(r+lookup[n-1][int(S[n-1])]) % 13] += dp[n-1][r] % mod
print(dp[-1][5] % mod)
### BUGGY CODE ###

def check():
    N, M = map(int, input().split())
    A = sorted([int(i) for i in input().split()])
    sousa = sorted([[int(i) for i in input().split()] for i in range(M)],
                   reverse=True, key=lambda x:x[1])
    index = 0
    for cnt, value in sousa:
        for i in range(cnt):
            if min(A) < value:
                A[index] = value
            else:
                return(sum(A))
            index += 1
    return(sum(A))
  
print(check())

### FIXED CODE ###

def check():
    N, M = map(int, input().split())
    A = sorted([int(i) for i in input().split()])
    sousa = sorted([[int(i) for i in input().split()] for i in range(M)],
                   reverse=True, key=lambda x:x[1])
    index = 0
    for cnt, value in sousa:
        for i in range(cnt):
            if index == N:
                break
            if A[index] < value:
                A[index] = value
            else:
                return(sum(A))
            index += 1
    return(sum(A))
print(check())
### BUGGY CODE ###

# coding: utf-8
# Your code here!
N=int(input())
List = list(map(int, input().split()))

ANS=List[0]
i=1
while i<N:
    ANS=ANS*List[i]
    i+=1

if ANS>1000000000000000000:
    print(-1)
else:
    print(ANS)





### FIXED CODE ###

# coding: utf-8
# Your code here!
N=int(input())
List = list(map(int, input().split()))
List=sorted(List)
List=List[::-1]
#print(List)
if List.count(0)!=0:
    print(0)
    quit()
ANS=List[0]
i=1
while i<N:
    ANS=ANS*List[i]
    if ANS>1000000000000000000:
        print(-1)
        quit()
    i+=1

print(ANS)
### BUGGY CODE ###

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

while m>0:
  A.sort(reverse=True)
  A[0]=A[0]//2
  m-=1
print(sum(A))

### FIXED CODE ###

import heapq
n,m=map(int,input().split())
A=list(map(int,input().split()))

q=[]
for a in A:
  heapq.heappush(q,-a)
  
for _ in range(m):
  p=-heapq.heappop(q)//2
  heapq.heappush(q,-p)
print(-sum(q))
### BUGGY CODE ###

s = input()
t = input()
ls = len(s)
lt = len(t)


dp = [[0 for i in range(lt+1)] for j in range(ls+1)]
answer = ''

for i in range(ls):
    for j in range(lt):
        if s[i] == t[j]:
            dp[i+1][j+1] = dp[i][j] + 1
        else:
            dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])


i = ls-1
j = lt-1
while (0 <= i) & (0 <= j):
    if s[i] == t[j]:
        answer += s[i]
        i -= 1
        j -= 1
    elif dp[i+1][j+1] == dp[i+1][j]:
        j -= 1
    else:
        i -= 1
if len(answer) == 0:
  print('')
else:
  print(answer[::-1])


### FIXED CODE ###

s = input()
t = input()
ls = len(s)
lt = len(t)


dp = [[0 for i in range(lt+1)] for j in range(ls+1)]
answer = ''

for i in range(ls):
    for j in range(lt):
        if s[i] == t[j]:
            dp[i+1][j+1] = dp[i][j] + 1
        else:
            dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])


i = ls-1
j = lt-1
while (0 <= i) & (0 <= j):
    if s[i] == t[j]:
        answer += s[i]
        i -= 1
        j -= 1
    elif dp[i+1][j+1] == dp[i+1][j]:
        j -= 1
    else:
        i -= 1
if len(answer) == 0:
  print('')
else:
  print(answer[::-1])
### BUGGY CODE ###

n=int(input())
As=list(map(int,input().split()))

Asmin=[i-1 for i in As]
Aspul=[i+1 for i in As]

ans=-100
for i in As:
  tmp=As.count(i+1)+As.count(i)+As.count(i-1)
  if ans<tmp:
    ans=tmp
print(ans)

### FIXED CODE ###

from itertools import chain
from collections import Counter
n=int(input())
As=list(map(int,input().split()))
As = [[a-1, a, a+1] for a in As]
As = list(chain.from_iterable(As))

result_cntr = Counter(As).most_common()
print(result_cntr[0][1])
### BUGGY CODE ###

import sys
def solve():
    sys.setrecursionlimit(1000000)
    N, Q = map(int, input().split())
    tree = [[] for i in range(N)]
    counter = [0] * N
    arrived = [False] * N
    for i in range(N-1):
        a, b = map(int, input().split())
        tree[a-1].append(b-1)
        tree[b-1].append(a-1)
    
    for i in range(Q):
        p, x = map(int, input().split())
        counter[p-1] += x
    
    arrived[0] = True
    adder(0, counter, tree, arrived)

    print(*counter)

def adder(ind, counter, tree, arrived):
    for i in tree[ind]:
        if arrived[i]:
            continue
        counter[i] += counter[ind]
        arrived[i] = True
        adder(i, counter, tree, arrived)
    if not tree[ind]:
        return

if __name__ == '__main__':
    solve()


### FIXED CODE ###

import sys
def solve():
    sys.setrecursionlimit(1000000)
    input = sys.stdin.readline
    N, Q = map(int, input().split())
    tree = [[] for i in range(N)]
    counter = [0] * N
    arrived = [False] * N
    for i in range(N-1):
        a, b = map(int, input().split())
        tree[a-1].append(b-1)
        tree[b-1].append(a-1)
    
    for i in range(Q):
        p, x = map(int, input().split())
        counter[p-1] += x
    
    arrived[0] = True
    adder(0, counter, tree, arrived)

    print(*counter)

def adder(ind, counter, tree, arrived):
    for i in tree[ind]:
        if arrived[i]:
            continue
        counter[i] += counter[ind]
        arrived[i] = True
        adder(i, counter, tree, arrived)
    if not tree[ind]:
        return

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

import sys

def main():
  input = sys.stdin.readline
  N, S = map(int, input().split())
  C = list(map(int, input().split()))
  C = list(set([abs(c - S) for c in C]))
  min_C = min(C)
  ans = 1
  for i in range(min_C, 1, -1):
    if all([c % i == 0 for c in C]):
      ans = i
      break
  print(ans)


if __name__ == '__main__':
  main()

### FIXED CODE ###

import sys

def main():
  input = sys.stdin.readline
  N, S = map(int, input().split())
  C = list(map(int, input().split()))
  C = list(set([abs(c - S) for c in C]))
  min_C = min(C)
  ans = 1
  for i in range(min_C, 1, -1):
    if min_C % i != 0:
      continue
    
    if all([c % i == 0 for c in C]):
      ans = i
      break
  print(ans)


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

s = input()
count = 0
for i in range(0,len(s)):
    for j in range(i+4,len(s)):
        ss = s[i:j+1]
        if int(ss) % 2019  == 0:
            count += 1
print(count)

### FIXED CODE ###

s = input()
n = len(s)
r = list(reversed(s))
x = 1
t = 0
c = [0] * 2019
ans = 0
for i in range(n):
    c[t] += 1
    t += (int(r[i]))*x
    t %= 2019
    ans += c[t]
    x = x*10%2019
   
print(ans)
### BUGGY CODE ###

n = int(input())
uvw = []
for i in range(n-1):
    uvw.append(list(map(int, input().split(' '))))
uvw.sort()
result = [0]*(n+1)
result[uvw[0][1]] = uvw[0][2]
s = uvw[0][0]
del uvw[0]
n_visit = []
horyuu = []
count = n-2
while count > 0:
    for i in range(len(uvw)):
        if uvw[i][1] != s and uvw[i][0] != s:
            if result[uvw[i][0]] == 0 and result[uvw[i][1]] != 0:
                result[uvw[i][0]] =  result[uvw[i][1]] + uvw[i][2]
                count -= 1
            elif result[uvw[i][0]] != 0 and result[uvw[i][1]] == 0:
                result[uvw[i][1]] =  result[uvw[i][0]] + uvw[i][2]
                count -= 1
        else:
            if uvw[i][1] != s and uvw[i][0] == s:
                result[uvw[i][1]] = uvw[i][2]
                count -= 1
            elif uvw[i][0] != s and uvw[i][1] == s:
                result[uvw[i][0]] = uvw[i][2]
                count -= 1
            else:
                horyuu.append(uvw[i])
    uvw = horyuu
    horyuu = []

for i in range(1,n+1):
    if result[i]%2 == 0:
        print(0)
    else:
        print(1)

### FIXED CODE ###

from collections import deque

n = int(input())
visit = [-1 for _ in range(n+1)]
friends = [[] for _ in range(n+1)]
for i in range(n-1):
    u, v, w = map(int, input().split())
    friends[u].append([v, w])
    friends[v].append([u, w])

q = deque([1])
visit[1] = 0
while q:
    position = q.popleft()
    for i, cost in friends[position]:
        if visit[i] < 0:
            visit[i] = visit[position] + cost
            q.append(i)

for i in visit[1:]:
    print(i%2)
### BUGGY CODE ###

import sys
S = [ c for c in input()]

#aiは、その数より左側の連続した<の数(Si-1から数える)か、その数より右側の連続した>の数(Siから数える)の大きい方
a = []
for i in range(len(S)+1):
    cnt = [0,0]
    j = i
    while j-1 >= 0:
        if S[j-1] == "<" and j >= 0:
            cnt[0] +=1
            j -= 1
        else:
            break
    
    j = i
    while j <= len(S)-1:
        if S[j] == ">" and j<= len(S)-1:
            cnt[1] +=1
            j += 1
        else:
            break
    if cnt[0] >= cnt[1]:
        a.append(cnt[0])
    else:
        a.append(cnt[1])
    
print(sum(a))



### FIXED CODE ###

import sys
import copy
import math
import itertools
import numpy as np
S=input()
N = len(S)+1
a = [0]*N
b = [0]*N
for i in range(N-1):
    if S[i]=="<":
        a[i+1]=a[i]+1

for i in reversed(range(N-1)):
    if S[i]==">":
        b[i]=b[i+1]+1

for i in range(N):
    if a[i] < b[i]:
        a[i]=b[i]

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

import sys
from collections import deque
readline = sys.stdin.readline
N = int(readline())

testimonies = [[[], []] for _ in range(N)]
for i in range(N):
    A = int(readline())
    for _ in range(A):
        x, y = map(int, readline().rstrip().split())
        testimonies[i][y].append(x-1)

def check(honest_persons):
    """矛盾がないか検証する"""
    honest_checked = set(honest_persons)  # 宛先を確認済みの正直者の人
    honest_stack = deque(honest_persons)  # 宛先を確認する正直者の人の待ち行列
    honest, liers = honest_persons[:], []  # 正直者の人, 不親切な人

    # 正直者の人の証言も元に、正直者の人/不親切な人を追加していく
    while len(honest_stack) > 0:
        honest_person = honest_stack.popleft()
        honest_checked.add(honest_person)
        next_honest_persons = testimonies[honest_person][1]

        # 検証済み以外の人をstackする
        for person in next_honest_persons:
            if person not in honest_checked:
                honest_stack.append(person)

        honest += testimonies[honest_person][1]
        liers += testimonies[honest_person][0]

        if len(set(honest) & set(liers)) != 0:
            return False

    return True

def main():
    # bit全探索する
    ans = 0
    has_checked = []
    for i in range(1, 2**N):
        comb = bin(i)[2:].zfill(N)
        honest_persons = []
        for p, c in enumerate(comb):
            if c == '1':
                honest_persons.append(p)
        
        flag = False
        for checked in has_checked:
            if checked < set(honest_persons):
                flag = True
                break
        
        if flag:
            continue

        if check(honest_persons):
            ans = max(ans, sum(list(map(int, list(comb)))))
        else:
            has_checked.append(set(honest_persons))

    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
N = int(sys.stdin.readline())

testimonies = [[-1 for _ in range(N)] for _ in range(N)]
for i in range(N):
    A = int(sys.stdin.readline())
    for _ in range(A):
        x, y = map(int, sys.stdin.readline().rstrip().split())
        testimonies[i][x-1] = y

def check(honest_persons):
    flag = True
    for i in range(N):
        if honest_persons[i]:
            for j in range(N):
                if testimonies[i][j] == -1:
                    continue
                if testimonies[i][j] != honest_persons[j]:
                    flag = False
                    break
    return flag

def main():
    ans = 0
    for i in range(1, 2**N):
        honest_persons = bin(i)[2:].zfill(N)
        honest_persons = list(map(int, list(honest_persons)))

        if check(honest_persons):
            ans = max(ans, sum(honest_persons))

    print(ans)

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

#入力
N,M=map(int,input().split())
H=list(map(int,input().split()))

#道の行列初期化
road=[[0]*N for l in range(N)]

for i in range(M):
    a,b=map(int,input().split())
    #道行列を入力
    road[a-1][b-1]=H[b-1]
    road[b-1][a-1]=H[a-1]

result=0

for j in range(N):
    result += (H[j]>max(road[j]))*1

print(result)

### FIXED CODE ###

#入力
N,M=map(int,input().split())
H=list(map(int,input().split()))

#隣接展望台の最大標高リスト初期化
road_max=[0 for l in range(N)]

for i in range(M):
    a,b=map(int,input().split())
    if road_max[a-1]<H[b-1]:
        road_max[a-1]=H[b-1]
    if road_max[b-1]<H[a-1]:
        road_max[b-1]=H[a-1]

result=[(road_max[p]<H[p])*1 for p in range(N)]

print(sum(result))
### BUGGY CODE ###

import sys
import itertools

N = int(input())
A = list(input().split())
A = [int(A[i]) for i in range(N+1)]
MAX = [2**i for i in range(N+1)]
A_inter = list(reversed(list(itertools.accumulate(reversed(A)))))

for i in range(N+1):
    if A[i] > MAX[i]:
        print(-1)
        sys.exit()
    elif i != N:
        MAX[i+1] = (MAX[i] - A[i]) * 2
        
print(sum([min(MAX[i], A_inter[i]) for i in range(N+1)]))

### FIXED CODE ###

import sys
import itertools

N = int(input())
A = list(input().split())
A = [int(A[i]) for i in range(N+1)]
MAX = [1 for i in range(N+1)]
A_inter = list(reversed(list(itertools.accumulate(reversed(A)))))

for i in range(N+1):
    if A[i] > MAX[i]:
        print(-1)
        sys.exit()
    elif i != N:
        MAX[i+1] = (MAX[i] - A[i]) * 2
        
print(sum([min(MAX[i], A_inter[i]) for i in range(N+1)]))
### BUGGY CODE ###

from collections import deque

H, W = map(int, input().split())
m = [list(input()) for i in range(H)]
ans = 0
q = deque()

for h in range(H):
  for w in range(W):
    if m[h][w] == "#":
      q.append((h, w, 0))

while q:
  h, w, c = q.popleft()
  ans = max(ans, c)
  for dh, dw in ((-1, 0), (1, 0), (0, -1), (0, 1)):
    if 0 <= h+dh < H and 0 <= w+dw < W and m[h + dh][w + dw] == ".":
      m[h + dh][w + dw] = "#"
      q.append((h+dh, w+dw, c+1))

print(ans)

### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
m = [list(input()) for i in range(H)]
ans = 0
q = deque()

for h in range(H):
  for w in range(W):
    if m[h][w] == "#":
      q.append((h, w, 0))

while q:
  h, w, c = q.popleft()
  ans = max(ans, c)
  for dh, dw in ((-1, 0), (1, 0), (0, -1), (0, 1)):
    if 0 <= h+dh < H and 0 <= w+dw < W and m[h + dh][w + dw] == ".":
      m[h + dh][w + dw] = "#"
      q.append((h+dh, w+dw, c+1))

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

_ = input()
a = list(map(int, input().split()))

result = 1
for a_i in a:
    result *= a_i

if 10**18 < result:
    print(-1)
else:
    print(result)


### FIXED CODE ###

def main():
    _ = input()
    a = list(map(int, input().split()))

    result = 1
    for a_i in a:
        if a_i == 0:
            return 0

    for a_i in a:
        result *= a_i

        if 10**18 < result:
            return -1

    return result


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

N, K, Q = map(int, input().split())
A = list(int(input()) for _ in range(Q))
a = list(set(A))
if Q >= K:
  ans = ["No"] * N
  for i in range(len(a)):
    if K - (Q - A.count(a[i])) > 0:
      ans[a[i]-1] = "Yes"
else:
  ans = ["Yes"] * N

for x in ans:
  print(x)

### FIXED CODE ###

N, K, Q = map(int, input().split())
A = list(int(input()) for _ in range(Q))

score = [0] * N
for i in range(Q):
  score[A[i] - 1] += 1
 
ans = []
for j in range(N):
  if K - Q + score[j] <= 0:
    ans.append("No")
  else:
    ans.append("Yes")
 
for a in ans:
  print(a)
### BUGGY CODE ###

S = input()
ans = 0

while(1):
    before = len(S)
    S = S.replace("01","")
    S = S.replace("10","")
    after = len(S)
    if before - after  == 0:
        break
    else:
        ans += before - after




print(ans)

### FIXED CODE ###

S = input()

one = S.count("1")
zero = S.count("0")

print(min(one,zero)*2)
### BUGGY CODE ###

S = input()
N = len(S) + 1

la = [0] * N

cnt0 = 0
if S[0] == ">":
    cnt0 += 1
    j = 1
    while j <= len(S)-1 and S[j] == ">":
        cnt0 += 1
        j += 1
la[0] = cnt0

for i in range(1, N-1):
    j = i-1
    k = i+1
    cnt1 = 0
    cnt2 = 0
    if S[i-1] == "<" and i >= 0:
        while j >= 0 and S[j] == S[i-1] :
            cnt1 += 1 
            j -= 1
    if S[i] == ">":
        while k <= N-1 and S[i] == S[k-1]:
            cnt2 += 1
            k += 1 
    la[i] = max(cnt1, cnt2)

cntn = 0
if S[-1] == "<":
    cntn += 1
    j = -2
    while j >= -len(S) and S[j] == "<":
        cntn += 1
        j -= 1
la[-1] = cntn

print(sum(la))

### FIXED CODE ###

S = input()
N = len(S) + 1

ans = 0

cnt0 = 0
if S[0] == ">":
    cnt0 += 1
    j = 1
    while j <= len(S)-1 and S[j] == ">":
        cnt0 += 1
        j += 1
ans += cnt0*(cnt0+1)//2


for i in range(1, N-1):
    if S[i-1] == "<" and S[i] == ">":
        j = i-1
        k = i+1
        cnt1 = 0
        cnt2 = 0
        if S[i-1] == "<" and i >= 0:
            while j >= 0 and S[j] == S[i-1] :
                cnt1 += 1 
                j -= 1
        if S[i] == ">":
            while k <= N-1 and S[i] == S[k-1]:
                cnt2 += 1
                k += 1 
        ans += max(cnt1, cnt2)*(max(cnt1, cnt2)+1)//2
        ans += (min(cnt1, cnt2)-1)*(min(cnt1, cnt2))//2


cntn = 0
if S[-1] == "<":
    cntn += 1
    j = -2
    while j >= -len(S) and S[j] == "<":
        cntn += 1
        j -= 1
ans += cntn*(cntn+1)//2


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

N = int(input())

for h in range(1,3501):
  for n in range(1,3501):
    if (4*h*n-N*n-N*h)!= 0:
        w = N*h*n/(4*h*n-N*n-N*h)
        if w >0 and w.is_integer():
          print(h,n,int(w))
          exit()

### FIXED CODE ###

N = int(input())
for h in range(1, 3501):
    for n in range(h, 3501):
        if (4*h*n-N*n-N*h)>0 and (N*h*n)%(4*h*n-N*n-N*h)==0:
            print(h, n, (N*h*n)//(4*h*n-N*n-N*h))
            exit()
### BUGGY CODE ###

from  bisect import bisect

n,d,a=map(int,input().split())
monster=[list(map(int,input().split())) for i in range(n)]
monster.sort(key=lambda i:i[0])
r=[monster[i][0] for i in range(n)]
hp=[monster[i][1] for i  in range(n)]

#print(r,hp)
i,ans=0,0
while i<n:
  #print(i)
  s=hp[i]
  #print(s)
  if s>0:
    cnt=(s+a-1)//a
    #print(cnt)
    ans+=cnt
    damage=cnt*a
    #print(damage)
    for j in range(i,min(bisect(r,r[i]+2*d),n)):
      hp[j]-=damage
  #print(hp)
  i+=1
print(ans)


### FIXED CODE ###

from  bisect import bisect

n,d,a=map(int,input().split())
monster=[list(map(int,input().split())) for i in range(n)]
monster.sort(key=lambda i:i[0])
r=[monster[i][0] for i in range(n)]
hp=[monster[i][1] for i  in range(n)]
#print(r,hp)

d=2*d
i,ans,damages=0,0,[0]*n
while i<n:
  if i>0:
    damages[i]+=damages[i-1]
    s=hp[i]+damages[i]
  else:
    s=hp[i]
  if s>0:
    cnt=(s+a-1)//a
    ans+=cnt
    #print(ans)
    damage=cnt*a
    damages[i]-=damage
    zone=bisect(r,r[i]+d)
    if zone<n:
      damages[zone]+=damage 
  i+=1
  #print(damages)
  #print(hp)
print(ans)
### BUGGY CODE ###

N = int(input())

ans = [0 for _ in range(N)]

num_m = (N-4)//2

for x in range(1, num_m):
    for y in range(1, num_m-x):
        for z in range(1, num_m-x-y):
            n = x**2+y**2+z**2+x*y+y*z+z*x
            if n <= N-1:
                ans[n-1] += 1


print(*ans, sep="\n")

### FIXED CODE ###

N = int(input())

ans = [0 for _ in range(N)]

for x in range(1, 101):
    for y in range(1, 101):
        for z in range(1, 101):
            n = x**2+y**2+z**2+x*y+y*z+z*x
            if n <= N:
                ans[n-1] += 1


print(*ans, sep="\n")
### BUGGY CODE ###

import collections
N = int(input())
A = [collections.Counter(list(input())) for i in range(N)]
ans=0
for i in range(N):
    for j in range(i+1,N):
        if A[i]==A[j]:
            ans+=1
print(ans)

### FIXED CODE ###

N = int(input())
dic = {}
ans = 0
for i in range(N):
    tmp = "".join(sorted(input()))
    if tmp in dic:
        ans += dic[tmp]
        dic[tmp] += 1
    else:
        dic[tmp] = 1
print(ans)
### BUGGY CODE ###

X=int(input())
def prime_factorize(n):
    a=[]
    while n%2==0:
        a.append(2)
        n//=2
    f=3
    while f*f <=n:
        if n%f ==0:
            a.append(f)
            n//=f
        else:
            f+=2
    if n!=1:
        a.append(n)
    return a
if X!=1:
    M=prime_factorize(X)
    M=list(set(M))
else:
    M=[1]
for i in M:
    for k in range(X):
        A=k
        B=A-i
        if A**5-B**5==X:
            print(A,B)
            break

### FIXED CODE ###

import sys
X=int(input())
for A in range(-120,120):
    for B in range(-120,120):
        if A**5-B**5==X:
            print(A,B)
            sys.exit()
### BUGGY CODE ###

from operator import mul
from functools import reduce


def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom


N = int(input())
s = ["".join(sorted(input())) for _ in range(N)]
number_of_anagrams = []
ans = 0

for string in set(s):
    cnt = s.count(string)
    if cnt > 1:
        number_of_anagrams.append(cnt)

for num in number_of_anagrams:
    ans += combinations_count(num, 2)

print(ans)

### FIXED CODE ###

N = int(input())
unique_string = {}
ans = 0

for _ in range(N):
    s = "".join(sorted(input()))
    try:
        ans += unique_string[s]
        unique_string[s] += 1
    except KeyError:
        unique_string[s] = 1

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

import itertools
import numpy as np
n = int(input())

p = np.array([(i+1) for i in range(n)])

ps = np.array(list(itertools.permutations(p)))

a = []
for i in range(len(ps)):
    a.append(np.sum(ps[i] % p))

print(max(a))


### FIXED CODE ###

n = int(input())

print(int((n * (n - 1)) // 2))
### BUGGY CODE ###

n,m = map(int,input().split())

tmp_list = [[0]for i in range(n)]
p_list = []
y_list = []

for i in range(m):
    p,y = map(int,input().split())
    tmp_list[p-1].append(y)
    p_list.append(p)
    y_list.append(y)

import copy
tmpsort = copy.deepcopy(tmp_list)
for i in range(len(tmp_list)):
    tmpsort[i].sort()
for i in range(len(p_list)):
    idx = tmpsort[p_list[i]-1].index(y_list[i])
    print((str(p_list[i]).zfill(6) + str(idx).zfill(6)))

### FIXED CODE ###

N,M = map(int, input().split())  
piys = [[] for _ in range(N)]   
for i in range(M):  
    p, y = map(int, input().split())  
    piys[p-1].append((y,i))  

ans = [None]*M  
for p,iys in enumerate(piys):  
    iys.sort()  
    for k,(y,i) in enumerate(iys):  
        ans[i] = "%06d%06d" % (p+1,k+1)  

for i in ans:  
    print(i)
### BUGGY CODE ###

n, m = map(int, input().split())

#できる限り平均的に分けてあげたほうがいいってことはわかる。
i = 1
ans = 1
while n*i <= m:
    if m % i == 0 and m / i >= n:
        ans = i
    i += 1
print(ans)


### FIXED CODE ###

def solve():
    n, m = map(int, input().split())
    for i in range(m//n,0,-1):
        if m % i == 0:
            break
    print(i)

solve()
### BUGGY CODE ###

import collections

n = int(input())
s = [input() for _ in range(n)]
ans = 0

for i, e1 in enumerate(s):
    for e2 in s[i+1:]:
        if collections.Counter(e1) == collections.Counter(e2):
            ans += 1

print(ans)


### FIXED CODE ###

n = int(input())
s = {}
ans = 0

for i in range(n):
    e = ''.join(sorted(input()))
    s[e] = s.get(e, 0) + 1

for e in s.values():
    ans += e*(e-1) // 2
print(ans)