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

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

#最小公倍数でよいか？
#全てのjについてAiBiはAjで割り切れる
#計算時間は？
from fractions import gcd
mod =10**9+7
#これが邪魔だったらしい
"""
def lcd(x,y):
    g = gcd(x,y)
    return x*y//g
"""
ag = 1
for i in range(n):
    ag = ag*a[i]//gcd(ag,a[i])

ans = 0

for i in range(n):
    ans += ag//a[i]

ans %=mod

print(ans)


### FIXED CODE ###


from fractions import gcd
import random
n = int(input())
a = list(map(int, input().split( )))
random.shuffle(a)
#最小公倍数でよいか？
#全てのjについてAiBiはAjで割り切れる
#計算時間は？

mod =10**9+7
def lcd(x,y):
    g = gcd(x,y)
    return x*y//g

ag1 = 1
for i in range(n//2):
    ag1 = lcd(ag1,a[i])
ag2 = 1
for i in range(n//2,n):
    ag2 = lcd(ag2,a[i])

ag3 = lcd(ag1,ag2)

ans = 0

for i in range(n//2):
    ans += ag1//a[i]
ans*=ag3//ag1
ans %=mod
ans2 = 0
for i in range(n//2,n):
    ans2 += ag2//a[i]
ans2*= ag3//ag2
ans2%=mod 
ans += ans2
ans %=mod
print(ans)
### BUGGY CODE ###

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

    # 全探索するとN!なのでN=2000のときO(N^2000)となるので無理
    # DPで解く
    # dp[i][l] = 係数が大きい順にi個左右の端どちらにつめるか決めて、左をl回(右はn-l回)選んだときの指標最大値

    # 降順にAをソート+元のインデックスも保存しておく
    Awithidx = [[a,i] for i,a in enumerate(A)]
    sortedA = sorted(Awithidx, reverse=True)
    # DP
    dp = [[0]*(N+1) for _ in range(N+1)]
    for i in range(N):
        for l in range(i+1):
            r = i-l
            dp[i+1][l] = max(dp[i+1][l], dp[i][l]+sortedA[i][0]*abs((N-r-1)-sortedA[i][1]))
            dp[i+1][l+1] = max(dp[i+1][l+1], dp[i][l]+sortedA[i][0]*abs(l-sortedA[i][1]))
    print(max(dp[N]))

main()


### FIXED CODE ###

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

    # 全探索するとN!なのでN=2000のときO(N^2000)となるので無理
    # DPで解く
    # dp[i][l] = 係数が大きい順にi個左右の端どちらにつめるか決めて、左をl回(右はn-l回)選んだときの指標最大値

    # 降順にAをソート+元のインデックスも保存しておく
    Awithidx = [[a,i] for i,a in enumerate(A)]
    sortedA = sorted(Awithidx, reverse=True)
    # DP
    dp = [[0]*(N+1) for _ in range(N+1)]
    for i in range(N):
        a = sortedA[i][0]
        idx = sortedA[i][1]
        for l in range(i+1):
            r = i-l
            dp[i+1][l] = max(dp[i+1][l], dp[i][l]+a*abs((N-r-1)-idx))
            dp[i+1][l+1] = max(dp[i+1][l+1], dp[i][l]+a*abs(l-idx))
    print(max(dp[N]))

main()
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
for r in [A.count(i) for i in range(1, N + 1)]:
    print(r)


### FIXED CODE ###

import collections
N = int(input())
A = list(map(int, input().split()))
c = collections.Counter(A)
for i in range(1, N + 1):
    if c[i]:
        print(c[i])
    else:
        print(0)
### BUGGY CODE ###

N = int(input())
a=list(map(int,input().split()))
gos=[0]*(N-1)
for i in range(1,N):
    mae=sum(a[:i])
    ato=sum(a)-mae
    gos[i-1]=(abs(mae-ato))
print(min(gos))

### FIXED CODE ###

N = int(input())
a=list(map(int,input().split()))
ans=2020202020
s=sum(a)
mae=a[0]
for i in range(1,N):
    mae+=a[i]
    ato=s-mae
    if mae-ato>0:
        ans=min(abs(sum(a[:i])-sum(a[i:])),abs(sum(a[:i+1])-sum(a[i+1:])))
        break
    else:
        ans=min(ans,abs(mae-ato))
print(ans)
### BUGGY CODE ###

n,m,q = map(int,input().split())
lis = [list(map(int,input().split())) for i in range(m)]
li = [list(map(int,input().split())) for i in range(q)]
ans = [[0] * n for i in range(n)]
for a,b in lis:
  ans[a-1][b-1] += 1
for a,b in li:
  cou = 0
  for i in range(a-1,b):
    cou += sum(ans[i][i:b])
  print(cou)

### FIXED CODE ###

n,m,q = map(int,input().split())
lis = [[0 for i in range(n+1)] for j in range(n+1)]
for i in range(m):
    l,r = map(int,input().split())
    lis[l][r] += 1
for i in range(1,n+1):
    for j in range(1,n+1):
        lis[i][j] += lis[i-1][j] + lis[i][j-1] - lis[i-1][j-1]
for i in range(q):
    p,q = map(int,input().split())
    print(lis[q][q] - lis[q][p-1] - lis[p-1][q] + lis[p-1][p-1])
### BUGGY CODE ###

A,B,N=input().split()
A=int(A)
B=int(B)
N=int(N)

ans=0
for x in range(N+1):
    ans=max(ans,int(A*x/B)-(A*int(x/B)))

print(ans)

### FIXED CODE ###

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

if N<B:
    print(int(A*N/B))
else:
    print(int(A*(B-1)/B))
### BUGGY CODE ###

import bisect

def main():
    s = input()
    k = int(input())
    n = len(s)
    dp = []
    for l in range(n):
        for r in range(l + 1, n + 1):
            t = s[l:r]
            i = bisect.bisect_right(dp, t)
            if i>0:
                if t == dp[i-1]: continue
            if len(dp) < k:
                bisect.insort(dp, t)
            elif t < dp[-1]:
                dp.pop()
                bisect.insort(dp, t)
    print(dp[-1])

main()


### FIXED CODE ###

import bisect

def main():
    s = input()
    k = int(input())
    n = len(s)
    dp = []
    for l in range(n):
        for r in range(l + 1, min(n + 1, l + 6)):
            t = s[l:r]
            i = bisect.bisect_right(dp, t)
            if i > 0:
                if t == dp[i - 1]: continue
            if len(dp) < k:
                bisect.insort(dp, t)
            elif t < dp[-1]:
                dp.pop()
                bisect.insort(dp, t)
    print(dp[-1])

main()
### BUGGY CODE ###


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

a = []
f = S[0]
l = 0
for i in range(1, N+1):
    #print(S[i])
    if f != S[i]:
        #a.append([l, i-1, int(f)])
        #a.append([i-l, int(f)])
        a.append(i-l)
        l = i
        f = S[i]
        
#print(a)

if S[0] == '0':
    a = [0] + a

MAX = 0
for i in range(len(a)):
    if i % 2 == 0:
        #print(a[i:i+2*K+1])
        #print(sum(a[i:i+2*K+1]))
        MAX = max(MAX, sum(a[i:i+2*K+1]))
        if len(a) < i+1+2*K+1:
            break

print(MAX)

### FIXED CODE ###


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

a = []
f = S[0]
l = 0
for i in range(1, N+1):
    if f != S[i]:
        a.append(i-l)
        l = i
        f = S[i]
        

if S[0] == '0':
    a = [0] + a

SUM = sum(a[0:0+2*K+1])

MAX = max(0, SUM)
for i in range(2, len(a)):
    if i % 2 == 0:
        try:
            SUM = SUM - (a[i-2]+a[i-1]) + (a[i+2*K-1]+a[i+2*K])
        except:
            try:
                SUM = SUM - (a[i-2]+a[i-1]) + (a[i+2*K-1])
            except:
                break
        
        MAX = max(MAX, SUM)


print(MAX)
### BUGGY CODE ###

N,K = list(map(int,input().split()))
print(N)
print(K)
per = 0
def f(x,y):
    count = 0
    while (x <= y):
        x = 2*x
        count += 1
    return count

for i in range(N):
    b = int(f(i,K))
    per += (1/N)((1/2)**b)
    print(per)
print(per)

### FIXED CODE ###

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

def f(x,y):
    count = 0
    while (x < y):
        x = 2*x
        count += 1
    return count

for i in range(N):
    b = int(f(i+1,K))
    per += (1/N)*((1/2)**b)
print(per)
### BUGGY CODE ###

cell=list(map(int,input().split()))
n=cell[0]
pren=n
while 2>0:
    n=abs(n-cell[1])
    if n >pren:
        break
    else:
        pren=n


print(pren)

### FIXED CODE ###

import math
def main(cell):

    n=cell[0]
    k=cell[1]
    if k==0:
        return n
    else:

        risk=math.floor(n/k)
        if risk ==0:
            n=n
        else:
            n=abs(n-k*risk)
        pren=n
        while 2>0:
            n=abs(n-k)
            if n >pren:
                break
            else:
                pren=n

        return pren
    


cell=list(map(int,input().split()))
pren=main(cell)
print(pren)
### BUGGY CODE ###

import math
N = int(input())
A = [int(_) for _ in input().split()]


def gcd(x, y):
    if x < y:
        return gcd(y, x)
    elif y == 0:
        return x
    else:
        return gcd(y, x % y)


class SegmentTree():
    def m(self, v1, v2):  # ***monoid***
        return gcd(v1, v2)

    def __init__(self, array):
        m = self.m
        e = self.e = 0  # ***identity element***
        size = self.size = 10**6  # ***limit for array size***
        n = self.n = len(array)
        dat = self.dat = [e] * n + array + [e] * (2 * size - 2 * n)
        for i in range(n - 1, 0, -1):  # build
            dat[i] = m(dat[i << 1], dat[i << 1 | 1])

    def modify(self, p, v):  # set value at position p (0-indexed)
        m, n, dat = self.m, self.n, self.dat
        p += n
        dat[p] = v
        while p > 1:
            dat[p >> 1] = m(dat[p], dat[p ^ 1])
            p >>= 1

    def query(self, l, r):  # result on interval [l, r) (0-indexed)
        m, e, n, dat = self.m, self.e, self.n, self.dat
        res = e
        l += n
        r += n
        while l < r:
            if l & 1:
                res = m(res, dat[l])
                l += 1
            if r & 1:
                r -= 1
                res = m(res, dat[r])
            l >>= 1
            r >>= 1
        return res


ST = SegmentTree(A)
ans = 0
for i, a in enumerate(A):
    ST.modify(i, ST.e)
    ans = max(ans, ST.query(0, N))
    ST.modify(i, a)
print(ans)


### FIXED CODE ###

import itertools
N = int(input())
A = [int(_) for _ in input().split()]
gcd = lambda x, y: gcd(y, x % y) if x % y else y
L = list(itertools.accumulate(A, func=gcd))
R = list(itertools.accumulate(A[::-1], func=gcd))[::-1]
ans = max(R[1], L[-2])
for i in range(1, N - 1):
    ans = max(ans, gcd(L[i - 1], R[i + 1]))
print(ans)
# https://img.atcoder.jp/abc125/editorial.pdf
### BUGGY CODE ###

# coding: utf-8

N = int(raw_input())
CSF = [map(int, raw_input().split()) for _ in range(N-1)]

for i in range(N-1):
    ans = CSF[i][0] + CSF[i][1]

    for j in range(i+1, N-1):
        t = CSF[j][1]
        while t < ans:
            t += CSF[j][2]

        ans = t+CSF[j][0]

    print ans

print 0

### FIXED CODE ###

# coding: utf-8
import math

N = int(raw_input())
CSF = [map(float, raw_input().split()) for _ in range(N-1)]

for i in range(N-1):
    ans = CSF[i][0] + CSF[i][1]
    for j in range(i+1, N-1):
        s, t, u = CSF[j][0], CSF[j][1], CSF[j][2]
        if t < ans:
            n = int(math.ceil((ans - t) / u))
            ans = int(s + t + u * n)
        else:
            ans = s + t

    print int(ans)

print 0
### BUGGY CODE ###

import math
from functools import reduce
import itertools



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


a = int(input())
ans = 0
nums = []
for i in range(1, a+1):
    nums.append(i)

for balls in itertools.product(nums, repeat=3):
    ans += int(gcd(balls[0], balls[1], balls[2]))

print(ans)


### FIXED CODE ###

from math import gcd

a = int(input())

ans = 0
for i in range(1, a+1):
    for k in range(1, a+1):
        for j in range(1, a+1):
            ans += gcd(gcd(i,k),j)


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

import sys
input = sys.stdin.readline

def main():
    N, M = map(int, input().split())
    jobs = {}
    for _ in range(N):
        A, B = map(int, input().split())
        if A > M:
            continue
        if A in jobs.keys():
            jobs[A] = jobs[A] + [B]
        else:
            jobs[A] = [B]

    profit = 0
    days = jobs.keys()
    potential_jobs = []

    # M-1日後から今日まで遡る
    for elappsed_day in range(1, M+1):
        if elappsed_day in days:
            potential_jobs += jobs[elappsed_day]
        if len(potential_jobs) > 0:
            profit += potential_jobs.pop(potential_jobs.index(max(potential_jobs)))
            
    print(profit)

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
from heapq import heappush, heappop
input = sys.stdin.readline

def main():
    N, M = map(int, input().split())
    jobs = {}
    for _ in range(N):
        A, B = map(int, input().split())
        if A > M:
            continue
        if A in jobs.keys():
            jobs[A] += [-B]
        else:
            jobs[A] = [-B]

    profit = 0
    days = jobs.keys()
    potential_jobs = []
    
    # M-1日後から今日まで遡る
    for elappsed_day in range(1, M+1):
        if elappsed_day in days:
            for job in jobs[elappsed_day]:
                heappush(potential_jobs, job)
        if len(potential_jobs) > 0:
            profit += heappop(potential_jobs)
            
    print(-profit)

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

n = int(input())
s = input()
counter = 0

for i in range(0, n-2):
  for j in range(i+1, n-1):
    if s[i] == s[j]:
      continue
    for k in range(j+1, n):
      if s[j] == s[k] or s[k] == s[i]:
        continue
      if j-i != k-j:
        counter += 1
    
print(counter)


### FIXED CODE ###

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

r = s.count('R')
g = s.count('G')
b = s.count('B')
counter = 0

for i in range(n-2):
  for j in range(i+1, n-1):
    k = 2*j - i
    if k > n-1:
      break
    if s[i] != s[j] and s[j] != s[k] and s[k] != s[i]:
      counter += 1
      
print(r*g*b - counter)
### BUGGY CODE ###

s = input()
t = input()

table = ['' for j in range(len(t) + 1)]
table_pre = ['' for j in range(len(t) + 1)]

for i, si in enumerate(s):
    for j, tj in enumerate(t):
        if si == tj:
            table[j + 1] = table_pre[j] + si
        else:
            x = table[j]
            y = table_pre[j + 1]
            table[j + 1] = x if len(x) > len(y) else y
    table, table_pre = table_pre, table
print(table_pre[-1])


### FIXED CODE ###

s = input()
t = input()

table = [[0 for j in range(len(t) + 1)] for i in range(len(s) + 1)]

for i, si in enumerate(s):
    table_pre = table[i]
    table_cur = table[i + 1]
    for j, tj in enumerate(t):
        if si == tj:
            table_cur[j + 1] = table_pre[j] + 1
        else:
            table_cur[j + 1] = max(table_cur[j], table_pre[j + 1])

ls, lt = len(s), len(t)
ans = ''
while ls and lt:
    if table[ls][lt] == table[ls][lt - 1]:
        lt -= 1
    elif table[ls][lt] == table[ls - 1][lt]:
        ls -= 1
    else:
        ans = s[ls - 1] + ans
        ls -= 1
        lt -= 1
print(ans)
### BUGGY CODE ###

h,w,m=map(int,input().split())
table=[]
H=[0]*h
W=[0]*w
li_h=[]
li_w=[]

for i in range(m):
    h1,w1=list(map(int,input().split()))
    table.append((h1-1,w1-1))
    H[h1-1]+=1
    W[w1-1]+=1

h_flag=0
w_flag=0



Hh=[i for i, x in enumerate(H) if x == max(H)]
Ww=[i for i, x in enumerate(W) if x == max(W)]

cnt=0

for (h, w) in table:
    if H[h] == max(H) and W[w] == max(W):
        cnt += 1

if cnt<len(Hh)*len(Ww):
    print(max(H)+max(W))
else:
    print(max(H)+max(W)-1)



### FIXED CODE ###

h,w,m=map(int,input().split())
table=[]
H=[0]*h
W=[0]*w
li_h=[]
li_w=[]

for i in range(m):
    h1,w1=list(map(int,input().split()))
    table.append((h1-1,w1-1))
    H[h1-1]+=1
    W[w1-1]+=1

h_flag=0
w_flag=0

Hm=max(H)
Wm=max(W)

Hh=[i for i, x in enumerate(H) if x == Hm]
Ww=[i for i, x in enumerate(W) if x == Wm]

cnt=0

for (h, w) in table:
    if H[h] == Hm and W[w] ==  Wm:
        cnt += 1

if cnt<len(Hh)*len(Ww):
    print(Hm+Wm)
else:
    print(Hm+Wm-1)
### BUGGY CODE ###

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

import numpy as np
import math
A = np.array(A)
b = np.zeros(N)
for i in reversed(range(1, N + 1)):
    a = A[i - 1]
    idxs = np.arange(1, math.floor(N / i) + 1) * i
    s = np.sum(b[idxs - 1])
    if (s % 2 == 0 and a == 1) or (s % 2 == 1 and a == 0):
        b[i - 1] = 1
    # print(i, idxs, s, b)


if len(b) == 0:
    print(0)
else:
    counter = 0
    res = ''
    for i in range(len(b)):
        if b[i] == 1:
            if res == '':
                res += str(i + 1)
            else:
                res += ' ' + str(i + 1)
            counter += 1
    print(counter)
    print(res)


### FIXED CODE ###

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

ans = [0] * n

for i in reversed(range(1, n+1)):
    count = 0
    for j in range(2 * i, n + 1, i):
        count += ans[j-1]

    if count % 2 != a[i-1]:
        ans[i-1] = 1

print(sum(ans))
for i in range(n):
    if ans[i] == 1:
        print(i + 1)
### BUGGY CODE ###

n=int(input())
S=[input() for _ in range(n)]
S_set = set(S)
setl = sorted(S_set)
cnt={}

for s in S_set:
    cnt[s] = S.count(s)

m=max(cnt.values())
L=[]

for a in setl:
    if cnt[a] == m:
        print(a)


### FIXED CODE ###

n=int(input())

cnt={}
ans=[]

for i in range(n):
    s=input()
    if s in cnt.keys():
        cnt[s] += 1
    else:
        cnt[s] = 1

m=max(cnt.values())
key = sorted(cnt.keys())

for a in key:
    if cnt[a] == m:
        print(a)
### BUGGY CODE ###

N = int(input())
mod = 10**9+7

for i in range(1, N):
    N *= i % mod

print(N % mod)

### FIXED CODE ###

N = int(input())
mod = 10**9+7

for i in range(1, N):
    N *= i
    N %= mod

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

from bisect import bisect_right
import sys
input = sys.stdin.buffer.readline

class SegmentTree:
    """
    0-indexed
    query : [L, R)
    """
    def __init__(self, size, initValue, cmpFunc):
        self.size = 1 << (size.bit_length())  # 完全二分木にする
        self.data = [initValue] * (2 * self.size - 1)
        self.initValue = initValue
        self.cmpFunc = cmpFunc

    def build(self, rawData):
        self.data[self.size - 1: self.size - 1 + len(rawData)] = rawData
        for i in range(self.size - 1)[:: -1]:
            self.data[i] = self.cmpFunc(self.data[2 * i + 1], self.data[2 * i + 2])

    def update(self, index, value):
        index += self.size - 1
        self.data[index] = value
        while index >= 0:
            index = (index - 1) // 2
            self.data[index] = self.cmpFunc(self.data[2 * index + 1], self.data[2 * index + 2])

    def query(self, left, right):
        L = left + self.size
        R = right + self.size
        ret = self.initValue
        while L < R:
            if R & 1:
                R -= 1
                ret = self.cmpFunc(ret, self.data[R - 1])
            if L & 1:
                ret = self.cmpFunc(ret, self.data[L - 1])
                L += 1
            L >>= 1
            R >>= 1
        return ret

N, D, A = map(int, input().split())
XH = [tuple(map(int, input().split())) for _ in range(N)]
XH.sort()
X = [x for x, _ in XH]

tree = SegmentTree(N + 1, 0, lambda a, b: a + b)

ans = 0
for i, (x, h) in enumerate(XH):
    cnt = tree.query(0, i + 1)
    h -= cnt * A

    if h <= 0:
        continue

    ness = -(-h // A)
    ans += ness
    tree.update(i, tree.query(i, i + 1) + ness)
    j = bisect_right(X, x + 2 * D)
    tree.update(j, tree.query(j, j + 1) - ness)

print(ans)

### FIXED CODE ###

from bisect import bisect_right

N, D, A = map(int, input().split())
XH = [tuple(map(int, input().split())) for _ in range(N)]
XH.sort()

X = [x for x, _ in XH]

ans = 0
ims = [0] * (N + 1)
cnt = 0

for now, (x, h) in enumerate(XH):
    cnt += ims[now]
    if cnt * A >= h:
        continue
    ness = -(-(h - cnt * A) // A)
    cnt += ness

    i = bisect_right(X, x + D * 2)
    ims[now] += ness
    ims[i] -= ness
    ans += ness

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

from copy import copy, deepcopy # pythonのみ．copyは1次元，deepcopyは多次元．
# from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
# from functools import reduce
# from heapq import heapify, heappop, heappush
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import statistics # Pythonのみ
# import string
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    n,k=map(int,input().split())
    A=list(map(int,input().split()))+[0]

    m=n
    log = 0
    while m >= 2:
        m = m // 2
        log += 1
    from itertools import accumulate

    for i in range(min(k,n*2*log+1)):
        B=[0]*(n+1)

        for j in range(n):
            val=A[j]
            #if val==0: continue
            B[max(0,j-val)]+=1
            B[min(n,j+val+1)]-=1
        A=list([0]+list(accumulate(B)))[1:]
    
    

    print(*A[:-1])    
    
    
resolve()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

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

    for i in range(k):
        B=[0]*(n+1)

        for j in range(n):
            val=A[j]
            B[max(0,j-val)]+=1
            B[min(n,j+val+1)]-=1
        
        for k in range(n):
            B[k+1]+=B[k]
        A=B[:-1]

        if A==[n]*(n):
            break
    
    

    print(*A)    
    
resolve()
### BUGGY CODE ###

from functools import reduce

n, m = map(int, input().split())
l = [[] for i in range(n+1)]

for i in range(m):
  p, y = map(int, input().split())
  l[p].append([p, y, i])

for i in range(1, len(l)):

  temp = sorted(l[i], key=lambda x: x[1])

  for j in range(len(temp)):
    temp[j] = [str(temp[j][0]).zfill(6), str(j+1).zfill(6), temp[j][2]]
  
  l[i] = temp

ans = reduce(lambda x, y: x + y, l[1:])

for item in sorted(ans, key=lambda x: x[2]):
  print(item[0] + item[1])

### FIXED CODE ###

n, m = map(int, input().split())
l = [[] for i in range(n+1)]

for i in range(m):
  p, y = map(int, input().split())
  l[p].append([p, y, i])

for i in range(1, len(l)):

  temp = sorted(l[i], key=lambda x: x[1])

  for j in range(len(temp)):
    temp[j] = [str(temp[j][0]).zfill(6), str(j+1).zfill(6), temp[j][2]]
  
  l[i] = temp

ans = []

for item in l:
  ans += item

for item in sorted(ans, key=lambda x: x[2]):
  print(item[0] + item[1])
### BUGGY CODE ###

n, q = map(int,input().split())
S = input()
lr = [[] for i in range(q)]
for i in range(q):
  lr[i] =list(map(int,input().split()))

ans = []
for i,j in lr:
  ans.append(S[i-1:j].count('AC'))
  
for i in ans:
  print(i)
  
  
  

### FIXED CODE ###

n, q = map(int,input().split())
S = list(input())
lr = [[] for i in range(q)]
for i in range(q):
  lr[i] =list(map(int,input().split()))

Sl = [0 for i in range(n+1)]
for i in range(1,n):
  if (S[i-1] == "A")&(S[i]=="C"):
    Sl[i] = Sl[i-1]+1
  else:
    Sl[i] = Sl[i-1]
Sl[n] = Sl[n-1]

ans = []
for i,j in lr:
  ans.append(Sl[j-1]-Sl[i-1])
  
for i in ans:
  print(i)
### BUGGY CODE ###

S = str(input())
T = str(input())
def check(S):
  done = []
  for i in range(len(S)):
    if i not in done:
      indexes = [j for j, x in enumerate(S) if x == S[i]]
      done.append(indexes)
  return done
if check(S) == check(T):
  print("Yes")
else:
  print("No")

### FIXED CODE ###

S = list(str(input()))
T = list(str(input()))
check = 1
bij1 = {}
bij2 = {}
for i in range(len(S)):
  if S[i] in bij1 and bij1[S[i]] != T[i]:
    check = 0
    break
  elif T[i] in bij2 and bij2[T[i]] != S[i]:
    check = 0
    break
  elif S[i] not in bij1 and T[i] not in bij2:
    bij1[S[i]] = T[i]
    bij2[T[i]] = S[i]
    
if check:
  print("Yes")
else:
  print("No")
### BUGGY CODE ###

n,k = map(int,input().split())
score = [0 for i in range(n)]
P = list(map(int,input().split()))
C = list(map(int,input().split()))
ans = -float('inf')
for i in range(n):
    start = i
    cur = i
    i_s_score = 0
    i_s_score_max = C[P[cur]-1]
    move_num = 0
    for j in range(n):
        cur = P[cur]-1
        i_s_score += C[cur]
        i_s_score_max = max(i_s_score, i_s_score_max)
        move_num += 1
        if cur == start:
            break
    if i_s_score <= 0:
        ans = max(ans, i_s_score_max)
    else:
        temp = i_s_score*(k//move_num)
        rest = k%move_num
        ans = max(ans, temp)
        i_s_score = temp
        for j in range(rest):
            cur = P[cur]-1
            i_s_score += C[cur]
            ans = max(ans, i_s_score)
print(ans)


### FIXED CODE ###

n,k = map(int,input().split())
P = list(map(int,input().split()))
C = list(map(int,input().split()))
ans = -10**100
for i in range(n):
    start = i
    cur = i
    i_s_score = 0
    i_s_score_max = C[P[cur]-1]
    move_num = 0
    for j in range(n):
        cur = P[cur]-1
        i_s_score += C[cur]
        i_s_score_max = max(i_s_score, i_s_score_max)
        move_num += 1
        if cur == start:
            break
    if i_s_score <= 0:
        ans = max(ans, i_s_score_max)
    else:
        temp = i_s_score*(k//move_num)
        if (k//move_num >= 1):
            temp_dash = i_s_score*(k//move_num-1)+i_s_score_max
            ans = max(ans, temp_dash)
        rest = k%move_num
        ans = max(ans, temp)
        i_s_score = temp
        for j in range(rest):
            cur = P[cur]-1
            i_s_score += C[cur]
            ans = max(ans, i_s_score)
print(ans)