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

def main():
    import sys
    input = sys.stdin.readline

    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

    N, R, L = map(int, input().split())
    P = list(map(int, input().split()))

    val2idx = [0] * (N+1)
    for i, p in enumerate(P):
        val2idx[p] = i + 1
    inf = 10**14
    dp = [[inf] * (N+1) for _ in range(N+1)]
    dp[0][0] = 0
    bit = Bit(N+1)
    for p in range(1, N+1):
        i = val2idx[p]
        for j in range(N+1):
            if i > j:
                dp[p][j] = min(dp[p][j], dp[p-1][j] + L)
                dp[p][i] = min(dp[p][i], dp[p-1][j] + R * (i - j - 1 - (bit.sum(i) - bit.sum(j))))
            else:
                dp[p][j] = min(dp[p][j], dp[p - 1][j])
        bit.add(i, 1)
    print(min(dp[-1]))
    #[print(i, dp[i]) for i in range(N+1)]


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline

    N, R, L = map(int, input().split())
    P = list(map(int, input().split()))

    val2idx = [0] * (N+1)
    for i, p in enumerate(P):
        val2idx[p] = i + 1
    bigger = [[0] * (N+1) for _ in range(N+1)]
    for p in range(1, N+1):
        for j in range(N):
            if P[j] > p:
                bigger[p][j+1] = bigger[p][j] + 1
            else:
                bigger[p][j + 1] = bigger[p][j]
    #print(bigger)
    inf = 10**14
    dp = [[inf] * (N+1) for _ in range(N+1)]
    dp[0][0] = 0

    for p in range(1, N+1):
        i = val2idx[p]
        for j in range(N+1):
            if i > j:
                dp[p][j] = min(dp[p][j], dp[p-1][j] + L)
                dp[p][i] = min(dp[p][i], dp[p-1][j] + R * (bigger[p][i] - bigger[p][j]))
            else:
                dp[p][j] = min(dp[p][j], dp[p - 1][j])
    print(min(dp[-1]))
    #[print(i, dp[i]) for i in range(N+1)]


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


import math
import bisect


prime = [2,3,5,7,11,13,17,19]
for i in range(prime[-1]+2,100000,2):

    x = int( math.sqrt(i) )
    x += 1 if x%2 == 0 else 0

    found = False
    for p in prime:
        if x < p:
            break;

        if i % p == 0:
            found = True
                
    if not found:
        prime.append(i)

# print(prime)


q = int(input())

for _ in range(q):

    l, r = map(int,input().split())
 #   l += 1 if l%2 == 0 else 0

#    print((l,r))

    ans = 0
    for i in range( l , r+1, 2):

        xi = bisect.bisect_right(prime, i)
        #print(xi)

        if prime[xi-1] != i:
            continue

        i2 = (i+1)//2
        yi = bisect.bisect_right(prime, i2, hi = xi)
        if prime[yi-1] != i2:
            continue

        ans += 1

    print(ans)

### FIXED CODE ###


import math
import bisect


prime = [2]

tab = [False]*100001
tab[2] = True
for i in range(3,100000+1,2):

    x = int( math.sqrt(i) )
    x += 1 if x%2 == 0 else 0

    found = False
    for p in prime:
        if x < p:
            break;

        if i % p == 0:
            found = True
            break
                
    if not found:
        prime.append(i)
        tab[i] = True

#print(prime[0:10])
#print(tab[0:10])
q = int(input())

ac = [0] * len(tab)

for i in range(1,len(ac)):
    ac[i] = ac[i-1] + (1 if tab[i] and tab[(i+1)//2] else 0)

#print(ac)
for _ in range(q):

    l, r = map(int,input().split())
    
    ans = ac[r] - ac[l-1]

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

import sys

N = int(input())
A = list(map(int, input().split()))
ans = 1
for a in A:
    if a == 0:
        print(0)
        sys.exit()
    ans *= a

if ans > 10**18:
    print(-1)
else:
    print(ans)


### FIXED CODE ###

import sys

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

if 0 in A:
    print(0)
    sys.exit();

ans = 1
for a in sorted(A, reverse=True):
    ans *= a
    if ans > 10**18:
        print(-1)
        break
else:
    print(ans)
### BUGGY CODE ###

def exhaustive_search(arr, num):
    for bit in range(1 << len(arr)):
        total = 0
        for i in range(len(arr)):
            if 1 & (bit >> i) == 1:
                total += arr[i]
            if total == num:
                return "yes"
    return "no"

input()
A = [int(x) for x in input().split()]
input()
ms = [int(x) for x in input().split()]
for m in ms:
    print(exhaustive_search(A, m))

### FIXED CODE ###

input()
A = [int(x) for x in input().split()]
input()
ms = [int(x) for x in input().split()]

enable_create = [False]*2000
for bit in range(1 << len(A)):
    n = 0
    for i in range(len(A)):
        if 1 & (bit >> i) == 1:
            n += A[i]
    enable_create[n] = True

for m in ms:
    print("yes" if enable_create[m] else "no")
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)
readline = sys.stdin.readline
from collections import deque


def solve_beam():
    D = int(readline())
    C = list(map(int, readline().split()))
    S = [list(map(int, readline().split())) for i in range(D)]
    N = 26

    lasts = [0] * N

    ans = [None] * D

    W, DEPTH = 3, 7

    def rec(day, rem):
        if rem == 0 or day > D:
            return 0, 0
        gains = sorted(((S[day - 1][t] + (day - lasts[t]) * C[t], t) for t in range(N)), reverse=True)
        max_gain = -1e10
        max_gain_t = 0
        for i in range(W):
            gain, t = gains[i]
            _t = lasts[t]
            lasts[t] = day
            f_gain, _ = rec(day + 1, rem - 1)
            lasts[t] = _t
            gain += f_gain
            if gain > max_gain:
                max_gain = gain
                max_gain_t = t

        return max_gain, max_gain_t

    for day in range(D):
        _, t = rec(day, DEPTH)
        lasts[t] = day
        ans[day - 1] = t
    
    for a in ans:
        print(a + 1)


solve_beam()

### FIXED CODE ###

import sys
readline = sys.stdin.readline

def solve_greedy():
    D = int(readline())
    C = list(map(int, readline().split()))
    S = [list(map(int, readline().split())) for i in range(D)]
    N = 26

    lasts = [0] * N

    ans = [None] * D

    for day in range(1, D + 1):
        m, mt = -1e10, 0
        for t in range(N):
            a = S[day - 1][t] + (day - lasts[t]) * C[t]
            if a > m:
                mt = t
                m = a
        
        lasts[mt] = day

        neg = sum((day - lasts[t]) * C[t] for t in range(N))
        pos = S[day - 1][t]

        ans[day - 1] = mt
    
    for a in ans:
        print(a + 1)



solve_greedy()
### BUGGY CODE ###

import math
import numpy as np


def sum_gcd(k: int) -> int:
    cache = np.zeros((k + 1, k + 1, k + 1), dtype=int)

    def cached_gcd(a: int, b: int, c: int) -> int:
        k0, k1, k2 = sorted([a, b, c])

        result = cache[k0][k1][k2]
        if result > 0:
            return result
        else:
            result = math.gcd(math.gcd(k0, k1), k2)
            cache[k0][k1][k2] = result
            return result

    answer = 0
    for h in range(1, k + 1):
        for i in range(1, k + 1):
            for j in range(1, k + 1):
                answer += cached_gcd(h, i, j)

    return answer


def main():
    k = int(input().rstrip())
    print(sum_gcd(k))


if __name__ == '__main__':
    main()


### FIXED CODE ###

import math
from typing import List, NoReturn


def sum_gcd(k: int) -> int:
    cache: List[List[List[int]]] = [[[0] * (k + 1) for i in range(k + 1)] for j in range(k + 1)]

    def cached_gcd(a: int, b: int, c: int) -> int:
        k0: int
        k1: int
        k2: int
        k0, k1, k2 = sorted([a, b, c])

        result: int = cache[k0][k1][k2]
        if result > 0:
            return result
        else:
            result = math.gcd(math.gcd(k0, k1), k2)
            cache[k0][k1][k2] = result
            return result

    answer: int = 0
    for h in range(1, k + 1):
        for i in range(1, k + 1):
            for j in range(1, k + 1):
                answer += cached_gcd(h, i, j)

    return answer


def main() -> NoReturn:
    k: int = int(input().rstrip())
    print(sum_gcd(k))


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

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

a=[int(input()) for i in range(q)]
points=[k for i in range(n)]
for j in a:
    points[j-1]=points[j-1]+1
    for k in range(n):
        points[k]-=1
        
for ans in points:
    if ans>0:
        print('Yes')
    else:
        print('No')
    

### FIXED CODE ###

import collections
n,k,q=map(int,input().split())
a=[int(input()) for i in range(q)]
points=['No' for i in range(n)]
c = collections.Counter(a)

zone=k-q


for v in c:
    
    if zone+c.get(v)>=1:
        points[v-1]='Yes'
if zone>=1:
    for h in points:
        print('Yes')
else:
    for h in points:
        print(h)
### BUGGY CODE ###

n = int(input())
s = input()
ans = 0
for i in range(10):
  for j in range(10):
    for k in range(10):
      lst = [i,j,k]
      flag = 0
      for l in range(n):
        if int(s[l]) == lst[flag]:
          flag += 1
          if flag == 3:
            ans += 1
            break
print(ans)

### FIXED CODE ###

n = int(input())
s = input()
ans = 0
for i in range(1000):
  i = str(i).zfill(3)
  flag = 0
  for l in range(n):
    if s[l] == i[flag]:
      flag += 1
      if flag == 3:
        ans += 1
        break
print(ans)
### BUGGY CODE ###

import numpy as np
n = int(input())
a = list(map(int, input().split()))
A = []
for i in range(n):
    c = [0] * n
    if i != n-1:
        c[i], c[i+1] = 1/2, 1/2
    else:
        c[0], c[n-1] = 1/2, 1/2
    A.append(c)

A = np.array(A)
b = np.array(a)
ans = list(np.linalg.solve(A, b))
ans = map(int, ans)
ans = map(str, ans)
print(" ".join(ans))

### FIXED CODE ###

n = int(input())
a = [int(x) for x in input().split()]
s = sum(a)
ans = [0] * n
even_a = 0
for i in a[1::2]:
    even_a += i
ans[0] = s - 2 * even_a
for i in range(1, n):
    ans[i] = 2 * a[i-1] - ans[i-1]
print(" ".join(map(str, ans)))
### BUGGY CODE ###

a,aa=map(int,input().split())
b=list(map(int,input().split()))
c=[0 for i in range(a)]
for i in range(1,a):
  for j in range(1,aa+1):
    if i-j<0:
      break
    elif j==1:
      c[i]=c[i-j]+abs(b[i]-b[i-j])
    elif c[i]<=c[i-j]:
      continue
    else:
      c[i]=min(c[i-j]+abs(b[i]-b[i-j]),c[i])
  
print(c[-1])

### FIXED CODE ###

def solve():
  a,aa=map(int,input().split())
  b=list(map(int,input().split()))
  c=[0]*a
  c[0]=0
  for i in range(1,a):
    c[i] = min(c[j] + abs(b[i] - b[j]) for j in range(max(0,i-aa),i))
  print(c[-1])
  
solve()
### BUGGY CODE ###

from queue import Queue
import itertools
import numpy as np

R, C = map(int, input().split())
sy, sx = 1, 1
gy, gx = R, C

field = [["#"] * (C + 2)] + \
        [list("#" + input() + "#") for i in range(R)] + \
        [["#"] * (C + 2)]
dxy = [(0,1), (0,-1), (1,0), (-1,0)]
flg = False
cnt = 0

field_1d = list(itertools.chain.from_iterable(field))
field01 = [1 if i == '.' else 0 for i in field_1d]
dot_num = np.array(field01).sum()

q = Queue()
q.put([sy, sx])
field[sy][sx] = 0

while flg == False:
    yx = q.get()
    cnt = field[yx[0]][yx[1]]
    for dy, dx in dxy:
        y_n, x_n = yx[0] + dy, yx[1] + dx
        if y_n == gy and x_n == gx:
            field[y_n][x_n] = cnt + 1
            flg = True
            print(dot_num - (cnt+2))
            break
        if field[y_n][x_n] == '#':
            continue
        if field[y_n][x_n] == '.':
            q.put([y_n, x_n])
            field[y_n][x_n] = cnt + 1
    if flg:
        break
if flg == False:
    print(-1)

### FIXED CODE ###

from collections import deque
 
 
def dfs(field):
    q = deque([(0, 0, 0)])
    visited = [[False] * w for _ in range(h)]
    while q:
        i, j, d = q.popleft()
        if i == h - 1 and j == w - 1:
            return d
        if visited[i][j]:
            continue
        visited[i][j] = True
        if i > 0 and field[i - 1][j] == '.':
            q.append((i - 1, j, d + 1))
        if i < h - 1 and field[i + 1][j] == '.':
            q.append((i + 1, j, d + 1))
        if j > 0 and field[i][j - 1] == '.':
            q.append((i, j - 1, d + 1))
        if j < w - 1 and field[i][j + 1] == '.':
            q.append((i, j + 1, d + 1))
    else:
        return -1
 
 
h, w = map(int, input().split())
field = [input() for _ in range(h)]
dot_cnt = sum(r.count('.') for r in field)
d = dfs(field)
if d == -1:
    print(-1)
else:
    print(dot_cnt - (d+1))
### BUGGY CODE ###

def func(a):
  global mx
  mx = min(mx, abs(int(a)-x))
  return int(a)

n,x = map(int,input().split())
mx = 10**9
xlist = list(map(func,input().split()))

for i in range(mx,0,-1):
  for j in range(n):
    if abs(x-xlist[j])%i != 0:
      break
  else:
    print(i)
    break
  

### FIXED CODE ###

from fractions import gcd
def func(a):
  return abs(int(a)-x)
n,x = map(int,input().split())
xlist = list(map(func,input().split()))
for i in range(1,n):
  xlist[i] = gcd(xlist[i],xlist[i-1])
print(xlist[n-1])
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
    N, M, P = map(int, input().split())
    g = [[] for _ in range(N+1)]
    g2 = [[] for _ in range(N+1)]
    data0 = [None] * (M+1)
    data1 = [None] * (M+1)
    data2 = [None] * (M+1)
    for i in range(M):
        a, b, c = map(int, input().split())
        data0[i] = a
        data1[i] = b
        data2[i] = c


    for i in range(M):
        g[data1[i]].append(data0[i])
        g2[data0[i]].append(data1[i])

    visit = [False]*(N+1)
    visit2 = [False]*(N+1)

    queue = [N]
    while len(queue) > 0:
        nextqueue = []
        for now in queue:
            visit[now] = True
            for next in g[now]:
                if not visit[next]:
                    nextqueue.append(next)
        queue = nextqueue[:]

    queue = [1]
    while len(queue) > 0:
        nextqueue = []
        for now in queue:
            visit2[now] = True
            for next in g2[now]:
                if not visit2[next]:
                    nextqueue.append(next)
        queue = nextqueue[:]




    for i in range(1, N+1):
        visit[i] = visit[i] and visit2[i]


    INF = -100000001
    d = [INF] * (N+1)
    d[1] = 0

    for i in range(N):
        d_N = [d[i] for i in range(1, N+1) if visit[i]]
        for j in range(M):
            d[data1[j]] = max(d[data1[j]], d[data0[j]]+data2[j]-P)
        if i == N-1:
            if d_N != [d[i] for i in range(1, N+1) if visit[i]]:
                ans = -1

            else:
                ans = d[N]

    if ans == -1:
        print(-1)
    else:
        print(max(0, ans))

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
import queue
input = sys.stdin.readline

def main():
    N, M, P = map(int, input().split())
    g = [[] for _ in range(N+1)]
    g2 = [[] for _ in range(N+1)]
    data = [list(map(int, input().split())) for _ in range(M)]
    for a, b, _ in data:
        g2[b].append(a)
        g[a].append(b)

    visit = [False]*(N+1)
    visit2 = [False]*(N+1)

    q = queue.Queue()
    q.put(1)
    visit[1] = True
    while (not q.empty()):
        now = q.get()
        for next in g[now]:
            if not visit[next]:
                visit[next] = True
                q.put(next)

    q = queue.Queue()
    q.put(N)
    visit2[N] = True
    while (not q.empty()):
        now = q.get()
        for next in g2[now]:
            if not visit2[next]:
                visit2[next] = True
                q.put(next)

    for i in range(1, N+1):
        visit[i] = visit[i] and visit2[i]


    INF = 1000000001
    d = [(-1)*INF for i in range(N+1)]
    d[1] = 0

    for i in range(N):
        d_N = [d[i] for i in range(1, N+1) if visit[i]]
        for j in range(M):
            a = data[j][0]
            b = data[j][1]
            c = data[j][2]
            d[b] = max(d[b], d[a]+c-P)
        if i == N-1:
            if d_N != [d[i] for i in range(1, N+1) if visit[i]]:
                ans = -1

            else:
                ans = d[N]

    if ans == -1:
        print(-1)
    else:
        print(max(0, ans))

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

X = int(input())
A = [i for i in range(0, 10000)]
res = []
for i in range(len(A)):
  a = A[i]
  for j in range(len(A)):
    b = -A[j]
    cal = a ** 5 - b ** 5
    if cal == X:
      print(a, b)
      exit()


### FIXED CODE ###

X = int(input())
A = [(i**5) for i in range(0, 1000)]
res = []
for i in range(len(A)):
  a = A[i]
  for j in range(len(A)):
    b = -A[j]
    cal = a - b
    cal2 = a + b
    if cal == X:
      print(i, -j)
      exit()
    elif cal2 == X:
      print(i, j)
      exit()
### BUGGY CODE ###

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

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

for i in range(N):
    L = A[0:i]+A[i+1:N]
    c = collections.Counter(L)
    l = [i for i in c.values() if i != 1]
    ans = 0
    for j in l:
        ans += combinations_count(j,2)
    print(ans)

### FIXED CODE ###

import numpy as np
N = int(input())
A = np.array(input().split(),np.int64)

bincnt = np.bincount(A)

total = (bincnt * (bincnt - 1)).sum() // 2
ans = (total - (bincnt-1))[A].astype(str)

print('\n'.join(ans))
### BUGGY CODE ###

#!/usr/bin/env python3
def main():
    import numpy as np

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

    dp = np.zeros((N * 2, (W + 1)), dtype=np.int64)
    for n in range(N):
        for w in range(W + 1):
            can_w, can_v = products[n]
            if w >= can_w:
                dp[n + 1][w] = max(dp[n + 1][w], dp[n][w - can_w] + can_v)
            dp[n + 1][w] = max(dp[n + 1][w], dp[n][w])
    print(np.max(dp))


if __name__ == '__main__':
    main()


### FIXED CODE ###

def resolve():
    import sys
    
    readline = sys.stdin.readline

    N, W = map(int, readline().split())
    lst = [list(map(int, readline().split())) for _ in [0] * N]
    
    dp = [[0] * (W + 1) for _ in [0] * N]

    for i in range(N):
        w, v = lst[i][0], lst[i][1]
        for sum_w in range(W + 1):
            if sum_w >= w:
                dp[i][sum_w] = max(dp[i][sum_w],
                                   dp[i - 1][sum_w - w] + v)
            dp[i][sum_w] = max(dp[i][sum_w], dp[i - 1][sum_w])
    print(max(dp[-1]))


resolve()
### BUGGY CODE ###

S=input()
Q=int(input())
query=[[i for i in input().split()] for _ in range(Q)]

rf=0
for q in query:
    if q[0] == "1":
        rf ^= 1
    else:
        if q[1] == '1':
            if rf:
                S = S + q[2]
            else:
                S = q[2] + S
        else:
            if rf:
                S = q[2] + S
            else: 
                S = S + q[2]
print(S[::-1] if rf else S)

### FIXED CODE ###

from collections import deque
S = deque([input()])
Q=int(input())
query=[[i for i in input().split()] for _ in range(Q)]

rf=0
for q in query:
    if q[0] == "1":
        rf ^= 1
    else:
        if q[1] == '1':
            if rf:
                S.append(q[2])
            else:
                S.appendleft(q[2])
        else:
            if rf:
                S.appendleft(q[2])
            else: 
                S.append(q[2])
print(''.join(S)[::-1] if rf else ''.join(S))
### BUGGY CODE ###

from sys import stdin
input = stdin.readline

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

for ta in a:
    ans *= ta

if (ans > 10 ** 18):
    print(-1)
else:
    print(ans)


### FIXED CODE ###

from sys import stdin
input = stdin.readline

n = int(input())
a = list(map(int, input().split()))
ans = 1
flag = True

for ta in a:
    ans *= ta
    if (ans > 10 ** 18):
        flag = False
        ans = 1

if (flag or ans == 0):
    print(ans)
else:
    print(-1)
### BUGGY CODE ###

s = input()
K = int(input())

s_set = set()

for i in range(len(s)):
    sub_s = s[i]
    s_set.add(sub_s)
    for j in range(i+1, len(s)):
        sub_s += s[j]
        s_set.add(sub_s)

print(sorted(s_set)[K-1])

        


### FIXED CODE ###

s = input()
K = int(input())

s_set = set()

for i in range(len(s)):
    sub_s = s[i]
    s_set.add(sub_s)
    for j in range(i+1, len(s)):
        sub_s += s[j]
        s_set.add(sub_s)
        if len(sub_s) == 5:
            break


print(sorted(s_set)[K-1])
### BUGGY CODE ###

def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
               
        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d

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

cost = [[float("inf") for i in range(n)] for i in range(n)] 

for i in range(n-1):
    # x,y,z = map(int,input().split())
    # cost[x][y] = z
    # cost[y][x] = z
    cost[i][i+1] = 1
    cost[i+1][i] = 1
cost[a-1][b-1] = 1
cost[b-1][a-1] = 1


ANS = []
for i in range(n):
    ANS.extend(dijkstra(i, n, n, cost))

import collections

c = collections.Counter(ANS)

for i in range(1, n):
    print(c[i]//2)

### FIXED CODE ###

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

b = b - 1
c = c - 1
A = []

for i in range(a):
    for j in range(i+1, a):
        A.append(min(abs(i - b) + 1 + abs(j - c), abs(j - i)))
import collections
C = collections.Counter(A)

for i in range(1, a):
    print(C[i])
### BUGGY CODE ###

# N < 90なのでテーブルにする必要ある？
def L(i):
    if i == 0:
        return 2
    elif i == 1:
        return 1
    else:
        return L(i- 1) + L(i-2)

s = int(input())
print(L(s))


### FIXED CODE ###

# N < 90なのでテーブルにする必要ある？
table = [0]*90
def L(i):
    if i == 0:
        table[i] = 2
    elif i == 1:
        table[i] = 1
    else:
        table[i] = table[i- 1] + table[i-2]

s = int(input())
for i in range(s + 1):
    L(i)
print(table[s])
# tleした