Harryxun/stf_run huggingface dataset:
import sys
    S = str(input())
    Q = int(input())
    Query = [list(map(str, input().split())) for _ in range(Q)]
     
    sArry = S.split()
    for i in range(Q):
    #    print(i,Query[i])
        if Query[i][0] == '1':
            tmp_first = sArry[0]
            sArry[0] = sArry[-1]
            sArry[-1] = tmp_first
        else:
            if Query[i][1] == '1':
                sArry.insert(0, Query[i][2])
            else:
                sArry.append(Query[i][2])
                
    print("".join(sArry))



### FIXED CODE ###

from collections import deque

S = str(input())
Q = int(input())
Query = [list(map(str, input().split())) for _ in range(Q)]

sArry = deque(S)
rFlag = False
for i in range(Q):
    if Query[i][0] == '1':
        rFlag = (rFlag == False)
        
    else:
        if rFlag:
            if Query[i][1] == '1':
                sArry.append(Query[i][2])
            else:
                sArry.appendleft(Query[i][2])
        else:
            if Query[i][1] == '1':
                sArry.appendleft(Query[i][2])
            else:
                sArry.append(Query[i][2])
            
#    print("  ", i, rFlag, "".join(sArry), Query[i])



if rFlag:
    print("".join(reversed(sArry)))
else:
    print("".join(sArry))
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 = j+1
    if k < n and S[i] != S[j] and S[i] != S[k] and S[j] != S[k]:
      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 = j-i + j
        if k < N and S[i] != S[j] and S[j] != S[k] and S[i] != S[k]:
            ans -= 1

print(ans)
import math

def insertionSort(A,n,g,cnt):
	for i in range(g,n):
		v = A[i]
		j = i - g
		while j >= 0 and A[j] > v:
			A[j+g] = A[j]
			j = j - g
			cnt += 1
		A[j+g] = v
	return A,cnt

def shellSort(A,n):
	cnt = 0
	#m = n//2 + 1
	#G = [2*i + 1*(i==0) for i in range(m)[::-1]]
	m = int(math.log(n,2)) + 1
	G = [2**i for i in range(m)[::-1]]
	for g in G:
		A,cnt = insertionSort(A,n,g,cnt)
	return A,m,G,cnt

if __name__ == '__main__':
	
	n = int(input())
	A = []
	[A.append(int(input())) for i in range(n)]
	A,m,G,cnt = shellSort(A,n)
	print(m)
	print(' '.join([str(i) for i in G]))
	print(cnt)
	[print(a) for a in A]
	print(A == sorted(data))

### FIXED CODE ###

def insertionSort(A,n,g,cnt):
	for i in range(g,n):
		v = A[i]
		j = i - g
		while j >= 0 and A[j] > v:
			A[j+g] = A[j]
			j = j - g
			cnt += 1
		A[j+g] = v
	return A,cnt

def shellSort(A,n):
	cnt = 0
	G = [1]
	while G[-1]*3+1 <= n:
		G.append(G[-1]*3 + 1)
	G = G[::-1]
	m = len(G)
	for g in G:
		A,cnt = insertionSort(A,n,g,cnt)
	return A,m,G,cnt

if __name__ == '__main__':
	
	n = int(input())
	A = []
	[A.append(int(input())) for i in range(n)]
	
	'''
	data = [int(d) for d in data.split('\n')]
	n = data.pop(0)
	A = data[:]
	'''
	
	A,m,G,cnt = shellSort(A,n)
	print(m)
	print(' '.join([str(i) for i in G]))
	print(cnt)
	[print(a) for a in A]
N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
AX = [A[i][0] for i in range(N)]
BX = [A[i][1] for i in range(N)]
AX.sort()
BX.sort()
if N % 2 == 1:
  L = AX[(N-1)//2]
  R = BX[(N-1)//2]
  print(R-L+1)
else:
  L = AX[N//2] + AX[N//2+1]
  R = BX[N//2] + BX[N//2+1]
  print(R-L+1)


### FIXED CODE ###

N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
AX = [A[i][0] for i in range(N)]
BX = [A[i][1] for i in range(N)]
AX.sort()
BX.sort()
if N % 2 == 1:
  L = AX[(N-1)//2]
  R = BX[(N-1)//2]
  print(R-L+1)
else:
  L = AX[N//2-1] + AX[N//2]
  R = BX[N//2-1] + BX[N//2]
  print(R-L+1)
N = int(input())
v = [int(e) for e in input().split()]

a = sorted(v, reversed = True) #昇順に並べる
result = a[0]
for i in range(1, N):
    result += (result + a[i]) / 2
print(result)

### FIXED CODE ###

N = int(input())
v = [int(e) for e in input().split()]

v.sort() #昇順に並べる
result = v[0]
for i in range(1, N):
    result = (result + v[i]) / 2
print(result)
from itertools import combinations, product
from math import factorial

def nCr(n, r):
  return int(factorial(n) / factorial(n - r) / factorial(r))

n = int(input())
k = int(input())
size = len(str(n))
count = 0 if k > size - 1 else (nCr(size - 1, k) * (9 ** k))
if k == 1:
  count += sum(i * (10 ** (size - 1)) <= n for i in range(1, 10))
else:
  first = int(str(n)[0])
  count += (first - 1) * nCr(size - 1, (k - 1)) * (9 ** (k - 1))
  for digits in combinations(range(size - 1), k - 1):
    count += sum(
      sum(num * (10 ** digit) for num, digit in zip(nums, digits)) <= n % (10 ** (size - 1))
      for nums in product(range(1, 10), repeat = k - 1)
    )
print(count)


### FIXED CODE ###

from itertools import combinations, product
from math import factorial

def nCr(n, r):
  return int(factorial(n) / factorial(n - r) / factorial(r))

n = int(input())
k = int(input())
size = len(str(n))
count = 0 if k > size - 1 else nCr(size - 1, k) * (9 ** k)
if k == 1:
  count += sum(i * (10 ** (size - 1)) <= n for i in range(1, 10))
else:
  first = int(str(n)[0])
  count += 0 if k > size else (first - 1) * nCr(size - 1, k - 1) * (9 ** (k - 1))
  for digits in combinations(range(size - 1), k - 1):
    count += sum(
      sum(num * (10 ** digit) for num, digit in zip(nums, digits)) <= n % (10 ** (size - 1))
      for nums in product(range(1, 10), repeat = k - 1)
    )
print(count)
N, M = map(int,input().split())
E = [[] for k in range(N)]

for k in range(M):
    X, Y, Z = map(int,input().split())
    E[X-1].append(Y-1)
    E[Y-1].append(X-1)
G = [-1]*N

def dfs(now,group):
    if G[now] == -1:
        G[now] = group
        for tsugi in E[now]:
            dfs(tsugi,group)

ans = 0
for k in range(N):
    if G[k] == -1:
        dfs(k,ans)
        ans += 1
print(ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(100010)

N, M = map(int,input().split())
E = [[] for k in range(N)]

for k in range(M):
    X, Y, Z = map(int,input().split())
    E[X-1].append(Y-1)
    E[Y-1].append(X-1)
G = [-1]*N

def dfs(now,group):
    if G[now] == -1:
        G[now] = group
        for tsugi in E[now]:
            dfs(tsugi,group)

ans = 0
for k in range(N):
    if G[k] == -1:
        dfs(k,ans)
        ans += 1
print(ans)
s = input()
t = 'AKIHABARA'
i, j = 0, 0
ans = 'YES'
while j < len(t):
    if i == len(s) and t[j] == 'A':
        j += 1
    elif s[i] == t[j]:
        i += 1
        j += 1
    elif t[j] == 'A':
        j += 1
    else:
        ans = 'NO'
        break
print(ans)


### FIXED CODE ###

import re
s = input()
if re.match('A?KIHA?BA?RA?$', s):
    print('YES')
else:
    print('NO')
a,b,c = map(int,input().split())
q = a-b
ans = c - ans

if ans < 0:
  ans = 0
  
print(ans)

### FIXED CODE ###

a,b,c = map(int,input().split())
q = a-b
ans = c-q

if ans < 0:
  ans = 0
  
print(ans)
import sys
import numpy as np

input = lambda: sys.stdin.readline().rstrip()

def solve(a):
    # a_max = max(a)
    # idx_max = a.index(a_max)
    idx_max = a.argmax()
    a_max = a[idx_max]
    return ((len(a) - 1 - idx_max) * a_max) - sum(a[idx_max + 1:]), idx_max

def solve2(a):
    idx_min = 0
    sum_a = 0
    len_a = len(a)
    for i in range(1, len_a):
        if a[0] < a[i]:
            return ((i - 1) * a[0]) - sum_a, i
        else:
            sum_a += a[i]
            if i == len_a - 1:
                return (i * a[0]) - sum_a, i + 1

def main():
    n = int(input())
    a = np.array(list(map(int, input().split())))
    ans = 0
    while(1):
        k, idx_max = solve2(a)
        ans += k
        if idx_max == len(a):
            break
        a = a[idx_max:]
    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip()

def main():
    n = int(input())
    a = list(map(int, input().split()))
    idx_start = 0
    sum_a = 0
    ans = 0
    cnt = 0
    len_a = len(a)

    for i in range(1, len_a):
        if a[idx_start] < a[i]:
            ans += (cnt * a[idx_start]) - sum_a
            idx_start = i
            sum_a = 0
            cnt = 0
        else:
            sum_a += a[i]
            cnt += 1
            if i == len_a - 1:
                ans += (cnt * a[idx_start]) - sum_a
    print(ans)
if __name__ == '__main__':
    main()
N=int(input())
S=[input() for _ in range(N)]
cnt=[0]*N
cnt2=[]
flag=0

for i in range(N):
    if S[i][0]=='M':
        cnt[0]+=1
    elif S[i][0]=='A':
        cnt[1]+=1
    elif S[i][0]=='R':
        cnt[2]+=1
    elif S[i][0]=='C':
        cnt[3]+=1
    elif S[i][0]=='H':
        cnt[4]+=1

for i in range(N):
    if cnt[i]!=0:
        cnt2.append(cnt[i])
        
import math
import itertools
ans=0

for v in itertools.combinations(cnt2, 3):
    ans+=v[0]*v[1]*v[2]

print(ans)

### FIXED CODE ###

N=int(input())
S=[input() for _ in range(N)]
cnt=[0]*N
cnt2=[]
flag=0

if len(S)>1:
    for i in range(N):
        if S[i][0]=='M':
            cnt[0]+=1
        elif S[i][0]=='A':
            cnt[1]+=1
        elif S[i][0]=='R':
            cnt[2]+=1
        elif S[i][0]=='C':
            cnt[3]+=1
        elif S[i][0]=='H':
            cnt[4]+=1

for i in range(N):
    if cnt[i]!=0:
        cnt2.append(cnt[i])
        
import math
import itertools
ans=0

for v in itertools.combinations(cnt2, 3):
    ans+=v[0]*v[1]*v[2]

print(ans)
n, q = map(int, input().split())

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

f = [0]*n
for i in range(q):
    p, x = map(int, input().split())
    p -= 1
    f[p] += x

def dfs(x, d, s):
    for y in v[x]:
        if d[y]:
            s += f[y]
            ans[y] = s
            d[y] = 0
            dfs(y, d, s)
            s -= f[y]

ans = [0]*n
d = [1]*n
d[0] = 0
ans[0] = f[0]
s = f[0]
dfs(0, d, s)
print(*ans)

### FIXED CODE ###

from collections import deque
n, q = map(int, input().split())
g = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)
count = [0]*n
for i in range(q):
    p, x = map(int, input().split())
    count[p-1] += x
q = deque([0])
d = [0]*n
while q:
    v = q.popleft()
    d[v] = 1
    for i in g[v]:
        if d[i]:
            continue
        count[i] += count[v]
        q.append(i)
print(*count)
N = int(input())

A = []
for i in range(N):
  A.append(int(input()))

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

def LCM(a,b):
  return int(a*b/GCD(a,b))

prev = A[0]
for i in range(1,N):
  lcm = LCM(prev, A[i])
  prev = lcm

print(prev)

### FIXED CODE ###

N = int(input())

A = []
for i in range(N):
  A.append(int(input()))

def GCD(a,b):
  if a < b:
    a, b = b, a
  while b > 0:
    a, b = b, a%b
  
  return a

def LCM(a,b):
  return a*b // GCD(a,b)

lcm = A[0]
for i in range(1,N):
  lcm = LCM(lcm, A[i])

print(lcm)
n,m = map(int,input().split())
if m!=0:
    ls = [int(input()) for _ in range(m)]

else:
    ls = []
    
dp = [0 for _ in range(n+1)]
dp[1] = 1
dp[2] = 2

for i in range(3,n+1):
    if i in ls :
        dp[i] = 0
    else:
        dp[i] = (dp[i-1]+dp[i-2])%(10**9+7)

print(dp[n]%(10**9+7))

### FIXED CODE ###

n,m = map(int,input().split())
ls = set()
for i in range(m):
    ls.add(int(input()))
dp = [0]*(n+1)
dp[0]=1
if 1 in ls:
    dp[1]= 0
else:
    dp[1]= 1
for i in range(2,n+1):
    if i in ls :
        continue
    dp[i] = dp[i-1]+dp[i-2]
print(dp[n]%(10**9+7))
class Node:
    def __init__(self, id, p, w):
        self.id = id
        self.w = w
        self.parent = p
        self.childs = []


N = int(input())
uvw = [list(map(int, input().split())) for _ in range(N - 1)]
nodes = [None for i in range(N + 1)]
nodes[1] = Node(1, None, 0)
for u, v, w in sorted(uvw):
    if nodes[u] != None:
        nodes[v] = Node(v, nodes[u], nodes[u].w + w)
        nodes[u].childs.append(nodes[v])
    elif nodes[v] != None:
        nodes[u] = Node(u, nodes[v], nodes[v].w + w)
        nodes[v].childs.append(nodes[u])

for node in nodes[1:]:
    print(node.w % 2)


### FIXED CODE ###

from collections import deque


class Node:
    def __init__(self, id, w):
        self.id = id
        self.w = w


N = int(input())
uvw = [list(map(int, input().split())) for _ in range(N - 1)]
pairs = [[] for _ in range(N + 1)]
for u, v, w in uvw:
    pairs[u].append([v, w])
    pairs[v].append([u, w])

nodes = {1: Node(1, 0)}
q = deque([nodes[1]])
while len(q) > 0:
    node = q.pop()
    for v, w in pairs[node.id]:
        if v not in nodes:
            nodes[v] = Node(v, node.w + w)
            q.append(nodes[v])

for i in range(1, N + 1):
    print(nodes[i].w % 2)
N,S,K=map(int,input().split())
ans=[S]*N
for i in range(K):
  ans[i]=S+1
print(*ans)


### FIXED CODE ###

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

ans = [0]*N
T = 10**9
if T == S:
    T = 10**9 - 1
for i in range(N):
    if i < K:
        ans[i] = S
    else:
        ans[i] = T
print(" ".join(map(str, ans)))
import itertools
import numpy as np


def check1(b: list):
    """
    FalseならOK
    Args:
        b:

    Returns:

    """
    for idx, num in enumerate(b[:-1]):
        return num in b[idx + 1:]


def check2(b: list):
    """
    FalseならOK
    Args:
        b:

    Returns:

    """
    return True in [is_prime(int(np.sum(np.array(i)))) for i in itertools.combinations(b, 5)]



def is_prime(q):
    q = abs(q)
    if q == 2: return True
    if q < 2 or q & 1 == 0: return False
    return pow(2, q - 1, q) == 1


if __name__ == '__main__':

    num_list = []
    size = int(input())
    while len(num_list) != size:
        x = np.random.randint(1000)
        if is_prime(x):
            num_list.append(x)
            if len(num_list) >= 2:
                if not check1(num_list):
                    if len(num_list) >= 5:
                        if not check2(num_list):
                            continue
                        else:
                            del num_list[len(num_list) - 1]
                else:
                    del num_list[len(num_list) - 1]

    print(' '.join(map(str, num_list)))


### FIXED CODE ###

import datetime
a, b = map(int, input().split(' '))
start = datetime.date(2018, 1, 1).toordinal()
end = datetime.date(2018, a, b).toordinal()

def checker(num):
    check_day = datetime.date(2018, num, num).toordinal()
    if start <= check_day <= end:
        return True
    else:
        return False

print(list(map(checker, [i for i in range (1, 13)])).count(True))
#conding utf-8
N = int(input())
A = input().split()
ans = 0
t = 0
for i in range(N):
  A[i] = int(A[i])
for i in range(N):
  if A[i] == 0:
    for j in range(N):
      if A[j]<0:
        A[j] = -A[j]
    ans = sum(A)
for j in range(N):
  if A[j]<0:
    t +=1
if t%2 == 0:
  for j in range(N):
    if A[j]<0:
      A[j] = -A[j]
      ans = sum(A)
else:
  for j in range(N):
    if A[j]<0:
      A[j] = -A[j]
  A[A.index(min(A))] = -A[A.index(min(A))]
  ans = sum(A)
      
print(ans)

### FIXED CODE ###

#conding utf-8
ABT =input().split()
a = int(ABT[0])
b = int(ABT[1])
t = int(ABT[2])

x = int(t/a)
print(x*b)
# -*- coding: utf-8 -*-
"""
Created on Mon May 18 14:53:59 2020

@author: 17664
"""

yomi = {2:'hon', 4:'hon', 5:'hon', 7:'hon', 9:'hon', 0:'pon', 1:'pon',
        6:'pon', 8:'pon', 3:'bon'}

print(yomi[input()[-1]])

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Mon May 18 14:53:59 2020

@author: 17664
"""

yomi = {2:'hon', 4:'hon', 5:'hon', 7:'hon', 9:'hon', 0:'pon', 1:'pon',
        6:'pon', 8:'pon', 3:'bon'}

print(yomi[int(input()[-1])])
N = int(input())
A = []
XY = []
honest_count = []

for i in range(N):
    a = int(input())
    A.append(a)
    inter = []
    for x in range(a):
        xy = list(map(int,input().split()))
        inter.append(xy)
    XY.append(inter)

for i in range(2**N):
    pt = [0]*N
    ck = 1
    for j in range(N):
        if (i>>j)&1:
            pt[N-j-1]=1
    for k in range(N):
        if pt[k] ==1:
            for l in range(A[k]):
                if XY[k][l][1] != pt[XY[k][l][0] -1]:
                    ck = 0
    if ck == 1:
        honest_count.append(sum(pt))
print(max(honest_count))


### FIXED CODE ###

A, B, C = map(int, input().split())
if A+B+C > 21:
    print('bust')
else:
    print('win')
s = input()
a = int(s[0] + s[1])
b = int(s[2] + s[3])

if a = 0 or b = 0:
    print('NA')
elif a>=13 and b >=13:
    print('NA')
elif a >= 13:
    print('YYMM')
elif b >= 13:
    print('MMYY')
else:
    print('AMBIGUOUS')

### FIXED CODE ###

s = input()
a = int(s[0] + s[1])
b = int(s[2] + s[3])

if  1 <= a <= 12 and 1 <= b <= 12:
    print('AMBIGUOUS')
elif 1<= b <= 12:
    print('YYMM')
elif 1<= a <= 12:
    print('MMYY')
else:
    print('NA')
N=int(input())
a=list(map(int,input().split()))
b=[0]*N
sum=0
for i in range(N):
  b[a[i]]+=1

for i in range(N):
  sum+=b[i]*(b[i]-1)//2
for i in range(N):
  print(sum-b[a[i]]+1)

### FIXED CODE ###

N=int(input())
a=list(map(int,input().split()))
b=[0]*N
sum=0
for i in range(N):
  b[a[i]-1]+=1

for i in range(N):
  sum+=b[i]*(b[i]-1)//2
for i in range(N):
  print(sum-b[a[i]-1]+1)
from collections import deque

h, w = map(int,input().split())
grid = [input() for i in range(h)]

#初期の黒の位置からの距離
dist = [[-1]*w for _ in range(h)] 

#黒の位置をキューに追加（複数スタート）
black_cells = deque()
for i in range(h):
    for j in range(w):
        if grid[i][j] == '#':
            black_cells.append((h,w))
            dist[i][j] = 0

def bfs(black_cells, dist):
    d = 0
    while black_cells:
        h,w = black_cells.popleft()
        d = dist[h][w]
        for dy, dx in ((1,0),(0,1),(-1,0),(0,-1)):
            new_h = h + dh
            new_w = w + dw
            if new_h <0 or h<=new_h or new_w <0 or w <= new_w:
                continue
            if dist[new_h][new_w] == -1: # セルがしろであるのと同意
                dist[new_h][new_w] = d+1
                
                black_cells.append((new_h,new_w))
    return d

d = bfs(black_cells, dist)
print(d)

### FIXED CODE ###

from collections import deque
 
def solve(h, w, a):
    used = [[True] * (w+2) for _ in range(h+2)]
    que = deque()
    for r in range(h):
        used[r+1][1:-1] = map(lambda _:_=="#", a[r])
        for c in range(w):
            if a[r][c] == "#":
                que.append((r+1, c+1, 0))
    neighbors = [(1,0), (0,1), (-1,0), (0,-1)]
    while que:
        r, c, k = que.popleft()
        for dr, dc in neighbors:
            nr, nc = r+dr, c+dc
            if not used[nr][nc]:
                que.append((nr, nc, k+1))
                used[nr][nc] = True
    return k
 
h, w = map(int, input().split())
a = [input() for _ in range(h)]
print(solve(h, w, a))
N = int(input())
A = [int(input()) for i in range(N)]
B = sorted(A,reverse=True)
max1 = B[0]
max2 = B[1]
print(max1,max2)
for i in A:
    if A[i] == max1:
        print(max2)
    else:
        print(max1)

### FIXED CODE ###

import numpy as np
N = int(input())
num_list = [int(input()) for i in range(N)]
a = max(num_list)
if num_list.count(a) > 1:
  for j in range(N):
    print(a)
else:
  b = np.sort(num_list)
  c = b[-2]
  for k in range(int(num_list.index(a))):
    print(a)
  print(c)
  for l in range(N-int(num_list.index(a))-1):
    print(a)
N,K = map(int, input().split())
Ds = list(map(int, input().split()))

able = []
for i in range(10):
    if i in Ds:continue
    able.append(i)
# print(able)

sN = str(N)
n = len(sN)
m = able[0] #最小


if int(sN[0]) > max(able):
    if m == 0:
        ans = str(able[1]) + str(able[0]) * n
    else:
        ans = str(able[0]) * (n+1)
    print(ans)
    exit()
prev = -1
flg = True #確定していない
ans = ""
for i,s in enumerate(sN):
    flg2 = False
    if flg:
        for j,a in enumerate(able):
            if int(s) < a:
                ans += str(a)
                flg = False
                flg2 = True
                break
            if int(s) == a:
                ans += str(a)
                flg = True
                flg2 = True
                break
        if not flg2:
            ans = ans[:-1]
            ans += str(able[prev+1]) + str(m)
            flg = True
    else:
        ans += str(m)    
    prev = j

print(ans)


### FIXED CODE ###

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

able = []
for i in range(10):
    if i in Ds:continue
    able.append(i)
# print(able)

sN = str(N)
n = len(sN)
m = able[0] #最小


if int(sN[0]) > max(able):
    if m == 0:
        ans = str(able[1]) + str(able[0]) * n
    else:
        ans = str(able[0]) * (n+1)
    print(ans)
    exit()
prev = -1
flg = True #確定していない
ans = ""
for i,s in enumerate(sN):
    flg2 = False
    if flg:
        for j,a in enumerate(able):
            if int(s) < a:
                ans += str(a)
                flg = False
                flg2 = True
                break
            if int(s) == a:
                ans += str(a)
                flg = True
                flg2 = True
                break
        if not flg2:
            if prev == len(able)-1:
                if m == 0:
                    ans = str(able[1]) + str(able[0]) * n
                else:
                    ans = str(able[0]) * (n+1)
                print(ans)
                exit() 
            ans = ans[:-1]
            ans += str(able[prev+1]) + str(m)
            flg = False
    else:
        ans += str(m)    
    prev = j
    # print(ans)

print(ans)
N,K = map(int,input().split())
P = list(map(int,input().split()))
T = [0]*N

for i in range(N):
    P[i] = (1 + P[i])/2

for i in range(1,N):
    P[i] += P[i-1]

for i in range(K,N):
    T[i] = P[i] - P[i-K]

T = T[K:]

if N == 1:
    print(P[i])
else:
    print(max(T))

### FIXED CODE ###

N,K = map(int,input().split())
P = list(map(int,input().split()))
T = [0]*N

for i in range(N):
    P[i] = (1 + P[i])/2

if N == K:
    print(sum(P))

else:
    for i in range(1,N):
        P[i] += P[i-1]

    for i in range(K,N):
        T[i] = P[i] - P[i-K]

    T = T[K:]

    print(max(T))
import sys
import resource
sys.setrecursionlimit(10000)
n,k=map(int,input().rstrip().split())
p=list(map(int,input().rstrip().split()))
c=list(map(int,input().rstrip().split()))
def find(start,now,up,max,sum,count,flag):
    if start==now:
        flag+=1
    if start==now and flag==2:
        return [max,sum,count]
    elif count==up:
        return [max,sum,count]
    else:
        count+=1
        sum+=c[p[now-1]-1]
        if max<=sum:
            max=sum
        return find(start,p[now-1],up,max,sum,count,flag)
kara=[-10000000000]
for i in range(1,n+1):
    m=find(i,i,n,c[p[i-1]-1],0,0,0)
    if m[2]>=k:
        m=find(i,i,k,c[p[i-1]-1],0,0,0)
        if m[0]>kara[0]:
            kara[0]=m[0]
        result=kara[0]
    elif m[1]<=0:
        if m[0]>kara[0]:
            kara[0]=m[0]
    else:
        w=k%m[2]
        if w==0:
            w=m[2]
        spe=find(i,i,w,c[p[i-1]-1],0,0,0)[0]
        if m[1]+spe>m[0] and m[1]*(k-w)//m[2]+spe>kara[0]:
            kara[0]=m[1]*(k-w)//m[2]+spe
        elif m[1]+spe<=m[0] and m[1]*((k-w)//m[2]-1)+m[0]>kara[0]:
            kara[0]=m[1]*((k-w)//m[2]-1)+m[0]
        result=kara[0]
print(result)

### FIXED CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))
c=list(map(int,input().split()))
now=-100000000000
for i in range(1,n+1):
    retu=[]
    sum1=0
    sum2=0
    sum3=0
    max1=-1000000000000
    max2=-1000000000000
    flag=0
    x=i
    while(flag==0):
        x=p[x-1]
        sum1+=c[x-1]
        retu.append(c[x-1])
        if x==i:
            flag=1
    if len(retu)>=k: #操作回数が周期未満
        for j in range(k):
            sum2+=retu[j]
            if sum2>max1:
                max1=sum2
        ans=max1
    elif sum1<=0: #周期和が負
        for j in range(len(retu)):
            sum3+=retu[j]
            if sum3>max2:
                max2=sum3
        ans=max2
    else:
        w=k%len(retu)
        
        if w==0:
            w=len(retu)
        for j in range(w):
            sum2+=retu[j]
            if sum2>max1:
                max1=sum2
        for j in range(len(retu)):
            sum3+=retu[j]
            if sum3>max2:
                max2=sum3
        if max1+sum1>max2:
            ans=sum1*(k-w)//len(retu)+max1
        else:
            ans=sum1*((k-w)//len(retu)-1)+max2
    now=max(now,ans)
print(now)