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

X = 998244353

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

def calc_inverse(n, law):
	if n == 1:
		return 1
	
	pre_r = law
	pre_x = 0
	pre_y = 1
	cur_r = n
	cur_x = 1
	cur_y = 0
	
	while True:
		d = pre_r // cur_r
		r = pre_r % cur_r
		
		nxt_r = r
		nxt_x = pre_x - d * cur_x
		nxt_y = pre_y - d * cur_y
		
		if nxt_r == 1:
			ret = nxt_x
			while ret < 0:
				ret += law;
			return ret;
		elif nxt_r == 0:
			return None
		
		pre_r = cur_r;
		pre_x = cur_x;
		pre_y = cur_y;
		cur_r = nxt_r;
		cur_x = nxt_x;
		cur_y = nxt_y;

inv_cache = [1]
for i in range(1, K + 1):
	inv_cache.append(calc_inverse(i, X))

inv_f_cache = [1]
d = 1
for i in range(1, K + 1):
	d = (d * inv_cache[i]) % X
	inv_f_cache.append(d)

def C(n, m):
	c = 1
	for i in range(n - m + 1, n + 1):
		c = (c * i) % X
#	d = 1
#	for i in range(1, m + 1):
#		d = (d * inv_cache[i]) % X
	return (c * inv_f_cache[m]) % X


total = 0
for k in range(K + 1):
	total = (total + M * pow(M - 1, N - 1 - k, X) * C(N - 1, k)) % X
	
#	print(k, M * pow(M - 1, N - 1 - k, X))
	

print(total)


### FIXED CODE ###

X = 998244353

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

def calc_inverse(n, law):
	if n == 1:
		return 1
	
	pre_r = law
	pre_x = 0
	pre_y = 1
	cur_r = n
	cur_x = 1
	cur_y = 0
	
	while True:
		d = pre_r // cur_r
		r = pre_r % cur_r
		
		nxt_r = r
		nxt_x = pre_x - d * cur_x
		nxt_y = pre_y - d * cur_y
		
		if nxt_r == 1:
			ret = nxt_x
			while ret < 0:
				ret += law;
			return ret;
		elif nxt_r == 0:
			return None
		
		pre_r = cur_r;
		pre_x = cur_x;
		pre_y = cur_y;
		cur_r = nxt_r;
		cur_x = nxt_x;
		cur_y = nxt_y;

inv_cache = [1]
for i in range(1, K + 1):
	inv_cache.append(calc_inverse(i, X))

inv_f_cache = [1]
d = 1
for i in range(1, K + 1):
	d = (d * inv_cache[i]) % X
	inv_f_cache.append(d)

f_cache = [1]
c = 1
for i in range(N - 1, N - K - 1, -1):
	c = (c * i) % X
	f_cache.append(c)

#print(f_cache, inv_f_cache)

def C(n, m):
#	if m in f_cache:
#		c = f_cache[m]
#	else:
#		c = 1
#		for i in range(n - m + 1, n + 1):
#			c = (c * i) % X
#		f_cache[m] = c
#	d = 1
#	for i in range(1, m + 1):
#		d = (d * inv_cache[i]) % X
#	print(m)
	return (f_cache[m] * inv_f_cache[m]) % X


total = 0
for k in range(K + 1):
	total = (total + M * pow(M - 1, N - 1 - k, X) * C(N - 1, k)) % X
	
#	print(k, M * pow(M - 1, N - 1 - k, X))
	

print(total)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N, A = map(int, input().split())
    X = list(map(int, input().split()))

    # dp[i][k][s] := i個までみて，それまでにk選んでて，そのときの総和がsとなる物の総数
    dp = [[[0] * (N * A + 1) for _ in range(N + 1)] for _ in range(N + 1)]

    dp[0][0][0] = 1
    for i in range(N):
        for k in range(N):
            for s in range(N * A + 1):
                # 使わない
                dp[i + 1][k][s] += dp[i][k][s]

                # 使う
                if s + X[i] <= N * A:
                    dp[i + 1][k + 1][s + X[i]] += dp[i][k][s]

    ans = 0
    for i in range(1, N + 1):
        ans += dp[-1][i][i * A]

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N, A = map(int, input().split())
    X = list(map(int, input().split()))

    # dp[i][k][s] := i個までみて，それまでにk選んでて，そのときの総和がsとなる物の総数
    dp = [[[0] * (N * A + 1) for _ in range(N + 1)] for _ in range(N + 1)]

    dp[0][0][0] = 1
    for i in range(N):
        for k in range(N):
            for s in range(N * A + 1):
                # 使わない
                dp[i + 1][k][s] += dp[i][k][s]

                # 使う
                if s + X[i] <= N * A:
                    dp[i + 1][k + 1][s + X[i]] += dp[i][k][s]

    ans = 0
    for i in range(1, N + 1):
        ans += dp[-1][i][i * A]

    print(ans)


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

from numpy.linalg import solve

N = int(input())
solve_arr = [int(i) for i in input().split()]

w_arr = []

for i in range(N):
  arr = [0]*N
  if i == N-1:
    arr[i] = 1/2
    arr[0] = 1/2
  else:
    arr[i] = 1/2
    arr[i+1] = 1/2
  w_arr.append(arr)
  
ans = solve(w_arr, solve_arr)
for i in ans:
  print(str(int(i)) + " ", end ="")

### FIXED CODE ###

N = int(input())
dam_arr = list(map(int,input().split()))
mount_arr = []

# calculate 1st mount's rain
rain = 0
for i in range(N):
  if i%2==0:
    rain += dam_arr[i]
  else:
    rain -= dam_arr[i]
    
mount_arr.append(rain)

# caluculate others
for i in range(N-1):
  mount_arr.append(2*dam_arr[i]-mount_arr[-1])

mount_arr=[str(a) for a in mount_arr]
mount_arr=" ".join(mount_arr)
print(mount_arr)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
import copy
from collections import defaultdict,deque

N=input()
AL=defaultdict(lambda: set())
IN=defaultdict(lambda: 0)


for i in range(N):
	A=map(int, sys.stdin.readline().split())
	for j in range(N-2):
		x=i+1
		x_next=i+1
		y_now=A[j]
		y_next=A[j+1]
		#print x,y_now,x_next,y_next
		if x>y_now: x,y_now=y_now,x
		if x_next>y_next: x_next,y_next=y_next,x_next
		IN[(x_next,y_next)]+=1
		AL[(x,y_now)].add((x_next,y_next))

q=deque()

for i in range(1,N+1):
	for j in range(i+1,N+1):
		if IN[(i,j)]==0:
			q.append((i,j))

DAY=defaultdict(lambda: 1)	#距離

ans=-1
while q:
	fro=q.pop()
	for to in AL[fro]:
		alt=DAY[fro]+1
		if DAY[to]<alt:
			ans=max(ans,alt)
			DAY[to]=max(DAY[to],DAY[fro]+1)
			q.append((to[0],to[1]))

print ans

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
import copy
from collections import defaultdict,deque

N=input()
A=[[]]+[ map(int, sys.stdin.readline().split()) for _ in range(N) ]
C=defaultdict(lambda: 0)

Now=[ 0 for _ in range(N+1)]
game=set()
next_game=set()

for i in range(1,N+1):
	a=i
	b=A[i][0]
	if a>b: a,b=b,a
	game.add((a,b))

day=0

while game:
	next_game=set()
	Visit=defaultdict(lambda: None) 

	for x,y in game:
		now_x=Now[x]
		now_y=Now[y]

		xopp=A[x][now_x]
		yopp=A[y][now_y]

		if (x,y)==(yopp,xopp) and Visit[x] is None and Visit[y] is None:
			Visit[x]=1
			Visit[y]=1
			if now_x<N-2:
				now_x+=1
				Now[x]=now_x
				x_nextopp=A[x][now_x]
				if x_nextopp<x: x,x_nextopp=x_nextopp,x
				next_game.add((x,x_nextopp))

			if now_y<N-2:
				now_y+=1
				Now[y]=now_y
				y_nextopp=A[y][now_y]
				if y_nextopp<y: y,y_nextopp=y_nextopp,y
				next_game.add((y,y_nextopp))

	game=next_game
	day+=1


for i in range(1,N+1):
	if Now[i] != N-2:
		print -1
		quit()
else:
	print day
### BUGGY CODE ###

from collections import defaultdict

n = int(input())
alist = list(map(int,input().split()))
q = int(input())


dict_n = defaultdict(lambda:0)

for i in alist:
    dict_n[i] += 1

bclist = []
for i in range(q):
    b,c  = map(int,input().split())
    bclist.append([b,c])


for i in range(q):
    
    b = bclist[i][0]
    c = bclist[i][1]

    dict_n[c] += dict_n[b]
    del(dict_n[b])
    
    sum = 0
    for key in dict_n:
        sum += key * dict_n[key]
    print(sum)

### FIXED CODE ###

from collections import defaultdict

n = int(input())
alist = list(map(int,input().split()))
q = int(input())


dict_n = defaultdict(lambda:0)

for i in alist:
    dict_n[i] += 1

bclist = []
for i in range(q):
    b,c  = map(int,input().split())
    bclist.append([b,c])

sum = sum(alist)
for i in range(q):
    
    b = bclist[i][0]
    c = bclist[i][1]

    sum += dict_n[b]*c - dict_n[b]*b
    dict_n[c] += dict_n[b]
    del(dict_n[b])

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

n,m,s = map(int,input().split())
road = [[] for _ in range(n)]
#print(road)
for _ in range(m):
  u,v,a,b = map(int,input().split())
  u -= 1
  v -= 1
  road[u].append([v,a,b])
  road[v].append([u,a,b])
#print(road)
coin = []
for _ in range(n):
  c,d = map(int,input().split())
  coin.append([c,d])
if s >= 2500:
  s = 2499
inf = 10**18
#print('#')
arr = [[inf for _ in range(2500)] for _ in range(n)]
c,d = coin[0]
#print(c,d)
#print(len(arr[0]))
for i in range(2500):
  if i <= s:
    arr[0][i] = 0
  elif i - c < 0:
    arr[0][i] = arr[0][0]+d
  else:
    arr[0][i] = arr[0][i-c]+d
now = {0}
#print(road)
for _ in range(2500):
  #print(now)
  last = now
  now = set()
  for x in last:
    for y in road[x]:
      #print('#',x,y)
      v,a,b = y
      now.add(v)
      c,d = coin[v]
      for i in range(2500):
        if i + a < 2500:
          arr[v][i] = min(arr[v][i],arr[x][i+a]+b)
      for i in range(2500):
        if i - c < 0:
          arr[v][i] = min(arr[v][i],arr[v][0]+d)
        else:
          arr[v][i] = min(arr[v][i],arr[v][i-c]+d)
for ii in range(1,n):
  print(arr[ii][0])
#print(arr[0])

### FIXED CODE ###

n,m,s = map(int,input().split())
road = [[] for _ in range(n)]
#print(road)
for _ in range(m):
  u,v,a,b = map(int,input().split())
  u -= 1
  v -= 1
  road[u].append([v,a,b])
  road[v].append([u,a,b])
#print(road)
coin = []
for _ in range(n):
  c,d = map(int,input().split())
  coin.append([c,d])
if s >= 2500:
  s = 2499
inf = 10**18
#print('#')
arr = [[inf for _ in range(2500)] for _ in range(n)]
c,d = coin[0]
#print(c,d)
#print(len(arr[0]))
for i in range(2500):
  if i <= s:
    arr[0][i] = 0
  elif i - c < 0:
    arr[0][i] = arr[0][0]+d
  else:
    arr[0][i] = arr[0][i-c]+d
now = {0}
#print(road)
for _ in range(100):
  #print(now)
  last = now
  now = set()
  for x in last:
    for y in road[x]:
      #print('#',x,y)
      v,a,b = y
      now.add(v)
      c,d = coin[v]
      for i in range(2500):
        if i + a < 2500:
          arr[v][i] = min(arr[v][i],arr[x][i+a]+b)
      for i in range(2500):
        if i - c < 0:
          arr[v][i] = min(arr[v][i],arr[v][0]+d)
        else:
          arr[v][i] = min(arr[v][i],arr[v][i-c]+d)
for ii in range(1,n):
  print(arr[ii][0])
#print(arr[0])
### BUGGY CODE ###

r, g, b, n = map(int, input().split())
l = [r, g, b]
l.sort()

N1 = n // l[2]
N2 = n // l[1]
N3 = n // l[0]

cnt = 0

for i in range(N1+1):
    for j in range(N2+1):
        for k in range(N3+1):
            if i*l[2] + j*l[1]+ k*l[0]==n:
                cnt += 1

print(cnt)


### FIXED CODE ###

r, g, b, n = map(int, input().split())
l = [r, g, b]
l.sort()

N1 = n // l[2]
N2 = n // l[1]
N3 = n // l[0]

cnt = 0

for i in range(N1+1):
    N2 = n-i*l[2] // l[1]
    for j in range(N2+1):
        if ((n-i*l[2]-j*l[1]) % l[0] == 0) and ((n-i*l[2]-j*l[1]) // l[0] >= 0):
            cnt += 1
            # print(i, j, (n-i*l[2]-j*l[1]) // l[0])
print(cnt)
### BUGGY CODE ###

R, G, B, N = [int(n) for n in input().split()]

count = 0
for r in range(N//R + 1):
    for g in range((N-r*R)//G + 1):
        b_ = N - (R * r + G * g) 
        if b_ % B == 0 and 0 <= b_ / B <=  N//B:
                count += 1

print(count)


### FIXED CODE ###

R, G, B, N = [int(n) for n in input().split()]

count = 0
for r in range(N//R + 1):
    for g in range((N-r*R)//G + 1):
        b_ = N - (R * r + G * g) 
        if b_ % B == 0:
                count += 1

print(count)
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline
R,C,K = map(int,input().split())
goods = [[0]*(C+1) for _ in range(R+1)]
INF = 10**18
for i in range(K):
    ri,ci,vi = map(int,input().split())
    goods[ri][ci] = vi
DP = [[[-INF,-INF,-INF,-INF] for _ in range(C+1)] for _ in range(R+1)]
DP[1][1][0] = 0
if goods[1][1]:
    DP[1][1][1] = goods[1][1]
for j in range(1,C):
    DP[1][j+1][0] = 0
    if goods[1][j+1]:
        DP[1][j+1][1] = max(DP[1][j][1],DP[1][j][0]+goods[1][j+1])
        DP[1][j+1][2] = max(DP[1][j][2],DP[1][j][1]+goods[1][j+1])
        DP[1][j+1][3] = max(DP[1][j][3],DP[1][j][2]+goods[1][j+1])
    else:
        DP[1][j+1][1] = DP[1][j][1]
        DP[1][j+1][2] = DP[1][j][2]
        DP[1][j+1][3] = DP[1][j][3]
for i in range(1,R):
    DP[i+1][1][0] = max(DP[i][1])
    if goods[i+1][1]:
        DP[i+1][1][1] = DP[i+1][1][0] + goods[i+1][1]
for i in range(2,R+1):
    for j in range(2,C+1):
        DP[i][j][0] = max(max(DP[i-1][j]),DP[i][j-1][0])
        if goods[i][j]:
            DP[i][j][1] = max(DP[i][j][0]+goods[i][j],DP[i][j-1][1])
            DP[i][j][2] = max(DP[i][j-1][2],DP[i][j-1][1]+goods[i][j])
            DP[i][j][3] = max(DP[i][j-1][3],DP[i][j-1][2]+goods[i][j])
        else:
            DP[i][j][1] = DP[i][j-1][1]
            DP[i][j][2] = DP[i][j-1][2]
            DP[i][j][3] = DP[i][j-1][3]
print(max(DP[R][C]))

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
R,C,K = map(int,input().split())
goods = [[0]*(C+1) for _ in range(R+1)]
INF = 10**18
for i in range(K):
    ri,ci,vi = map(int,input().split())
    goods[ri][ci] = vi
DP = [[[-INF]*(C+1) for _ in range(R+1)] for _ in range(4)]
DP[0][1][1] = 0
if goods[1][1]:
    DP[1][1][1] = goods[1][1]
for j in range(1,C):
    DP[0][1][j+1] = 0
    if goods[1][j+1]:
        DP[1][1][j+1] = max(DP[1][1][j],DP[0][1][j]+goods[1][j+1])
        DP[2][1][j+1] = max(DP[2][1][j],DP[1][1][j]+goods[1][j+1])
        DP[3][1][j+1] = max(DP[3][1][j],DP[2][1][j]+goods[1][j+1])
    else:
        DP[1][1][j+1] = DP[1][1][j]
        DP[2][1][j+1] = DP[2][1][j]
        DP[3][1][j+1] = DP[3][1][j]
for i in range(1,R):
    DP[0][i+1][1] = max(DP[0][i][1],DP[1][i][1],DP[2][i][1],DP[3][i][1])
    if goods[i+1][1]:
        DP[1][i+1][1] = DP[0][i+1][1] + goods[i+1][1]
for i in range(2,R+1):
    for j in range(2,C+1):
        DP[0][i][j] = max(DP[0][i-1][j],DP[1][i-1][j],DP[2][i-1][j],DP[3][i-1][j],DP[0][i][j-1])
        if goods[i][j]:
            DP[1][i][j] = max(DP[0][i][j]+goods[i][j],DP[1][i][j-1])
            DP[2][i][j] = max(DP[2][i][j-1],DP[1][i][j-1]+goods[i][j])
            DP[3][i][j] = max(DP[3][i][j-1],DP[2][i][j-1]+goods[i][j])
        else:
            DP[1][i][j] = DP[1][i][j-1]
            DP[2][i][j] = DP[2][i][j-1]
            DP[3][i][j] = DP[3][i][j-1]
print(max(DP[0][R][C],DP[1][R][C],DP[2][R][C],DP[3][R][C]))
### BUGGY CODE ###

n = int(input())
lis = [input() for _ in range(n)]
s = set(lis)
a = []
for i in s:
    a.append([lis.count(i), i])
M = max(a, key=lambda i : i[0])
anslis = [i[1] for i in a if i[0]==M[0]]
anslis.sort()
for i in anslis:
    print(i)

### FIXED CODE ###

n = int(input())
dic = {}
for _ in range(n):
    s = input()
    if s not in dic:
        dic[s] = 1
    else:
        dic[s] += 1
m = max(dic.values())
anslis = []
for k, v in dic.items():
    if v == m:
        anslis.append(k)
print('\n'.join(sorted(anslis)))
### BUGGY CODE ###

import sys
n =int(input())
a = list(map(int,input().split()))
b = 1
for i in range(n):
    b *= a[i]
if b> 10**18:
    print("-1")
    sys.exit()
print(b)


### FIXED CODE ###

import sys
n =int(input())
a = list(map(int,input().split()))
if a.count(0) >0:
    print(0)
    sys.exit()
b = 1
for i in range(n):
    b *= a[i]
    if b> 10**18:
        print("-1")
        sys.exit()
print(b)
### BUGGY CODE ###

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

a.sort()

result = 0
mod = 10**9+7

def solve(x, y):
    if x == 0:
        return 1
    else:
        x = min(x, y-x)
        r = 1
        for i in range(y-x+1, y+1):
            r = (r*i)%mod
        for i in range(1, x+1):
            r //= i
        return r

s, l = 0, 0

for i in range(n-k+1):
    for j in range(i+k-1, n):
        x = solve(k-2, j-i-1)
        s = s+a[i]*x
        l = l+a[j]*x
print((l-s)%mod)

### FIXED CODE ###

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

a.sort()

result = 0
mod = 10**9+7

 
def cmb(n, r, mod=mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
mod = 10**9+7 #出力の制限
n = 10**5+1
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル
 
for i in range( 2, n+1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )


if k==1:
    print(0)
else:
    result = 0
    for i in range(N-k+1):
        result += (a[N-i-1]-a[i])*cmb(N-1-i, k-1)
        result %= mod

    print(result%mod)
### BUGGY CODE ###

# coding : utf-8
 
import numpy as np
 
N = int(input())
 
A = [int(i) for i in input().split()]
 
 
count = 0
 
#dist = [0 for i in range(N)]
dist = np.zeros(N)
 
for i in range(N):
	dist[:i+1] += A[i]
	#print(dist)
	count += sum(dist[:i+1]==0)
 
#print(dist)
 
print(count)

### FIXED CODE ###

# coding : utf-8
 
import numpy as np
 
N = int(input())
 
A = [int(i) for i in input().split()]

S = [0 for i in range(N+1)]

for i in range(N):
	S[i+1] = S[i] + A[i]

S = sorted(S)
cnt = 0
block = 1
s = S[0]
for i in range(1,N+1):
	if s == S[i]:
		cnt += block
		block += 1
	else:
		s = S[i]
		block = 1

#print(S)
print(cnt)
### BUGGY CODE ###

N, M = [int(x) for x in input().split(" ")]
S = input()
T = input()

N = len(S)
M = len(T)


def gcd(a, b):
    if (a < b):
        return gcd(b, a)
    if a % b == 0:
        return b
    else:
        return gcd(b, a % b)


def maxkobai(a, b):
    return a * b // gcd(a, b)


#print(gcd(N, M))
#print(maxkobai(N, M))


L = maxkobai(N, M)
ret = L
x = ['-' for i in range(L+1)]

for n in range(0, N):
    x[n * (L//N) + 1] = S[n]

# print(x)

for m in range(0, M):
    idx = m * (L // M) + 1
    if x[idx] != '-':
        if (x[idx] != T[m]):
            ret = -1

print(ret)


### FIXED CODE ###

N, M = [int(x) for x in input().split(" ")]
S = input()
T = input()

N = len(S)
M = len(T)


S = [ord(c) for c in S]
T = [ord(c) for c in T]


def gcd(a, b):
    if a < b:
        a, b = b, a
    while b:
        a, b = b, a % b
    return a


def maxkobai(a, b):
    return a * b // gcd(a, b)


L = maxkobai(N, M)
ret = L
x = dict()

for n in range(0, N):
    x[n * (L//N) + 1] = S[n]


for m in range(0, M):
    idx = m * (L // M) + 1
    tmp = x.get(idx, 0)

    if tmp != T[m] and tmp != 0:
        ret = -1
        break

print(ret)
### BUGGY CODE ###

import queue
N,M=map(int,input().split())
G=[[] for i in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
Q=int(input())
v=[0 for i in range(Q)]
d=[0 for i in range(Q)]
c=[0 for i in range(Q)]
for i in range(Q):
    v[i],d[i],c[i]=map(int,input().split());v[i]-=1
q=queue.Queue()
ans=[0 for i in range(N)]
for t in range(Q)[::-1]:
    reached=[0 for i in range(N)]
    q.put((v[t],d[t]))
    while(not(q.empty())):
        x,l=q.get()
        reached[x]=1
        if ans[x]==0:
            ans[x]=c[t]
        if l==0:
            continue
        for y in G[x]:
            if reached[y]==0:
                q.put((y,l-1))
for line in ans:
    print(line)


### FIXED CODE ###

from collections import deque
N,M=map(int,input().split())
G=[[] for i in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
Q=int(input())
v=[0 for i in range(Q)]
d=[0 for i in range(Q)]
c=[0 for i in range(Q)]
for i in range(Q):
    v[-i-1],d[-i-1],c[-i-1]=map(int,input().split());v[-i-1]-=1
q=deque()
color=[0 for i in range(N)]
dp=[-1 for i in range(N)]
for t in range(Q):
    if dp[v[t]]>=d[t]:
        continue
    dp[v[t]]=d[t]
    q.append((v[t],d[t]))
    while(q):
        vv,dd=q.popleft()
        if color[vv]==0:
            color[vv]=c[t]
        dd-=1
        for y in G[vv]:
            if dp[y]>=dd:
                continue
            dp[y]=dd
            q.append((y,dd))
for line in color:
    print(line)
### BUGGY CODE ###

n = int(input())
s = input()

ans = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        if s[i] == s[j]:
            continue
        l = j-i
        for k in range(j+1,n):
            if s[k] != s[i] and s[k] != s[j]:
                if k-j != l:
                    ans += 1

print(ans)

### FIXED CODE ###

n = int(input())
s = input()
 
ans = s.count("R") * s.count("G") * s.count("B")
for i in range(n-2):
    for j in range(i+1,n-1):
        k = 2*j-i
        if k < n:
            if s[k] != s[i] and s[k] != s[j] and s[i] != s[j]:
                    ans -= 1
                    
print(ans)
### BUGGY CODE ###

from collections import defaultdict 
import sys
import math 

def get_array(): return list(map(int , sys.stdin.readline().strip().split()))
def get_ints(): return map(int, sys.stdin.readline().strip().split())
def input(): return sys.stdin.readline().strip()

n = int(input())

start = 0
for i in range(1,n+1):
	start = start*10+7
	if start%n==0:
		print(i)
		break
else:
	print(-1)

### FIXED CODE ###

from collections import defaultdict 
import sys
import math 

def get_array(): return list(map(int , sys.stdin.readline().strip().split()))
def get_ints(): return map(int, sys.stdin.readline().strip().split())
def input(): return sys.stdin.readline().strip()

n = int(input())

start = 0
for i in range(1,n+1):
	start = (start*10+7)%n
	if start==0:
		print(i)
		break
else:
	print(-1)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N = int(input())
edges = []
# edges = [[] for _ in range(N)]
sum_w = 0
for i in range(N-1):
    u, v, w = map(int, input().split())
    edges.append([u-1,v-1,w])

    # edges[u-1].append([v-1,w])
    # edges[v-1].append([u-1,w])


dist = [None]*N
dist[0] = 0
cnt = 1 # 点1個は確定済み
while cnt < N:
    for edge in edges:
        if dist[edge[0]] == None and dist[edge[1]] != None:
            dist[edge[0]] = dist[edge[1]] + edge[2]
            cnt += 1
        elif dist[edge[1]] == None and dist[edge[0]] != None:
            dist[edge[1]] = dist[edge[0]] + edge[2]
            cnt += 1

for item in dist:
    print(item%2)

### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())
tree = [[] for _ in range(N)]
for i in range(N-1):
    u, v, w = map(int, input().split())
    tree[u-1].append([v-1,w])
    tree[v-1].append([u-1,w])

dist = [None]*N
dist[0] = 0
comp = [0]*N
next_ptr = [0]
for ptr in next_ptr:
    comp[ptr] = 1
    edges = tree[ptr]
    for edge in edges:
        if comp[edge[0]] == 0:
            dist[edge[0]] = dist[ptr] + edge[1]
            next_ptr.append(edge[0])

for item in dist:
    print(item%2)
### BUGGY CODE ###

n, m = map(int, input().split())
for k in range(m // n, -1, -1):
    if m % k == 0:
        print(k)
        exit()

### FIXED CODE ###

import collections
import itertools
import math


def eratosthenes(n):
    sieve = [True for _ in range(n + 1)]
    sieve[0] = False
    sieve[1] = False

    def _update(p):
        if sieve[p]:
            for i in range(p * 2, n + 1, p):
                sieve[i] = False

    _update(2)
    p = 3
    while p * p <= n:
        _update(p)
        p += 2
    return sieve


n, m = map(int, input().split())
m2 = math.ceil(math.sqrt(m)) + 1
sieve = eratosthenes(m2)
counter = collections.Counter()

mm = m
for k in range(2, m2):
    if sieve[k] and m % k == 0:
        while mm % k == 0:
            mm //= k
            counter[k] += 1
if mm > 1:
    counter[mm] += 1

es = [range(k + 1) for k in counter.values()]
res = 1
for ks in itertools.product(*es):
    x = 1
    for p, k in zip(counter.keys(), ks):
        x *= p**k
    if x <= m // n:
        res = max(res, x)
print(res)