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

#!python3

from heapq import heappush, heappop, heapify

iim = lambda: map(int, input().rstrip().split())

def resolve():
    H, N = iim()
    AB = [tuple(iim()) for i in range(N)]

    AB.sort(key=lambda a: (a[0]/a[1], a[0]), reverse=True)

    S = []
    for a, b in AB:
        n = H // a + 1
        h = H
        i = 1
        while n >= i:
            S.append((a*i, b*i))
            n -= i
            i <<= 1
        if n:
            S.append((a*n, b*n))

    N2 = len(S)
    def ubound(b, a, i):
        for j in range(i, N2):
            aj, bj = S[j]
            if a + aj >= H:
                return (b+bj, b + (H-a) * bj / aj)
            a += aj
            b += bj

        return (inf, inf)

    q = []
    u0, u1 = ubound(0, 0, 0)

    inf = float("inf")
    heappush(q, (u1, u0, 0, 0, 0))
    um = u0
    #print(AB)
    #print(H, S)
    while q:
        #print(q)
        uq0, uq1, aq, bq, i = heappop(q)

        if uq0 > um:
            break

        if i >= N2: continue

        ai, bi = S[i]
        if aq + ai < H:
            heappush(q, (uq0, uq1, aq + ai, bq + bi, i + 1))

        u0, u1 = ubound(bq, aq, i + 1)
        if u1 <= um:
            if u0 < um:
                um = u0
            if u1 <= um:
                heappush(q, (u1, u0, aq, bq, i + 1))

    print(um)



if __name__ == "__main__":
    resolve()


### FIXED CODE ###

#!python3
import sys
sys.setrecursionlimit(1000000)

from heapq import heappush, heappop, heapify

iim = lambda: map(int, input().rstrip().split())

def resolve():
    H, N = iim()
    AB = [tuple(iim()) for i in range(N)]
    inf = float("inf")
    AB.sort(key=lambda a: (a[0]/a[1], -a[0]), reverse=True)

    def memo(f):
        cache = {}
        def wrapper(*a):
            if a in cache:
                return cache[a]
            b = f(*a)
            cache[a] = b

            return b

        return wrapper

    @memo
    def calc(h):
        if h <= 0: return 0

        bi = inf
        for a, b in AB:
            bj = b + calc(h - a)
            if bi > bj:
                bi = bj
            else:
                break
        return bi

    print(calc(H))



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

#import numpy as np

N = int(input())
A = list(map(int, input().split()))
A = sorted(A)#わるほう
remove_list = []

kouho = [x for x in set(A) if A.count(x) == 1]

#target = kouho[:]
if kouho != []:
    maxA = max(kouho)

for i in range(len(A)):
    if kouho == []:
        break
    maxN = int(maxA/A[i])
    for n in range(2,maxN+1):
        buf = A[i]*n
        remove_list.append(buf)
            #print(A[i]*n)
#target = kouho[:]
kouho = list(set(kouho) - set(remove_list))
print(len(kouho))

### FIXED CODE ###

#import numpy as np

N = int(input())
A = list(map(int, input().split()))
A.sort()#わるほう

#kouho = sorted([x for x in set(A) if A.count(x) == 1])
#maxA = 10**5

#target = kouho[:]
maxA = A[-1]
work=[0]*(A[-1]+1)

for i in range(len(A)):
    if work[A[i]]<=1:
        maxN = int(maxA/A[i])
        for n in range(1,maxN+1):
            buf = A[i]*n
            #remove_list.append(buf)
            work[buf]+=1
                #print(A[i]*n)

#target = kouho[:]
#kouho = list(set(kouho) - set(remove_list))

sm=0
for s in A:
    if work[s]==1: sm+=1
print(sm)

#print(len(kouho))
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
M=10**9+7
s=0
for i in range(n-1):
  for j in range(i+1,n):
    s+=(a[i]^a[j])%M
print(s%M)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
M=10**9+7

ans = 0
for i in range(61):
  ones=sum([1 for a in A if (a>>i)&1])
  ans += (1<<i)*ones*(N-ones)
  ans %= M

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

M = int(input())
dc = [[int(i) for i in input().split()] for _ in range(M)]

digit = [0] * 10
for d, c in dc :
    digit[d] += c

ret = digit[0]
digit[0] = 0
while sum(digit) != 1 :
    for a in range(1, 10) :
        for b in range(1, 10) :
            if a + b >= 10 :
                na = (a + b) // 10
                nb = (a + b) % 10
                if a == b :
                    x = digit[a] // 2
                    digit[na] += x
                    digit[nb] += x
                    digit[a] -= 2 * x
                else :
                    x = min(digit[a], digit[b])
                    digit[na] += x
                    digit[nb] += x
                    digit[a] -= x
                    digit[b] -= x
                ret += x
            else :
                if a == b :
                    x = digit[a] // 2
                    digit[a+b] += x
                    digit[a] -= 2 * x
                else :
                    x = min(digit[a], digit[b])
                    digit[a+b] += x
                    digit[a] -= x
                    digit[b] -= x

for d, c in dc :
    if d != 0 :
        ret += c
        
print(ret - 1)

### FIXED CODE ###

M = int(input())
dc = [[int(i) for i in input().split()] for _ in range(M)]

ret = 0
s = 0
for d, c in dc :
    s += d * c
    t = s // 10
    ret += t
    s %= 10
    s += t
    
while s >= 10 :
    t = s // 10
    ret += t
    s %= 10
    s += t

for d, c in dc :
    ret += c
        
print(ret - 1)
### BUGGY CODE ###

def calc(x):
    return (x+1)/2

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

# print(p)

ans = 0
for i in range(n-k+1):
    _ans = sum(p[i:i+k])
    if _ans > ans:
        ans = _ans
print(ans)


### FIXED CODE ###

def calc(x):
    return (x+1)/2

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

_ans = sum(p[0:k])
ans = _ans
for x in range(n-k):
    # print(x, x + k)
    _ans = _ans - p[x] + p[x + k]
    ans = max(ans, _ans)

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

import sys
sys.setrecursionlimit(10**5)
def bfs(ind):
    kouho=friends[ind]
    for i in kouho:
        if sans[i]!=-1:
            continue
        sans[i]=sans[ind]
        l[sans[ind]].add(i)
        bfs(i)
n,m,k=list(map(int,input().split()))
f=[list(map(int,input().split())) for _ in range(m)]
friends=[set() for _ in range(n)]
friends_num=list(map(lambda x:len(x),friends))
bl=[list(map(int,input().split())) for _ in range(k)]
l=[{i} for i in range(n)]

for each in f:
    a,b=each
    friends[a-1].add(b-1)
    friends[b-1].add(a-1)

block=[set() for _ in range(n)]
for each in bl:
    a,b=each
    block[a-1].add(b-1)
    block[b-1].add(a-1)

sans=[-1 for _ in range(n)]
sans[0]=0
bfs(0)
for i in range(n):
    if sans[i]!=-1:
        continue
    sans[i]=i
    bfs(i)
ans=[0 for _ in range(n)]
#"""
for i in range(n):
    tmp=(l[sans[i]]-block[i])-friends[i]-{i}
    ans[i]=len(tmp)

#"""
ans=" ".join(map(str,ans))
print(ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**5)
total=0
def bfs(ind,num):
    kouho=friends[ind]
    
    for i in kouho:
        if sans[i]!=-1:
            continue
        num+=1
        sans[i]=sans[ind]
        l[sans[ind]].add(i)
        num+=bfs(i,0)
    return num
n,m,k=list(map(int,input().split()))
f=[list(map(int,input().split())) for _ in range(m)]
friends=[set() for _ in range(n)]
friends_num=list(map(lambda x:len(x),friends))
bl=[list(map(int,input().split())) for _ in range(k)]
l=[{i} for i in range(n)]

for each in f:
    a,b=each
    friends[a-1].add(b-1)
    friends[b-1].add(a-1)

block=[set() for _ in range(n)]
for each in bl:
    a,b=each
    block[a-1].add(b-1)
    block[b-1].add(a-1)

sans=[-1 for _ in range(n)]
sans[0]=0
total=bfs(0,total)
for i in range(n):
    if sans[i]!=-1:
        continue
    sans[i]=i
    total=bfs(i,total)
ans=[0 for _ in range(n)]


for i in range(n):
    l[i]=set(l[i])


for i in range(n):
    tmp=l[sans[i]]
    ans[i]+=len(tmp)-len(friends[i])-1
    for j in block[i]:
        if sans[i]==sans[j]:
            ans[j]-=1

ans=" ".join(map(str,ans))
#print("total:",total)
print(ans)
### BUGGY CODE ###

s=str(input())
t=str(input())
ls=len(s)
lt=len(t)

dp=[[0 for i in range(lt+1)]for j in range(ls+1)]
for i in range(ls):
  for j in range(lt):
    if s[i]==t[j]:
      dp[i+1][j+1]=dp[i][j]+1
    else:
      dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j])

ans=""
x=ls
y=lt
while x>0 and y>0:
  if dp[x][y]==dp[x-1][y]:
    x-=1
  elif dp[x][y]==dp[x][y-1]:
    y-=1
  else:
    ans=s[x-1]+ans
    x-=1
    y-=1
print(ans)

### FIXED CODE ###

s=str(input())
t=str(input())
ls=len(s)
lt=len(t)

dp=[[0 for i in range(lt+1)]for j in range(ls+1)]
for i in range(ls):
  for j in range(lt):
    if s[i]==t[j]:
      dp[i+1][j+1]=dp[i][j]+1
    else:
      dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j])

ans=""
x=ls
y=lt
while x>0 and y>0:
  if dp[x][y]==dp[x-1][y]:
    x-=1
  elif dp[x][y]==dp[x][y-1]:
    y-=1
  else:
    ans=s[x-1]+ans
    x-=1
    y-=1
print(ans)
### BUGGY CODE ###

S = input()
Q = int(input())
query = [list(input().split()) for _ in range(Q)]
is_reverse = False
for q in query:
    if q[0] == "1":
        is_reverse = not is_reverse
    else:
        if is_reverse:
            if q[1] == "2":
                S = q[2] + S
            else:
                S += q[2]
        else:
            if q[1] == "1":
                S = q[2] + S
            else:
                S += q[2]

if is_reverse:
    print(S[::-1])
else:
    print(S)


### FIXED CODE ###

S = list(input())
Q = int(input())
query = [list(input().split()) for _ in range(Q)]
mae = []
ato = []
is_reverse = False
for q in query:
    if q[0] == "1":
        is_reverse = not is_reverse
    else:
        if is_reverse:
            if q[1] == "2":
                mae.append(q[2])
            else:
                ato.append(q[2])
        else:
            if q[1] == "1":
                mae.append(q[2])
            else:
                ato.append(q[2])
mae.reverse()
mae.extend(S)
mae.extend(ato)
if is_reverse:
    mae.reverse()
    print("".join(mae))
else:
    print("".join(mae))
### BUGGY CODE ###

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

cnt = 0
for first in range(N):
    for second in range(first+1,N):
        for third in range(second+1,N):
            if L[third] < L[first] + L[second]:
                cnt += 1
                # print(L[first],L[second],L[third])

print(cnt)


### FIXED CODE ###

import bisect

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

cnt = 0
for first in range(N):
    for second in range(first+1,N):
        bnd = bisect.bisect_left(L,L[first]+L[second]) - 1
        dif = bnd - second
        if dif > 0:
            cnt += dif

print(cnt)
### BUGGY CODE ###

S = input()
T = input()

for i in range(len(S)):
    s = S[i]
    t = T[i]
    
    # 文字列の入れ替
    S = S.replace(s, '0')
    S = S.replace(t, s)
    S = S.replace('0', t)

            
if S == T:
    re = 'Yes'
else:
    re = 'No'
    
print(re)

### FIXED CODE ###

S = input()
T = input()

def count_string(strInput):
    tmp = {}
    for s in strInput:
        if s in tmp:
            tmp[s] += 1
        else:
            tmp[s] = 1
    
    re = [tmp[a] for a in tmp]
    re = sorted(re)
    return re

S_count = count_string(S)
T_count = count_string(T)

if S_count == T_count:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

l,r=map(int,input().split())
min = 2018
for i in range(l,r,1):
  for j in range(i+1,r+1,1):
    if (i*j)%2019 < min:
      min = (i*j)%2019

print(min)

### FIXED CODE ###

L,R=map(int,input().split())
if R-L>2019:
  print(0)
elif L%2019==0 or R%2019==0:
  print(0)
elif L//2019!=R//2019:
  print(0)
else:
  L=L%2019
  R=R%2019
  ans=2019
  for i in range(L,R):
    for j in range(i+1,R+1):
      ans=min(ans,(i*j)%2019)
      if ans==0:
        break

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

from math import gcd

K = int(input())
total = 0
for a in range(K):
    for b in range(K):
        for c in range(K):
            d = gcd(a+1,b+1)
            total += gcd(d,c+1)
print(total)

### FIXED CODE ###

import math
from functools import reduce

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

K = int(input())
total = 0
for a in range(K):
    for b in range(K):
        for c in range(K):
           total += gcd(a+1,b+1,c+1)
print(total)
### BUGGY CODE ###

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

for j in range(len(A)):
    for i in range(len(A)):
        if(j!=i):
            if(A[j]==A[i]):
                x +=1
                pass
            pass
        pass
    pass

if(x==0):
    print('YES')
else:
    print('NO')
    

### FIXED CODE ###

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

def has(seq):
    return len(seq) != len(set(seq))

if(has(A)):
    print('NO')
else:
    print('YES')
### BUGGY CODE ###

import bisect
import sys
import math
import itertools
sys.setrecursionlimit(10000)

INF = float('inf')

# input macro
def i():
    return int(raw_input())
def ii():
    return map(int,raw_input().split(" "))
def s():
    return raw_input()
def ss():
    return raw_input().split(" ")
def slist():
    return list(raw_input())

###########

n,x=ii()
a=ii()
mi=[[0 for j in range(n)] for k in range(n)]
for s in range(n):
    mi[s][0]=a[s]
    for m in range(1,n):
        mi[s][m]=min(mi[s][m-1],a[(s-m)%n])
ans=INF
for m in range(n):
    cnt=x*m+sum([mi[s][m] for s in range(n)])
    ans=min(cnt,ans)

print ans


### FIXED CODE ###

n,x=map(int,raw_input().split(" "))
a=map(int,raw_input().split(" "))
t=[i for i in a]
s=10**15
for m in range(n):
    t=[min(t[j],a[(j-m)%n]) for j in range(n)]
    s=min(x*m+sum(t),s)
print s
### BUGGY CODE ###

input()
a=1
b=map(int,input().split())
for i in b:
  a*=i
if a>10**18:
  a=-1
print(a)

### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
if 0 in l:
  print(0)
else:
  a=1
  for i in l:
    a=a*i
    if a>10**18:
      print(-1)
      exit()
  print(a)
### BUGGY CODE ###

# n=int(input())
# a,b=map(int, input().split())
# c=list(map(int, input().split()))
# s=[list(map(int,list(input()))) for i in range(h)]  # 二次元配列入力　二次元マップみたいな入力のとき

# a=100
# b=0.987654321
# print('{0:06d}-{1:6f}'.format(a,b))  # 0埋めのときの出力
# 000100-0.987654

import numpy as np
import math
import copy
import itertools
from math import factorial

from operator import mul
from functools import reduce

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result


div_num  = 1000000007

N, M=map(int, input().split())

dmg = [int(input()) for _ in range(M)]

for i in range(M - 1):
    # 連番なら終了
    if dmg[i] + 1 == (dmg[i + 1]):
        print(0)
        exit()

comb_list = []
start = 0
for i in range(len(dmg) + 1):
    if i == len(dmg):
        interval = N - start
    else:
        interval = (dmg[i] - 1) - start
    j = 0
    comb_sum = 0
    while True:
        if (2 * j) > interval:
            break
        num_ptn_1_2 = j + (interval - (2 * j))
        r = j
        #comb_sum += int(factorial(num_ptn_1_2) / factorial(r) / factorial(num_ptn_1_2 - r))
        #comb_sum += int(comb(num_ptn_1_2,r,exact=True))
        comb_sum += cmb(num_ptn_1_2,r)
        j += 1
    if i < len(dmg):
        # 壊れた階段の次を始点にする
        start = dmg[i] + 1
    comb_list.append(comb_sum)

result = 1

for elem in comb_list:
    result *= elem

print(result % div_num)

### FIXED CODE ###

# n=int(input())
# a,b=map(int, input().split())
# c=list(map(int, input().split()))
# s=[list(map(int,list(input()))) for i in range(h)]  # 二次元配列入力　二次元マップみたいな入力のとき

# a=100
# b=0.987654321
# print('{0:06d}-{1:6f}'.format(a,b))  # 0埋めのときの出力
# 000100-0.987654

import numpy as np
import math
import copy
import itertools

mod  = 1000000007

N, M=map(int, input().split())

broken = [0 for _ in range(N + 2)]

for i in range(M):
    n = int(input())
    broken[n] = True

dp = [0 for _ in range(N + 2)]
dp[N] = 1
for i in range(0, N)[::-1]:
    if broken[i]:
        dp[i] = 0
        continue
    dp[i] = (dp[i + 1] + dp[i + 2]) % mod

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

import itertools
n = int(input())
s = input()

memo = {}
for i in range(len(s)):
  if s[i] not in memo:
    memo[s[i]] = 1
  else:
    memo[s[i]] += 1
 
li = []
for i in memo.values() :
  li.append(i)

ans = 0
for i in itertools.product(range(2),repeat=len(li)):
#  print(i)
  tmp = 1
  for j in range(len(li)):
    if i[j] != 0:
      tmp = tmp * li[j]
  ans = ans + tmp
print((ans-1)%1000000007)

### FIXED CODE ###

import itertools
n = int(input())
s = input()

memo = {}
for i in range(len(s)):
  if s[i] not in memo:
    memo[s[i]] = 1
  else:
    memo[s[i]] += 1
 
li = []
for i in memo.values() :
  li.append(i)

ans = 1
for i in li:
  ans = (ans*(i+1))%1000000007
print((ans-1)%1000000007)
### BUGGY CODE ###

import numpy as np
N=input()

lists = []
temp=np.asarray([i for i in range(10)])

dic={0:1}

for i in N:
    new_dic={}
    hoge=list(dic.items())
    if i == "?":
        for amari,count in hoge:
            amari*=10
            a=(temp+amari)%13
            for pa in a:
                if pa in new_dic:
                    new_dic[pa]+=count
                else:
                    new_dic[pa]=count
    else:
        num=int(i)
        for amari,count in hoge:
            a = (amari*10 + num)%13
            if a in new_dic:
                new_dic[a]+=count
            else:
                new_dic[a]=count
    dic = new_dic

try:
    print(dic[5]%(10**9 + 7))
except:
    print(0)

### FIXED CODE ###


N=input()

lists = []
temp=[i for i in range(10)]

MOD=10**9+7

dic={0:1}

for i in N:
    new_dic={}
    hoge=list(dic.items())
    if i == "?":
        for amari,count in hoge:
            amari*=10
            for num in temp:
                a = (amari + num) % 13
                if a in new_dic:
                    new_dic[a]+=count
                else:
                    new_dic[a]=count
    else:
        num=int(i)
        for amari,count in hoge:
            a = (amari*10 + num)%13
            if a in new_dic:
                new_dic[a]+=count
            else:
                new_dic[a]=count
    for key in new_dic:
        new_dic[key] %= MOD
    dic = new_dic

try:
    print(dic[5])
except:
    print(0)
### BUGGY CODE ###

"""
We Love ABC
DP使う問題
T : 文字列
i < j < k < len(T)
Ti = "A"
Tj = "B"
Tk = "C"
i j k の順で取れたら、1カウント
- TはA, B, C, ? で構成される
- ? は　ABC のいずれか
これらを満たす場合の数

i番目の文字において、ABCのどこまで進んだか
null:   0
A   :   1
B   :   2
C   :   3

?の扱いが厄介
?があると単純に選択肢が3倍になる
A? -> AA, AB, AC
B? -> BA, BB, BC
まだ選んでいない時 : 入力の選択肢が3倍に増える
dp[i+1][1]: 
    すでにAを選んでいる時 : iまでのAの選び方が3倍に増えるので、dp[i][1]*3
    何も選んでいない場合  : ?がAになれるので、dp[i][0]を加える
ほかも同じ
"""
mod = 10**9 + 7

S = input()
N = len(S)
dp = [[0]*4 for i in range(100800)]
dp[0][0] = 1
for i in range(N):
    s = S[i]
    dp[i+1][0] = dp[i][0] 
    dp[i+1][1] = dp[i][1] 
    dp[i+1][2] = dp[i][2] 
    dp[i+1][3] = dp[i][3] 
    if s == "A":
        # Aを選ぶ選択肢がそれまでのA,?分増える
        dp[i+1][1] += dp[i][0]
    if s == "B":
        # Bを選ぶ選択肢がそれまでのAの選択肢分増える
        dp[i+1][2] = dp[i][2] + dp[i][1] 
    if s == "C":
        # Cを選ぶ選択肢がBまでを選んだ分だけ増える
        dp[i+1][3] = dp[i][3] + dp[i][2]
    if s == "?":
        # ?を選んだ場合。選択肢は3倍に広がる
        dp[i+1][0] = 3*dp[i][0]
        dp[i+1][1] = dp[i][0] + 3*dp[i][1]
        dp[i+1][2] = dp[i][1] + 3*dp[i][2]  
        dp[i+1][3] = dp[i][2] + 3*dp[i][3]
        
# Cまで行った数を求める
print(dp[N][3]%mod)

### FIXED CODE ###

"""
We Love ABC
DP使う問題
T : 文字列
i < j < k < len(T)
Ti = "A"
Tj = "B"
Tk = "C"
i j k の順で取れたら、1カウント
- TはA, B, C, ? で構成される
- ? は　ABC のいずれか
これらを満たす場合の数

i番目の文字において、ABCのどこまで進んだか
null:   0
A   :   1
B   :   2
C   :   3

?の扱いが厄介
?があると単純に選択肢が3倍になる
A? -> AA, AB, AC
B? -> BA, BB, BC
まだ選んでいない時 : 入力の選択肢が3倍に増える
dp[i+1][1]: 
    すでにAを選んでいる時 : iまでのAの選び方が3倍に増えるので、dp[i][1]*3
    何も選んでいない場合  : ?がAになれるので、dp[i][0]を加える
ほかも同じ
"""
mod = 10**9 + 7

S = input()
N = len(S)
dp = [[0]*4 for i in range(100800)]
dp[0][0] = 1
for i in range(N):
    s = S[i]
    dp[i+1][0] = dp[i][0] 
    dp[i+1][1] = dp[i][1] 
    dp[i+1][2] = dp[i][2] 
    dp[i+1][3] = dp[i][3] 
    if s == "A":
        # Aを選ぶ選択肢がそれまでのA,?分増える
        dp[i+1][1] += dp[i][0]
    if s == "B":
        # Bを選ぶ選択肢がそれまでのAの選択肢分増える
        dp[i+1][2] = dp[i][2] + dp[i][1] 
    if s == "C":
        # Cを選ぶ選択肢がBまでを選んだ分だけ増える
        dp[i+1][3] = dp[i][3] + dp[i][2]
    if s == "?":
        # ?を選んだ場合。選択肢は3倍に広がる
        dp[i+1][0] = (3*dp[i][0])%mod
        dp[i+1][1] = (dp[i][0] + 3*dp[i][1]) % mod
        dp[i+1][2] = (dp[i][1] + 3*dp[i][2]) % mod
        dp[i+1][3] = (dp[i][2] + 3*dp[i][3]) % mod
        
# Cまで行った数を求める
print(dp[N][3]%mod)
### BUGGY CODE ###

s = input()
q = int(input())
for _ in range(q):
    t = input()
    if t[0] == '1':
        s = s[::-1]
    elif t[2] == '1':
        s = t[4] + s
    else:
        s = s + t[4]
print(s)


### FIXED CODE ###

s = input()
q = int(input())
cnt = 0
front = ''
rear = ''
for _ in range(q):
    t = input()
    if t[0] == '1':
        cnt += 1
    elif t[2] == '1':
        if cnt%2 == 1:
            rear = rear + t[4]
        else:
            front = front + t[4]
    else:
        if cnt%2 == 1:
            front = front + t[4]
        else:
            rear = rear + t[4]
if cnt%2 == 1:
    s = (front[::-1] + s + rear)[::-1]
else:
    s = front[::-1] + s + rear
print(s)
### BUGGY CODE ###

x,y,z,k=map(int,input().split())
a=[int(i) for i in input().split()]
b=[int(i) for i in input().split()]
c=[int(i) for i in input().split()]
a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)
if k<x: a=a[:k]
if k<y: b=b[:k]
if k<z: c=c[:k]
d=[]
ans=[]
for i in a:
    for j in b:
        d.append(i+j)
d.sort(reverse=True)
if len(d)<k: d=d[:k]
for i in c:
    for j in d:
        ans.append(i+j)
ans.sort(reverse=True)
for i in range(k):
    print(ans[i])

### FIXED CODE ###

x,y,z,k=map(int,input().split())
a=[int(i) for i in input().split()]
b=[int(i) for i in input().split()]
c=[int(i) for i in input().split()]
a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)
if k>x: a=a[:k]
if k>y: b=b[:k]
if k>z: c=c[:k]
d=[]
ans=[]
for i in a:
    for j in b:
        d.append(i+j)
d.sort(reverse=True)
if len(d)>k: d=d[:k]
for i in c:
    for j in d:
        ans.append(i+j)
ans.sort(reverse=True)
for i in range(k):
    print(ans[i])
### BUGGY CODE ###

import math
from bisect import bisect_right
from bisect import bisect_left

n = int(input())
L = list(map(int,input().split()))
L.sort()
c = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        lg = L[i] + L[j]
        st = L[j] - L[i]
        if lg > L[j+1] and st < L[n-1]:
            if lg > L[n-1]:
                m1 = n - (j+1)
            else:
                m1 = bisect_left(L[j+1:],lg)
            if st > L[j+1]:
                m2 = 0
            else:
                m2 = bisect_right(L[j+1:],st)
            c += max(0,m1-m2)
print (c)

### FIXED CODE ###

import math
from bisect import bisect_right
from bisect import bisect_left

n = int(input())
L = list(map(int,input().split()))
L.sort()
c = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        lg = L[i] + L[j]
        st = L[j] - L[i]
        if lg > L[j+1] and st < L[n-1]:
            if lg > L[n-1]:
                m1 = n - (j+1)
            else:
                m1 = bisect_left(L[j+1:],lg)
            c += max(0,m1)
print (c)