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

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

a=list(map(int, input().split()))
b=list(map(int, input().split()))
dis=[list(map(int,input().split()))  for l in range(M)]


comp1=a[dis[0][0]-1]+a[dis[0][0]-1]-dis[0][2]
for l in range(M):
    y=a[dis[l][0]-1]+b[(dis[l][1])-1]-dis[l][2]
    if comp1>y:
        comp1=y

comp2=int(a[0]+b[0])
for l in range(A):
    for m in range(B):
        x=int(a[l]+b[m])
        if comp2>x:
            comp2=x
                  
print(min(comp1,comp2))

### FIXED CODE ###

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

a=list(map(int, input().split()))
b=list(map(int, input().split()))
dis=[list(map(int,input().split()))  for l in range(M)]

comp1=a[dis[0][0]-1]+b[dis[0][1]-1]-dis[0][2]
for l in range(M):
    y=a[dis[l][0]-1]+b[(dis[l][1])-1]-dis[l][2]
    if comp1>y:
        comp1=y

comp2=min(a)+min(b)
                  
print(min(comp1,comp2))
### BUGGY CODE ###

import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    MOD = 2 ** 61 - 1
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    N = NI()
    cnt = collections.defaultdict(int)
    ans = 0
    S = [SI() for _ in range(N)]
    for s in S:
        cnt[s[1:]] |= 1<<(ord(s[0])-ord('a'))

    for s in S:
        a = []
        bit = 0
        for x in s:
            x = ord(x) - ord('a')
            bit |= 1 << x
            a.append(bit)
        for i in range(len(s),1,-1):
            if i == len(s):
                d = ''
            else:
                d = s[i:]
            ans += bin(cnt[d] & a[i-1]).count('1')

    print(ans)
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    MOD = 2 ** 61 - 1
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    N = NI()
    cnt = collections.defaultdict(int)
    ans = 0
    S = [SI() for _ in range(N)]
    for s in S:
        h = 0
        for i in range(len(s)-1,0,-1):
            h = (h * 27 + ord(s[i]) - ord('a') + 1) % MOD
        cnt[h] |= 1<<(ord(s[0])-ord('a'))

    for s in S:
        a = []
        bit = 0
        for x in s:
            x = ord(x) - ord('a')
            bit |= 1 << x
            a.append(bit)
        h = 0
        for i in range(len(s)-1,0,-1):
            ans += bin(cnt[h] & a[i]).count('1')
            h = (h * 27 + ord(s[i]) - ord('a') + 1) % MOD

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

import sys
n, x, y = map(int, sys.stdin.readline().split())

x -= 1
y -= 1
    
final = [0]*(n-1)
for i in range(n-1):
    for j in range(i+1, n):
        dist = min([abs(j - i), abs(x-i) + 1 + abs(y-j), abs(y-i) + 1 + abs(x-j)])
        final[dist-1] += 1 
for one in final:
    print(one)

### FIXED CODE ###

import sys
n, x, y = map(int, sys.stdin.readline().split())

x -= 1
y -= 1
    
final = [0]*(n-1)


for i in range(n-1):
    for j in range(i+2, n):
        if j < x or i > y:
            dist = j-i
        else:
            dist = min([j - i, abs(x-i) + 1 + abs(y-j), abs(y-i) + 1 + abs(x-j)])
        final[dist-1] += 1 
final[0] = n
res = [str(one) for one in final]
print ("\n".join(res))
### BUGGY CODE ###

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

while (len(l) < N):
  tmp  = ['b' for i in range(A) if (len(l) + i) < N]
  tmp2 = ['r' for i in range(B) if (len(l) + len(tmp) + i) < N]
  l += (tmp + tmp2)

print(l.count('b'))


### FIXED CODE ###


N, A, B = map(int, input().split())
out = N // (A + B) * A
rem = min(N % (A + B), A)
print(out + rem)
### BUGGY CODE ###

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

cand = set(a)

exist = set()
dup = set()
for item in a:
    if item in exist:
        dup.add(item)
    else:
        exist.add(item)

dame_set = set()

a.sort()
ret = 0

for val in a:
    if val in dup:
        i = 1
        cnt = 10 ** 6 // val
        while i <= cnt:
            dame_set.add(i * val)
            i += 1
    else:
        if val in dame_set:
            continue
        else:
            ret += 1
            i = 1
            cnt = 10 ** 6 // val
            while i <= cnt:
                dame_set.add(i * val)
                i += 1

print(ret)


### FIXED CODE ###

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

cand = set(a)

exist = set()
dup = set()
for item in a:
    if item in exist:
        dup.add(item)
    else:
        exist.add(item)

dame_set = set()

a.sort()
ret = 0

for val in a:
    if val in dup:
        if val in dame_set:
            continue
        else:
            i = 1
            cnt = 10 ** 6 // val
            while i <= cnt:
                tmp = i * val
                if tmp in cand:
                    dame_set.add(tmp)
                i += 1
    else:
        if val in dame_set:
            continue
        else:
            ret += 1
            i = 1
            cnt = 10 ** 6 // val
            while i <= cnt:
                tmp = i * val
                if tmp in cand:
                    dame_set.add(tmp)
                i += 1

print(ret)
### BUGGY CODE ###

import collections
n=int(input())
s=sorted([input() for k in range(n)])
if(len(set(s))==len(s)):
    for u in range(len(s)):
        print(s[u])
    exit()
else:
    s1=[q for q in sorted(list(set(s))) if s.count(q) > 1]
c=collections.Counter(s)
p=[]
for i in s1:
    p.append(c[i])
max=max(p)
for j, x in enumerate(p):
    if(x == max):                                                                                             print(s1[j])

### FIXED CODE ###

N = int(input())
d = {}
for _ in range(N):
  s = input()
  if(s not in d):
    d[s] = 1
  else:
    d[s] += 1
d2 = sorted(d.items(),key=lambda x:x[1], reverse=True)
s1=[]
s1.append(d2[0][0])
p=d2[0][1]
for t in d2[1:]:
  q=t[1]
  if(q==p):
    s1.append(t[0])
  else:
    break
s1=sorted(s1)
for i in s1:
  print(i)
### BUGGY CODE ###

T = int(input())
ABCD = [list(map(int,input().split())) for _ in range(T)]

for a,b,c,d in ABCD:
    if a < b:
        print('No')
        continue
    if d < b:
        print('No')
        continue
    tmp = a % b
    if tmp > c:
        print('No')
        continue
    if d % b == 0:
        print('Yes')
        continue
    if c >= b-1:
        print('Yes')
        continue
    if a%2 == 0 and b%2 == 0 and d %2 == 0 and b-c == 2:
        print('Yes')
        continue

    dp = [a]
    now = a
    for _ in range(c+2):
        if now < b:
            print('No')
            break
        now %= b
        if now in dp:
            print('Yes')
            break
        if now > c:
            print('No')
            break
        dp.append(now)
        now += d




    

### FIXED CODE ###

#from math import gcd
from fractions import gcd
T = int(input())
ABCD = [list(map(int,input().split())) for _ in range(T)]

for a,b,c,d in ABCD:
    if a < b:
        print('No')
        continue
    if d < b:
        print('No')
        continue
    tmp = a % b
    if tmp > c:
        print('No')
        continue
    if d % b == 0:
        print('Yes')
        continue
    if c >= b-1:
        print('Yes')
        continue
    if a%2 == 0 and b%2 == 0 and d %2 == 0 and b-c == 2:
        print('Yes')
        continue
    GCD = gcd(b,d)
    if b-GCD +(a%GCD) > c:
        print('No')
    else:
        print('Yes')
### BUGGY CODE ###

s=input()
n=int(input())
cnt=0
for _ in range(n):
    tmp=input()
    if tmp[0]=="1":
        cnt+=1
    else:
        num,side,st=tmp.split()
        if side=="1":
            if cnt%2==0:
                s=st+s
            else:
                s=s+st
        else:
            if cnt%2==0:
                s=s+st
            else:
                s=st+s
if cnt%2==1:
    s=s[::-1]
print(s)

### FIXED CODE ###

s=input()
n=int(input())
cnt=0
left=[]
right=[]
for _ in range(n):
    tmp=input()
    if tmp[0]=="1":
        cnt+=1
    else:
        num,side,st=tmp.split()
        if side=="1":
            if cnt%2==0:
                left.append(st)
            else:
                right.append(st)
        else:
            if cnt%2==0:
                right.append(st)
            else:
                left.append(st)
left="".join(left)
left=left[::-1]
right="".join(right)
s=left+s+right
if cnt%2==1:
    s=s[::-1]
print(s)
### BUGGY CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]

n = INT()
a = LIST()
l = 1
for i in range(n):
    l = lcm(l, a[i])
ans = 0
for i in range(n):
    ans += l // a[i]
    ans %= mod
print(ans)

### FIXED CODE ###

import sys
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def LIST(): return list(map(int, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]

n = INT()
a = LIST()
l = 1
for i in a:
    l = lcm(l, i)
l %= mod
ans = 0
for i in a:
    ans += l * pow(i, mod - 2, mod)
print(ans % mod)
### BUGGY CODE ###

import sys

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prl = lambda x: print(*x ,sep='\n')

s = ns()
ans = 0
for i in range(len(s)-3):
    for j in range(i+3,len(s)):
        ain = int(s[i:j+1]) % 2019 == 0
        if ain:
            ans += 1

print(ans)

### FIXED CODE ###

import sys
from collections import defaultdict as de


readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prl = lambda x: print(*x ,sep='\n')

s = ns()
digit = 1
ans = 0
num = 0
amari = de(int)
amari[0] = 1
"""
大筋のやり方は
https://drken1215.hatenablog.com/entry/2020/04/29/171300
を参照。

「この下のfor文について」
1211400を考える。
1万の桁を考えるとき
digit = 10000
digit = 1924 mod 2019
11400 = 10000 + 1400 = 1924 + 1400 = ans mod 2019
つまり、ある桁までの2019のあまりはその一つ下の桁までのあまりと
その桁の数*桁のあまりを足したもののあまりである
"""

for i in s[::-1]:
    num = num + int(i) * digit
    num %= 2019
    digit *= 10
    digit %= 2019
    amari[num] += 1

for j in amari.values():
    ans += j*(j-1)//2

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

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

P = [[] for _ in range(ord('Z') - ord('A') + 1)]
for i in range(N):
  p = ord(S[i]) - ord('A')
  P[p].append(i)

dG = [0 for _ in range(N)]
G = [1 for _ in range(N)]
for i in range(Q):
  t,d = input().split()
  ti = ord(t) - ord('A')
  
  for j in P[ti]:
    g = G[j]
    G[j] = 0
    dG[j] = g
  for j in P[ti]:
    dg = dG[j]
    if ('L' == d):
      if (0 < j):
        G[j-1] += dg
    elif ('R' == d):
      if (j < (N-1)):
        G[j+1] += dg
print(sum(G))


### FIXED CODE ###

N,Q = map(int, input().split())
S = input()
C = [tuple(map(str, input().split())) for _ in range(Q)]
C = C[::-1]

left = -1
right = N

for (t,d) in C:
  if ('L' == d):
    if (S[left+1] == t):
      left += 1
      if (N-1 <= left):
        print(0)
        exit()
    if (right < N):
      if (S[right] == t):
        right += 1
        if (N < right):
          right = N
  else:
    if (S[right-1] == t):
      right -= 1
      if (right <= 0):
        print(0)
        exit()
    if (-1 < left):
      if (S[left] == t):
        left -= 1
        if (left < -1):
          left = -1

print(right - left - 1)
### BUGGY CODE ###

n = int(input().strip())
a = list(map(int, input().split()))
left = {}
for i in range(len(a)):
    if left.get(a[i] + i):
        left[a[i] + i].append(i)
    else:
        left[a[i] + i] = [i]
ans = 0
for i in range(len(a)):
    if left.get(i - a[i]):
        ans += len(list(filter(lambda x: x < i, left[i - a[i]])))
print(ans)


### FIXED CODE ###

n = int(input().strip())
a = list(map(int, input().split()))
dic = {}
ans = 0
for i in range(len(a)):
    if dic.get(i - a[i]):
        ans += dic[i - a[i]]
    if dic.get(a[i] + i):
        dic[a[i] + i] += 1
    else:
        dic[a[i] + i] = 1
print(ans)
### BUGGY CODE ###

import heapq
def SME(start,end):
    if end > N : end = N
    count = 0
    for i,x in enumerate(Whole[start:end]):
        heapq.heappush(A,[x,i])
    for j in range(start,end):
        a = heapq.heappop(A)
        if None not in ANS[a[1]:a[1]+L] : continue
        for i in range(L):
            idx = a[1] + i
            try :
                if ANS[idx] : continue
                else :
                    ANS[idx] = a[0]
                    count += 1
            except IndexError : continue
        if count > N * parameter : break
    for i in range(L):
        if ANS[i] : continue
        else : ANS[i] = min(Whole[:i+1])
    while i < N :
        if None not in ANS[i:i+L//2] :
            i += L//2
            continue
        if ANS[i] : continue
        else: ANS[i] = min(Whole[i+1-L:i+1])
        i+=1
    return ANS
[N,L] = [int(x) for x in input().split()]
Whole = [int(x) for x in input().split()]
A = []
parameter = 0.999
ANS = [None]*N
ANS = SME(0, N)
for i in ANS[L-1:-1]:print(i, end=" ")
print(ANS[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

import math

k = int(input())

a = []

s = str(k)
flg = 0

for i in range(1, 1000000):
    n = math.floor(math.log10(i))
    s = str(i)
    cnt = 0

    if n < 1:
        a.append(i)
    else:
        for j in range(n):
            if abs(int(s[j]) - int(s[j + 1])) <= 1:
                cnt += 1
            if cnt == n:
                a.append(i)

    if len(a) == k:
        print(a[k - 1])
        break


### FIXED CODE ###

from collections import deque

k = int(input())

q = deque(range(1, 10))

for i in range(k):
    t = q.popleft()

    if t % 10 != 0:
        q.append(10 * t + t % 10 - 1)

    q.append(10 * t + t % 10)

    if t % 10 != 9:
        q.append(10 * t + t % 10 + 1)
 
print(t)
### BUGGY CODE ###

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


def comb(x, y):
    return math.factorial(x) // (math.factorial(x-y) * math.factorial(y))


count = 0
for i in range(1, n+1):
    if i == a:
        continue
    if i == b:
        continue
    elif i != a or i != b:
        count += comb(n, i)

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

### FIXED CODE ###

n, a, b = map(int, input().split())
mod = 10**9 + 7


def comb(n, r):
    res = 1
    for i in range(1, r+1):
        res = res*(n-i+1) % mod
        res = res*pow(i, mod-2, mod) % mod
    return res


ans = pow(2, n, mod) - 1
ans = (ans - comb(n, a)) % mod
ans = (ans - comb(n, b)) % mod
print(ans)
### BUGGY CODE ###

def makerectangle(n , a):

    listmax = []
    a.sort(reverse=True)
    for i in range(n):
        if a.count(a[i]) > 1 and listmax.count(a[i]) == 0:
            if a.count(a[i]) > 3 and len(listmax) == 0:
                return a[i] * a[i]
            else:
                listmax.append(a[i])
        if len(listmax) > 1:
            return listmax[0] * listmax[1]
    return 0



def main():
    n = int(input())
    a = list(map(int,input().split()))
    print(makerectangle(n , a))

if __name__ == '__main__':
    main()

### FIXED CODE ###

def makerectangle(n , a):

    listmax = []
    a.sort(reverse=True)
    for i in range(n):
        if len(a) > i + 1 and a[i] == a[i + 1] and listmax.count(a[i]) == 0:
            if len(a) > i + 3 and a[i] == a[i + 3] and len(listmax) == 0:
                return a[i] * a[i]
            else:
                listmax.append(a[i])
        if len(listmax) > 1:
            return listmax[0] * listmax[1]
    return 0


def main():
    n = int(input())
    a = list(map(int,input().split()))
    print(makerectangle(n , a))

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

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

MOD = 10**9 + 7
import itertools

ans = 0
Cmb = itertools.combinations(A, 2)
for cmb in Cmb:
    ans = (ans + cmb[0]*cmb[1]%MOD)%MOD
print(ans%MOD)

### FIXED CODE ###

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

import numpy
A_CS = numpy.cumsum(sorted(A, reverse=True))
A_CS = A_CS%MOD

A = sorted(A)

#print(A_CS)
ans = 0
for i in range(n-1):
#    print(A[i], A_CS[-i-2])
#    A_CS -= A[i]
    ans = (ans+(A[i]*A_CS[-i-2])%MOD)%MOD
print(ans)
### BUGGY CODE ###

N, W = map(int, input().split())
w = [0] * N
v = [0] * N
for i in range(N):
    w[i], v[i] = map(int, input().split())

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

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

print(max(dp[N]))


### FIXED CODE ###

dp = [[0] * 100100 for i in range(110)]

N, W = map(int, input().split())
w = [0] * N
v = [0] * N
for i in range(N):
    w[i], v[i] = map(int, input().split())

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

print(dp[N][W])
### BUGGY CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
b = ['' for i in range(n)]
maxd = len(bin(10 ** 12))-2
bink = bin(k)[2:]
digitk = len(bink)
bink = bink.zfill(maxd)[::-1]
#print(bink)
for i in range(n):
    b[i] = format(a[i], 'b').zfill(maxd)[::-1]
#print(b)

s = [0 for i in range(maxd)]

for i in range(digitk):
    for j in range(i):
        count = sum(list(map(lambda x: int(x[j]), b)))
        if count <= n//2:
            s[i] += (n - count) * 2 ** j
        else:
            s[i] += count * 2 ** j

    count = sum(list(map(lambda x: int(x[i]), b)))
    s[i] += count * 2 ** i

    for j in range(i+1, maxd):
        count = sum(list(map(lambda x: int(x[j]), b)))
        if int(bink[j]) == 0:
            s[i] += count * 2 ** j

        else:
            s[i] += (n-count) * 2 ** j

print(max(s))


### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
b = ['' for i in range(n)]
maxd = len(bin(10 ** 12 + 1))-2
bink = bin(k)[2:]
digitk = len(bink)
bink1 = bin(k+1)[2:]
digitk1 = len(bink1)
bink = bink.zfill(maxd)[::-1]
bink1 = bink1.zfill(maxd)[::-1]
for i in range(n):
    b[i] = format(a[i], 'b').zfill(maxd)[::-1]
#print(b)

s = [0 for i in range(maxd)]
c = [0 for i in range(maxd)]
for i in range(maxd):
    c[i] = sum(list(map(lambda x: int(x[i]), b)))
for i in range(digitk1):
    if bink1[i] == '1':
        for j in range(i):
            if c[j] <= n/2:
                s[i] += (n-c[j]) * 2 ** j
            else:
                s[i] += c[j] * 2 ** j

        s[i] += c[i] * 2 ** i

        for j in range(i+1, digitk1):
            if bink1[j] == '1':
                s[i] += (n-c[j]) * 2 ** j
            else:
                s[i] += c[j] * 2 ** j

    for j in range(digitk1, maxd):
        s[i] += c[j] * 2 ** j
print(max(s))
### BUGGY CODE ###

import math

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

max = 0
for i in range(N+1):
    value = math.floor(A*i/B) - A*math.floor(i/B)
    if value > max:
        max=value
print(max)


### FIXED CODE ###

import math

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

def f(x):
    return math.floor(A*x/B) - A*math.floor(x/B)
print(f(min(N,B-1)))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
# 
import math
import sys
import itertools
import numpy as np
import bisect

# いっこ入力
n =int(input())

# n行の数をリストへ
a = [int(input()) for i in range(n)] 

# color
c = [a[0]]

for i in range(1,n):
#    print(c)
    p = bisect.bisect_left(c, a[i])
#    print(p)
    if p ==0:
        c.insert(0,a[i])
    else:
        c[p-1]=a[i]
        c.sort()

print(len(c))


### FIXED CODE ###

# -*- coding: utf-8 -*-
# 
import math
import sys
import bisect

# いっこ入力
n =int(input())

# n行の数をリストへ
a = [int(input()) for i in range(n)] 

# color
c = [-999]*n

for i in range(0,n):
#    if c[0] >= a[i]:
#        c.insert(0,a[i])
#    else:
    p = bisect.bisect_left(c, a[i])
    c[p-1]=a[i]
#        print(c)
#        print(p)

print(len(c) - bisect.bisect_left(c, -1))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)

s = input()
t = input()

dp = [[0]*(len(t)+1) for i in range(len(s)+1)]

for i in range(1,len(s)+1):
  for j in range(1,len(t)+1):
    dp[i][j] = max(dp[i-1][j-1],dp[i][j-1])
    if s[i-1] == t[j-1]:
      dp[i][j] += 1

ansl = []
cnt = dp[-1][-1]
def tami(i,j):
  global cnt
  if cnt == 0:
    return
  if s[i-1] == t[j-1]:
    cnt -= 1
    ansl.append(i-1)
  if dp[i-1][j-1]==cnt:
    tami(i-1,j-1)
  elif dp[i][j-1]==cnt:
    tami(i,j-1)

tami(len(s),len(t))

ans = ""
for i in ansl:
  ans += s[i]
print(ans[::-1])

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)

s = input()
t = input()

dp = [[0]*(len(t)+1) for i in range(len(s)+1)]

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

ansl = []
cnt = dp[-1][-1]
def tami(i,j):
  global cnt
  if cnt == 0:
    return
  if s[i-1] == t[j-1]:
    cnt -= 1
    ansl.append(i-1)
  if dp[i-1][j-1]==cnt:
    tami(i-1,j-1)
  elif dp[i][j-1]==cnt:
    tami(i,j-1)
  elif dp[i-1][j]==cnt:
    tami(i-1,j)

tami(len(s),len(t))

ans = ""
for i in ansl:
  ans += s[i]
print(ans[::-1])
### BUGGY CODE ###

s = input()
q = int(input())
#queries = []
for _ in range(0, q):
    query = input()
    if len(query) == 1:
 #       queries.append([int(query)])
        s = s[::-1]
    else:
        query = query.split(' ')
        query = [int(query[0]), int(query[1]), query[2]]
#        queries.append(query)
        if query[1] == 1:
            s = query[2] + s
        else:
            s = s + query[2]



#for i in range(0, q):
#    if queries[i][0] == 1:
#        s = s[::-1]
#    else:
#        if queries[i][1] == 1:
#            s = queries[i][2] + s
#        else:
#            s = s + queries[i][2]

print(s)

### FIXED CODE ###

#import sys
#input = sys.stdin.readline

def main():
    s = input()
    q = int(input())
    is_rev = False
    l = ''
    r = ''
    for _ in range(0, q):
        query = input()
        if len(query) == 1:
            is_rev = not is_rev
        else:
            query = query.split(' ')
            query = [int(query[0]), int(query[1]), query[2]]
            if (query[1] == 1 and is_rev) or (query[1] == 2 and not is_rev):
#                s = s + query[2]
                r += query[2]
            else:
#                s = query[2] + s
                l += query[2]
    if is_rev:
        print(r[::-1] + s[::-1] + l)
    else:
        print(l[::-1] + s + r)

main()
### BUGGY CODE ###

n = int(input())
print(sum(range(n)))



### FIXED CODE ###

n = int(input())
print(n * (n - 1) // 2)