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

from collections import deque

N,M = map(int, input().split())
A = [0]*M
B = [0]*M
for i in range(M):
    A[i], B[i] = map(int, input().split())
    
parent = [0]*(N+1)
parent[0] = -1
parent[1] = -1

nextroom = deque()
nextroom.append(1)
for j in range(N):
    for i in range(M):
        if A[i]==nextroom[0] and parent[B[i]]==0:
            nextroom.append(B[i])
            parent[B[i]] = A[i]
        if B[i]==nextroom[0] and parent[A[i]]==0:
            nextroom.append(A[i])
            parent[A[i]] = B[i]
    nextroom.popleft()
    
if parent.count(0)==0:
    print('Yes')
    for i in range(2,len(parent)):
        print(parent[i])
else:
    print('No')

### FIXED CODE ###

from collections import deque

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

AB = [list(map(int, input().split())) for _ in range(M)]

G = {i:[] for i in range(N+1)}
for a,b in AB:
    G[a].append(b)
    G[b].append(a)
    
parent = [0]*(N+1)
parent[0]==-1
parent[1]==-1
q = deque()
q.append(1)
while len(q)>0:
    room = q.popleft()
    child = G[room]
    
    for i in child:
        if parent[i] == 0:
            parent[i] = room
            q.append(i)
    
    
if min(parent[2:])==0:
    print('No')
else:
    print('Yes')
    for i in parent[2:]:
        print(i)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def min_cost_flow(E, s, t, f):
    NN = 2 * N + 6
    G = [[] for _ in range(NN)]
    for a, b, cap, c in E:
        G[a].append([b, cap, c, len(G[b])])
        G[b].append([a, 0, -c, len(G[a])-1])
    prevv = [-1] * NN
    preve = [-1] * NN
    res = 0
    while f > 0:
        dist = [1<<100] * NN
        dist[s] = 0
        update = 1
        while update:
            update = 0
            for v in range(NN):
                if dist[v] == 1<<100: continue
                for i, (b, _cap, c, r) in enumerate(G[v]):
                    if _cap > 0 and dist[b] > dist[v] + c:
                        dist[b] = dist[v] + c
                        prevv[b] = v
                        preve[b] = i
                        update = 1
        if dist[t] == 1<<100:
            return -1
        d = f
        v = t
        while v != s:
            d = min(d, G[prevv[v]][preve[v]][1])
            v = prevv[v]
        f -= d
        res += d * dist[t]
        v = t
        while v != s:
            G[prevv[v]][preve[v]][1] -= d
            G[v][G[prevv[v]][preve[v]][3]][1] += d
            v = prevv[v]
    return res

E = []
N = int(input())
su = 0
INF = 0
for i in range(N):
    x, y, cnt = map(int, input().split())
    E.append((2*N+4, i, cnt, 0))
    E.append((i, 2*N, cnt, x + y + INF))
    E.append((i, 2*N+1, cnt, x - y + INF))
    E.append((i, 2*N+2, cnt, - x + y + INF))
    E.append((i, 2*N+3, cnt, - x - y + INF))
    su += cnt

for i in range(N):
    x, y, cnt = map(int, input().split())
    E.append((i+N, 2*N+5, cnt, 0))
    E.append((2*N, i+N, cnt, - x - y + INF))
    E.append((2*N+1, i+N, cnt, - x + y + INF))
    E.append((2*N+2, i+N, cnt, x - y + INF))
    E.append((2*N+3, i+N, cnt, x + y + INF))

print(su * INF * 2 - min_cost_flow(E, 2*N+4, 2*N+5, su))

### FIXED CODE ###

from networkx import*
N = int(input())
G = MultiDiGraph()
for i in range(N):
    x, y, c = map(int, input().split())
    G.add_node(i, demand = -c)
    G.add_weighted_edges_from([(i, -1, x + y)], capacity = c)
    G.add_weighted_edges_from([(i, -2, x - y)], capacity = c)
    G.add_weighted_edges_from([(i, -3, -x + y)], capacity = c)
    G.add_weighted_edges_from([(i, -4, -x - y)], capacity = c)
for i in range(N):
    x, y, c = map(int, input().split())
    G.add_node(N + i, demand = c)
    G.add_weighted_edges_from([(-1, N + i, -x - y)], capacity = c)
    G.add_weighted_edges_from([(-2, N + i, -x + y)], capacity = c)
    G.add_weighted_edges_from([(-3, N + i, x - y)], capacity = c)
    G.add_weighted_edges_from([(-4, N + i, x + y)], capacity = c)

print(-min_cost_flow_cost(G))
### BUGGY CODE ###

def chmax(a, b):
    if a < b:
        a = b
        return a
    else:
        return a


n, w = map(int, input().split())
ls = [[int(_) for _ in input().split()] for _ in range(n)]

dp = [[0] * (w + 1) for _ in range(n + 1)]

for i in range(1, n + 1):
    for sumw in range(w + 1):
        if sumw + ls[i - 1][0] <= w:
            dp[i][sumw + ls[i - 1][0]] = chmax(dp[i][sumw + ls[i - 1][0]], dp[i - 1][sumw] + ls[i - 1][1])
        
        dp[i][sumw] = chmax(dp[i][sumw], dp[i - 1][sumw])

print(dp[n][w])

### FIXED CODE ###

def chmax(a, b):
    if a < b:
        a = b
        return a
    else:
        return a


n, w = map(int, input().split())
ls = [[int(_) for _ in input().split()] for _ in range(n)]

dp = [[0] * (w + 1) for _ in range(n + 1)]

for i in range(1, n + 1):
    for sumw in range(w + 1):
        if sumw + ls[i - 1][0] <= w:
            dp[i][sumw + ls[i - 1][0]] = chmax(dp[i][sumw + ls[i - 1][0]], dp[i - 1][sumw] + ls[i - 1][1])
        
        dp[i][sumw] = chmax(dp[i][sumw], dp[i - 1][sumw])

print(dp[n][w])
### BUGGY CODE ###

n = int(input())
ans = 1

while True:
    if ans % n == 0 and ans % 2 == 0:
        print(ans)
        break
    ans += 1


### FIXED CODE ###

n = int(input())

#a,bの最大公約数
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#a,bの最小公倍数
def lcm(a, b):
    return a * b // gcd (a, b)

print(lcm(2, n))
### BUGGY CODE ###

import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

n,m,r=na()
rs = na()
for i in range(r):
    rs[i] -= 1

g = [[99999999999]*n for _ in range(n)]
for i in range(n):
    g[i][i] = 0
for i in range(m):
    a, b, c = na()
    a -= 1
    b -= 1
    g[a][b] = g[b][a] = c

for k in range(n):
    for i in range(n):
        for j in range(n):
            g[i][j] = min(g[i][j], g[i][k] + g[k][j])

from itertools import *

ans = 9999999999999999999
for ord in permutations(rs):
    w = 0
    for i in range(1, r):
        w += g[ord[i-1]][ord[i]]
    ans = min(ans, w)
print(ans)

### FIXED CODE ###

import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

n,m,r=na()
rs = na()
for i in range(r):
    rs[i] -= 1

g = [[99999999999]*n for _ in range(n)]
for i in range(n):
    g[i][i] = 0
for i in range(m):
    a, b, c = na()
    a -= 1
    b -= 1
    g[a][b] = g[b][a] = c

for k in range(n):
    for i in range(n):
        for j in range(n):
            g[i][j] = min(g[i][j], g[i][k] + g[k][j])

from itertools import *

ans = 9999999999999999999
for ord in permutations(rs):
    w = 0
    for i in range(1, r):
        w += g[ord[i-1]][ord[i]]
    ans = min(ans, w)
print(ans)
### BUGGY CODE ###

n = int(input())
dam = list(map(int,input().split()))
yama =[0]*n
sum_dam = sum(dam)
dam2 = dam[0]*2 +2
for yama[0] in range(0,dam2,2):
  for i in range(1,n):
    yama[i] = dam[i-1]*2 - yama[i-1] 
    if yama[i] < 0:
      break
  if (yama[n-1] + yama[0])//2 == dam[n-1]:
    joined = " ".join(map(str, yama))
    print(joined)
    break

### FIXED CODE ###

n = int(input())
dam = list(map(int,input().split()))
mountain =[0]*n
all_water = sum(dam)
def dam_water(num):
  sum_dam = 0
  for i in range(num,n,2):
    sum_dam += dam[i]
  return sum_dam

mountain[0] = all_water - 2 * (dam_water(1))

for i in range(1,n):
  mountain[i] = 2*dam[i-1] - mountain[i-1]

print(" ".join(map(str,mountain)))
### BUGGY CODE ###

import itertools

N,K = map(int,(input().split()))
h = [int(input())for _ in range(N)]

hmin =[]

c = itertools.combinations(h,K)

for v in c:
    hmin.append(max(v)-min(v))
print(min(hmin))

### FIXED CODE ###

N,K = map(int,(input().split()))
h = [int(input())for _ in range(N)]
h.sort()

print(min(h[i+K-1]-h[i] for i in range(N-K+1)))
### BUGGY CODE ###

import sys
def IL(): return map(int,sys.stdin.readline().rstrip().split())

if __name__=='__main__':
    n,k = IL()
    a = list(IL())
    l = n-k+1
    b = []
    ans = []
    for i in range(l):
        tmp = a[i:i+k]
        result = 1
        for rep in tmp:
            result = result*rep
        b.append(result)
        if 0<i:
            if b[i-1]<result:
                ans.append('Yes')
            else:
                ans.append('No')
    
    for rep in ans:
        print(rep)
    exit()

### FIXED CODE ###

import sys
def IL(): return map(int,sys.stdin.readline().rstrip().split())

if __name__=='__main__':
    n,k = IL()
    a = list(IL())
    l = n-k
    pre = b = 0
    for i in range(l):
        if a[i]<a[i+k]:
            print('Yes')
        else:
            print('No')
    exit()
### BUGGY CODE ###

a = int(input())
b = list(map(int,input().split()))
c = 1
for i in range(a):
  c = c * b[i]
if c > 10 ** 18:
  print(-1)
else:
  print(c)

### FIXED CODE ###

a = int(input())
b = list(map(int,input().split()))
c = 1
if 0 in b:
  print(0)
else:
  for i in range(a):
    c = c * b[i]
    if c > 10 ** 18:
      break
  if c > 10 ** 18:
    print(-1)
  else:
    print(c)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
M = 10**9+7
n = int(input())
l = list(map(int,input().split()))
x = max(l)
s = bin(x)
u = len(s)-2
o = [0]*u
z = [0]*u
for i in l:
    x = bin(i)
    x = x[2:]
    a = list(x)
    d = u - len(a)
    a = (["0"] * d) + a
    j = 0
    while(j < len(o)):
        if a[j] == "1":
            o[j] = o[j]+1

        else:
            z[j] = z[j]+1

        j = j+1

#print(o)
#print(z)
o = o[::-1]
z = z[::-1]
cnt = 0
for j in range(len(o)):
    cnt = (cnt+((o[j]*z[j]*(2**j))))%M


print(cnt)

### FIXED CODE ###

def readinput():
    n=int(input())
    l=list(map(int,input().split()))
    return n,l

def main(n,a):
    MOD=10**9+7
    hist=[0]*61
    bs=[]
    for i in range(n):
        # s=list(reversed(bin(a[i])[2:]))
        # for j in range(len(s)):
        #     if s[j]=='1':
        #         hist[j]+=1
        # bs.append(s)

        s=bin(a[i])[2:]
        for j in range(len(s)):
            if s[j]=='1':
                hist[len(s)-j-1]+=1
        # j=0
        # ai=a[i]
        # while ai>0:
        #     if ai&1==1:
        #         hist[j]+=1
        #     ai = ai >> 1
        #     j+=1


    #print(bs)
    #print(hist)
    #print(hist)
    sum=0
    # for i in range(n-1):
    #     s=bs[i]
    #     b=1
    #     for j in range(len(s)):
    #         if s[j]=='0':
    #             sum=(sum+hist[j]*b)%MOD
    #         else:
    #             sum=(sum+( n-i-hist[j] )*b)%MOD
    #             hist[j]-=1
    #         b*=2
    #     for j in range(len(s),61):
    #         sum=(sum+hist[j]*b)%MOD
    #         b*=2
    b=1
    for j in range(61):
        sum=(sum+( hist[j]*(n-hist[j])*b )%MOD )%MOD
        b*=2

    return sum

if __name__=='__main__':
    n,l=readinput()
    ans=main(n,l)
    print(ans)
### BUGGY CODE ###

N = int(input())
a = [int(input()) for _ in range(N)]
pikaa = 1
ans = 0
while 1:
    pikaa = a[pikaa - 1]
    ans += 1
    if pikaa == 1:
        print(-1)
        exit()
    elif pikaa == 2:
        print(ans)
        exit()


### FIXED CODE ###

N = int(input())
a = [int(input()) for _ in range(N)]
pikaa = 1
ans = 0
for _ in range(N):
    pikaa = a[pikaa - 1]
    ans += 1
    if pikaa == 2:
        print(ans)
        exit()
print(-1)
### BUGGY CODE ###

import sys

s = [ord(a)-97 for a in list(sys.stdin.readline().rstrip())]
t = [ord(b)-97 for b in list(sys.stdin.readline().rstrip())]
len_s = len(s)
len_t = len(t)

dp = [[0] * (len_t+1) for i in range(len_s+1)]
for i in range(len_s):
    for j in range(len_t):
        if s[i] == t[j]:
            dp[i+1][j+1] = dp[i][j] + 1
        else:
            dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])

strings = []
while len_s > 0 and len_t > 0:
    if s[len_s-1] == t[len_t-1]:
        len_s -= 1
        len_t -= 1
        strings.insert(0,chr(s[len_s]+97))
    elif dp[len_s][len_t-1] > dp[len_s-1][len_t]:
        len_t -= 1
    else:
        len_s -= 1

print("".join(strings))


### FIXED CODE ###

import sys

s = [ord(a)-97 for a in list(sys.stdin.readline().rstrip())]
t = [ord(b)-97 for b in list(sys.stdin.readline().rstrip())]
len_s = len(s)
len_t = len(t)

dp = [[0] * (len_t+1) for i in range(len_s+1)]
for i in range(len_s):
    for j in range(len_t):
        if s[i] == t[j]:
            dp[i+1][j+1] = dp[i][j] + 1
        else:
            dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])

strings = []
while len_s > 0 and len_t > 0:
    if s[len_s-1] == t[len_t-1]:
        len_s -= 1
        len_t -= 1
        strings.insert(0,chr(s[len_s]+97))
    elif dp[len_s][len_t-1] > dp[len_s-1][len_t]:
        len_t -= 1
    else:
        len_s -= 1

print("".join(strings))
### BUGGY CODE ###

N, M = (int(x) for x in input().split())
a, b, b2, p = [], [], [], []
for i in range(N):
    p.append([int(x) for x in input().split()])
    a.append(p[i][0])
    b.append(p[i][1])
ans = 0
while M > 0:
    idx = [i for i, x in enumerate(a) if x == min(a)]
    if len(idx) == 1:
        n = b[idx[0]]
        idx = idx[0]
    else:
        b2.append([i, b[i]] for i in idx)
        n = max(b2[:][1])
        idx = b2.index(b2[:][1] == n)
    if M - n >= 0:
        ans += a[idx] * n
        M -= n
    else:
        ans += a[idx] * M
        M = 0
    del a[idx]
    del b[idx]

print(ans)


### FIXED CODE ###

n, m = map(int, input().split())
l = []
for _ in range(n): l.append([int(x) for x in input().split()])
l.sort()
s = cnt = 0
for a, b in l:
    if cnt + b < m:
        s += a*b
        cnt += b
    else:
        s += a * (m - cnt)
        break
print(s)
### BUGGY CODE ###

def index(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect.bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    return -1

n = int(input())
import bisect
dat = []
for i in range(n):
    x = int(input())
    a =  index(dat, x)
    if a == -1:
        bisect.insort_left(dat, x)
    else:
        del dat[a]
print(len(dat))

### FIXED CODE ###

dat = dict()

n = int(input())
import bisect
for i in range(n):
    x = int(input())
    if x in dat:
        del dat[x]
    else:
        dat[x] = 1

print(len(dat))
### BUGGY CODE ###

import sys
import bisect
import copy
sys.setrecursionlimit(10 ** 6)
def input():
    return sys.stdin.readline()[:-1]

def dfs(v,prev = -1):
    for u in graph[v]:
        if u == prev:
            continue
        x = As[u]
        if x > LIS[v][-1]:
            LIS[u] = LIS[v] + [x]
        else:
            l = copy.copy(LIS[v])
            l[bisect.bisect_left(l, x)] = x
            LIS[u] = l
        ans_array[u] = len(LIS[u])
        dfs(u,v)

N = int(input())
As = list(map(int,input().split()))
graph = [[] for _ in range(N)]

for i in range(N-1):
    a,b = list(map(int,input().split()))
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
LIS = [[] for i in range(N)]
LIS[0].append(As[0])
ans_array = [0] * N
ans_array[0] = 1
dfs(0)
for i in range(N):
    print(ans_array[i])


### FIXED CODE ###

import sys
import bisect
import copy
sys.setrecursionlimit(10 ** 6)
def input():
    return sys.stdin.readline()[:-1]
inf = 10**9+1

def dfs(v,prev = -1):
    x = As[v]
    if len(LIS) == 0 or x > LIS[-1]:
        old = inf
        i = len(LIS)
        LIS.append(x)
    else:
        i = bisect.bisect_left(LIS, x)
        old = LIS[i]
        LIS[i] = x

    a = len(LIS)
    ans_array[v] = a
    for u in graph[v]:
        if u == prev:
            continue
        dfs(u,v)
    if old == inf:
        LIS.pop(-1)
    else:
        LIS[i] = old

N = int(input())
As = list(map(int,input().split()))
graph = [[] for _ in range(N)]

for i in range(N-1):
    a,b = list(map(int,input().split()))
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
LIS = []
ans_array = [0] * N
dfs(0)
for i in range(N):
    print(ans_array[i])
### BUGGY CODE ###

n = int(input())
s = [''] * n
s = [input() for _ in range(n)]
  
def is_anagram(a, b):
    if len(a) != len(b): 
        return False
    else:
        return sorted(a) == sorted(b)

import itertools
a = map(lambda x: is_anagram(x[0], x[1]), list(itertools.combinations(s, 2)))
print(sum(a))


### FIXED CODE ###

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

dic = {}
count = 0
for a in s:
  key = "".join(sorted(a))
  if key in dic:
    count += dic[key]
    dic[key] += 1
  else:
    dic[key] = 1

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

def main(N,K,p):
    summary = 0
    sumi = 0
    for i in range(len(p)-K+1):
        for j in range(K):
            sumi += p[i+j]
        summary = max(summary,sumi)
        sumi = 0
    return (summary + K) / 2 

N,K = map(int,input().split())
p = list(map(int,input().split()))
print(main(N,K,p))


### FIXED CODE ###

def main(N,K,p):
    sumi = 0
    ruiseki = [0] * (N+1)
    for i in range(N):
        ruiseki[i+1] = ruiseki[i] + p[i]
    for j in range(N-K+1):
        sumi = max(sumi, (ruiseki[j+K]-ruiseki[j]))
    return (sumi + K) / 2
N,K = map(int,input().split())
p = list(map(int,input().split()))
print(main(N,K,p))
### BUGGY CODE ###


def main():
    h,w,d = map(int,input().split())
    dic = {}
    for y in range(h):
        line = list(map(int,input().split()))
        for x in range(w):
            num = line[x]
            dic[num] = (x,y)
    Q = int(input())
    for q in range(Q):
        l,r = map(int,input().split())
        cst = 0
        while l != r:
            (x,y) = dic[l]
            (nx,ny) = dic[l+d]
            cst += abs(nx - x) + abs(ny - y)
            l += d
        print(cst)

if __name__ == '__main__':
    main()

### FIXED CODE ###

h,w,d = map(int,input().split())
dic = {}

for y in range(h):
    line = list(map(int,input().split()))
    for x in range(w):
        num = line[x]
        dic[num] = (x,y)

com_sum = [0]*(h*w + 1)

for n in range(1,d+1):
    com_sum[n] = 0
    while n+d <= h*w:
        nx,ny = dic[n+d]
        x,y = dic[n]
        com_sum[n+d] = com_sum[n] + abs(nx-x) + abs(ny-y)
        n += d
    
Q = int(input())
for q in range(Q):
    l,r = map(int,input().split())
    print(com_sum[r] - com_sum[l])
### BUGGY CODE ###

N = int(input())
X = list(map(int,input().split()))
from statistics import median
for i in range(N):
    B = X[:i]+X[i+1:]
    print(median(B))

### FIXED CODE ###

import statistics
from bisect import bisect_left
N = int(input())
X = list(map(int,input().split()))
Y = sorted(X)
a,b = statistics.median_low(Y),statistics.median_high(Y)
for i in X:
    Z = bisect_left(Y,i)
    if Z<N//2:
        print(b)
    else:
        print(a)
### BUGGY CODE ###

x,y,z,k=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
l1=[]
#print(a,end=" a\n")
#print(b,end=" b\n")
for i in a:
  for j in b:
    # print(i,j)
    l1.append(i+j)
l1.sort(reverse=True)
#print(l1)
l1=l1[:min(len(l1),3000)]
l2=[]
for i in l1:
  for j in c:
    l2.append(i+j)
l2.sort(reverse=True)
#print(l2)
print("\n".join(map(str,l2[:k])))


### FIXED CODE ###

import sys
input=sys.stdin.readline
x,y,z,k=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)
l1=sorted([i+j for i in a for j in b],reverse=True)[:k]
l2=sorted([i+j for i in l1 for j in c],reverse=True)[:k]
for i in l2:
  print(i)
### BUGGY CODE ###

n,k = map(int, input().split())
p = list(int(x)-1 for x in input().split())
c = list(map(int, input().split()))
score = -10**9
loop = [[] for _ in range(n+1)]
group = [0]*n
while 0 in group:
  i = group.index(0)
  here = i
  while group[i]==0:
    here = p[here]
    loop[i+1].append(here+1)
    group[here] = i+1
while [] in loop:
  loop.remove([])
for i in loop:
  s = [0]
  cc = []
  for j in i:
    s.append(s[-1]+c[j-1])
    cc.append(c[j-1])
  s.remove(0)
  l = k%len(s)
  resd = -10**9-1
  cum = -10**9-1
  cc = cc + cc[:-1]
  for j in range(len(s)):
    resd = max(sum(cc[j:j+l]),resd)
  for j in range(1,min(k,len(s))+1):
    for m in range(len(s)):
      cum = max(sum(cc[m:m+j]),cum)
  if s[-1]>0 and len(s)<k:
    sc = s[-1]*(k//len(s))+resd
  else:
    sc = cum
  score = max(sc,score)
print(score)

### FIXED CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))
c=list(map(int,input().split()))
ans=-10**18
flag=dict()
for i in range(n):
    if i in flag:
        continue
    cur=i
    accum=[]
    flag[cur]=0
    s=0
    while flag[cur]<2:
        cur=p[cur]-1
        s+=c[cur]
        accum.append(s)
        if cur not in flag:
            flag[cur]=0
        else:
            flag[cur]+=1
    l=len(accum)//2
    loop = accum[l-1]
    accum=[0]+accum
    for x in range(1,l+1):
        if loop<=0 or k//l<1:
            ans=max(ans,max(accum[x:x+min(k,l)])-accum[x-1])
        else:
            a=max(accum[x:x+l-1])-accum[x-1]
            d=accum[x+l-1]-accum[x-1]
            if k%l!=0:
                b=max(accum[x:x+k%l])-accum[x-1]
                ans=max(ans,max(k//l*d,k//l*d+b,(k//l-1)*d+a))
            else:
                b=max(accum[x:x+l-1])-accum[x-1]
                ans=max(ans,max(k//l*d,(k//l-1)*d+a))
print(ans)
### BUGGY CODE ###

n = int(input())
p = list(map(int, input().split()))
ans = 0
for i in range(n):
    if min(p[:i + 1]) == p[i]:
        ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
p = list(map(int, input().split()))
mnm = 2 * 10**5
ans = 0
for i in p:
    if i <= mnm:
        mnm = i
        ans += 1
print(ans)
### BUGGY CODE ###

n=int(input())
L=list(map(int,input().split()))
L.sort()
count=0
for i in range(n-2):
  for j in range(i+1,n-1):
    for k in range(j+1,n):
      if L[i]+L[j]>L[k]:
        count+=1
      else:
        break
print(count)

### FIXED CODE ###

n=int(input())
L=list(map(int,input().split()))
L.sort()
count=0
for i in range(n-2):
  for j in range(i+1,n-1):
    x=j+1
    y=n-1
    while y!=x+1 and y!=x:
      if L[i]+L[j]>L[(x+y)//2]:
        x=(x+y)//2
      else:
        y=(x+y)//2
    p=y if L[i]+L[j]>L[y] else x
    if L[i]+L[j]<=L[p]:
      count+=0
    else:
      count+=p-j
print(count)
### BUGGY CODE ###

S = input()
Q = int(input())
rev = 1
for _ in range(Q):
    query = input()
    if len(query) == 1:
        rev *= -1
    else:
        T, F, C = query.split()
        if rev == 1:
            if F == "1":
                S = C + S
            else:
                S = S + C
        else:
            if F == "1":
                S = S + C
            else:
                S = C + S

if rev == -1:
    S = S[::-1]

print(S)


### FIXED CODE ###

from collections import deque

S = list(input())
Q = int(input())

S = deque(S)
rev = 1
for _ in range(Q):
    query = input()
    if len(query) == 1:
        rev *= -1
    else:
        T, F, C = query.split()
        if rev == 1:
            if F == "1":
                S.appendleft(C)
            else:
                S.append(C)
        else:
            if F == "1":
                S.append(C)
            else:
                S.appendleft(C)

if rev == -1:
    S = reversed(S)

print("".join(S))
### BUGGY CODE ###

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

if n == 1:
    print(m)
    exit()
a = []
for i in range(1, m):
    if m % n == 0:
        print(m // n)
        exit()
    if m % i == 0 and i * n <= m:
        a.append(i)

print(max(a))


### FIXED CODE ###

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

if n == 1:
    print(m)
    exit()
a = []
b = []
for i in range(1, math.ceil(math.sqrt(m))):
    if m % n == 0:
        print(m // n)
        exit()
    if m % i == 0:
        b.append(i)
        b.append(m // i)
        
#print(b)

for i in range(len(b)):
    if b[i] * n <= m:
        a.append(b[i])
#print(a)

if len(b) == 2:
    print(1)
else:
    print(max(a))