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

import sys
from heapq import heappush, heappop
input = sys.stdin.readline
def inpl(): return list(map(int, input().split()))

N, M, L = inpl()
G = [[] for _ in range(N)]
G2 = [[999]*(N) for _ in range(N)]

for _ in range(M):
    a, b, c = inpl()
    if c <= L:
        G[a-1].append([b-1, c])
        G[b-1].append([a-1, c])

for i in range(N):
    supply = [999]*N
    remain = [0]*N
    supply[i] = 1
    remain[i] = L
    Q = [(1, -L, i)]
    while Q:
        s, r, p = heappop(Q)
        r = -r
        if s > supply[p]:
            continue
        if (s == supply[p]) and (r < remain[p]):
            continue
        for q, c in G[p]:
            if r >= c:
                if supply[q] > s:
                    supply[q] = s
                    remain[q] = r - c
                    heappush(Q, (s, c-r, q))
                elif (supply[q] == s) & (remain[q] < r - c):
                    remain[q] = r-c
                    heappush(Q, (s, c-r, q))
            else:
                if supply[q] > s:
                    supply[q] = s + 1
                    remain[q] = L - c
                    heappush(Q, (s+1, c-L, q))
                elif (supply[q] == (s+1)) & (remain[q] < L - c):
                    supply[q] = s+1
                    remain[q] = L-c
                    heappush(Q, (s+1, c-L, q))
    for j in range(N):
        G2[i][j] = supply[j]


for _ in range(int(input())):
    s, t = inpl()
    if G2[s-1][t-1] == 999:
        print(-1)
    else:
        print(G2[s-1][t-1]-1)


### FIXED CODE ###

import sys
from heapq import heappush, heappop
input = sys.stdin.readline
def inpl(): return list(map(int, input().split()))

N, M, L = inpl()
G = [[] for _ in range(N)]
G2 = [[999]*(N) for _ in range(N)]

for _ in range(M):
    a, b, c = inpl()
    if c <= L:
        G[a-1].append([b-1, c])
        G[b-1].append([a-1, c])

for i in range(N):
    supply = [999]*N
    remain = [0]*N
    supply[i] = 1
    remain[i] = L
    Q = [(1, -L, i)]
    while Q:
        s, r, p = heappop(Q)
        r = -r
        if s > supply[p]:
            continue
        if (s == supply[p]) and (r < remain[p]):
            continue
        for q, c in G[p]:
            if r >= c:
                if supply[q] > s:
                    supply[q] = s
                    remain[q] = r - c
                    heappush(Q, (s, c-r, q))
                elif (supply[q] == s) & (remain[q] < r - c):
                    remain[q] = r-c
                    heappush(Q, (s, c-r, q))
            else:
                if supply[q] > (s + 1):
                    supply[q] = s + 1
                    remain[q] = L - c
                    heappush(Q, (s+1, c-L, q))
                elif (supply[q] == (s+1)) & (remain[q] < L - c):
                    supply[q] = s+1
                    remain[q] = L-c
                    heappush(Q, (s+1, c-L, q))
    for j in range(N):
        G2[i][j] = supply[j]


for _ in range(int(input())):
    s, t = inpl()
    if G2[s-1][t-1] == 999:
        print(-1)
    else:
        print(G2[s-1][t-1]-1)
### BUGGY CODE ###

K = int(input())
trip = dict()
pair = dict()

def gcd(a, b):
    d = frozenset([a, b])
    if d in pair:
        return pair[d]

    if b == 0:
        pair[d] = a
        return a

    while b:
        a %= b
        a, b = b, a

    pair[d] = a
    return a

def gcd3(K):

    res = 0

    for i in range(1, K+1):
        for j in range(1, K+1):
            for k in range(1, K+1):
                l = frozenset([i, j, k])
                if l in trip:
                    res += trip[l]
                    continue

                x = gcd(i, gcd(j, k))
                # print("i:%d, j:%d, k:%d, x:%d" % (i, j, k, x))
                res += x
                trip[l] = x

    return res

print(gcd3(K))


### FIXED CODE ###

import math 

K = int(input())

def sol(K):
    res = 0
    for i in range(1, K+1):
        for j in range(1, K+1):
            t = math.gcd(i, j)
            for k in range(1, K+1):
                res += math.gcd(k, t)

    return res
  
print(sol(K))
### BUGGY CODE ###

import math

input()
d = None
u = set()
r = 'pairwise'
for x in map(int, input().split()):
  d = math.gcd(d or x, x)
  s = set()
  i = 2
  while i * i <= x:
    while x % i == 0:
      if i in u:
        r = 'setwise'
      s.add(i)
      x //= i
    i += 1
  if x > 1:
    if x in u:
      r = 'setwise'
    s.add(x)
  u |= s
print((r, 'not')[d > 1], 'coprime')


### FIXED CODE ###

N = 1000001
 
spf = [*range(N)]
i = 2
while i * i < N:
  if spf[i] == i:
    for j in range(i * i, N, i):
      if spf[j] == j:
        spf[j] = i
  i += 1
  
r = 'pairwise'
n = int(input())
a = [int(x) for x in input().split() if x > '1']
if len(a) > 1:
  u = set()
  i = None
  for x in a:
    s = set()
    while x > 1:
      p = spf[x]
      if p in u:
        r = 'setwise'
      s.add(p)
      x //= p
    u |= s
    if len(a) == n:
      if i is None: i = s
      else: i &= s
  if i:
    r = 'not'
print(r, 'coprime')
### BUGGY CODE ###

import itertools
n,k = map(int,input().split())
p = list(map(int,input().split()))
lstp = []
for i in range(n-k+1):
    lstp.append(0.5*(sum(p[i:i+k])+k))
print("{:.6f}".format(max(lstp)))

### FIXED CODE ###

n,k = map(int,input().split())
p = list(map(int,input().split()))
wa = sum(p[0:k])
next_wa = wa
for i in range(n-k):
    next_wa = next_wa - p[i] + p[i+k]
    if  next_wa > wa:
        wa = next_wa
print(0.5*(wa+k))
### BUGGY CODE ###

n=int(input())
from math import sqrt
for k in range(1,n+1):

    ans=0
    p=int(sqrt(k))
    for x in range(1,p+1):
        for y in range(1,int(sqrt(k-x**2)) + 1 ):
            if k-x**2 - y**2 -x*y<=0:
                continue
            for z in range(1,int(sqrt(k-x**2 - y**2 -x*y))+1):
                if z*(z+x+y)==k-x**2 -y**2 -x*y:
                    ans+=1
    print(ans)


### FIXED CODE ###

n=int(input())

ans=[0]*(n+1)

for x in range(1,101):
    for y in range(1,101):
        for z in range(1,101):
            f= x**2 + y**2 + z**2 + x*y + y*z + z*x
            if f<=n:
                ans[f]+=1

for i in range(1,n+1):
    print(ans[i])
### BUGGY CODE ###

import copy
X = input()
X = list(X)
prev = ""
while(1):
    prev = copy.copy(X)
    for i in range(len(X) - 1):
        if X[i]+X[i + 1] == "ST":
            X.pop(i+1)
            X.pop(i)
            break
    if prev == X:
        break
print(len(X))

### FIXED CODE ###

X = input()
Y = []
for i in X:
    Y.append(i)
    if len(Y) > 1:
        if Y[-2] + Y[-1] == "ST":
            Y.pop()
            Y.pop()
print(len(Y))
### BUGGY CODE ###

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

for n in range(N):
    print(A.count(n+1))


### FIXED CODE ###

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

#for n in range(N):
#    print(A.count(n+1))

M = {}
for a in A:
    M[a] = M.get(a,0) + 1

for n in range(N):
    print(M.get(n+1,0))
### BUGGY CODE ###

n=int(input())
mod=10**9+7
import math
v=math.factorial(n)
ans=[]
for i in range(1,v+1):
    if v%i==0:
        ans.append(i)
print(len(ans))


### FIXED CODE ###

n=int(input())
import math
fac=math.factorial(n)
mod=10**9+7
ans=[0]*(n+1)
ans[0]=ans[1]=1
i=2
while i*i<=n:
    j=2
    while i*j<=n and ans[i]==0:
        ans[i*j]=1
        j+=1
    i+=1
v=[]
for i in range(n+1):
    if ans[i]==0:
        v.append(i)
total=1
count=0
for i in v:
    while fac%i==0:
        count+=1
        fac//=i
    total*=count+1
    count=0
print(total%mod)
### BUGGY CODE ###

# -*- coding:utf-8 -*-
def pow(x,n):
    if n == 0:
        return 1
    if n % 2 == 0:
        return pow(x**2, int(n/2))
    else:
        return pow(x**2, int(n/2))*x
    
n,m = map(int,input().split())
x = 1000000007
print(pow(n,m)%x)

### FIXED CODE ###

def mpow(x,n,mod):
    if n == 0:
        return 1
    if n % 4 == 0:
        return mpow((x**4)%mod,int(n/4),mod)
    elif n%4 == 1:
        return (mpow(x,int(n-1),mod)*x)%mod
    elif n%4 == 2:
        return (mpow(x,int(n-2),mod)*(x**2))%mod
    elif n%4 == 3:
        return (mpow(x,int(n-3),mod)*(x**3))%mod
n,m = map(int,input().split())
mod = 1000000007
print(mpow(n,m,mod))
### BUGGY CODE ###

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

cnt = 1
ans =[0] * n

for _ in range(n):
    for i in range(n):
        if a[i] == cnt:
            ans[cnt-1] = i+1
            cnt += 1
            break

print(' '.join(map(str, ans)))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
num = list(range(1, n+1))

cin = dict(zip(a, num))
ans =[]

for i in range(n):
    ans.append(cin[i+1])

print(' '.join(map(str, ans)))
### BUGGY CODE ###

S=input()
ans,n=0,len(S)
dp=[0]*(2019)
s,dp[0]=0,1
for i in range(1,n+1):
  s=(s+int(S[-i])*10**(i-1))%2019
  ans+=dp[s]
  dp[s]+=1
print(ans)

### FIXED CODE ###

S=input()
ans,n=0,len(S)
dp=[0]*(2019)
s,dp[0],k=0,1,1
for i in range(1,n+1):
  s=(s+int(S[-i])*k)%2019
  k=(k*10)%2019
  ans+=dp[s]
  dp[s]+=1
print(ans)
### BUGGY CODE ###

import collections
S=input()
l=len(S)
t=0
p=0
m=[0] * l
ss=[0]*(l+1)
for i in range(l):
    m[i]=int(S[i])*(10**(l-1-i))%2019
    ss[i+1]=(ss[i]+m[i])%2019

k=collections.Counter(ss)

for i in k.values():
    if i>1:
        t+=(i-1)
print(t)



### FIXED CODE ###

s = input()[::-1] # 入力文字列を逆順でsに格納

counts = [0] * 2019
counts[0] = 1

num, d = 0, 1

for char in s:
    num += int(char) * d
    num %= 2019
    d *= 10
    d%= 2019
    counts[num] += 1

ans = 0
for cnt in counts:
    ans += cnt * (cnt - 1) // 2

print(ans) # 答えの出力
### BUGGY CODE ###

import sys
input = sys.stdin.readline

k,q = map(int,input().split())
d_array = list(map(int,input().split()))

for _ in range(q):
    n, x, m = map(int,input().split())
    d_mod_array = [d % m for d in d_array]
    d_sum = sum(d_mod_array)
    mod_total = x % m + d_sum * ((n-1) // k) + sum(d_mod_array[:(n-1)%k])
    reduce_total = mod_total // m

    zero_count = d_mod_array.count(0)
    zero_total = zero_count * ((n-1) // k) + d_mod_array[:(n-1)%k].count(0)
    ans = (n-1) - reduce_total - zero_total
    print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

k,q = map(int,input().split())
d_array = list(map(int,input().split()))

ans_array = []
for _ in range(q):
    n, x, m = map(int,input().split())
    d_mod_array = [d % m for d in d_array]
    d_sum = 0
    d_part = 0
    zero_count = 0
    zero_part = 0
    part = (n-1) % k
    for i,d in enumerate(d_mod_array):
        d_sum += d
        if i < part:
            d_part += d
        if d == 0:
            zero_count += 1
            if i < part:
                zero_part += 1
    mod_total = x % m + d_sum * ((n-1) // k) + d_part
    reduce_total = mod_total // m

    zero_total = zero_count * ((n-1) // k) + zero_part
    ans = (n-1) - reduce_total - zero_total
    ans_array.append(str(ans))

print("\n".join(ans_array))
### BUGGY CODE ###

n,k=map(int,input().split())
H=[int(i) for i in input().split()]
H.extend([0 for i in range(k+1)])

dp=[1e10 for i in range(n+1)]
dp.extend([0 for i in range(k+1)])
dp[0]=0

for i in range(n-1):
    for q in range(1,k+1):
        dp[i+q]=min(dp[i+q],dp[i]+abs(H[i+q]-H[i]))
   

print(dp[n-1])

### FIXED CODE ###

n,k=map(int,input().split())
H=[int(i) for i in input().split()]
H.extend([0 for i in range(k+1)])

dp=[1e10 for i in range(n+1)]
dp.extend([0 for i in range(k+1)])
dp[0]=0

for i in range(n-1):
    for q in range(1,k+1):
        dp[i+q]=min(dp[i+q],dp[i]+abs(H[i+q]-H[i]))
   

print(dp[n-1])
### BUGGY CODE ###

# vim: set fileencoding=utf-8:
import bisect


def main():
    N, K = map(int, raw_input().split())
    x = [int(ele) for ele in raw_input().split()]
    o = bisect.bisect_right(x, 0)

    zenpou = x
    kouhou = x

    top = min(o + K, N)
    bottom = max(o - K, 0)
    x = x[bottom:top]

    best = 999999999999
    u = len(x)
    for i in range(u):
        if u < i + K:
            break

        hani = x[i:i + K]
        if hani[0] < 0 and hani[-1] < 0:
            best = min(best, abs(hani[0]))
        elif hani[0] < 0 <= hani[-1]:
            best = min(best, 2 * abs(hani[0]) + hani[-1])
        elif 0 <= hani[0] and 0 <= hani[-1]:
            best = min(best, hani[-1])

    print(best)


if __name__ == "__main__":
    main()


### FIXED CODE ###

# vim: set fileencoding=utf-8:
import bisect


def main():
    N, K = map(int, raw_input().split())
    x = [int(ele) for ele in raw_input().split()]
    o = bisect.bisect_right(x, 0)
    top = min(o + K, N)
    bottom = max(o - K, 0)
    best = 999999999999
    for i in xrange(K):
        if top < bottom + i + K:
            break

        if x[bottom + i + K - 1] < 0:
            best = min(best, abs(x[bottom + i]))
        elif x[bottom + i] < 0 <= x[bottom + i + K - 1]:
            ans1 = 2 * min(abs(x[bottom + i]), x[bottom + i + K - 1])
            ans2 = max(abs(x[bottom + i]), x[bottom + i + K - 1])
            ans = min(best, ans1 + ans2)
            best = min(best, ans)
        elif 0 <= x[bottom + i]:
            best = min(best, x[bottom + i + K - 1])

    print(best)


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

s = input()
ans = 0
count = 0
a = ''
for i in range(len(s)-3):
    for j in range(i,len(s)):
        a += s[j]
        ans = int(a)
        if ans % 2019 == 0:
            count += 1
    a = ''
    ans = 0
print(count)

### FIXED CODE ###

s = input()
counts = [0]*2019
counts[0] += 1
num = 0
d = 1
for c in reversed(s):
    num += int(c) * d
    counts[num % 2019] += 1
    d *= 10
    d %= 2019
ans = 0
for count in counts:
    ans += count*(count -1) // 2
print(ans)
### BUGGY CODE ###

N,Q=map(int, input().split())
s=input()
td=[input().split() for i in range(Q)]

def move(s,td,position):
    p=position
    for spell in td:
        if s[p]==spell[0] and spell[1]=='L':
            p-=1
        elif s[p]==spell[0] and spell[1]=='R':
            p+=1
        if p<0 or p>=N: break
    return p

l=0
r=N-1
watched=[0]*N
while(True):
    p=(r+l)//2
    if watched[p]>0:
        if p<N-1 and watched[p+1]==0:
            p+=1
        else:
            break
    res=move(s,td,p)
    if res<0:
        l=p
        watched[p]=1
    else:
        r=p
        if watched[p]==0: watched[p]=2
ans_l=N
for i in range(N):
    if watched[i]==2:
        ans_l=i
        break

l=0
r=N-1
watched2=[0]*N
while(True):
    p=(r+l)//2
    if watched2[p]>0:
        if p<N-1 and watched2[p+1]==0:
            p+=1
        else:
            break
    res=move(s,td,p)
    if res>=N:
        r=p
        watched2[p]=3
    else:
        l=p
        if watched2[p]==0: watched2[p]=2
ans_r=0
for i in range(N-1,-1,-1):
    if watched2[i]==2:
        ans_r=i
        break
print(max(0,ans_r-ans_l+1))


### FIXED CODE ###

N,Q=map(int, input().split())
s=input()
td=[input().split() for i in range(Q)]

def move(s,td,position):
    p=position
    for spell in td:
        if s[p]==spell[0] and spell[1]=='L':
            p-=1
        elif s[p]==spell[0] and spell[1]=='R':
            p+=1
        if p<0 or p>=N: break
    return p

l=0
r=N-1
watched=[0]*N
while(True):
    p=(r+l)//2
    if watched[p]>0:
        if p<N-1 and watched[p+1]==0:
            p+=1
        else:
            break
    res=move(s,td,p)
    if res<0:
        l=p
        watched[p]=1
    else:
        r=p
        if watched[p]==0: watched[p]=2
ans_l=N
for i in range(N):
    if watched[i]==2:
        ans_l=i
        break

l=0
r=N-1
watched2=[0]*N
while(True):
    p=(r+l)//2
    if watched2[p]>0:
        if p<N-1 and watched2[p+1]==0:
            p+=1
        else:
            break
    res=move(s,td,p)
    if res>=N:
        r=p
        watched2[p]=3
    else:
        l=p
        if watched2[p]==0: watched2[p]=2
ans_r=-1
for i in range(N-1,-1,-1):
    if watched2[i]==2:
        ans_r=i
        break
print(max(0,ans_r-ans_l+1))
### BUGGY CODE ###

def d_wizard_in_maze():
    from collections import deque
    H, W = [int(i) for i in input().split()]
    Start_row, Start_col = [int(i) - 1 for i in input().split()]
    Goal_row, Goal_col = [int(i) - 1 for i in input().split()]
    Grid = [input() for _ in range(H)]

    neighbor = ((-1, 0), (1, 0), (0, -1), (0, 1))  # 上下左右
    warp = tuple((i, j) for i in range(-2, 3) for j in range(-2, 3)
                 if (i, j) not in neighbor)
    # dist[r][c]: スタートから (r, c) に到達するために必要なワープ回数の最小値
    dist = [[float('inf')] * W for _ in range(H)]

    def is_inside(row, col):
        return 0 <= row < H and 0 <= col < W

    def next_query(row, col, time, _next, cost):
        for dr, dc in _next:
            nr, nc = row + dr, col + dc
            if is_inside(nr, nc) and Grid[nr][nc] == '.' and time < dist[nr][nc]:
                if cost == 0:
                    queue.append((nr, nc, time))
                else:
                    queue.appendleft((nr, nc, time + 1))

    queue = deque([(Start_row, Start_col, 0)])
    while queue:
        row, col, time = queue.pop()
        if time > dist[row][col]:
            continue  # キューに入れた時点では候補だったが、後に歩いて行けるとわかった

        dist[row][col] = time
        next_query(row, col, time, neighbor, 0)
        next_query(row, col, time, warp, 1)
    return -1 if dist[Goal_row][Goal_col] == float('inf') else dist[Goal_row][Goal_col]

print(d_wizard_in_maze())

### FIXED CODE ###

def d_wizard_in_maze():
    from collections import deque
    H, W = [int(i) for i in input().split()]
    Start_row, Start_col = [int(i) - 1 for i in input().split()]
    Goal_row, Goal_col = [int(i) - 1 for i in input().split()]
    Grid = [input() for _ in range(H)]

    warp_count = [[-1] * W for i in range(H)]
    neighbor_4 = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    neighbor_25 = [(i, j) for i in range(-2, 3) for j in range(-2, 3)]
    queue = deque([(Start_row, Start_col, 0)])  # コスト 0 の移動は左詰めする

    while(queue):
        row, col, count = queue.popleft()
        if warp_count[row][col] != -1:
            continue
        warp_count[row][col] = count

        for dr, dc in neighbor_4:
            nr, nc = row + dr, col + dc
            if 0 <= nr < H and 0 <= nc < W and Grid[nr][nc] == '.':
                if warp_count[nr][nc] == -1:
                    queue.appendleft((nr, nc, count))

        for dr, dc in neighbor_25:
            nr, nc = row + dr, col + dc
            if 0 <= nr < H and 0 <= nc < W and Grid[nr][nc] == '.':
                queue.append((nr, nc, count + 1))

    return warp_count[Goal_row][Goal_col]

print(d_wizard_in_maze())
### BUGGY CODE ###

import copy
n = int(input())
a = [list(map(int, input().split())) for i in range(n)]

for i in range(n):
    al = copy.copy(a)
    del al[i]
    print(max(al)[0])

### FIXED CODE ###

import copy
n = int(input())
a = [list(map(int, input().split())) for i in range(n)]

a_l = []
for i in range(n):
    a_l.append(a[i][0])
a1 = sorted(a_l)
m1 = a1[-1]
m2 = a1[-2] 

for i in a_l:
    if i == m1:
        print(m2)
    else:
        print(m1)
### BUGGY CODE ###

import math

#n = int(input())
#a, b, c = [int(i) for i in input().split()]
#table = [[int(i) for i in input().split()] for j in range(n)]
#table = [list(input()) for n in range(h)]
#list = [int(i) for i in input().split()]
#num = [int(i) for i in range(n)]
#s = [input() for i in range(n)]
s = input()
#list = list(s)
#temp = [[0 for _ in range(13)] for _ in range(13)]

n = len(s)
ans = [0 for i in range(n)]

for i in range(n) :
    if(s[i] == "R") :
        j = 1
        while(s[i+j] == "R") :
            j += 1
        if(j % 2 == 0) :
            ans[i+j] += 1
        else:
            ans[i+j-1] += 1
    else:
        j = 1
        while(s[i-j] == "L") :
            j += 1
        if (j % 2 == 0):
            ans[i-j] += 1
        else:
            ans[i-j+1] += 1

print(*ans)

### FIXED CODE ###

import math

#n = int(input())
#a, b, c = [int(i) for i in input().split()]
#table = [[int(i) for i in input().split()] for j in range(n)]
#table = [list(input()) for n in range(h)]
#list = [int(i) for i in input().split()]
#num = [int(i) for i in range(n)]
#s = [input() for i in range(n)]
s = input()
#list = list(s)
#temp = [[0 for _ in range(13)] for _ in range(13)]

n = len(s)
ans = [0 for i in range(n)]
ans2 = [0 for i in range(n)]

for i in range(n) :
    if(s[i] == "L") :
        if(s[i-1] == "R") :
            ans[i] = i
            ans2[i] += 1
        elif(s[i-2] == "L") :
            ans[i] = ans[i-2]
            ans2[ans[i]] += 1
        else:
            ans[i] = i-2
            ans2[ans[i]] += 1

for i in range(n-1, -1 ,-1) :
    if(s[i] == "R") :
        if(s[i+1] == "L") :
            ans[i] = i
            ans2[i] += 1
        elif (s[i+2] == "R"):
            ans[i] = ans[i+2]
            ans2[ans[i]] += 1
        else:
            ans[i] = i + 2
            ans2[ans[i]] += 1


print(*ans2)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
q = int(input())
b_c = []
for i in range(q):
    b_c.append(list(input().split()))

for i in range(q):
    for k in range(n):
        if int(b_c[i][0]) == a[k]:
            a[k] = int(b_c[i][1])
    print(sum(a))

### FIXED CODE ###

import collections

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

ans = sum(a)

for i in range(q):
    b,c = map(int, input().split())
    B = dic[b]
    ans = ans + (c-b) * B
    print(ans)
    dic[b] = 0
    dic[c] = dic[c] + B
### BUGGY CODE ###

s = input()
q = int(input())
for i in range(q):
	tfc = list(map(str, input().split()))
	if tfc[0] == '1':
		s = s[::-1]
	if tfc[0] == '2':
		if tfc[1] == '1':
			s = tfc[2] + s
		if tfc[1] == '2':
			s += tfc[2]
print(s)

### FIXED CODE ###

from collections import deque

s = input()
q = int(input())
revflag = 1
d = deque(s)
for i in range(q):
	tfc = list(map(str, input().split()))
	if tfc[0] == '1':
		revflag *= -1
	elif tfc[1] == '1':
		if revflag > 0:
			d.appendleft(tfc[2])
		else:
			d.append(tfc[2])
	else:
		if revflag > 0:
			d.append(tfc[2])
		else:
			d.appendleft(tfc[2])
if revflag > 0:
	print(''.join(d))
else:
	print(''.join(reversed(d)))
### BUGGY CODE ###

n = int(input())
l = list( map(int, input().split())) 
ans = 0

lsorted = sorted(l, reverse=True)

for longest in range(len(l)-2):

    for second in range(longest+1, len(l)):


        for k in range(second+1, len(l)):
            if lsorted[longest] - lsorted[second] - lsorted[k] >= 0:                
                break
            else:
                ans += 1

print(ans)

### FIXED CODE ###

from bisect import bisect_left

n = int(input())
l = list( map(int, input().split())) 
ans = 0
l.sort()

for i in range(n-2):
    shortest = l[i]
    for j in range(i+1, n-1):
        second = l[j]
        # このスライスしたやつと地味にTLEになる...
        # k = bisect_left(l[j], shortest + second)
        # ans += k

        k = bisect_left(l, shortest + second)
        ans += k - j - 1

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

s = input()
n = ""

c = 0
ln = len(s)
while "ABC" in s:
	f = []
	for i in s:
		if len(n) == 3:
			f.append(n[0])
			n = n[1:]
		n += i
		if n == "ABC":
			n = "BCA"
			c += 1
			f.append(n)
			n = ""
	s = "".join(f)
	if n:
		s += n		
print(c)
	


### FIXED CODE ###

s=input()
n=0
c=0
i=0
while i<len(s):
  if s[i]=="A":
    c+=1
  elif s[i:i+2]=="BC":
    n+=c
    i+=1
  else:
    c=0
  i+=1
print(n)