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

#!/usr/bin/env python3
import sys


def solve(N: int, P: "List[int]"):

    result = 0
    min_num = min(P)
    min_index = P.index(min_num)
    P = P[: min_index + 1]
    for i in range(len(P)):
        if P[i] == min(P[: i + 1]):
            result += 1
        else:
            pass
    print(result)

    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    P = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, P)


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, P: "List[int]"):

    result = 1
    min_num = P[0]
    for i in range(N):
        if P[i] < min_num:
            result += 1
            min_num = P[i]
        else:
            pass
    print(result)

    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    P = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, P)


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

N,S,Q,*K = open(0).read().split()
N = int(N)
K = map(int,K)
C = [0]*N
M = [0]*N
for i in range(N):
  if S[i]=='C':
    C[i] = 1
  elif S[i]=='M':
    M[i] = 1
for k in K:
  CMS = [0]*N
  SDMC = 0
  SMC = 0
  SC = 0
  Ms = 0
  for i in range(N):
    if i>=k:
      Ms -= M[i-k]
    if S[i]=='C':
      CMS[i] = Ms
    elif S[i]=='M':
      Ms += 1
  for i in range(N-1,-1,-1):
    if i<=N-1-k:
      SC -= C[i+k]
      SMC -= CMS[i+k]
    if S[i]=='C':
      SC += 1
    elif S[i]=='M':
      SMC += SC
    elif S[i]=='D':
      SDMC += SMC
  print(SDMC)

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

N = int(readline())
S = np.frombuffer(readline().rstrip(),'S1')
Q = int(readline())
query = map(int,read().split())

isD = S == b'D'
isM = S == b'M'
isC = S == b'C'

cumD = isD.cumsum(dtype=np.int64)
cumM = isM.cumsum(dtype=np.int64)

def F(K):
    """
    ・Cごとに数える。
    ・そのためには(i-K,i] 内のDMの個数を調べる（負インデックスには関係ない文字があると思っておく）
    ・区間内のDの個数、Mの個数が取得できれば、差分が取得できるので最後に累積和
    """
    # (i-K,i]内のDの個数、Mの個数
    D = cumD.copy(); D[K:] -= cumD[:-K]
    M = cumM.copy(); M[K:] -= cumM[:-K]
    # 最後がMのとき、Dの個数分増える
    DM = isM * D
    # 左端のDを捨てるとき、Mの個数分減る
    DM[K:] -= isD[:-K] * M[K-1:-1]
    np.cumsum(DM,out=DM)
    # Cごとに集計
    return DM[isC].sum()

print('\n'.join(str(F(K)) for K in query))
### BUGGY CODE ###

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

result = 0
for x in range(k + 1):
    for y in range(k + 1):
        for z in range(k + 1):
            if x + y + z == s:
                result += 1

                break

print(result)


### FIXED CODE ###

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

result = 0
for x in range(k + 1):
    for y in range(k + 1):
        z = s - x - y
        if 0 <= z <= k:
            result += 1

print(result)
### BUGGY CODE ###

def solve():
    N = int(input())
    S = input()

    base = 37
    def rolling_hash(s, mod):
        l = len(s)
        h = [0]*(l + 1)
        v = 0
        for i in range(l):
            h[i+1] = v = (v * base + ord(s[i])) % mod
        pw = [1]*(l + 1)
        v = 1
        for i in range(l):
            pw[i+1] = v = v * base % mod
        return h, pw

    mod1 = 10**9 + 9; mod2 = 10**9 + 7
    h1, pw1 = rolling_hash(S, mod1)
    h2, pw2 = rolling_hash(S, mod2)

    def chk(l, h, pw, mod):
        p = pw[l]
        for i in range(min(l, N-2*l+1)):
            D[i] = (h[l+i] - h[i]*p) % mod
        s = set()
        for i in range(l, N-l+1):
            s.add(D[i-l])
            D[i] = v = (h[l+i] - h[i]*p) % mod
            if v in s:
                return 1
        return 0

    H = [set() for i in range(N//2+2)]
    D = [0]*N
    E = [0]*N
    k = N//2
    for l in range(1, N//2+1):
        if not chk(l, h1, pw1, mod1):
            k = l-1
            break
    ans = 0
    for l in range(k, 0, -1):
        if chk(l, h2, pw2, mod2):
            ans = l
            break
    print(ans)
solve()

### FIXED CODE ###

def solve():
    N = int(input())
    S = input()

    base = 37
    def rolling_hash(s, mod):
        l = len(s)
        h = [0]*(l + 1)
        v = 0
        for i in range(l):
            h[i+1] = v = (v * base + ord(s[i])) % mod
        pw = [1]*(l + 1)
        v = 1
        for i in range(l):
            pw[i+1] = v = v * base % mod
        return h, pw

    mod1 = 10**9 + 9; mod2 = 10**9 + 7
    h1, pw1 = rolling_hash(S, mod1)
    h2, pw2 = rolling_hash(S, mod2)

    def chk(l, h, pw, mod):
        p = pw[l]
        for i in range(min(l, N-2*l+1)):
            D[i] = (h[l+i] - h[i]*p) % mod
        s = set()
        for i in range(l, N-l+1):
            s.add(D[i-l])
            D[i] = v = (h[l+i] - h[i]*p) % mod
            if v in s:
                return 1
        return 0

    H = [set() for i in range(N//2+2)]
    D = [0]*N
    E = [0]*N
    k = N//2
    for l in range(1, N//2+1):
        if not chk(l, h1, pw1, mod1):
            k = l-1
            break
    ans = 0
    for l in range(k, 0, -1):
        if chk(l, h2, pw2, mod2):
            ans = l
            break
    print(ans)
solve()
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from collections import Counter
def main():
    N, P = map(int, input().split())
    S = list(map(int, input().rstrip("\r\n")))[::-1]
    ans = 0
    if P == 2 or P == 5:
        for i in range(N):
            if int(S[i]) % P == 0:ans += N-i
    else:
        D = [0] * (N+1)
        tenpow = 1
        for i in range(N):
            S[i] = tenpow * S[i] % P
            tenpow *= 10 % P
            D[i+1] = (S[i] + D[i]) % P
        c = Counter(D)
        for v in c.values():
            ans += v*(v-1)//2
    print(ans)
if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
from collections import Counter
def main():
    N, P = map(int, input().split())
    S = list(map(int, input().rstrip("\r\n")))
    S.reverse()
    ans = 0
    if P == 2 or P == 5:
        for i in range(N):
            if S[i] % P == 0:ans += N-i
    else:
        A = [0] * N
        tenpow = 1
        for i in range(N):
            A[i] = (S[i]*tenpow) % P
            tenpow *= 10
            tenpow %= P
        D = [0] * (N+1)
        for i in range(N):
            D[i+1] = (D[i] + A[i]) % P
        c = Counter(D)
        for v in c.values():
            ans += v*(v-1)//2
    print(ans)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

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

bc = [list(map(int, input().split())) for i in range(q)]

a.sort()
uni = list(set(a))

kosu = [a.count(i) for i in uni]

for i in bc:
    b = i[0]
    c = i[1]

    if b in uni:
        # remove original
        tar = uni.index(b)
        uni.pop(tar)
        num = kosu.pop(tar)
        
        # add new
        if c in uni:
            idx = uni.index(c)
            kosu[idx] += num
        else:
            uni.append(c)
            kosu.append(num)

    ans = 0
    for ii in range(len(uni)):
        ans += uni[ii] * kosu[ii]

    print(ans)

### FIXED CODE ###

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

bc = [list(map(int, input().split())) for i in range(q)]

cnt = [0] * 100005 

for i in range(n):
    cnt[a[i]] += 1
    
tot = 0
for j in range(len(cnt)):
    tot += j * cnt[j]

# print(tot)

for k in range(q):
    b = bc[k][0]
    c = bc[k][1]
    tot -= b*cnt[b]
    tot -= c*cnt[c]
    cnt[c] += cnt[b]
    cnt[b] = 0
    tot += b*cnt[b]
    tot += c*cnt[c]
    print(tot)
### BUGGY CODE ###

import sys
input=sys.stdin.readline

class BIT:
  def __init__(self,n):
    self.n=n+1
    self.BIT=[0]*self.n
  def add(self,i,x):
    idx=i
    while idx<self.n:
      self.BIT[idx]+=x
      idx+=(idx&-idx)
  def _sum(self,i):
    ret=0
    idx=i
    while idx>0:
      ret+=self.BIT[idx]
      idx-=(idx&-idx)
    return ret
  def sum(self,l,r):
    return self._sum(r)-self._sum(l-1)
  def value(self,i):
    return self._sum(i)-self._sum(i-1)

n,q=map(int,input().split())
arr=list(map(int,input().split()))
query=[]
for i in range(q):
  l,r=map(int,input().split())
  query.append((l,r,i))
query=sorted(query,key=lambda x:x[0])
ans=[0]*q
bit=BIT(n)
pos_now=[-1]*(n+1)
pos_all=[[] for _ in range(n+1)]
for i in range(n):
  val=arr[i]
  if pos_now[val]==-1:
    bit.add(i+1,1)
    pos_now[val]=0
  pos_all[val].append(i+1)
for i in range(n+1):
  pos_all[i].append(-1)
prev=1
for l,r,id in query:
  while prev<l:
    val=arr[prev-1]
    if pos_all[val][pos_now[val]+1]!=-1:
      pos_now[val]+=1
      bit.add(pos_all[val][pos_now[val]],1)
    prev+=1
  ans[id]=bit.sum(l,r)
for val in ans:
  print(val)

### FIXED CODE ###

import sys
input=sys.stdin.readline

class BIT:
  def __init__(self,n):
    self.n=n+1
    self.BIT=[0]*self.n
  def add(self,i,x):
    idx=i
    while idx<self.n:
      self.BIT[idx]+=x
      idx+=(idx&-idx)
  def _sum(self,i):
    ret=0
    idx=i
    while idx>0:
      ret+=self.BIT[idx]
      idx-=(idx&-idx)
    return ret
  def sum(self,l,r):
    return self._sum(r)-self._sum(l-1)
  def value(self,i):
    return self._sum(i)-self._sum(i-1)

n,q=map(int,input().split())
arr=list(map(int,input().split()))
query=[]
for i in range(q):
  l,r=map(int,input().split())
  query.append((l,r,i))
query=sorted(query,key=lambda x:x[0])
ans=[0]*q
bit=BIT(n)
pos_now=[-1]*(n+1)
pos_prev=[-1]*(n+1)
dic={}
for i in range(n):
  val=arr[i]
  dic[i+1]=-1
  if pos_now[val]==-1:
    bit.add(i+1,1)
    pos_now[val]=i+1
  if pos_prev[val]!=-1:
    dic[pos_prev[val]]=i+1
  pos_prev[val]=i+1
prev=1
for l,r,id in query:
  while prev<l:
    val=arr[prev-1]
    if dic[pos_now[val]]!=-1:
      pos_now[val]=dic[pos_now[val]]
      bit.add(pos_now[val],1)
    prev+=1
  ans[id]=bit.sum(l,r)
for val in ans:
  print(val)
### BUGGY CODE ###

import sys

n, y = input().split()
n = int(n)
y = int(y)

for a in range(n+1):
	for b in range(n+1-a):
		for c in range(n+1-a-b):
			if (a + b + c == n) and (a * 10000 + b * 5000 + c * 1000 == y):
				print(str(a) + ' ' + str(b) + ' ' + str(c))
				sys.exit()

print('-1 -1 -1')

### FIXED CODE ###

import sys

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

for a in range(n+1):
	for b in range(n+1-a):
		c = n - a - b
		if (a * 10000 + b * 5000 + c * 1000 == y):
				print(str(a) + ' ' + str(b) + ' ' + str(c))
				sys.exit()
	
print('-1 -1 -1')
sys.exit()
### BUGGY CODE ###

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

from itertools import accumulate
B = [0] + A
B = list(accumulate(B))

INF = 10**18
dp = [[INF]*(n+1) for i in range(n+1)]
# dp[i][j]: 区間[i, j)のスライムを取り除いたコストの最小値
for i in range(n):
    dp[i][i+1] = 0
# 区間の幅(d)が狭い方から更新していく(d: 2, 3, ...n+1)
# d = 0, 1については初期化で更新した
for d in range(2, n+1):
    for i in range(n+1-d):
        j = i + d
        for k in range(i+1, j):
            dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j]+B[j]-B[i])
#print(dp)
print(dp[0][n])

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)

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

memo = [[float('inf')]*410 for _ in range(410)]
visit = [[False]*410 for _ in range(410)]

from itertools import accumulate
B = [0]+A
B = list(accumulate(B))

def dp(l, r):
  if l == r:
    return 0
  if visit[l][r]:
    return memo[l][r]
  visit[l][r] = True
  res = float('inf')
  for c in range(l, r):
    res = min(res, dp(l, c)+dp(c+1, r)+B[r+1]-B[l])
  memo[l][r] = res
  return res

print(dp(0, n-1))
### BUGGY CODE ###

n = int(input())

a = list(map(lambda x:int(x), input().split()))

junban = []

for i in range(n):
    jun = a.index(i+1)
    #junban.append(jun+1)
    if i != n:
        print(jun+1," ",end="")
    else:
        print(jun+1)




### FIXED CODE ###

n = int(input())

a = list(map(lambda x:int(x), input().split()))

junban = []
for i in range(n):
    junban.append(0)

for i in range(n):
    junban[a[i]-1] = str(i+1)



print(" ".join(junban))
### BUGGY CODE ###

x, y = map(int, input().split())
if x == y:
  print(-1)
else:
  i = 1
  n = x
  while n % y == 0:
    n = i * x
    i += 1
  print(n)

### FIXED CODE ###

x, y = map(int, input().split())
if x % y == 0:
  print(-1)
else:
  i = 1
  n = x
  while n % y == 0:
    n = i * x
    i += 1
  print(n)
### BUGGY CODE ###

from collections import deque
def bfs(maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    while queue:
      #queueには訪れた地点が入っている。そこから、4方向に移動できるか考え、queueから消す。
        y, x = queue.popleft()#queueに入っていたものを消す。
        if [y, x] == [gy, gx]:#もしゴールについていたならば、そのときの手数を出す。
            print(visited[y][x])
            quit()
            return visited[y][x]
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
          p = 0
          l = 1
          while p == 0:
              new_y, new_x = y + j * l, x + k * l 
              if (0 <= new_y < H) and (0 <= new_x < W): 
                if maze[new_y][new_x] == "@":
                  p = 1
                elif visited[new_y][new_x] == -1:#まだ来たことない点だったという条件
                  visited[new_y][new_x] = visited[y][x] + 1
                  queue.append([new_y, new_x])#新しい点を足す。
              else:
                p = 1
              l += 1
              if l == K + 1:
                p = 1

H, W, K = map(int, input().split())
#K = min(K, max(H, W))
x1, y1, x2, y2 = map(int, input().split())
x1, y1, x2, y2 = x1-1, y1-1, x2-1, y2-1
C = [0] * H
for i in range(H):
  C[i] = str(input())
visited = [[-1] * W for i in range(H)]
bfs(C, visited, x1, y1, x2, y2)
#print(visited)
print(-1)
  




### FIXED CODE ###

from collections import deque
def bfs(maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    while queue:
      #queueには訪れた地点が入っている。そこから、4方向に移動できるか考え、queueから消す。
        y, x = queue.popleft()#queueに入っていたものを消す。
        if [y, x] == [gy, gx]:#もしゴールについていたならば、そのときの手数を出す。
            return visited[y][x]
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
          p = 0
          l = 1
          while p == 0:
              new_y, new_x = y + j * l, x + k * l 
              if (0 <= new_y < H) and (0 <= new_x < W): 
                if maze[new_y][new_x] == "@":
                  p = 1
                elif visited[new_y][new_x] == -1:#まだ来たことない点だったという条件
                  visited[new_y][new_x] = visited[y][x] + 1
                  queue.append([new_y, new_x])#新しい点を足す。
                elif visited[new_y][new_x] < visited[y][x] + 1:
                  p = 1
              else:
                p = 1
              l += 1
              if l == K + 1:
                p = 1

H, W, K = map(int, input().split())
#K = min(K, max(H, W))
x1, y1, x2, y2 = map(int, input().split())
x1, y1, x2, y2 = x1-1, y1-1, x2-1, y2-1
C = [0] * H
for i in range(H):
  C[i] = str(input())
visited = [[-1] * W for i in range(H)]
bfs(C, visited, x1, y1, x2, y2)
#print(visited)
print(visited[x2][y2])
### BUGGY CODE ###

import numpy as np
N,K=[int(i) for i in input().split()]
S=input()
linelist=[1]
for i in range(1,len(S)):
	if S[i-1]!=S[i]:
		linelist.append(1)
	else:
		linelist[-1]+=1
c=0
line=np.array(linelist)
if S[0]=="0":
	for i,num in enumerate(line):
		if i%2==0:
			if i+2*K<=len(line):
				c=max(c,np.sum(line[i:i+2*K]))
			else:
				c=max(c,np.sum(line[i:]))
				break
		else:
			if i+2*K+1<=len(line):
				c=max(c,np.sum(line[i:i+2*K+1]))
			else:
				c=max(c,np.sum(line[i:]))
				break
else:
	for i,num in enumerate(line):
		if i%2==1:
			if i+2*K<=len(line):
				c=max(c,np.sum(line[i:i+2*K]))
			else:
				c=max(c,np.sum(line[i:]))
				break
		else:
			if i+2*K+1<=len(line):
				c=max(c,np.sum(line[i:i+2*K+1]))
			else:
				c=max(c,np.sum(line[i:]))
				break
print(c)

### FIXED CODE ###

N,K=[int(i) for i in input().split()]
S=input()
cur=0
line=[]

for i in range(len(S)):
	if i==0:
		if S[0]=="0":
			line.append(0)
		line.append(1)
	else:
		if S[i-1]!=S[i]:
			line.append(1)
		else:
			line[-1]+=1
c=0
for i in range(len(line)):

	if i==0:
		if i+2*K+1<=len(line):
			s=sum(line[i:2*K+1])
			c=s
		else:
			s=sum(line[i:])
			c=s
	elif i%2==0:
		if i+2*K+1<=len(line):
			s=s-line[i-2]-line[i-1]+line[i+2*K-1]+line[i+2*K]
			c=max(c,s)
		else:
			c=max(c,sum(line[i:]))
			break
print(c)
### BUGGY CODE ###

def main():
    
    n,m,l = map(int,input().split())
    E = [[] for i in range(n)]
    for i in range(m):
        a,b,c = map(int,input().split())
        E[a-1].append((b-1,c))
        E[b-1].append((a-1,c))

    import heapq

    def dijkstra(graph, node, start):
        dist = [[float("INF")]*2 for _ in range(node)]
        
        dist[start] = [0,l]
        q = []
        heapq.heappush(q, (0,start,l))
        
        while q:
            count,cur,fuel = heapq.heappop(q)
            for nex, nex_len in graph[cur]:
                if fuel >= nex_len:
                    nex_fuel = fuel - nex_len
                    if dist[nex][0] > count or (dist[nex][0]==count and nex_fuel > dist[nex][1]):
                        heapq.heappush(q, (count,nex,nex_fuel))
                        dist[nex] = [count,nex_fuel]
                else:
                    if l >= nex_len:
                        nex_fuel = l-nex_len
                        nex_count = count+1
                        if dist[nex][0] > nex_count or (dist[nex][0]==nex_count and nex_fuel > dist[nex][1]):
                            heapq.heappush(q, (nex_count,nex,nex_fuel))
                            dist[nex] = [nex_count,nex_fuel]

        return dist


    ans = []
    for i in range(n):
        ans.append(dijkstra(E, n, i))
    
    x = int(input())
    for i in range(x):
        s,g = map(int,input().split())
        if ans[s-1][g-1][0] == float("INF"):
            print(-1)
        else:
            print(ans[s-1][g-1][0]) 
if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    n,m,l = map(int,input().split())
    E = [[float("INF")]*n for i in range(n)]
    for i in range(m):
        a,b,c = map(int,input().split())
        E[a-1][b-1] = c
        E[b-1][a-1] = c

    for k in range(n):
        for i in range(n):
            for j in range(n):
                E[i][j] = min(E[i][j],E[i][k]+E[k][j])
    wa = [[float("INF")]*n for i in range(n)]
    for i in range(n):
        for j in range(n):
            if E[i][j] <= l:
                wa[i][j] = 1
    for k in range(n):
        for i in range(n):
            for j in range(n):
                wa[i][j] = min(wa[i][j],wa[i][k]+wa[k][j])
    
    x = int(input())
    for i in range(x):
        s,g = map(int,input().split())
        if wa[s-1][g-1] == float("INF"):
            print(-1)
        else:
            print(wa[s-1][g-1]-1)

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

mod = 998244353
n, s = map(int, input().split())
arr = list(map(int, input().split()))
dp = [[0] * (s + 1) for _ in range(n + 1)]
dp[0][0] = 1

for i in range(1, n + 1):
    var = arr[i - 1]
    for j in range(s, -1, -1):
        dp[i][j] = 2 * dp[i - 1][j]
        dp[i][j] %= mod
        if j - var >= 0 and dp[i - 1][j - var] != 0:
            dp[i][j] += dp[i - 1][j - var]
            dp[i][j] %= mod
print(int(dp[n][s]))


### FIXED CODE ###

mod = 998244353
n, s = map(int, input().split())
arr = list(map(int, input().split()))
dp = [[0] * (s + 1) for _ in range(n + 1)]
dp[0][0] = 1

for i in range(1, n + 1):
    var = arr[i - 1]
    for j in range(0, s + 1):
        dp[i][j] = 2 * dp[i - 1][j]
        dp[i][j] %= mod
        if j - var >= 0 and dp[i - 1][j - var] != 0:
            dp[i][j] += dp[i - 1][j - var]
            dp[i][j] %= mod
print(int(dp[n][s]))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N, Q = map(int, input().split())
S = input()
l = []
for i in range(Q):
    a, b = map(int, input().split())
    ps = S[a-1: b]
    num = ps.count('AC')
    print(num)

### FIXED CODE ###

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

pos = [0] * N
i = 0
while i < N-1:
    if S[i] == 'A':
        if S[i+1] == 'C':
            pos[i+1] = 1
    i += 1

nums = [0] * (N+1)
for i in range(1, N+1):
    nums[i] += nums[i-1] + pos[i-1]

for _ in range(Q):
    l, r = map(int, input().split())
    print(nums[r]-nums[l])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10000)
mod=10**9+7
s=input()
n=len(s)
Sum_A=[0]*(n+1)
Sum_B=[0]*(n+1)
Sum_C=[0]*(n+1)
Sum_q=[0]*(n+1)
for i in range(1, n+1):
    Sum_A[i]=Sum_A[i-1]
    Sum_C[i]=Sum_C[i-1]
    Sum_q[i]=Sum_q[i-1]
    if s[i-1]=='A':
        Sum_A[i]+=1
    elif s[i-1]=='C':
        Sum_C[i]+=1
    elif s[i-1]=='?':
        Sum_q[i]+=1
ans=0

def pow1(x, n):
    """
    O(log n)
    """
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2

    return K * x

def count(x, q):
    return int(x*pow1(3, q)+q*pow1(3, q-1))

for i in range(n):
    if s[i]=='B' or s[i]=='?':
        ans+=count(Sum_A[i], Sum_q[i])*count(Sum_C[n]-Sum_C[i+1], Sum_q[n]-Sum_q[i+1])
        ans%=mod
print(ans)


### FIXED CODE ###

mod=10**9+7
s=input()
n=len(s)
Sum_A=[0]*(n+1)
Sum_B=[0]*(n+1)
Sum_C=[0]*(n+1)
Sum_q=[0]*(n+1)
for i in range(1, n+1):
    Sum_A[i]=Sum_A[i-1]
    Sum_C[i]=Sum_C[i-1]
    Sum_q[i]=Sum_q[i-1]
    if s[i-1]=='A':
        Sum_A[i]+=1
    elif s[i-1]=='C':
        Sum_C[i]+=1
    elif s[i-1]=='?':
        Sum_q[i]+=1
ans=0
def count(x, q):
    return int(x*pow(3, q, mod)+q*pow(3, (q-1), mod)) if q>0 else int(x*pow(3, q, mod))
for i in range(n):
    if s[i]=='B' or s[i]=='?':
        ans+=count(Sum_A[i], Sum_q[i])*count(Sum_C[n]-Sum_C[i+1], Sum_q[n]-Sum_q[i+1])
        ans%=mod
print(ans)
### BUGGY CODE ###

"""Boot-camp-for-Beginners_Easy013_A_Candy-Distribution-Again_30-August-2020.py"""

A, B, C = map(int, input().split())
a, b, c = A, B, C
i = 0
while True:
    if (A % 2 == 0 and B % 2 == 0 and C % 2 == 0):
        i += 1
        a, b, c = A, B, C
        A = (b+c)/2
        B = (c+a)/2
        C = (a+b)/2
    elif (A % 2 == 1 or B % 2 == 1 or C % 2 == 1):
        print(i)
        break
    elif(A == B or B == C or C == A):
        print(-1)
        break
    else:
        continue

### FIXED CODE ###

"""Boot-camp-for-Beginners_Easy013_A_Candy-Distribution-Again_30-August-2020.py"""

A, B, C = map(int, input().split())
a, b, c = A, B, C
i = 0
while True:
    if (A % 2 == 0 and B % 2 == 0 and C % 2 == 0):
        i += 1
        a, b, c = A, B, C
        A = (b+c)/2
        B = (c+a)/2
        C = (a+b)/2
 #       print(A,B,C)
        if(A == a and B == b and C == c):
            print(-1)
            break
    else:
        print(i)
        break
        if(A == a and B == b and C == c):
            print(-1)
            break
### BUGGY CODE ###

S = list(raw_input())

i = 0
cnt = 0
while len(S) > 0:
    if i+1 == len(S):
        break
    if S[i] != S[i+1]:
        del S[i]
        del S[i]
        i = -1
        cnt += 2
    i += 1

print cnt

### FIXED CODE ###

S = list(raw_input())

i = 0
cnt = 0
while len(S) > 0:
    if i+1 == len(S):
        break
    if S[i] != S[i+1]:
        del S[i]
        del S[i]
        if i <= 0:
            i = -1
        else:
            i -= 2
        cnt += 2
    i += 1

print cnt
### BUGGY CODE ###

s = list(input())
q = int(input())
query = [list(input().split()) for i in range(q)]
for i in query:
    if i[0] == "1":
        s.reverse()
    else:
        if i[1] == "1":
            s.insert(0, i[2])
        else:
            s.append(i[2])
print(*s, sep="")

### FIXED CODE ###

s = input()
q = int(input())
t = ""
for i in range(q):
    que = input().split()
    if que[0] == "1":
        s, t = t, s
    else:
        if que[1] == "1":
            t += que[2]
        else:
            s += que[2]
print(t[::-1] + s)