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

import sys
input = sys.stdin.buffer.readline
H, W, K = map(int, input().split())
B = {}
for _ in range(K):
    r, c, v = map(int, input().split())
    B[(r, c)] = v

dp = [[0]*4 for _ in range(W+1)]

for i in range(1, H+1):
    for j in range(1, W+1):
        if (i, j) in B:
            v = B[(i, j)]
            dp[j][0] = max(dp[j-1][0], dp[j][0], dp[j][1], dp[j][2], dp[j][3])
            dp[j][1] = max(dp[j-1][1], dp[j][0]+v)
            dp[j][2] = max(dp[j-1][2], dp[j-1][1]+v)
            dp[j][3] = max(dp[j-1][3], dp[j-1][2]+v)
        else:
            dp[j][0] = max(dp[j-1][0], dp[j][0], dp[j][1], dp[j][2], dp[j][3])
            dp[j][1] = dp[j-1][1]
            dp[j][2] = dp[j-1][2]
            dp[j][3] = dp[j-1][3]

print(max(dp[-1]))


### FIXED CODE ###

R, C, K = map(int, input().split())
# = int(input())
p = []
for k in range(K):
  p.append(list(map(int, input().split())))

maps = [[0 for _ in range(C)] for _ in range(R)]
for k in range(K):
  maps[p[k][0]-1][p[k][1]-1] += p[k][2]

point1 = [[0 for _ in range(C)] for _ in range(R)]
point2 = [[0 for _ in range(C)] for _ in range(R)]
point3 = [[0 for _ in range(C)] for _ in range(R)]

point1[0][0] = maps[0][0]

for r in range(R):
  for c in range(C):
    a, b, d = point1[r][c], point2[r][c], point3[r][c]  
    if c < C - 1:
      x = maps[r][c+1]
      point1[r][c+1] = max(point1[r][c+1], x, a)
      point2[r][c+1] = max(point2[r][c+1], a + x, b)
      point3[r][c+1] = max(point3[r][c+1], b + x, d)
    if r < R - 1:
      point1[r+1][c] = maps[r+1][c] + max(a, b, d)


print(max(point1[-1][-1], point2[-1][-1], point3[-1][-1]))
### BUGGY CODE ###

def MAP(): return list(map(int,input().split()))
def INT(): return int(input())
def FLOAT(): return float(input())
MOD = 10**9+7

n,k = MAP()
h = MAP()

dp = [MOD]*n
dp[0]=0

for i in range(n-1):
    for j in range(i+1,min(i+k+1,n)):
        dp[j] = min(dp[j],dp[i]+abs(h[i]-h[j]))
print(dp[n-1])

### FIXED CODE ###

def MAP(): return list(map(int,input().split()))
def INT(): return int(input())
def FLOAT(): return float(input())
MOD = 10**9+7

n,k = MAP()
h = MAP()

dp = [MOD]*n
dp[0]=0

for i in range(n-1):
    for j in range(i+1,min(i+k+1,n)):
        dp[j] = min(dp[j],dp[i]+abs(h[i]-h[j]))
print(dp[n-1])
### BUGGY CODE ###


from collections import deque
N, u, v = map(int, input().split())
u, v = u-1, v-1
AB = [list(map(int, input().split())) for a in range(N-1)]

G = [[] for a in range(N)]

for ab in AB:
  G[ab[0]-1].append(ab[1]-1)
  G[ab[1]-1].append(ab[0]-1)
#print(AB)
#print(G)

def bfs(current, goal):
#  print('bfs start')
#  print(current, goal)
  q = deque([current])
  costs = [0 for a in range(N)]
  done = [0 for a in range(N)]
  done[current] = 1
  while q:
    start = q.popleft()
#    print(start)
    if start == goal:
      return costs[goal]
    for i in G[start]:
      if done[i] == 0:
        q.append(i)
        costs[i] = costs[start] + 1
        done[i] = 1

distances = [0]
for i in range(N):
#  print(i)
  aoki = bfs(i, v)
  takahashi = bfs(i, u)
  if aoki > takahashi:
    distances.append(aoki)

print(max(distances)-1)

### FIXED CODE ###

from collections import deque
N, u, v = map(int, input().split())
u, v = u-1, v-1
AB = [list(map(int, input().split())) for a in range(N-1)]

G = [[] for a in range(N)]

for ab in AB:
  G[ab[0]-1].append(ab[1]-1)
  G[ab[1]-1].append(ab[0]-1)

qA = deque([v])
qT = deque([u])
costsA = [0 for a in range(N)]
doneA = [0 for a in range(N)]
costsT = [0 for a in range(N)]
doneT = [0 for a in range(N)]

doneA[v] = 1
doneT[u] = 1

def bfs(q, costs, done):
  while q:
    start = q.popleft()
    for i in G[start]:
      if done[i] == 0:
        q.append(i)
        costs[i] = costs[start] + 1
        done[i] = 1

bfs(qA, costsA, doneA)
bfs(qT, costsT, doneT)

distances = [0]
for i in range(N):
  if costsA[i] > costsT[i]:
    distances.append(costsA[i])

print(max(distances)-1)
### BUGGY CODE ###

N = int(input())
ans = 1

for i in range(1, N+1):
    ans *= i

print(ans % (10**9+7))

### FIXED CODE ###

N = int(input())
ans = 1

for i in range(1, N+1):
    ans = i * ans % (10**9+7)

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

S = input()
Q = int(input())
oldq=0
for i in range(Q):
    q = input().split()
    if q[0] == '1':
        if oldq == '1':
            continue
        S = S[::-1]
    else:
        if q[1] == '1':
            S = q[2] + S
        else:
            S += q[2]
    oldq = q
print(S)


### FIXED CODE ###

S = input()
Q = int(input())
qry = [input().split() for _ in range(Q)]
A = ''
B = ''
oq = 0
even = True
for q in qry:
    if q[0] == '1':
        even = not even
        if oq == '1':
            continue
    else:
        if even:
            if q[1] == '1':
                A = q[2] + A
            else:
                B += q[2]
        else:
            if q[1] == '1':
                B += q[2]
            else:
                A = q[2] + A
    oq = q

if even:
    print(A+S+B)
else:
    print(B[::-1]+S[::-1]+A[::-1])
### BUGGY CODE ###


def E(x):
    ans = 0
    for i in range(x):
        ans += (i+1)
    ans /= x
    return ans

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

p = list(map(int,input().split()))
E_lis = [E(i) for i in p]
res = []

for i in range(len(p)-k+1):
    temp = 0
    for j in range(k):
        temp += E_lis[i+j]
    res.append(temp)
print(max(res))


### FIXED CODE ###

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

p = list(map(int,input().split()))
counter_li = []
first = 0
for i in range(k):
    first+=p[i]
counter_li.append(first)
for i in range(1,len(p)-k+1):
    counter_li.append(counter_li[i-1]+ p[i+k-1] - p[i-1])
print(max(counter_li)/2+k/2)
### BUGGY CODE ###

import math
a,b,n = map(int,input().split())
ans = 0
start =  b // a
count = 0
check = start % b
count = 0
for i in range(start,n+1):
    dum1 = (a * i / b) // 1
    dum2 = a * ((i / b)//1)
    dum3 = dum1 - dum2
    #print(dum1,dum2)
    ans = max(ans,dum3)
    if i % b == check and count != 0:
        break
    count += 1
print(math.ceil(ans))

### FIXED CODE ###

import math
a,b,n = map(int,input().split())
if b-1 <= n:
    print(math.floor((a*(b-1))/b)-(a*math.floor((b-1)/b)))
else:
    print(math.floor((a * (n)) / b) - (a * math.floor((n) / b)))
### BUGGY CODE ###

N, M = map(int, input().split())
a = [[] for i in range(N+1)]
for i in range(M):
  u, v = map(int, input().split())
  a[u].append(v)
#print(a)

S, T = map(int, input().split())
def main():
  c = [S]
  m = [[False, False, False] for i in range(N+1)]
  for count in range(1, 3*N+1):
    vs = []
    for u in c:
      m[u][count %3] = True
      vs += a[u]
    c = []
    for v in vs:
      if (v == T and count %3 ==0):
        return count//3
      if not(m[v][(count+1) %3]):
        c.append(v)
  return -1
print(main())


### FIXED CODE ###

N, M = map(int, input().split())
a = [[] for i in range(N+1)]
for i in range(M):
  u, v = map(int, input().split())
  a[u].append(v)
#print(a)

S, T = map(int, input().split())
def main():
  c = [S]
  m = [[False, False, False] for i in range(N+1)]
  for count in range(1, 3*N+1):
    c2 = []
    for u in c:
      m[u][count %3] = True
      for v in a[u]:
        if (v == T and count %3 ==0):
          return count//3
        if not(m[v][(count+1) %3]):
          m[v][(count+1) %3]=True
          c2.append(v)
    c = c2
  return -1
print(main())
### BUGGY CODE ###

N,T = map(int,input().split())
AB = [tuple(map(int,input().split())) for i in range(N)]

dp = [[[-1,-1] for t in range(T)] for i in range(N+1)]
dp[0][0][0] = 0
maxt = 0
for i,(a,b) in enumerate(AB):
    maxt = min(T-1, maxt + a)
    for t in range(maxt, -1,-1):
        for k in range(2):
            dpitk = dp[i][t][k]
            if dpitk < 0: continue
            if dp[i+1][t][k] < dpitk: dp[i+1][t][k] = dpitk
            if t+a < T:
                if dp[i+1][t+a][k] < dpitk + b: dp[i+1][t+a][k] = dpitk + b
            if k==0:
                if dp[i+1][t][1] < dpitk + b: dp[i+1][t][1] = dpitk + b
print(max(a[1] for a in dp[-1]))

### FIXED CODE ###

N,T = map(int,input().split())
AB = [tuple(map(int,input().split())) for i in range(N)]

dp0 = {0:0}
dp1 = {0:0}

for i,(a,b) in enumerate(AB):
    _dp0 = {0:0}
    _dp1 = {0:0}
    for k0,v0 in dp0.items():
        if k0 in _dp0:
            _dp0[k0] = max(_dp0[k0], v0)
        else:
            _dp0[k0] = v0
        if k0+a < T:
            if k0+a in _dp0:
                _dp0[k0+a] = max(_dp0[k0+a], v0+b)
            else:
                _dp0[k0+a] = v0+b
        if k0 in _dp1:
            _dp1[k0] = max(_dp1[k0], v0+b)
        else:
            _dp1[k0] = v0+b
    for k1,v1 in dp1.items():
        if k1 in _dp1:
            _dp1[k1] = max(_dp1[k1], v1)
        else:
            _dp1[k1] = v1
        if k1+a < T:
            if k1+a in _dp1:
                _dp1[k1+a] = max(_dp1[k1+a], v1+b)
            else:
                _dp1[k1+a] = v1+b
    dp0 = _dp0
    dp1 = _dp1

print(max(dp1.values()))
### BUGGY CODE ###

N = int(input())
t = list(map(int,input().split()))
v = list(map(int,input().split()))

time = 0
sum_t = sum(t)
velo_cap =[float("inf")]*(2*sum_t+1)
for i in range(N):
  start_t = time
  goal_t = time + 2*t[i]
  for s in range(0,2*sum_t+1):
    if s < start_t:
      velo_cap[s] = min(velo_cap[s],2*v[i]+(start_t-s))
    elif s<goal_t:
      velo_cap[s] = min(velo_cap[s],2*v[i])
    else:
      velo_cap[s] = min(velo_cap[s],2*v[i]+(s-goal_t))
  time += 2*t[i]
for s in range(2*sum_t+1):
  velo_cap[s] = min(velo_cap[s],2*sum_t-s,s)


print(sum(velo_cap)/4-(velo_cap[0]+velo_cap[-1])/8)


### FIXED CODE ###

N = int(input())
t = list(map(int,input().split()))
v = list(map(int,input().split()))

time = 0
sum_t = sum(t)
velo_cap =[float("inf")]*(2*sum_t+1)
for i in range(N):
  start_t = time
  goal_t = time + 2*t[i]
  for s in range(0,2*sum_t+1):
    if s < start_t:
      velo_cap[s] = min(velo_cap[s],2*v[i]+(start_t-s))
    elif s<goal_t:
      velo_cap[s] = min(velo_cap[s],2*v[i])
    else:
      velo_cap[s] = min(velo_cap[s],2*v[i]+(s-goal_t))
  time += 2*t[i]
for s in range(2*sum_t+1):
  velo_cap[s] = min(velo_cap[s],2*sum_t-s,s)


print(sum(velo_cap)/4-(velo_cap[0]+velo_cap[-1])/8)
### BUGGY CODE ###

from functools import reduce
from operator import mul

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

res = reduce(mul, N_s)

if res > 10 ** 18:
    res = -1

print(res)


### FIXED CODE ###

N = input()
A_str = input().split()
A_array = map(int, A_str)

if "0" in A_str:
    print(0)
    exit()

res = 1
for A in A_array:
    res *= A
    if res > 10 ** 18:
        res = -1
        break

print(res)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import bisect_right
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
from decimal import Decimal
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
N,M = map(int,input().split())
count = [[0]*N for _ in range(N)]
fr = [[] for _ in range(N)]
for _ in range(M):
    a,b = map(int,input().split())
    a,b = a-1,b-1
    if count[a][b] == 1:
        continue
    count[a][b] = 1
    count[b][a] = 1
    fr[a].append(b)
    fr[b].append(a)
used = [-1]*N 
MAX = 0
def dfs(fr,cur,parent):
    global cnt
    children = fr[cur]
    for chi in children:
        if used[chi] != -1:
            continue
        if chi == parent:
            continue
        used[chi] = 0
        cnt += 1
        dfs(fr,chi,cur)
    return

for i in range(N):
    cnt = 1
    if used[i] != -1:
        continue
    used[i] = 0
    dfs(fr,i,-1)
    MAX = max(MAX, cnt)
print(MAX)

            








### FIXED CODE ###

# Union Find
#0オリジン以下注意

#xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
    
def unite(x, y):
    x = find(x)
    y = find(y)
    
    if x == y:
        return False
    else:
        #sizeの大きい方がx
        if par[x] > par[y]:
            x, y = y, x
        par[x] += par[y] #ここで集合の個数を更新している
        par[y] = x
        return True
    
#xとyが同じ集合に含まれているかどうかを判定(同じ集合にあればTrue)
def same(x, y):
    return find(x) == find(y)

#xが属する集合の個数
def size(x):
    return -par[find(x)]

#初期化
#根なら-size, 子なら親の頂点
n, m = map(int, input().split())
par = [-1]*n
for i in range(m):
    a, b = map(int, input().split())
    unite(a-1, b-1)
M = 0
for i in range(n):
    M = max(M, size(i))
print(M)

################以下にコードを書く
######2次元配列が与えられたら１次元に直す必要あり
### BUGGY CODE ###

#入力処理
A, B, M = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
x=[]
y=[]
c=[]
for i in range(M):
    x_input, y_input, c_input = map(int, input().split())
    x.append(x_input)
    y.append(y_input)
    c.append(c_input)

#処理
kingaku = []
tem=[]
tem1=[]
for i in range(A):
    for j in range(B):
        tem.append(int(a[i])+int(b[j]))
    kingaku.append(tem)
    tem = []

waribiki=[[0]*B]*A
for i in range(M):
    if waribiki[x[i]-1][y[i]-1] < c[i]:
        waribiki[x[i]-1][y[i]-1] = c[i]

inexpensive = 200000
for i in range(A):
    for j in range(B):
        if kingaku[i][j]-waribiki[i][j] < inexpensive:
            inexpensive=kingaku[i][j]-waribiki[i][j]

print(inexpensive) 

### FIXED CODE ###

#入力処理
A, B, M = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
kingaku=[]
for i in range(M):
    x_input, y_input, c_input = map(int, input().split())
    kingaku.append(a[x_input-1]+b[y_input-1]-c_input)
kingaku.append(min(a)+min(b))

print(min(kingaku))
### BUGGY CODE ###

import bisect

Q = int(input())

A = []
A_size = 0
A_med_min = 0
A_med_max = 0
MIN_SCORE = 0
for i in range(Q):
    q = input()
    if q[0]=="1": #更新
        dummy,a,b = map(int,q.split())
        #常にソート済リストを作れる
        bisect.insort_left(A,a)
        A_size+=1
        #中央値との差分からA群からなる最小値を更新
        sabun = 0
        if a<A_med_min:
            sabun = A_med_min - a
        elif a>A_med_max:
            sabun = a - A_med_max
        MIN_SCORE += sabun + b if A_size>1 else b
        #中央値の更新
        if A_size%2==0:
            A_med_min = A[(A_size//2)-1]
            A_med_max = A[A_size//2]
        else:
            A_med_min = A[A_size//2]
            A_med_max = A[A_size//2]
    elif q[0]=="2":
        print(A_med_min,MIN_SCORE)

### FIXED CODE ###

import heapq

Q = int(input())

A_left = [] #最大を取り出すのでminus queueにする
A_right = [] #最小を取り出す
A_middle = 0
A_size = 0
MIN_SCORE = 0
for i in range(Q):
    q = input()
    if q[0]=="1": #更新
        dummy,a,b = map(int,q.split())
        A_size+=1
        sabun = 0
        if A_size==1: #初期設定
            A_middle = a
            sabun = 0
        elif A_size%2==0: #偶数処理
            if a <= A_middle:
                sabun = A_middle - a
                heapq.heappush(A_left,a*(-1))
                heapq.heappush(A_right,A_middle)
            else:
                sabun = a - A_middle
                heapq.heappush(A_left,A_middle*(-1))
                heapq.heappush(A_right,a)
            A_middle = 0 #デバッグ用
        else: #奇数処理
            if a<A_left[0]*(-1):
                sabun = A_left[0]*(-1) - a
                A_middle = heapq.heappop(A_left)*(-1)
                heapq.heappush(A_left,a*(-1))
            elif a>A_right[0]:
                sabun = a - A_right[0]
                A_middle = heapq.heappop(A_right)
                heapq.heappush(A_right,a)
            else:
                sabun = 0
                A_middle = a
        MIN_SCORE += sabun + b if A_size>1 else b
    elif q[0]=="2":
        if A_size%2==0:
            print(A_left[0]*(-1),MIN_SCORE)
        else:
            print(A_middle,MIN_SCORE)
### BUGGY CODE ###

from collections import deque, defaultdict


def bfs(graph, start):
    ans = 'Yes'
    ans_list = {}

    queue = deque([start])
    visited = set()
    distance = defaultdict(int)
    distance[start] = 0
    while queue:
        current_vertex = queue.popleft()
        visited.add(current_vertex)
        for v in graph[current_vertex]:
            if v not in visited and v not in queue:
                queue.append(v)
                distance[v] = distance[current_vertex] + 1
                if distance[v] == distance[current_vertex] + 1:
                    ans_list[v] = current_vertex
    return ans_list

N, M = map(int, input().split())
paths = [tuple(map(int, input().split())) for _ in range(M)]

graph = defaultdict(set)
for A, B in paths:
    graph[A].add(B)
    graph[B].add(A)

ans_list = bfs(graph, 1)
ans_list = sorted(ans_list.items())

if len(ans_list) != N-1:
    print('No')
else:
    print('Yes')
    for k, v in ans_list:
        print(v)


### FIXED CODE ###

from collections import deque, defaultdict


def bfs(graph, start):

    queue = deque([start])
    visited = set()
    visited.add(start)
    parent = defaultdict(int)
    parent[start] = 0
    while queue:
        current_vertex = queue.popleft()
        for v in graph[current_vertex]:
            if v not in visited:
                queue.append(v)
                visited.add(v)
                parent[v] = current_vertex
    return parent

N, M = map(int, input().split())
paths = [tuple(map(int, input().split())) for _ in range(M)]

graph = defaultdict(set)
for A, B in paths:
    graph[A].add(B)
    graph[B].add(A)

parent = bfs(graph, 1)

print('Yes')
for k, v in sorted(parent.items()):
    if v != 0:
        print(v)
### BUGGY CODE ###

import math
def is_prime(x):
    if x == 2:
        return 1
    elif x % 2 == 0:
        return 0
    else:
        return pow(2, x - 1, x) == 1

def check(l,r):
  count = 0
  for i in range(l,r+1,2):
    if is_prime(i) == True and is_prime((i+1)//2) == True:
      count += 1
  return count


Q = int(input())

nums = []
for i in range(Q):
  l,r = map(int,input().split())
  nums.append(check(l,r))


for i in nums:
  print(i)

### FIXED CODE ###

NMAX = 10**5+1

is_prime = [True]*NMAX
for i in range(2, NMAX):
    if is_prime[i]:
        for j in range(2*i, NMAX, i):
            is_prime[j] = False

sim_2017 = [0]*NMAX
for i in range(3, NMAX, 2):
    if is_prime[i] and is_prime[(i+1)//2]:
        sim_2017[i] += 1
for i in range(1, NMAX):
    sim_2017[i] += sim_2017[i-1]

q = int(input())
for _ in range(q):
    l, r = list(map(int, input().split()))
    ans = sim_2017[r] - sim_2017[l-1]
    print(ans)
### BUGGY CODE ###

from collections import Counter

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

ans = 0

for i in range(N-2):
    for j in range(i+1, N-1):
        if len(set([S[i], S[j]])) == 2:
            sk = ({"R", "G", "B"} - set([S[i], S[j]])).pop()
            if 2*j - i < N and S[2*j - i] == sk:
                ans += Counter(S[j+1:])[sk] - 1
            else:
                ans += Counter(S[j+1:])[sk]

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 d in range(1, (N-i-1)//2+1):
        if {S[i], S[i+d], S[i+2*d]} == {"R", "G", "B"}:
            ans -= 1

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

#D
n,W = list(map(int,input().split()))
w = [0]*n
v = [0]*n
for i in range(n):
    w[i],v[i] = list(map(int,input().split()))
    
dp = [[0 for i in range(W+1)] for j in range(n)]
for i in range(n): #品物iまで
    for j in range(W+1):
        if j == 0:
            dp[i][j] = 0
            continue
        if j-w[i] >= 0:
            dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i]] + v[i])
        else:
            dp[i][j] = dp[i-1][j]
print(max([dp[i][W]for i in range(n)]))

### FIXED CODE ###

#D
n,W = list(map(int,input().split()))
w = [0]*n
v = [0]*n
for i in range(n):
    w[i],v[i] = list(map(int,input().split()))
    
dp = [[0 for i in range(W+1)] for j in range(n)]
for i in range(n): #品物iまで
    for j in range(W+1):
        if j == 0:
            dp[i][j] = 0
            continue
        if j-w[i] >= 0:
            dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i]] + v[i])
        else:
            dp[i][j] = dp[i-1][j]
print(max([dp[i][W]for i in range(n)]))
### BUGGY CODE ###

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

MOD = 1000000007

# DPテーブル
dp = [0]*(N+1)
dp[0] = 1
if 1 not in A:  # 1段目が壊れている場合もあるので注意
    dp[1] = 1

for i in range(2, N+1):
    if i in A:  # 壊れている場合
        continue
    else:
        dp[i] = (dp[i - 1] + dp[i - 2]) % MOD
        
print(dp[-1])

### FIXED CODE ###

N, M = map(int, input().split())
BrokenSteps = [int(input()) for _ in range(M)]
 
MOD = 1000000007
 
# DPテーブル
dp = [0]*(N+1)
dp[0] = 1
if 1 not in BrokenSteps:  # 1段目が壊れている場合もあるので注意
    dp[1] = 1

steps = list(range(2, N+1))  # 0,1段目は計算済みなので2段目以降
NoBrokenSteps = list(set(steps) - set(BrokenSteps))
    
for i in NoBrokenSteps:
    dp[i] = (dp[i - 1] + dp[i - 2]) % MOD
        
print(dp[-1])
### BUGGY CODE ###


def canProd(i,m,a,n):
    
    if m == 0:
        return True
    if i >= n:
        return False

    res = canProd(i+1,m,a,n) or canProd(i+1,m-a[i],a,n)
    return res


n = int(input())
a = [int(x) for x in input().split()]
q = int(input())
m = [int(x) for x in input().split()]

tf = []

for i in range(min(m),max(m)+1):
    if canProd(0,i,a,n):
        tf.append(i)



for i in m:
    if i in tf:
        print("yes")
    else:
        print("no")

### FIXED CODE ###

from functools import lru_cache

@lru_cache(maxsize = None)
def canProd(i,m):
     
    if m == 0:
        return True
    if i >= n:
        return False
 
    res = canProd(i+1,m) or canProd(i+1,m-a[i])
    return res
 
 
n = int(input())
a = [int(x) for x in input().split()]
q = int(input())
m = [int(x) for x in input().split()]

rs = [None]*2001

maxm = max(m)
minm = min(m)

for i in range(minm,maxm+1):
    if canProd(0,i):
        rs[i] = "yes"
    else:
        rs[i] = "no"

for i in m:
    print(rs[i])
### BUGGY CODE ###

import bisect
N = int(input())
D = list(map(int,input().split()))
M = int(input())
T = list(map(int,input().split()))
T.sort()
for i in range(N):
    b = bisect.bisect_left(T,D[i])
    if b<M and D[i]==T[b]:
        del T[b]
        M-=1
print("YES" if M==0 else "NO")

### FIXED CODE ###

from collections import defaultdict
N = int(input())
D = list(map(int,input().split()))
M = int(input())
T = list(map(int,input().split()))
ans = "YES"
d = defaultdict(lambda : 0)
for i in range(N):
    d[D[i]] += 1
for j in range(M):
    if d[T[j]] == 0:
        ans = "NO"
        break
    d[T[j]] -= 1
print(ans)