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

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

get_ints = lambda: [int(st) for st in input().split()]
N=int(input())
inarr=get_ints()

sorted_in = sorted(inarr)
comb = N * (N-1) // 2

def binsearch(lft, rgt):
    half = (lft + rgt) // 2
    # print(lft, rgt, sorted_in[half])
    if lft >= half:
        return lft
    summed = 0
    res = 0

    bit = Bit(2*N+1)
    for i, value in enumerate(map(lambda x: -1 if x < sorted_in[half] else 1, inarr)):
        summed += value
        # print("summed: {}, bit: {}".format(summed, i - bit.sum(N + summed)))
        count = i - bit.sum(N + summed)
        bit.add(N + summed, 1)
        res += count

    # print(res)
    if res <= (comb // 2):
        return binsearch(half, rgt)
    else:
        return binsearch(lft, half)

# print(sorted_in)
res = binsearch(0, N)
# print(res, sorted_in[res])
print(sorted_in[res])


### FIXED CODE ###

import math
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

get_ints = lambda: [int(st) for st in input().split()]
N=int(input())
inarr=get_ints()

sorted_in = sorted(inarr)
# print(sorted_in)
comb = N*(N+1) // 2

def binsearch(lft, rgt):
    half = (lft + rgt) // 2
    # print("investigate: lft {} rgt {} half {} value {}".format(lft, rgt, half, sorted_in[half]))
    if lft >= half:
        return half
    summed = 0
    res = 0

    bit = Bit(2*N+1)
    bit.add(N, 1)
    for i, x in enumerate(inarr):
        value = 1 if x >= sorted_in[half] else -1
        summed += value
        # print("summed: {}, bit: {}".format(summed, bit.sum(N + summed)))
        count = bit.sum(N + summed)
        bit.add(N + summed, 1)
        res += count

    # print("num {} cnt {} judge {}".format(sorted_in[half], res, math.ceil(comb/2)))
    if res >= math.ceil(comb/2):
        return binsearch(half, rgt)
    else:
        return binsearch(lft, half)

# print(sorted_in)
res = binsearch(0, N)
# print(res, sorted_in[res])
print(sorted_in[res])
### BUGGY CODE ###

n, k, q = map(int, input().split())
P = [k]*n
Q = [0]*n
for _ in range(q):
  a = int(input())
  Q = list(map(lambda x,y:x+y, Q,[0 if i+1==a else -1 for i in range(n)]))
P = list(map(lambda x,y: x+y,P,Q))
for p in P: print("Yes" if p>0 else "No")

### FIXED CODE ###

n, k, q = map(int, input().split())
P = [k]*n
Q = [-q]*n
for _ in range(q): Q[int(input())-1]+=1
P = map(lambda x,y:x+y, P,Q)
for p in P: print("Yes" if p>0 else "No")
### BUGGY CODE ###

from sys import stdin, setrecursionlimit


def cmb(n, r, mod=10 ** 9 + 7):
    r = min(r, n - r)
    x = y = 1
    for i in range(r):
        x *= n - i
        x %= mod
        y *= i + 1
        y %= mod
    return x * pow(y, mod - 2, mod) % mod


def main():
    mod = 10 ** 9 + 7
    n, k = map(int, stdin.readline().split())
    a = list(map(int, stdin.readline().split()))
    a.sort()
    ans = 0
    a_cmb = [0] * n
    for i in range(n):
        a_cmb[i] = cmb(i, k - 1, mod)
    for i in range(n - k + 1):
        ans -= a[i] * a_cmb[n - 1 - i]
        ans %= mod
    for i in range(k - 1, n):
        ans += a[i] * a_cmb[i]
        ans %= mod
    print(ans % mod)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()


### FIXED CODE ###

from sys import stdin, setrecursionlimit


def main():
    mod = 10 ** 9 + 7
    n, k = map(int, stdin.readline().split())
    a = list(map(int, stdin.readline().split()))
    a.sort()
    ans = 0

    m = n + 1

    fac = [0] * m
    finv = [0] * m
    inv = [0] * m

    def initialize_cmb(m):
        fac[0] = 1
        finv[0] = 1
        if m > 1:
            fac[1] = 1
            finv[1] = 1
            inv[1] = 1
            for i in range(2, m):
                fac[i] = fac[i-1] * i % mod
                inv[i] = mod - inv[mod % i] * (mod // i) % mod
                finv[i] = finv[i - 1] * inv[i] % mod

    def cmb(n, k, mod=10 ** 9 + 7):
        if n < k:
            return 0
        if n < 0 or k < 0:
            return 0
        return fac[n] * (finv[k] * finv[n - k] % mod) % mod

    initialize_cmb(m)

    for i in range(n - k + 1):
        ans -= a[i] * cmb(n - 1 - i, k - 1)
        ans %= mod
    for i in range(k - 1, n):
        ans += a[i] * cmb(i, k - 1)
        ans %= mod
    print(ans % mod)


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

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

# リストを扱いやすいように変形
def subtraction(x):
    return x - 1
A = list(map(subtraction, A))
# print(A)

# 通ったことのある場所を持っておく
ROUTE = [0]
t = A[0]
while not (t in ROUTE):
    ROUTE.append(t)
    t = A[t]


x=ROUTE.index(t) # ループのスタート地点
length = len(ROUTE) - x
# print(ROUTE, length)

if k < x:
    print(ROUTE[k]+1)
else:
    k = k - x
    s = k % length
    print(ROUTE[x + s]+1)


# 再び町1に戻ってくるまでの経路を調べる
# ROUTE = [0]
# t = A[0] # 現在地
# while t != 0:
#     ROUTE.append(t)
#     t = A[t]
# # print(ROUTE)

# length = len(ROUTE)
# print(ROUTE[k % length]+1)

### FIXED CODE ###

n, k  = map(int, input().split())
A = list(map(int, input().split()))
# リストを扱いやすいように変形
def subtraction(x):
    return x - 1
A = list(map(subtraction, A))

# 通ったことのある場所を持っておく
R = [0]*n
R[0] = 1
ROUTE = [0]
t = A[0]
while R[t] == 0:
    ROUTE.append(t)
    R[t] = 1
    t = A[t]

x = ROUTE.index(t) # ループのスタート地点
length = len(ROUTE) - x

if k < x:
    print(ROUTE[k]+1)
else:
    k = k - x
    s = k % length
    print(ROUTE[x + s]+1)
### BUGGY CODE ###

def gcd(N,M):
    while True:
        if min(N,M)==0:
            return max(N,M)
        elif N>M:
            N%=M
        elif M>N:
            M%=N
def lcm(N,M):
    return N*M//gcd(N,M)

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

L=lcm(N,M)

for i in range((N*M)//L):
    if S[i*L//M]!=T[i*L//N]:
        L=-1
        break
print(L)

### FIXED CODE ###

def gcd(N,M):
    while True:
        if min(N,M)==0:
            return max(N,M)
        elif N>=M:
            N%=M
        elif M>N:
            M%=N
def lcm(N,M):
    return N*M//gcd(N,M)

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

L=lcm(N,M)

for i in range((N*M)//L):
    if S[i*L//M]!=T[i*L//N]:
        L=-1
        break
print(L)
### BUGGY CODE ###

import sys
sample = sys.stdin.read().splitlines()
nandk  = list(map(int, sample[0].split()))
stones = list(map(int, sample[1].split()))
n, k = nandk[0], nandk[1]
dp = [float('inf')] * n
jumps = range(1, k+1)
dp[0] = 0
for idx in range(len(dp)):
  for jump in jumps:
    if idx+jump < len(dp):
      dp[idx+jump] =  min(dp[idx]+abs(stones[idx+jump]-stones[idx]), dp[idx+jump])
print(dp[-1])

### FIXED CODE ###

def main():
    n, k = map(int, input().split())
    h = tuple(map(int, input().split()))
    INF = 10 ** 9
    dp = [INF] * n
    dp[0] = 0
    for i in range(n):
        for j in range(1, k + 1):
            i_j = i + j
            if i_j < n:
                x = dp[i] + abs(h[i] - h[i_j])
                if dp[i_j] > x:
                    dp[i_j] = x
    print(dp[-1])


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

x = int(input())

if x >= 2000:
    print(1)
else:
    flag = False
    n = 19
    for a in range(n):
        for b in range(n):
            for c in range(n):
                for d in range(n):
                    for e in range(n):
                        for f in range(n):
                            val = x - a * 100 - b * 101 - c * 102 - d * 103 - e * 104 - f * 105
                            if val == 0:
                                flag = True
                                break
                        if flag:
                            break
                    if flag:
                        break
                if flag:
                    break
            if flag:
                break
        if flag:
            break

    print(1) if flag else print(0)


### FIXED CODE ###

x = int(input())

dp = [0] * 100001

dp[100] = dp[101] = dp[102] = dp[103] = dp[104] = dp[105] = 1

for i in range(106, 100001):
    if dp[i - 100] == 1 or dp[i - 101] == 1 or dp[i - 102] == 1 or dp[i - 103] == 1 or dp[i - 104] == 1 or dp[
        i - 105] == 1:
        dp[i] = 1

print(dp[x])
### BUGGY CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import sys

def qsort( a ):
	if not isinstance(a,list):
		raise TypeError('qsort can only sort \'list\'')
	if len(a) <= 1:
		return a
	p = a[0]
	for i in range(1,len(a)):
		if a[0] != a[i]:
			p = a[i]
			break
		elif i == len(a)-1:
			#all are same
			return a

	while True:
		i = 0
		j = len(a)
		for i in range( 0, len(a) ):
			if p <= a[i]:
				break
		for j in range( len(a)-1, -1, -1 ):
			if a[j] < p:
				break
		if i > j:
			a1 = qsort( a[:i] )
			a2 = qsort( a[i:] )
			a1.extend(a2)
			return a1
		else:
			tmp  = a[i]
			a[i] = a[j]
			a[j] = tmp

if __name__ == '__main__':
	m_list = []
	for i in range(0,10):
		m_list.append( int( sys.stdin.readline() ) )
	s = qsort(m_list)
	s.reverse()
	for i in range(0,3):
		print('{}'.format(s[i]))

### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import sys

def qsort( a ):
	if not isinstance(a,list):
		raise TypeError('qsort can only sort \'list\'')
	if len(a) <= 1:
		return a
	p = a[0]
	for i in range(1,len(a)):
		if a[0] != a[i]:
			if a[0] < a[i]:
				p = a[i]
			break
		elif i == len(a)-1:
			#all are same
			return a
	
	while True:
		i = 0
		j = len(a)
		for i in range( 0, len(a) ):
			if p <= a[i]:
				break
		for j in range( len(a)-1, -1, -1 ):
			if a[j] < p:
				break
		if i >= j:
			a1 = qsort( a[:i] )
			if i < len(a):
				a2 = qsort( a[i:] )
				a1.extend(a2)
			return a1
		else:
			tmp  = a[i]
			a[i] = a[j]
			a[j] = tmp

if __name__ == '__main__':
	m_list = []
	for i in range(0,10):
		m_list.append( int( sys.stdin.readline() ) )
	s = qsort(m_list)
	s.reverse()
	for i in range(0,3):
		print('{}'.format(s[i]))
### BUGGY CODE ###

n,m=map(int,input().split())
up=float('inf')
dp=[[up]*(1<<n) for i in range(m)]

dp[0][0]=0
buy=[]
a=[]
b=[]
for cnt in range(m):
    x,y=map(int,input().split())
    a.append(x)
    b.append(y)
    c=list(map(int,input().split()))
    tmp=0
    for w in c:
        tmp+=1<<(w-1)
    buy.append(tmp)

for i in range(m-1):
    for j in range(1<<n):
        dp[i+1][j]=min(dp[i+1][j],dp[i][j])
        dp[i+1][j|buy[i]]=min(dp[i][j]+a[i],dp[i+1][j|buy[i]])

if dp[m-1][-1]==float('inf'):
    print(-1)
else:
    print(dp[m-1][-1])

### FIXED CODE ###

n,m=map(int,input().split())
up=float('inf')
dp=[[up]*(1<<n) for i in range(m)]

dp[0][0]=0
buy=[]
a=[]
b=[]
for cnt in range(m):
    x,y=map(int,input().split())
    a.append(x)
    b.append(y)
    c=list(map(int,input().split()))
    tmp=0
    for w in c:
        tmp+=1<<(w-1)
    buy.append(tmp)

for i in range(m-1):
    for j in range(1<<n):
        dp[i+1][j]=min(dp[i+1][j],dp[i][j])
        dp[i+1][j|buy[i]]=min(dp[i][j]+a[i],dp[i+1][j|buy[i]])

if dp[m-1][-1]==float('inf'):
    print(-1)
else:
    print(dp[m-1][-1])
### BUGGY CODE ###

import sys

A, B, C = map(int, input().split())

if (A / 2) % 2 == 1 and (B / 2) % 2 == 1 and (C / 2) % 2 == 1:
    print(-1)
    sys.exit()

cnt = 0
while A % 2 == 0 and B % 2 == 0 and C % 2 == 0:
    a = B // 2 + C // 2
    b = A // 2 + C // 2
    c = A // 2 + B // 2
    A = a
    B = b
    C = c
    cnt += 1
print(cnt)


### FIXED CODE ###

A, B, C = map(int, input().split())


def F(a, b, c):
    if a % 2 == 1 or b % 2 == 1 or c % 2 == 1:
        return 0
    if a == b == c:
        return -1
    return F((a + b) // 2, (b + c) // 2, (c + a) // 2) + 1


print(F(A, B, C))
### BUGGY CODE ###

S = input()
Q = int(input())
Que = [input().split(" ") for i in range(Q)]
flip = False

for i in Que:
    T = int(i[0])
    if T == 1:
        flip = not(flip)
    else:
        F = int(i[1])
        C = i[2]
        if (F == 1 and not flip) or (F == 2 and flip):
            S = C + S
        else:
            S = S + C
print(S if not flip else S[::-1])


### FIXED CODE ###

import sys
from collections import deque

S = deque(sys.stdin.readline().rstrip())
Q = int(sys.stdin.readline().rstrip())
flip = False

for i in range(Q):
    Que = sys.stdin.readline().rstrip()
    if Que == "1":
        flip = not(flip)
    else:
        Query = Que.split()
        F = Query[1]
        if (F == "1") ^ flip:
            S.appendleft(Query[2])
        else:
            S.append(Query[2])
print("".join(S) if not flip else "".join(S)[::-1])
### BUGGY CODE ###

X = int(input())
 
flag = 0
A = 0
B = 0
 
for i in range(0, 100000):
  for j in range(0, i):
    if i**5 - j**5 == X:
      A = i
      B = j
      break
    elif i**5 + j**5 == X:
      A = i
      B = j
      break
    elif -i**5 - j**5 == X:
      A = -i
      B = j
      break
print(str(A) + ' ' + str(B))

### FIXED CODE ###

X = int(input())
 
flag = 0
A = 0
B = 0
 
for i in range(-120, 120):
  for j in range(-120, 120):
    if i**5 - j**5 == X:
      A = i
      B = j
      break
    elif i**5 + j**5 == X:
      A = i
      B = -j
      break
    elif -i**5 - j**5 == X:
      A = -i
      B = j
      break
print(str(A) + ' ' + str(B))
### BUGGY CODE ###

n,k=map(int,input().split())
l=list(map(int,input().split()))
dp=[0]*(n)
m=1
for i in range(n):
    dp[i]=m*l[i]
    m*=l[i]
x=[dp[k-1]]
j=0
m=1

for i in range(k,n):
    
    x.append(dp[i]//dp[i-k])
    if x[-1]>x[-2]:
        print("Yes")
    else:
        print("No")
    j+=1
    


### FIXED CODE ###

n,k = map(int,input().split())
a=list(map(int,input().split()))
 
for i in range(k,n):
    if(a[i] > a[i-k]):
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

from heapq import heappop, heappush
from collections import defaultdict

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

hp = []
for i, e in enumerate(a, 1):
    heappush(hp, [-e, i])

dp = defaultdict(int)
dp[(0, n + 1)] = 0
while hp:
    e, i = heappop(hp)
    e = -e
    dp2 = defaultdict(int)
    for k, v in dp.items():
        l, r = k
        dp2[(l + 1, r)] = max(dp2[(l + 1, r)], v + abs(l + 1 - i) * e)
        dp2[(l, r - 1)] = max(dp2[(l, r - 1)], v + abs(r - 1 - i) * e)

    dp = dp2

ans = 0
for k, v in dp.items():
    ans = max(ans, v)

print(ans)


### FIXED CODE ###

from heapq import heappop, heappush
from collections import defaultdict

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

hp = []
for i, e in enumerate(a, 1):
    heappush(hp, [-e, i])

dp = defaultdict(int)
dp[(0, n + 1)] = 0
while hp:
    e, i = heappop(hp)
    e = -e
    dp2 = defaultdict(int)
    for k, v in dp.items():
        l, r = k
        dp2[(l + 1, r)] = max(dp2[(l + 1, r)], v + abs(l + 1 - i) * e)
        dp2[(l, r - 1)] = max(dp2[(l, r - 1)], v + abs(r - 1 - i) * e)

    dp = dp2

ans = 0
for k, v in dp.items():
    ans = max(ans, v)

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

import math
X = int(input())

for a in range(1, 10000):
    a4 = a**4
    a3 = a**3
    a2 = a**2
    for b in range(-1, 10000):
        an = (a-b)*(a4 + (a3)*b + (a2)*(b**2) + a*(b**3) + b**4)

        if an == X:
            print(a, b)
            exit()


### FIXED CODE ###

import math
X = int(input())

for a in range(1, 1500):
    a4 = a**4
    a3 = a**3
    a2 = a**2
    for b in range(-1500, 1500):
        an = (a-b)*(a4 + (a3)*b + (a2)*(b**2) + a*(b**3) + b**4)
        if an < 0:
            break

        if an == X:
            print(a, b)
            exit()
### BUGGY CODE ###

dic = {}

def comb(n,k,p):
  from math import factorial
  
  if n / 2 < k:
    k = n - k
  
  if n<0 or k<0 or n<k: 
    return 0
  if n==0 or k==0: 
    return 1
  
  a=factorial(n) %p
  b=factorial(k) %p
  c=factorial(n-k) %p
  return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p

def power_func(a,b,p):
  if (a,b) in dic:
    return dic[(a,b)]
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    dic[(a,b)] = d*d %p
    return d*d %p
  if b%2==1:
    dic[(a,b)] = (a*power_func(a,b-1,p))%p
    return (a*power_func(a,b-1,p))%p

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


count = 0
i = n - 1
j = k - 1
k = 0
while True:
  tmp = comb(i, j, 10**9+7)
  count += tmp * a[-1-k]
  count -= tmp * a[k]
  count = count % (10 ** 9 + 7)
  if i == j:
    break
  i -= 1
  k += 1
    
print(count)


### FIXED CODE ###

# x^n % mod
def pow_k(x, n, mod):
  if n == 0:
    return 1

  K = 1
  while n > 1:
    if n % 2 != 0:
      K = (x * K) % mod
        
    x = (x * x) % mod

    n //= 2

  return (x * K) % mod

def main():
  MOD = 10 ** 9 + 7
  n,k = map(int,input().split())
  a = sorted(list(map(int,input().split())))
  
  g_k = 1
  for i in range(1,k):
    g_k *= i
    g_k %= MOD
    
  gyakugen = pow_k(g_k,MOD-2,MOD)
  array = [0] * (n+1)
  array[k-1] = g_k
  
  for i in range(k, n+1):
    array[i] = array[i-1] * i * pow_k(i-k+1,MOD-2,MOD)
    array[i] %= MOD
    
  ans = 0
  for i in range(n):
    if i-k+1 >= 0:        
      ans += array[i] * gyakugen * a[i]
      
    if n-i-k >= 0:
      ans -= array[n-i-1] * gyakugen * a[i]
      
    ans %= MOD
      
  print(ans)

main()
### BUGGY CODE ###

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

for i in range(n):
    j = a.index(i+1)
    m.append(str(j+1))
else:
    print(" ".join(m))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
b = [i for i in range(1,n+1)]
ab = dict(zip(a, b))
ab2 = sorted(ab.items())
m = []

for i in range(n):
    m.append(str(ab2[i][1]))
else:
    print(" ".join(m))
### BUGGY CODE ###

import sys
F = sys.stdin
N, Q = map(int, F.readline().strip("\n").split())
s = F.readline().strip("\n")
O = [None] * Q
for i in range(Q):
    O[i] = list(map(str, F.readline().strip("\n").split()))

leftlow, lefthigh = 0, N
while lefthigh - leftlow > 1:
    mid = (lefthigh + leftlow)//2
    now, nowi = s[mid], mid
    vanishleft = False
    for place, move in O:
        if place == now:
            if move == "L":
                if nowi == 0:
                    vanishleft = True
                    break
                else:
                    now, nowi = s[nowi - 1], nowi - 1
            if move == "R":
                if nowi == N - 1: break
                else: now, nowi = s[nowi + 1], nowi + 1
    if vanishleft:leftlow = mid
    else: lefthigh = mid

rightlow, righthigh = 0, N
while righthigh - rightlow > 1:
    mid = (righthigh + rightlow)//2
    now, nowi = s[mid], mid
    vanishright = False
    for place, move in O:
        if place == now:
            if move == "L":
                if nowi == 0: break
                else:
                    now, nowi = s[nowi - 1], nowi - 1
            if move == "R":
                if nowi == N - 1: 
                    vanishright = True
                    break
                else: now, nowi = s[nowi + 1], nowi + 1
    if vanishright:righthigh = mid
    else: rightlow = mid

print(righthigh - lefthigh)

### FIXED CODE ###

import sys
F = sys.stdin
N, Q = map(int, F.readline().strip("\n").split())
s = F.readline().strip("\n")
O = [None] * Q
for i in range(Q):
    O[i] = list(map(str, F.readline().strip("\n").split()))

leftlow, lefthigh = 0, N
while lefthigh - leftlow > 1:
    mid = (lefthigh + leftlow)//2
    now = mid
    for place, move in O:
        if place == s[now]:
            if move == "L": now -= 1
            else: now += 1
            if now == -1 or now == N: break
    if now == -1:leftlow = mid
    else: lefthigh = mid

rightlow, righthigh = 0, N
while righthigh - rightlow > 1:
    mid = (righthigh + rightlow)//2
    now = mid
    for place, move in O:
        if place == s[now]:
            if move == "L":now -= 1
            else: now += 1
            if now == -1 or now == N: break
    if now == N:righthigh = mid
    else: rightlow = mid

print(righthigh - lefthigh)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
dcg_list = [0] * N

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

for i in range(N):
    if i != 0:
        temp_dcg = A[0]
    else:
        temp_dcg = A[1]
    for j in range(i):
        temp_dcg = gcd(temp_dcg, A[j])
    for k in range(i + 1, N):
        temp_dcg = gcd(temp_dcg, A[k])
    dcg_list[i] = temp_dcg

print(max(dcg_list))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
gcd_list = [0] * N

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

#i-1番目までの最大公約数リスト
b = [0] * (N - 1)
b[0] = A[0]
for i in range(1, N - 1):
    b[i] = gcd(b[i - 1], A[i])
#i+1以降の最大公約数リスト
a = [0] * (N - 1)
a[N - 2] = A[N - 1]
for i in reversed(range(0, N - 2)):
    a[i] = gcd(a[i + 1], A[i + 1])

gcd_list[0] = a[0]
gcd_list[N-1] = b[N - 2]
for i in range(1, N - 1):
    gcd_list[i] = gcd(b[i - 1], a[i])

print(max(gcd_list))
### BUGGY CODE ###

N, K = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))

#if max(C) < 0:
#  print(min(C))
#  quit()
  
A = [0] * N

for i in range(N):#スタート地点
  q = [i + 1]
  now = i + 1
  score = []
  point = 0
  T = True
  while T:
    now = P[now - 1]
    point += C[now - 1]
    score.append(point)
    if now in q:
      T = False
    else:
      q.append(now)
  #print(q)#ループのルート
  #print(score)#ループ中のスコア
  if len(q) >= K:#一周未満
    score = score[:K]
    A[i] = max(score)
  else:#一周以上
    if score[-1] <= 0:#周回しない方がいいケース
      A[i] = max(score)
    else:#周回すべきケース
      ll = -float("inf")
      for j in range(len(q)):
        roop = int((K - (j + 1)) / len(q))
        ll = max(ll, roop * score[-1] + score[j])
        #print(i, ll, roop * score[-1] + score[j])
      A[i] = ll
      
      
#print(A)      
print(max(A))      
      
      
    
    
    


### FIXED CODE ###

N, K = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))
  
already = [0] * N
A = [-float("inf")] * N

for i in range(N):#スタート地点
  if already[i] == 0:
    already[i] = 1
    q = [i + 1]
    now = i + 1
    score = []
    T = True
    while T:
      now = P[now - 1]
      score.append(C[now - 1])
      if now in q:
        T = False
      else:
        q.append(now)
        already[now - 1] = 1
    
    #A.append(q)
    #S.append(score)
    #print(q)#ループのルート
    #print(score)#ループ中のスコア
    roop = sum(score)
    if len(q) >= K:
      aa = -float("inf")
      for j in range(len(q)):
        time = 0
        bb = 0
        p = j
        while time != K:
          time += 1
          bb += score[p]
          aa = max(aa, bb)
          p += 1
          if p == len(q):
            p = 0
      A[i] = aa      
    else:  
      if roop <= 0:
        aa = -float("inf")
        for j in range(len(q)):
          time = 0
          bb = 0
          p = j
          while time != len(q):
            time += 1
            bb += score[p]
            aa = max(aa, bb)
            p += 1
            if p == len(q):
              p = 0
        A[i] = aa            
      else:
        ll = int(K / len(q)) 
        rr = K % len(q)
        aa = -float("inf")
        for j in range(len(q)):
          time = 0
          bb = ll * roop
          p = j
          while time != len(q):
            time += 1
            bb += score[p]
            if time == rr + 1:
              bb -= roop
            aa = max(aa, bb)
            p += 1
            if p == len(q):
              p = 0
        A[i] = aa           
        

#print(A)      
print(max(A))
### BUGGY CODE ###

# -*- coding: utf-8 -*-

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

password = set()
for i in range(1,N+1):
    for j in range(i+1, N+1):
        for k in range(j+1, N+1):
            w = S[i-1] + S[j-1] + S[k-1]
            password.add(w)

print(len(password))

### FIXED CODE ###

# -*- coding: utf-8 -*-

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

ans = 0
for i in range(1000):
    pw = list("{0:03d}".format(i))

    if pw[0] in S:
        w1 = S.index(pw[0])
        if pw[1] in S[w1+1:]:
            w2 = w1+1 + S[w1+1:].index(pw[1])
            if pw[2] in S[w2+1:]:
                ans += 1

print(ans)