Harryxun/stf_run huggingface dataset:
from collections import defaultdict
import heapq


def dijkstra(N, adj, cost, start):
    INF = 10 ** 10
    min_cost = [INF] * N
    min_cost[start] = 0
    que = [(0, start)]
    while len(que) > 0:
        c, node = heapq.heappop(que)
        for next_node in adj[node]:
            next_cost = min_cost[node] + cost[(node, next_node)]
            if next_cost < min_cost[next_node]:
                min_cost[next_node] = next_cost
                heapq.heappush(que, (next_cost, next_node))
    return min_cost


def main():
    N, M, S, T = list(map(int, input().split()))
    S -= 1
    T -= 1
    adj = defaultdict(list)
    yen = defaultdict(int)
    snuuk = defaultdict(int)
    for _ in range(M):
        U, V, A, B = list(map(int, input().split()))
        U -= 1
        V -= 1
        adj[U].append(V)
        adj[V].append(U)
        yen[(U, V)], yen[(V, U)] = A, A
        snuuk[(U, V)], snuuk[(V, U)] = B, B
    min_yen = dijkstra(N, adj, yen, S)
    min_snuuk = dijkstra(N, adj, snuuk, T)
    # 都市iで両替をしてs -> tを移動した場合の最小コスト
    min_cost = [y + s for y, s in zip(min_yen, min_snuuk)]
    # ゴールの都市Tで両替するのはNGなことに注意
    city_cost = [(cost, city) for city, cost in enumerate(min_cost) if city != T]
    heapq.heapify(city_cost)
    ans = [0] * N
    cost, city = heapq.heappop(city_cost)
    for i in range(N):
        # i年後に都市0 ～ i - 1の両替所は使えない
        while city < i:
            cost, city = heapq.heappop(city_cost)
        ans[i] = 10 ** 15 - cost
    for a in ans:
        print(a)


if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import defaultdict
import heapq


def dijkstra(N, adj, cost, start):
    INF = 10 ** 15
    min_cost = [INF] * N
    min_cost[start] = 0
    que = [(0, start)]
    while len(que) > 0:
        c, node = heapq.heappop(que)
        for next_node in adj[node]:
            next_cost = min_cost[node] + cost[(node, next_node)]
            if next_cost < min_cost[next_node]:
                min_cost[next_node] = next_cost
                heapq.heappush(que, (next_cost, next_node))
    return min_cost


def main():
    MONEY_MAX = 10 ** 15
    N, M, S, T = list(map(int, input().split()))
    S -= 1
    T -= 1
    adj = defaultdict(list)
    yen = defaultdict(int)
    snuuk = defaultdict(int)
    for _ in range(M):
        U, V, A, B = list(map(int, input().split()))
        U -= 1
        V -= 1
        adj[U].append(V)
        adj[V].append(U)
        yen[(U, V)], yen[(V, U)] = A, A
        snuuk[(U, V)], snuuk[(V, U)] = B, B
    min_yen = dijkstra(N, adj, yen, S)
    min_snuuk = dijkstra(N, adj, snuuk, T)
    # 都市iで両替をしてs -> tを移動した場合の最小コスト
    min_cost = [y + s for y, s in zip(min_yen, min_snuuk)]
    city_cost = [(cost, city) for city, cost in enumerate(min_cost)]
    heapq.heapify(city_cost)
    ans = [0] * N
    cost, city = heapq.heappop(city_cost)
    for i in range(N):
        # i年後に都市0 ～ i - 1の両替所は使えない
        while city < i:
            cost, city = heapq.heappop(city_cost)
        ans[i] = MONEY_MAX - cost
    for a in ans:
        print(a)


if __name__ == '__main__':
    main()
a, b = map(int, input().split())

if (a*b) % 2:
    print(‘Odd’)
else:
    print(‘Even’)

### FIXED CODE ###

a, b = map(int, input().split())

if (a*b) % 2:
    print('Odd')
else:
    print('Even')
import queue

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

road = [[] for i in range(m)]

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

# cost to isMin
result = [[999999999999999, None, False] for i in range(n)]

# from tom
q = queue.Queue()

result[0] = [0, None, True]
for i in road[0]:
    q.put([0,i])

while not q.empty():
    n = q.get()
    result[n[1]]=[result[n[0]][0]+1, n[0], True]
    for i in road[n[1]]:
        if(not result[i][2]):
            q.put([n[1], i])

flag = True
for i in result:
    if(not i[2]):
        flag = False
        break

if(flag):
    print("Yes")
    for i in range(1,len(result)):
        print(result[i][1]+1)
else:
    print("No")


    



### FIXED CODE ###

import queue

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

road = [[] for i in range(n)]

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

# cost to isMin
result = [[999999999999999, None, False] for i in range(n)]

# from tom
q = queue.Queue()

result[0] = [0, None, True]
for i in road[0]:
    q.put([0,i])

while not q.empty():
    n = q.get()
    if(not result[n[1]][2]):
        result[n[1]]=[result[n[0]][0]+1, n[0], True]
        for i in road[n[1]]:
            q.put([n[1], i])

flag = True
for i in result:
    if(not i[2]):
        flag = False
        break

if(flag):
    print("Yes")
    for i in range(1,len(result)):
        print(result[i][1]+1)
else:
    print("No")
import sys

for s in sys.stdin:
	sur = [list(map(int, s.strip()))]
	if 1 not in sur[0]:
		sur.pop()
	for _ in range(7):
		sur.append(list(map(int, input().strip())))
		if 1 not in sur[-1]:
			sur.pop()

	if len(sur) == 1:
		print("C")
	elif len(sur) == 2:
		if sur[0].index(1) == sur[1].index(1):
			print("A")
		elif sur[0].index(1) < sur[1].index(1):
			print("E")
		else:
			print("G")
	elif len(sur) == 3:
		if sur[0].index(1) > sur[2].index(1):
			print("D")
		else:
			print("F")
	elif len(sur) == 4:
		print("B")

### FIXED CODE ###

import sys

while True:
	sur = []

	for _ in range(8):
		sur.append(list(map(int, input().strip())))
		if 1 not in sur[-1]:
			sur.pop()

	if len(sur) == 1:
		print("C")
	elif len(sur) == 2:
		if sur[0].index(1) == sur[1].index(1):
			print("A")
		elif sur[0].index(1) < sur[1].index(1):
			print("E")
		else:
			print("G")
	elif len(sur) == 3:
		if sur[0].index(1) > sur[2].index(1):
			print("D")
		else:
			print("F")
	elif len(sur) == 4:
		print("B")

	try:
		line = input()
	except:
		break
import math
def f(b,n):
    if n<b:
        return n
    else:
        return f(b,n//b)+(n%b)
N=int(input())
S=int(input())
if N==S:
    print(N+1)
else:
    for b in range(2,int(math.sqrt(N))+2):
        if f(b,N)==S:
            print(b)
            exit()
    for p in range(int(math.sqrt(N))+2):
        b=(N-S)//(p+1)
        if f(b,N)==S:
            print(b)
            exit()
    print(-1)


### FIXED CODE ###

import math
def f(b,n):
    if n<b:
        return n
    else:
        return f(b,n//b)+(n%b)
N=int(input())
S=int(input())
if N==S:
    print(N+1)
else:
    for b in range(2,int(math.sqrt(N))+2):
        if f(b,N)==S:
            print(b)
            exit()
    ans=10**13
    for p in range(1,int(math.sqrt(N))+2):
        if (N-S)%p!=0:
            continue
        b=(N-S)//p+1
        if b<=1:
            continue
        if f(b,N)==S:
            ans=b
    if ans==10**13:
        print(-1)
    else:
        print(ans)
import math
abc = [int(input()) for _ in range(5)]
tmp = 9
ans = 0
for i in range(5):
    tmpp = min(tmp, (abc[i]-1)%10)
    if tmp != tmpp:
        tmp = tmpp
        ii = i
for i in range(5):
    if i == ii:
        ans += abc[i]
    else:
        ans += (math.ceil(abc[i]/10))*10
print(ans)

### FIXED CODE ###

import math
abc = [int(input()) for _ in range(5)]
tmp = 9
ans = 0
ii = 0
for i in range(5):
    tmpp = min(tmp, (abc[i]-1)%10)
    if tmp != tmpp:
        tmp = tmpp
        ii = i
for i in range(5):
    if i == ii:
        ans += abc[i]
    else:
        ans += (math.ceil(abc[i]/10))*10
print(ans)
S = int(input())
ans = int(999)
diff = int(0)

for i in range(0, len(S) - 2):
    diff = abs(int(S[i:i+3]) - 753)
    if ans > diff:
        ans = diff
print(ans)

### FIXED CODE ###

S = input()
ans = int(999)
diff = int(0)

for i in range(0, len(S) - 2):
    diff = abs(int(S[i:i+3]) - 753)
    if ans > diff:
        ans = diff
print(ans)
import bisect

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

for _ in range(M):
    max_value = max(A)
    max_index = bisect.bisect_left(A,max_value)
    A[max_index] = max_value // 2

print(sum(A))

### FIXED CODE ###

import heapq
import sys

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

def main():
    N,M = map(int,input().split())
    A = list(map(int,input().split()))
    A = list(map(lambda x: x*(-1),A))

    heapq.heapify(A)

    for _ in range(M):
        max_value = heapq.heappop(A) * (-1)
        heapq.heappush(A,max_value//2 * (-1))

    print(sum(A) * (-1))

if __name__ == "__main__":
    main()
i = 0
while True:
    i += 1
    num = raw_input()
    if len(num) == 0:
        break
    print "Case %d: %s" % (i,num)

### FIXED CODE ###

i = 0
while True:
    i += 1
    num = raw_input()
    if num == "0":
        break
    print "Case %d: %s" % (i,num)
a, b = map(int, input().split())
c = [0]
for i in range(1, 999):
    c.append(c[i-1]+i)
    if c[i-1]-a >= 0:
        ans = c[i-1]-a
        break
print(ans)


### FIXED CODE ###

a, b = map(int, input().split())
c = [0]
for i in range(1, 1000):
    c.append(c[i-1]+i)
    if c[i-1]-a > 0:
        ans = c[i-1]-a
        if a+ans == c[i-1] and b+ans == c[i]:
            break
        else:
            ans = 0
print(ans)
n = int(input())
h = [int(i) for i in range(n)]
ans = []
a = 0
for i in range(n-1):
  if h[i] >= h[i+1]:
    a += 1
  else:
    ans.append(a)
    a = 0
print(max(ans))

### FIXED CODE ###

n = int(input())
h = [int(i) for i in input().split()]
ans = []
a = 0
for i in range(n-1):
  if h[i] >= h[i+1]:
    a += 1
  else:
    ans.append(a)
    a = 0
ans.append(a)
print(max(ans))
import math

def comb(n,r):
	return math.factorial(n)//math.factorial(n-r)//math.factorial(r)

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

for i in range(1,K+1):
	print(comb(N-K+1,i)*comb(K-1,i-1)%1000000007)

### FIXED CODE ###

from math import factorial
N, K = map(int, input().split())
mod = 10**9 + 7
def combination(n, r):
	if n >= r:
		return int(factorial(n) // (factorial(r) * factorial(n - r)))
	else:
		return 0

for i in range(1, K+1):
	print(combination(N-K+1, i) * combination(K-1, i-1)%mod)
N = int(input())
candi =int((N+1)/2*N -N)
import sys
sys.setrecursionlimit(1000000000)
def f(count,i):
    nex_num = (i//2) + 1
    count += (i%nex_num) #next_numを割るところに使う
    middle_sum = int((i-1 + nex_num )/2*(i -nex_num))
    count += middle_sum
    nex_num = nex_num -1
    if nex_num == 2:
        return count +1
    return f(count,nex_num)

def f2(count,i):
    nex_num = (i+1)//2
    count += (i%nex_num) #next_numを割るところに使う
    middle_sum = int((i-1 + nex_num )/2*(i -nex_num))
    count += middle_sum
    nex_num = nex_num -1
    if nex_num == 1:
        return count
    return f2(count,nex_num)

if N%2 == 0:
    nex_num = N
    count = f(0,nex_num)
else:
    nex_num = N
    count = f2(0,nex_num)
if candi > count:
    print(candi)
else:
    print(count)

### FIXED CODE ###

N = int(input())
print((N-1)*N//2)
n=int(input())
l=list(map(int, input().split()))
l=sorted([x for x in set(l) if l.count(x)<4])
ans=0
x=[]
for i in range(n):
    for j in range(i+1,n):
        for k in range(j+1,(n-sum((x>l[j]+l[i]) for x in l))):
            if (l[i]<(l[j]+l[k])and l[j]<(l[i]+l[k]) and x.count([l[i],l[j],l[k]])==0):
                x.append([l[i],l[j],l[k]])
                ans+=1

print(ans)

### FIXED CODE ###

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

c=a-2*b
if c<0:
    c=0
    
print(c)
a,b = int(input())

a-=1
b-=1

print(a*b)

### FIXED CODE ###

a,b=map(int, input().split())

print((a-1)*(b-1))
a,b,c = input().split()
print(a[0]+b[0]+c[0]

### FIXED CODE ###

a,b,c = input().split()
print(a[0]+b[0]+c[0])
def _comb(N,M):
    if not N:return(0)
    count=1
    for i in range(0,M):
        count*=N-i
    for i in range(1,M+1):
        count/=i
    return(int(count))

N,M=list(map(int,input().split()))
A=[int(input()) for i in range(M)]
A.append(N+1)
count=1
if 1 in A:pre=-1
else:pre=0
for a in A:
    count*=sum([_comb(a-1-pre-i,i) for i in range((a-1)-pre)])
    print(sum([_comb(a-1-pre-i,i) for i in range((a-1)-pre)]),a)
    pre=a+1
print(count%1000000007)


### FIXED CODE ###

N,M=map(int,input().split())
mod=10**9+7
A=set([int(input()) for i in range(M)])

data=[0 for i in range(N)]
if 1 not in A:
    data[0]=1
if N>=2:
    if 2 not in A:
        data[1]=1+data[0]


for i in range(2,N):
    if i+1 not in A:
        data[i]=data[i-1]+data[i-2]
        data[i]%=mod

#print(data)

print(data[-1])
n,k= list(map(int, input().split()))
j = list(map(int, input().split()))
s=0
sumlist=[0]*n
anslist=[0]*(n-k+1)
for i in range(n):
    s+=j[i]
    sumlist[i]=s
for i in range(len(anslist)):
    if i==0:
        z=sumlist[k-1]
        anslist[i]=z
    else:
        z=sumlist[i+k]-sumlist[i]
        anslist[i]=z
ans=max(anslist)
ans+=k
ans=ans/2
print(ans)
    

### FIXED CODE ###

n,k= list(map(int, input().split()))
j = list(map(int, input().split()))
s=0
sumlist=[0]*(n+1)
anslist=[0]*(n-k+1)
for i in range(n):
    s+=j[i]
    sumlist[i+1]=s
for i in range(len(anslist)):
     z=sumlist[i+k]-sumlist[i]
     anslist[i]=z
ans=max(anslist)
ans+=k
ans=ans/2
print(ans)
import sys
import math
from functools import reduce
input = sys.stdin.readline

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

def gcd_list(numbers):
    return reduce(math.gcd, numbers)

print(gcd_list(A))

### FIXED CODE ###

import sys

input = sys.stdin.readline

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

def gcd(m, n):
    x = max(m, n)
    y = min(m, n)
    if x%y == 0:
        return y
    else:
        while x%y != 0:
            z = x%y
            x = y
            y = z
        else:
            return z

A.sort()
ans = A[0]
for i in range(1, N):
    ans = gcd(ans, A[i])
print(ans)
a,b = map(int,input().split())

if a > b:
    print("GREATER")
elif a < b:
    print("LESS")
else:
    print("EQUAL")

### FIXED CODE ###

a = int(input())
b = int(input())

if a > b:
    print("GREATER")
elif a < b:
    print("LESS")
else:
    print("EQUAL")
a_list = list(input())
b_list = list(input())
c_list = list(input())

a_turn = True
b_turn = False
c_turn = False

max_battle = len(a_list) + len(b_list) + len(c_list)

for i in range(max_battle):
    if(a_turn):
        a_list.pop(0)
        if(len(a_list) == 0):
            print("a")
            exit() 
        else:
            if(a_list[0] == 'b'):
                a_turn = False
                b_turn = True 
            elif(a_list[0] == 'c'):
                a_turn = False
                c_turn = True  
    elif(b_turn):
        a_list.pop(0)
        if(len(b_list) == 0):
            print("b")
            exit() 
        else:
            if(b_list[0] == 'a'):
                b_turn = False
                a_turn = True 
            elif(b_list[0] == 'c'):
                b_turn = False
                c_turn = True  
    elif(c_turn):
        c_list.pop(0)
        if(len(c_list) == 0):
            print("c")
            exit() 
        else:
            if(c_list[0] == 'a'):
                c_turn = False
                a_turn = True 
            elif(a_list[0] == 'b'):
                c_turn = False
                b_turn = True  


### FIXED CODE ###

# 入力
SA=list(input())
SB=list(input())
SC=list(input())

# 次に捨てる人（初期値は'A')
x='a'

while True:
  if x=='a':
    # リストの要素が0ならば終了する
    if len(SA)==0:
      print('A')
      exit()

    # 先頭要素を除去してxに代入
    x=SA[0]
    SA.remove(x)
  elif x=='b':
    # リストの要素が0ならば終了する
    if len(SB)==0:
      print('B')
      exit()

    # 先頭要素を除去してxに代入
    x=SB[0]
    SB.remove(x)
  else:
    # リストの要素が0ならば終了する
    if len(SC)==0:
      print('C')
      exit()

    # 先頭要素を除去してxに代入
    x=SC[0]
    SC.remove(x)
n, m = [int(v) for v in input().split()]
a, b = [], []
d = {}
for i in range(m):
    ai, bi = [int(v) for v in input().split()]
    a.append(ai)
    b.append(bi)
    d[ai] = d.get(ai, [])
    d[ai].append(bi)
    d[bi] = d.get(bi, [])
    d[bi].append(ai)

r = {}
def trace(no, lv):
    lst = d[no]
    for c in lst:
        if c != 1:
            if c not in r or (r[c][1] > lv and r[c][1] != 0):
                r[c] = (no, lv)
                trace(c, lv + 1)
trace(1, 1)

for i in range(2, n):
    if i not in r:
        print('No')
        break
else:
    print('Yes')
    for i in range(2, n +1):
        print(r[i][0])

### FIXED CODE ###

n, m = [int(v) for v in input().split()]
a, b = [], []
d = {}
for i in range(m):
    ai, bi = [int(v) for v in input().split()]
    a.append(ai)
    b.append(bi)
    d[ai] = d.get(ai, [])
    d[ai].append(bi)
    d[bi] = d.get(bi, [])
    d[bi].append(ai)

r = {}
def trace():
    tasks = [(1, 0)]
    i = 0
    while i < len(tasks):
        no, lv = tasks[i]
        for c in d[no]:
            if c != 1:
                if c not in r or (r[c][1] > lv and r[c][1] != 0):
                    r[c] = (no, lv)
                    tasks.append((c, lv + 1))
        i += 1
trace()

for i in range(2, n):
    if i not in r:
        print('No')
        break
else:
    print('Yes')
    for i in range(2, n +1):
        print(r[i][0])
n,k = map(int,input().split())

al = list(map(int,input().split()))

ansl = []
used = [0 for i in range(n)]
now = 0
while True:
    if used[now] == 1:
        break
    ansl.append(now)
    used[now] = 1
    now = al[now] -1

l = len(ansl)
last = ansl.index(now)
loop = ansl[last:]
if k <= len(ansl):
    print(ansl[k])
else:
    k -= len(ansl)
    print(loop[k%len(loop)]+1)




### FIXED CODE ###

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

al = list(map(int,input().split()))

ansl = []
used = [0 for i in range(n+1)]
now = 0
while True:
    if used[now] == 1:
        break
    ansl.append(now)
    used[now] = 1
    now = al[now] - 1

l = len(ansl)
last = ansl.index(now)
loop = ansl[last:]

if k < len(ansl):
    print(ansl[k] + 1)
else:
    k -= len(ansl)
    print(loop[k % len(loop)] + 1)
N = int(input())
A = []
for i in range(N):
    a = input()
    b = a.split(".")
    if len(b)==1:
        A.append(int(a)*(10**9))
    else:
        A.append(int(b[0] + b[1] + (9-len(b[1]))*"0"))

B = [[0]*21 for i in range(21)]
ans1 = 0
for i in range(N):
    a = A[i]
    count1 = 0
    while a%2==0:
        a//=2
        count1+=1
    count2 = 0
    while a%5==0:
        a//=5
        count2+=1
    #print(count1,count2,A[i])
    B[count1][count2] += 1
    if count1>=9 and count2>=9:
        ans1+=1

C = [[0]*22 for i in range(22)]

for i in range(21):
    for j in range(21):
        C[i+1][j+1] = B[i][j] + C[i+1][j] + C[i][j+1] - C[i][j]

#print(*C,sep="\n")
ans = 0
for i in range(21):
    for j in range(21):
        k,l = min(18,i),min(18,j)
        #if B[i][j]>0:
        #    print(B[i][j],C[21][21] + C[18-k][18-l] - C[21][18-l] - C[18-k][21],i,j)
        ans += B[i][j] * (C[21][21] + C[18-k][18-l] - C[21][18-l] - C[18-k][21])

print((ans-ans1)//2)


### FIXED CODE ###

N = int(input())
A = []
for i in range(N):
    a = input()
    b = a.split(".")
    if len(b)==1:
        A.append(int(a)*(10**9))
    else:
        A.append(int(b[0] + b[1] + (9-len(b[1]))*"0"))

B = [[0]*50 for i in range(50)]
ans1 = 0
for i in range(N):
    a = A[i]
    count1 = 0
    while a%2==0:
        a//=2
        count1+=1
    count2 = 0
    while a%5==0:
        a//=5
        count2+=1
    #print(count1,count2,A[i])
    B[count1][count2] += 1
    if count1>=9 and count2>=9:
        ans1+=1

C = [[0]*51 for i in range(51)]

for i in range(50):
    for j in range(50):
        C[i+1][j+1] = B[i][j] + C[i+1][j] + C[i][j+1] - C[i][j]

#print(*C,sep="\n")
ans = 0
for i in range(50):
    for j in range(50):
        k,l = min(18,i),min(18,j)
        #if B[i][j]>0:
        #    print(B[i][j],C[21][21] + C[18-k][18-l] - C[21][18-l] - C[18-k][21],i,j)
        ans += B[i][j] * (C[50][50] + C[18-k][18-l] - C[50][18-l] - C[18-k][50])

print((ans-ans1)//2)
N, Y = map(int, input().split())
Y = Y / 1000

for i in range(N+1):
    for j in range(N-i+1):
        if 10*i + 5*j + N-i-j == Y:
            print("{} {} {}".format(i, j, N-i-j))
            exit()

print("-1 -1 -1")

### FIXED CODE ###

print("2018"+input()[4:])
def gcd(a, b):
    if a == b or b == 0:
        return a
    elif a == 0:
        return b
    elif a > b:
        return gcd(a - b, b)
    elif a < b:
        return gcd(a, b - a)

def solve():
    N = int(raw_input())
    arr = [int(_) for _ in raw_input().split()]
    left = [0] * (N + 1)
    right = [0] * (N + 1)
    left[0] = 0
    right[N] = 0
    for i in range(1, N+1):
        left[i] = gcd(left[i - 1], arr[i - 1])
    for i in range(N - 1, 0, -1):
        right[i] = gcd(right[i + 1], arr[i])
    max_gcd = 0
    for i in range(N):
        max_gcd = max(max_gcd, gcd(left[i], right[i+1]))
    print str(max_gcd)

if __name__ == '__main__':
    solve()


### FIXED CODE ###

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

def solve():
    N = int(raw_input())
    arr = [int(_) for _ in raw_input().split()]
    left = [0] * (N + 1)
    right = [0] * (N + 1)
    left[0] = 0
    right[N] = 0
    for i in range(1, N+1):
        left[i] = gcd(left[i - 1], arr[i - 1])
    for i in range(N - 1, 0, -1):
        right[i] = gcd(right[i + 1], arr[i])
    max_gcd = 0
    for i in range(N):
        max_gcd = max(max_gcd, gcd(left[i], right[i+1]))
    print str(max_gcd)

if __name__ == '__main__':
    solve()
N,K=map(int,input().split())
P=list(map(int,input().split()))
C=list(map(int,input().split()))
a=[]
s=set()
for i in range(N):
    idx=P[i]-1
    z=set()
    tl=[]
    rl=[]
    c=0
    tc=0
    while idx not in z and c<K:
        tl.append(C[idx])
        tc+=C[idx]
        rl.append(tc)
        s.add(tc)
        z.add(idx)
        idx=P[idx]-1
        c+=1
    d,m=divmod(K,c)
    tc=d*tc
    tc+=max(rl[:m])
    s.add(tc)
print(max(s))

### FIXED CODE ###

N,K=map(int,input().split())
P=list(map(int,input().split()))
C=list(map(int,input().split()))
a=[]
ans=-10**10
for i in range(N):
    idx=P[i]-1
    z=set()
    rl=[]
    c=0
    tc=0
    while idx not in z and c<K:
        tc+=C[idx]
        rl.append(tc)
        ans=max(ans,tc)
        z.add(idx)
        idx=P[idx]-1
        c+=1
    if c<K:
        d,m=divmod(K,c)
        if m==0:
            d-=1
            m=c
        tc=d*tc
        tc+=max(rl[:m])
        ans=max(ans,tc)
print(ans)
n,i=map(int,input(),split())
print(n-i+1)

### FIXED CODE ###

n,i=map(int,input().split())
print(n-i+1)
from collections import Counter
N = int(input())
V = list(map(int,input().split(" ")))
V1 = V[::2]
V2 = V[1::2]
ans = 0
if V1 == V2:
  ans = N//2
else:
  d1 = Counter(V1)
  d2 = Counter(V2)
  m1 = max(d1)
  m2 = max(d2)
  a = d1.pop(m1)
  b = d2.pop(m2)
  if a != b:
    if d1:
      ans += sum(d1.values())
    if d2:
      ans += sum(d2.values())
  else:
    c = max(d1.values())
    d = max(d2.values())
    tmp = N - a - d
    ans = min(tmp,N - b - c)
print(ans)

### FIXED CODE ###

from collections import Counter
N = int(input())
V = list(map(int,input().split(" ")))

V1 = V[::2]
V2 = V[1::2]
ans = 0
d1 = Counter(V1)
d2 = Counter(V2)
if len(d1) == 1 and V1 == V2:
    print(N//2)
    exit()
m1 = max(d1.items(), key = lambda x:x[1])
m2 = max(d2.items(), key = lambda x:x[1])
d1.pop(m1[0])
d2.pop(m2[0])
a = m1[1]
b = m2[1]
if m1[0] != m2[0]:
    if d1:
      ans += sum(d1.values())
    if d2:
      ans += sum(d2.values())
else:
    c = 0
    d = 0
    if d1:
	    c = max(d1.values())
    if d2:
	    d = max(d2.values())
    if c != 0:
        tmp = N-b-c
    if c == 0:
        tmp = N-b-a
    if d != 0:
        ttmp = N-a-d
    if d == 0:
        ttmp = N-a-b
    
    ans = min(tmp,ttmp)
print(ans)
def main():
    N,M,K = map(int,input().split())
    A = list(map(int,input().split()))
    B = list(map(int,input().split()))
    
    a,b = [0],[0]
    for i in range(N):
        a.append(a[i] + A[i])
    for i in range(N):
        b.append(b[i] + B[i])
        
    ans,j = 0,M
    for i in range(N+1):
        if a[i] > K:
            break
        while b[j] > K - a[i]:
            j -= 1
        ans = max(ans, i+j)
        
    print(ans)
    
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    N,M,K = map(int,input().split())
    A = list(map(int,input().split()))
    B = list(map(int,input().split()))
    
    a,b = [0],[0]
    for i in range(N):
        a.append(a[i] + A[i])
    for i in range(M):
        b.append(b[i] + B[i])
        
    ans,j = 0,M
    for i in range(N+1):
        if a[i] > K:
            break
        while b[j] > K - a[i]:
            j -= 1
        ans = max(ans, i+j)
        
    print(ans)
    
if __name__ == '__main__':
    main()