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


import sys
input = sys.stdin.readline
#区間の管理は　[a, b)で管理していることに注意

# INT_MIN = -10 ** 18
# MAX_N = 4 * 10 ** 5
# MAX_N = 20


# def init(n_):
#     #簡単にするために2のべき乗に揃える
#     n = 1
#     while n <= n_:
#         n *= 2
#     return n

#初期化
N = int(input())
n = 1
while n <= N:
    n *= 2

data = [0] * (2 * n - 1)

def update(k, a):
    k += n - 1
    data[k] = a
    while k > 0:
        data[k] = max(a, data[k])
        k = (k - 1) // 2
        # data[k] = max(data[2 * k + 1], data[2 * k + 2])

def query(a, b, k = 0, l = 0, r = n):
    if r <= a or b <= l:
        return 0
    elif a <= l and r <= b:
        return data[k]
    else:
        return max(query(a, b, 2 * k + 1, l, (l + r)//2), query(a, b, 2 * k + 2, (l + r)//2, r))

H = tuple(map(int, input().split()))
A = tuple(map(int, input().split()))

# ans = 0
for i in range(N):
    # h = int(input())
    # a = int(input())
    h = H[i]
    a = A[i]
    tmp = query(1, h + 1) #[1, h)での最大値
    # print (h, tmp)
    update(h, tmp + a)
    # ans = max(ans, tmp + a)
    # print (data)

print (query(1, N + 1))

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    #区間の管理は　[a, b)で管理していることに注意

    # INT_MIN = -10 ** 18
    # MAX_N = 4 * 10 ** 5
    # MAX_N = 20


    # def init(n_):
    #     #簡単にするために2のべき乗に揃える
    #     n = 1
    #     while n <= n_:
    #         n *= 2
    #     return n

    #初期化
    N = int(input())
    # n = 1
    # while n <= N:
    #     n *= 2

    n = 262144
    data = [0] * (2 * n - 1)

    def update(k, a):
        k = k + n - 1
        # data[k] = a
        while k >= 0:
            data[k] = max(a, data[k])
            k = (k - 1) // 2
            # data[k] = max(data[2 * k + 1], data[2 * k + 2])

    def query(a, b, k, l, r):
        if r <= a or b <= l:
            return 0
        elif a <= l and r <= b:
            return data[k]
        else:
            return max(query(a, b, 2 * k + 1, l, (l + r)//2), query(a, b, 2 * k + 2, (l + r)//2, r))

    H = tuple(map(int, input().split()))
    A = tuple(map(int, input().split()))

    # ans = 0

    dp = [A[0]] + [0] * (N - 1)
    update(H[0] - 1, A[0])
    for i in range(1, N):
        # h = int(input())
        # a = int(input())
        dp[i] = query(0, H[i] - 1, 0, 0, n) + A[i]
        # h = H[i]
        # a = A[i]
        # tmp = query(1, h + 1) #[1, h)での最大値
        # print (h, tmp)
        update(H[i] - 1, dp[i])
        # ans = max(ans, tmp + a)
        # print (data)

    print (query(0, N, 0, 0, n))

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

def mod_power(a, f_power):
    """
    a の p 乗を求めるアルゴリズム
    計算量はO(log(f_power))
    """
    if f_power == 0:
        return 1
    if f_power % 2 == 0:
        half = mod_power(a, f_power / 2)
        # half : a ** (power /2) の 2乗で a ** power を求める
        return half * half % MOD
    else:
        return a * mod_power(a, f_power - 1) % MOD


def comb(a, b):
    if b > a - b:
        return comb(a, a - b)
    # res = 1
    mul = 1
    div = 1
    for i in range(b):
        # res *= (a - i)
        # res /= (i + 1)
        mul *= (a - i)
        mul %= MOD

        div *= (i + 1)
        div %= MOD
    res = mul * mod_power(div, MOD - 2) % MOD
    return res


def prime_factorization(x):
    res = []
    i = 2
    left = x + 0
    while True:
        if (i * i > x) and (left == 1):
            break
        cnt = 0
        while left % i == 0:
            left /= i
            cnt += 1
        if cnt > 0:
            res.append(cnt)
        # print(i, res)
        i += 1
    return res


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

MOD = 10 ** 9 + 7

ans = 1
for power in prime_factorization(m):
    ans *= comb(n - 1 + power, power)
ans %= MOD

print(ans)
# print(prime_factorization(6))

### FIXED CODE ###

MOD = 10 ** 9 + 7


def prime_factorization(n):
    i = 2
    res = []
    while i * i <= n:
        cnt = 0
        while n % i == 0:
            n /= i
            cnt += 1
        if cnt > 0:
            res.append(cnt)
        i += 1
    if n > 1:
        res.append(1)
    return res


def comb(a, b):
    b = min(b, a - b)
    if b < 0:
        return 0
    elif b == 0:
        return 1
    elif b == 1:
        return a
    else:
        return (a % MOD) * pow(b, MOD - 2, MOD) % MOD * comb(a - 1, b - 1) % MOD


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

ans = 1
for power in prime_factorization(M):
    ans *= comb(N - 1 + power, power)
    ans %= MOD

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

n, m = map(int,input().split())
a = list(map(int,input().split()))
b = [0]*m
c = [0]*m
for y in range(m):
    b[y], c[y] = map(int,input().split())
for x in range(m):
    for y in range(b[x]):
        if c[x] <= min(a):
            break
        aj = a.index(min(a))
        a[aj] = c[x]
        
print(sum(a))

### FIXED CODE ###

n, m = map(int,input().split())
a = list(map(int,input().split()))
bc = [list(map(int, input().split())) for _ in range(m)]
bc.sort(reverse=True, key=lambda x:x[1])
tmp = []
for B, C in bc:
    tmp += [C]*B
    if len(tmp) >= n:
        break

a.extend(tmp)
a.sort(reverse=True)

print(sum(a[:n]))
### BUGGY CODE ###

from heapq import heappop, heappush, heapify
from collections import deque
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
A = [int(i) for i in input().split()]
S = []
for i in range(M):
  B,C = map(int, input().split())
  for j in range(B):
    heappush(S,-C)
A.sort()
i = 0
l = len(S)
while i < min(N,l):
  q = -1*heappop(S)
  if A[i] < q:
    A[i] = q
    i += 1
  else:
    break
print(sum(A))

### FIXED CODE ###

N, M = map(int, input().split())
A = [int(i) for i in input().split()]
table = []
for i in range(N):
  table.append((A[i],1))
for i in range(M):
  b,c = map(int, input().split())
  table.append((c,b))
table.sort()
count = 0
ans = 0
while True:
  c, b = table.pop()
  if b <= N - count:
    ans += c*b
    count += b
  else:
    ans += (N-count)*c
    break
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
N, K = map(int, input().split())
A = list(map(int, input().split()))

score = [1] * (N-K+1)
for i in range(K, N+1):
  if i == K:
    for j in range(K):
      score[0] *= A[j]
    continue
    
  score[i-K] = (score[i-K-1] // A[i-K-1]) * A[i-1]
  if score[i-K] > score[i-K-1]:
    print('Yes')
  else:
    print('No')

### FIXED CODE ###

# -*- coding: utf-8 -*-
N, K = map(int, input().split())
A = list(map(int, input().split()))

for i in range(K, N):
  if A[i] > A[i-K]:
    print('Yes')
  else:
    print('No')
### BUGGY CODE ###

from fractions import gcd
n,m=map(int,input().split())
s=input()
t=input()
p=gcd(n,m)
ans=n*m//p
tt=[0 for _ in range(ans)]
for i in range(n):
	tt[i*(ans//n)]=s[i]
for i in range(m):
	if tt[i*(ans//m)]!=t[i] and tt[i*(ans//m)]!=0:
		print(-1)
		exit()
print(ans)


### FIXED CODE ###

from fractions import gcd
n,m=map(int,input().split())
s=input()
t=input()
p=gcd(n,m)
ans=n*m//p 
for i in range(n):
	if abs((i*(ans//n)/(ans//m))-int(i*(ans//n)/(ans//m)))<=10**(-7):
		if s[i]==t[(i*(ans//n)//(ans//m))]:
			continue
		else:
			print(-1)
			exit()
print(ans)
### BUGGY CODE ###

import fractions
from functools import reduce

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

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)
K = int(input())

count=0
for i in range(1, K+1):
  for j in range(i, K+1):
    for k in range(j, K+1):
      if i == j and j == k:
        kake = 1
      elif i == j or j == k or i == k:
        kake = 3
      else:
        kake = 6
      count += gcd(i, j, k) * kake

print(count)

### FIXED CODE ###

def euclid(a, b):
    while b:
        a, b = b, a%b
    return a
  
K = int(input())

count=0
for i in range(1, K+1):
  for j in range(i, K+1):
    for k in range(j, K+1):
      if i == j and j == k:
        kake = 1
      elif i == j or j == k or i == k:
        kake = 3
      else:
        kake = 6
      count += euclid(euclid(i, j), k) * kake

print(count)
### BUGGY CODE ###

def judge(a, b):
    if a+b <= 9:
        return a+b
    return a+b-9

n = int(input())
ans = 0
key = 0
for i in range(n):
    a, b = map(int, input().split())
    if a == 0:
        ans += b
        continue
    for j in range(b):
        if key + a <= 9:
            ans += 1
        else:
            ans += 2
        key = judge(key, a)
print(ans-1)

### FIXED CODE ###

n = int(input())
d, c = 0, 0

for i in range(n):
    p, q = map(int, input().split())
    d = d + q
    c = c + p*q

print((d-1)+(c-1)//9)
### BUGGY CODE ###

n = int(input())
sl =[]
ans = 0
for i in range(n):
    s = sorted(input())
    ans+=sl.count(s)
    sl.append(s)
print(ans)


### FIXED CODE ###

n = int(input())
sl ={}
ans = 0
for i in range(n):
    s = ''.join(sorted(input()))
    if s in sl:
        sl[s] +=1
    else:
        sl[s] =1
for i in sl.values():
    ans += i*(i-1)/2
print(int(ans))
### BUGGY CODE ###

import sys
from fractions import Fraction

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

def a(s):
	r = Fraction(s)
	return r.numerator, r.denominator



def main():
	n = int(input())
	#b , c = tin()
	al = [a(input()) for _ in range(n)]
	ret = 0
	for i, (vin, vid) in enumerate(al):
		for (vjn, vjd) in al[i+1:]:
			if (vin*vjn) % (vid* vjd)==0:
				ret += 1
	return ret
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

### FIXED CODE ###

import sys
#from fractions import Fraction
import collections

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

def a(s):
	if s.count('.')==0:
		n2=0
		n5=0
		v = int(s)
	else:
		p = s.index('.')
		n2 = -(len(s) - p - 1)
		n5 = -(len(s) - p - 1)
		if p == 1 and s[0]=='0':
			v= int(s[2:])
		else:
			v = int(s[:p]+s[p+1:])
	while v % 2 == 0:
		v = v//2
		n2+=1
	while v % 5 == 0:
		v = v//5
		n5+=1
	return str(n2)+'_'+str(n5)

def main():
	n = int(input())
	#b , c = tin()
	al = [a(input()) for _ in range(n)]
	cal = collections.Counter(al)
	#pa(cal)
	ret = 0
	pp = set()
	for k in cal:
		for k2 in cal:
			if k+'_'+k2 in pp:
				continue
			#pa((vi*vj)/(10**20))
			if k==k2:
				a2, a5 = map(int, k.split('_'))
				if a2>=0 and a5 >= 0:
					ret += cal[k]*(cal[k]-1)//2
			else:
				a2, a5 = map(int, k.split('_'))
				b2, b5 = map(int, k2.split('_'))
				if a2+b2 >= 0 and a5+b5 >= 0:
					ret += cal[k]*cal[k2]
				
			pp.add(k+'_'+k2)
			pp.add(k2+'_'+k)
			#pa((k,k2,ret))
			
	return ret
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)
### BUGGY CODE ###

import sys
input = sys.stdin.readline


N, K = map(int, input().split())
A = list(map(int, input().split()))
A_unique = list(set(A))
A_list = []
if len(A_unique) <= K:
    print(0)
    exit()
else:
    del_num = len(A_unique) - K
    for i in A_unique:
        A_list.append(A.count(i))
    A_list.sort()
    print(sum(A_list[:del_num]))

### FIXED CODE ###

import sys
input = sys.stdin.readline
from collections import Counter


N, K = map(int, input().split())
A = list(map(int, input().split()))
A_count = Counter(A)
A_unique = list(set(A))
A_list = []
if len(A_unique) <= K:
    print(0)
    exit()
else:
    del_num = len(A_unique) - K
    for i in A_unique:
        A_list.append(A_count[i])
    A_list.sort()
    print(sum(A_list[:del_num]))
### BUGGY CODE ###

def main():
    from collections import deque
    import sys
    input = sys.stdin.readline
    H, W = (int(i) for i in input().split())
    c = [[s for s in input()] for i in range(H)]

    def bfs(c, sy, sx, H, W):
        que = deque()
        dist = [[-1]*W for i in range(H)]

        dist[sy][sx] = 0
        que.append((sy, sx))
        d = ((1, 0), (0, 1), (-1, 0), (0, -1))
        ret = 0
        flag = False  # 黒色マスにいるとき，True
        while que:
            uh, uw = que.popleft()
            if c[uh][uw] == "#":
                flag = True
            else:
                flag = False
            for dy, dx in d:
                next_h = uh + dy
                next_w = uw + dx
                if not(0 <= next_h < H and 0 <= next_w < W):
                    continue
                if dist[next_h][next_w] != -1:
                    continue
                if flag and c[next_h][next_w] == '#':
                    continue
                if not flag and c[next_h][next_w] == ".":
                    continue
                dist[next_h][next_w] = dist[uh][uw] + 1
                if c[next_h][next_w] == ".":
                    ret += 1
                que.append((next_h, next_w))
        return ret

    ans = 0
    for h in range(H):
        for w in range(W):
            if c[h][w] == "#":
                ans += bfs(c, h, w, H, W)
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    from collections import deque
    H, W = (int(i) for i in input().split())
    c = [input() for i in range(H)]
    seen = [[False]*W for _ in range(H)]
    que = deque()
    for h in range(H):
        for w in range(W):
            if c[h][w] == "#":
                que.append((h, w))

    def bfs(sy, sx):
        que = deque()
        que.append((sy, sx))
        d = ((1, 0), (0, 1), (-1, 0), (0, -1))
        flag = True  # Trueなら黒マス
        bla = 0
        whi = 0
        while que:
            uh, uw = que.popleft()
            if seen[uh][uw]:
                continue
            if c[uh][uw] == "#":
                flag = True
                bla += 1
                seen[uh][uw] = True
            else:
                flag = False
                whi += 1
                seen[uh][uw] = True
            for dy, dx in d:
                next_h = uh + dy
                next_w = uw + dx
                if not(0 <= next_h < H and 0 <= next_w < W):
                    continue
                if seen[next_h][next_w]:
                    continue
                if flag and c[next_h][next_w] == '#':
                    continue
                if not(flag) and c[next_h][next_w] == '.':
                    continue
                que.append((next_h, next_w))
        return whi*bla

    ans = 0
    for q in que:
        if seen[q[0]][q[1]]:
            continue
        ans += bfs(q[0], q[1])
    print(ans)


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

if __name__ == '__main__':
    import sys
    input = sys.stdin.readline


    nn = int(input())
    x = input()

    ans = 0
    def make_divisors(n):
        divisors = []
        for i in range(1, int(n**0.5)+1):
            if n % i == 0:
                if i % 2 != 0:
                    divisors.append(i)
                if i != n // i and (n//i)%2 != 0:
                    divisors.append(n//i)

        divisors.sort(reverse = True)
        return divisors

    fact_n = make_divisors(nn)

    used = {}

    ans = 0

    for i in fact_n:
        num_len = int(nn/i)
        can_divide = int(x[:num_len], 2)+1
        for key, value in used.items():
            if num_len%key == 0:
                can_divide -= value
        if int(x) < int((x[:num_len] + format(2**num_len-1-int(x[:num_len],2), 'b'))*int((i-1)/2)+x[:num_len]):
            can_divide -= 1
        used[num_len] = can_divide
        ans += can_divide*num_len*2


    print(ans%998244353)


### FIXED CODE ###

if __name__ == '__main__':
    import sys
    input = sys.stdin.readline


    nn = int(input())
    x = input()

    ans = 0
    def make_divisors(n):
        divisors = []
        for i in range(1, int(n**0.5)+1):
            if n % i == 0:
                if i % 2 != 0:
                    divisors.append(i)
                if i != n // i and (n//i)%2 != 0:
                    divisors.append(n//i)

        divisors.sort(reverse = True)
        return divisors

    fact_n = make_divisors(nn)

    used = {}

    ans = 0

    for i in fact_n:
        num_len = int(nn/i)
        base = x[:num_len]
        can_divide = int(base, 2)+1
        for key, value in used.items():
            if num_len%key == 0:
                can_divide -= value
        if x < (base + format(2**num_len-1-int(base,2), 'b').zfill(num_len))*int((i-1)/2)+base:
            can_divide -= 1
        used[num_len] = can_divide
        ans += can_divide*num_len*2
        ans = ans%998244353


    print(ans%998244353)
### BUGGY CODE ###

L, R = map(int, input().split())

min_num = 2019

for i in range(L, R):
    for s in range(i+1, R+1):
        if (i*s)%2019 < min_num:
            min_num = (i*s)%2019

print(min_num)

### FIXED CODE ###

L, R = map(int, input().split())

mod_list = []
min1 = 2019
min2 = 2019

if (R - L) > 2019:
    print(0)

else:
    for i in range(L, R):
        for s in range(i+1, R+1):
            if (i*s)%2019 <= min1:
                min1 = (i*s)%2019
    print(min1)
### BUGGY CODE ###

import sys
import os
from bisect import bisect_left
def index(a, x):
    i = bisect_left(a,x)
    if i != len(a) and a[i] == x:
        return True
    return False

R, G, B, N = map(int,input().split())
listB = [ i for i in range(N//B+1) ]
cnt = 0
for r in range(N//R+1):
    for g in range(N//G+1):
        if index(listB,(N - R*r - G*g)/B):
            cnt += 1
print(cnt)


### FIXED CODE ###

*j, N = map(int,input().split())
j.sort()
a,b,c = j
cnt = 0
for r in range(N//b+1):
    for g in range((N-b*r)//c+1):
        v = b*r+c*g
        if (N-v)%a == 0:
            cnt += 1
print(cnt)
### BUGGY CODE ###

n = int(input())
a = []
for _ in range(n):
	a.append(int(input()))

for i in range(n):
	b = set(a[:i]+a[i+1:])
	print(max(b))

### FIXED CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
m = max(a)

k = [i for i, x in enumerate(a) if x == m]

if len(k)>=2:
	for i in a:
		print(m)
else:
	b = []
	b += a
	mi = b.index(m)
	b.pop(mi) 
	m2 = max(b)
	for i in a:
		if i != m:
			print(m)
		else:
			print(m2)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
a.sort(reverse=True)
c=0
for i in range(len(a)):
  for j in range(len(a)):
    d=0
    if i==n-1-j:
      continue
    elif a[i]%a[n-1-j]==0:
      d+=1
      break
  if d==0:
     c+=1
print(c)  

### FIXED CODE ###

n=int(input())
A=list(map(int,input().split()))
dp=[0]*(10**6+1)
for i in A:
  dp[i]+=1
for i in range(1,10**6+1):
  if dp[i]>0:
    for j in range(2*i,10**6+1,i):
      dp[j]=0
print(dp.count(1))
### BUGGY CODE ###

def solve():
  n,t = (int(i) for i in input().split())
  a = list(int(i) for i in input().split())
  query = [-1*10**15]
  minA = a[0]
  for i in range(1,n):
    if minA < a[i]:
      if min(query) <= a[i]-minA:
        query.append(a[i]-minA)
    
    
    minA = min(minA,a[i])
  print(query.count(max(query)))
    
solve()


### FIXED CODE ###

def solve():
  n,t = (int(i) for i in input().split())
  a = list(int(i) for i in input().split())
  query = [-1]
  querymax = -1
  minA = a[0]
  for i in range(1,n):
    if minA < a[i]:
      if querymax <= a[i]-minA:
        querymax = a[i]-minA
        query.append(a[i]-minA)
    
    
    minA = min(minA,a[i])
  print(query.count(max(query)))
    
solve()
### BUGGY CODE ###

N, M = list(map(int, input().split()))
L = [0] * M
R = [0] * M
for i in range(M):
  L[i], R[i] = list(map(int, input().split()))
result = 0

for i in range(1, N+1):
  for j in range(M):
    if not(L[j] <= i <= R[j]):
      break
    if j == M-1:
      result += 1

print(result)

### FIXED CODE ###

N, M = list(map(int, input().split()))
L = [0] * M
R = [0] * M
for i in range(M):
  L[i], R[i] = list(map(int, input().split()))
result = min(R) - max(L) + 1
if result > 0:
  print(result)
else:
  print('0')
### BUGGY CODE ###

s=input()
q=int(input())
for i in range(q):
	a=input()
	if a=="1":
		s=s[::-1]
	else:
		if a[2]=="1":
			s=a[4]+s
		else:
			s=s+a[4]
print(s)

### FIXED CODE ###

from collections import deque

deq=deque()
k = input()
for i in range(len(k)):
	deq.append(k[i])
q=int(input())
x=True
for i in range(q):
	a=input()
	if a[0]=="1":
		x = not x
	elif a[2]=="1":
		if x==True:
			deq.appendleft(a[4])
		else:
			deq.append(a[4])
	else:
		if x==True:
			deq.append(a[4])
		else:
			deq.appendleft(a[4])
if x==True:
	c="".join(deq)
else:
	deq.reverse()
	c="".join(deq)
print(c)
### BUGGY CODE ###

n = int(input())
A = [int(i) for i in input().split()]
count = 0
for i in range(n):
    for j in range(i+1,n+1):
        if sum(A[i:j]) == 0:
            count += 1
print(count)

### FIXED CODE ###

n = int(input())

S = [0]
for i,s in enumerate(input().split()):
    S.append(int(s)+S[i])
S.sort()
S.append(10000000000)
count = 0
p = S[0]
l = 0
for i in range(n+2):
    if p != S[i]:
        count += (i-l)*(i-l-1)//2
        l = i
        p = S[i]
print(count)
### BUGGY CODE ###

from collections import deque
 
S = deque(input())
Q = int(input())
 
Q_list = [list(map(str, input().split())) for i in range(Q)]
 
for i in range(Q):
  if int(Q_list[i][0]) == 1:
    if len(S) >= 2:
      S.reverse()
  
  else:
    F = Q_list[i][1]
    C = Q_list[i][2]
    
    if int(F) == 1:
      S.appendleft(C)
    else:
      S.append(C)
      
print(''.join(S))

### FIXED CODE ###

from collections import deque
 
S = deque(input())
Q = int(input())
 
Q_list = [list(map(str, input().split())) for i in range(Q)]
 
rev = False
 
for i in range(Q):
  if int(Q_list[i][0]) == 1:
    rev = not rev
  
  else:
    F = Q_list[i][1]
    C = Q_list[i][2]
    
    if rev ^ (int(F) == 1): # 排他的論理和片方真片方ぎの時真になる
      S.appendleft(C)
    else:
      S.append(C)
      
if rev:
  S.reverse()
  
print(''.join(S))
### BUGGY CODE ###

from collections import Counter

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

c = Counter(s)

dbl = c["R"] * c["B"] * c["G"]
for l in range(1, n):
    for i in range(n):
        j = i + l
        k = j + l
        if j < n and k < n:
            if s[i] != s[j] and s[j] != s[k] and s[k] != s[i]:
                dbl -= 1

print(dbl)


### FIXED CODE ###

from collections import Counter

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

c = Counter(s)

dbl = c["R"] * c["B"] * c["G"]
for l in range(1, n):
    for i in range(n):
        j = i + l
        k = j + l
        if j < n and k < n:
            if s[i] != s[j] and s[j] != s[k] and s[k] != s[i]:
                dbl -= 1

print(dbl)
### BUGGY CODE ###

s=input()
l=len(s)
mod=10**9+7
dp=[[0 for j in range(13)] for i in range(l+1)]
dp[0][0]=1
for i in range(l):
    if s[i]=='?':
        for j in range(10):
            for k in range(13):
                dp[i+1][(k*10+j)%13]+=dp[i][k]%mod
    else:
        for k in range(13):
            dp[i+1][(k*10+int(s[i]))%13]+=dp[i][k]%mod
print(dp[-1][5]%mod)

### FIXED CODE ###

S = input()
l = len(S)
dp = [[0] * 13 for _ in range(l+1)]
dp[0][0] = 1
MOD = 10 ** 9 + 7
mul = 1
for i in range(l):
    if S[-(i+1)] == '?':
        for j in range(10):
            for k in range(13):
                dp[i+1][(j * mul + k) % 13] += dp[i][k]
                dp[i+1][(j * mul + k) % 13] %= MOD
    else:
        j = int(S[-(i+1)])
        for k in range(13):
            dp[i+1][(j * mul + k) % 13] += dp[i][k]
            dp[i+1][(j * mul + k) % 13] %= MOD
    mul = mul * 10 % 13
print(dp[l][5])