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

s = input()
q = int(input())

rev = 0
for i in range(q):
    inp = list(input().split())
    if inp[0] == '1':rev = rev ^ 1
    if inp[0] == '2':
        if (inp[1] == '1' and rev == 0) or (inp[1] == '2' and rev == 1):
            s = inp[2] + s
        else:
            s = s + inp[2]

print(s if rev == 0 else s[::-1])

### FIXED CODE ###

from collections import deque
s=input()
q=int(input())
ans_str=deque(s)
cnt=0
for _ in range(q):
    Q=list(input().split())
    if Q[0]=='1':
        cnt=1 if cnt==0 else 0

    else:
        if Q[1]=='1':
            if cnt==0 or len(ans_str)==1:
                ans_str.appendleft(Q[-1])
            else:
                ans_str.append(Q[-1])

        else:
            if cnt==0 or len(ans_str)==1:
                ans_str.append(Q[-1])
            else:
                ans_str.appendleft(Q[-1])
    #print(ans_str,cnt,Q)

ans=list(ans_str) if cnt==0 else list(ans_str)[::-1]
print(*ans,sep='')
### BUGGY CODE ###

n,k = map(int,input().split())
h = list(map(int,input().split()))
dp = [0]
for i in range(n-1):
    cnt = 10**9
    for j in range(k):
        if i-j < 0: continue
        cnt = min(dp[-1-j] + abs(h[i-j]-h[i+1]), cnt)
        #print("i =",i,"j =",j,"i-j =",i-j,"i+j =",i+j,"cnt =",cnt)
    dp.append(cnt)
print(dp[-1])

### FIXED CODE ###

n,k = map(int,input().split())
h = list(map(int,input().split()))
dp = [0]
for i in range(n-1):
    cnt = float("inf")
    for j in range(k):
        if i-j < 0: continue
        cnt = min(dp[-1-j] + abs(h[i-j]-h[i+1]), cnt)
        #print("i =",i,"j =",j,"i-j =",i-j,"i+j =",i+j,"cnt =",cnt)
    dp.append(cnt)
print(dp[-1])
### BUGGY CODE ###

from math import factorial


def combination(n, r):  # n個からr個選ぶ場合の数
    if n < r:
        return 0
    else:
        return factorial(n)//(factorial(r) * factorial(n-r))


from itertools import accumulate
N = int(input())
A = [int(i) for i in input().split()]
cumsum = list(accumulate(A))
ans = 0
for a in set(cumsum):
    cnt = 0
    for c in cumsum:
        if a == c:
            cnt += 1
    ans += combination(cnt, 2)
ans += cumsum.count(0)
print(ans)


### FIXED CODE ###

from math import factorial
from itertools import accumulate


def combination(n, r):  # n個からr個選ぶ場合の数
    if n < r:
        return 0
    else:
        return factorial(n)//(factorial(r) * factorial(n-r))


N = int(input())
A = [int(i) for i in input().split()]
ans = 0
cumsum = sorted(list(accumulate(A)))
now = None
cnt = 1
for a in cumsum:
    if now is None:
        now = a
    elif now == a:
        cnt += 1
    else:
        ans += combination(cnt, 2)
        cnt = 1
        now = a
ans += combination(cnt, 2)
ans += cumsum.count(0)
print(ans)
### BUGGY CODE ###

def main():
  N = int(input())
  A = list(map(int, input().split()))
  MOD = 10 ** 9 + 7
  ones = [sum(1 for a in A if a&(1<<i)) for i in range(60)]
  res = 0
  for j in range(N):
    a = A[j]
    for i in range(60):
      if (a >> i) & 1 == 0:
        res += ones[i] * (2 ** i)%MOD
      else:
        res += (N-ones[i]-j) * (2 ** i)%MOD
        ones[i] -= 1
      res %= MOD
  
  print(res)
if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
  N = int(input())
  A = list(map(int, input().split()))
  MOD = 10 ** 9 + 7
  ones = [sum(1 for a in A if a&(1<<i)) for i in range(60)]
  res = 0
  for i in range(60):
    res += ones[i] * (N - ones[i]) * ((2 ** i) % MOD)
    res %= MOD
  print(res)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

# coding: utf-8
# Your code here!
# coding: utf-8
# Your code here!
N,M=map(int,input().split())

dp=[[[[[[[[[[[[10**9]*2 for _ in range(2)]for _ in range(2)]for _ in range(2)]for _ in range(2)]for _ in range(2)]for _ in range(2)]for _ in range(2)]for _ in range(2)]for _ in range(2)]for _ in range(2)]for _ in range(2)]

dp[0][0][0][0][0][0][0][0][0][0][0][0]=0

for _ in range(M):
    al,bl=map(int,input().split())
    temp=[0]*12
    cl=list(map(int,input().split()))
    for item in cl:
        temp[item-1]=1
    for a in range(2):
        for b in range(2):
            for c in range(2):
                for d in range(2):
                    for e in range(2):
                        for f in range(2):
                            for g in range(2):
                                for h in range(2):
                                    for i in range(2):
                                        for j in range(2):
                                            for k in range(2):
                                                for l in range(2):
                                                    if dp[a][b][c][d][e][f][g][h][i][j][k][l]!=10**9:
                                                        dp[max(a,temp[0])][max(b,temp[1])][max(c,temp[2])][max(d,temp[3])][max(e,temp[4])][max(f,temp[5])][max(g,temp[6])][max(h,temp[7])][max(i,temp[8])][max(j,temp[9])][max(k,temp[10])][max(l,temp[11])]=min(dp[max(a,temp[0])][max(b,temp[1])][max(c,temp[2])][max(d,temp[3])][max(e,temp[4])][max(f,temp[5])][max(g,temp[6])][max(h,temp[7])][max(i,temp[8])][max(j,temp[9])][max(k,temp[10])][max(l,temp[11])],dp[a][b][c][d][e][f][g][h][i][j][k][l]+al)
                                                        
                            
    #print(temp)

fa=[0]*12
for i in range(N):
    fa[i]=1

#print(fa)
if dp[fa[0]][fa[1]][fa[2]][fa[3]][fa[4]][fa[5]][fa[6]][fa[7]][fa[8]][fa[9]][fa[10]][fa[11]]==10**9:
    print(-1)
else:
    print(dp[fa[0]][fa[1]][fa[2]][fa[3]][fa[4]][fa[5]][fa[6]][fa[7]][fa[8]][fa[9]][fa[10]][fa[11]])




### FIXED CODE ###

# coding: utf-8
# Your code here!
# coding: utf-8
# Your code here!
N,M=map(int,input().split())

dp=[10**9]*2**N

dp[0]=0

for _ in range(M):
    a,b=map(int,input().split())
    c=list(map(int,input().split()))
    cl=["0"]*N
    for item in c:
        cl[item-1]="1"
    plus=int(str("".join(cl)),2)
    for i in range(len(dp))[::-1]:
        if dp[i]!=10**9:
            #print(i,i|plus)
            dp[i|plus]=min(dp[i|plus],dp[i]+a)
if dp[-1]!=10**9:
    print(dp[-1])
else:
    print(-1)
### BUGGY CODE ###

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

# prepare
mul = 1
for i in range(k):
    mul *= a[i]

prev = mul
for i in range(k, n):
    next = prev / a[i - (k)] * a[i]
    if next > prev:
        print('Yes')
    else:
        print('No')
    prev = next

### FIXED CODE ###

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

for i in range(k, n):
    prev = a[i - k]
    next = a[i]
    if next > prev:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000000)

def gcd(a: int, b:int):
    while b:
        a,b=b,a%b
    return a

def merge(a,us,vs):
    i,j,res=0,0,[]
    while i<len(us) and j<len(vs):
        if a[us[i]]>=a[vs[j]]:
            res.append(us[i])
            i+=1
        else:
            res.append(vs[j])
            j+=1
    return res+us[i:]+vs[j:]

def dfs(g,a,u,vis):
    vis[u]=True
    res=[]
    for v in g[u]:
        if not vis[v]:
            res=merge(a,res,dfs(g,a,v,vis))
    return [u]+res

while 1:
    try:
        n=int(input())
        a=sorted(map(int,input().split()))
    except: break

    g=[[] for _ in range(n)]
    for i in range(n):
        for j in range(i+1,n):
            if gcd(a[i],a[j])!=1:
                g[i].append(j)
                g[j].append(i)

    vis=[False]*n
    res=[]
    for u in range(n):
        if not vis[u]:
            res=merge(a,res,dfs(g,a,u,vis))
    print(' '.join(str(a[u]) for u in res))


### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000000)

def gcd(a: int, b:int):
    while b:
        a,b=b,a%b
    return a

def merge(a,us,vs):
    i,j,res=0,0,[]
    while i<len(us) and j<len(vs):
        if a[us[i]]>=a[vs[j]]:
            res.append(us[i])
            i+=1
        else:
            res.append(vs[j])
            j+=1
    return res+us[i:]+vs[j:]

def dfs(g,a,u,vis):
    vis[u]=True
    res=[]
    for v in g[u]:
        if not vis[v]:
            res=merge(a,res,dfs(g,a,v,vis))
    return [u]+res

while 1:
    try:
        n=int(input())
        a=sorted(map(int,input().split()))
    except: break

    g=[[] for _ in range(n)]
    for i in range(n):
        for j in range(i+1,n):
            if gcd(a[i],a[j])!=1:
                g[i].append(j)
                g[j].append(i)

    vis=[False]*n
    res=[]
    for u in range(n):
        if not vis[u]:
            res=merge(a,res,dfs(g,a,u,vis))
    print(' '.join(str(a[u]) for u in res))
### BUGGY CODE ###

import heapq
import sys

sys.setrecursionlimit(1000)

BLACK = '#'
WHITE = '.'


def m():
    H, W = [int(x) for x in input().split(' ')]
    board = [[c for c in list(input())] for _ in range(H)]

    # x, y, score
    q = [(0, 0, 0)]
    is_reachable = False
    while len(q) > 0:
        p, x, y = heapq.heappop(q)
        board[x][y] = p
        if x == H - 1 and y == W - 1:
            is_reachable = True

        nexts = [(x+1, y), (x, y+1), (x-1, y), (x, y-1)]
        for i, j in nexts:
            if 0 <= i and i < H and 0 <= j and j < W:
                if board[i][j] == BLACK:
                    continue

                if board[i][j] == WHITE:
                    heapq.heappush(q, (p+1, i, j))
                    continue

                if board[i][j] > p+1:
                    heapq.heappush(q, (p+1, i, j))
                    continue

    if is_reachable:
        blacks = 0
        for i in range(H):
            for j in range(W):
                if board[i][j] == BLACK:
                    blacks += 1
        ans = H*W - blacks - board[H-1][W-1] - 1
        print(ans)
    else:
        print(-1)


m()


### FIXED CODE ###

import heapq
import sys

sys.setrecursionlimit(1000)

BLACK = '#'
WHITE = '.'


def m():
    H, W = [int(x) for x in input().split(' ')]
    board = [[c for c in list(input())] for _ in range(H)]

    # x, y, score
    q = [(0, 0, 0)]
    is_reachable = False
    while len(q) > 0:
        p, x, y = heapq.heappop(q)
        if x == H - 1 and y == W - 1:
            is_reachable = True

        nexts = [(x+1, y), (x, y+1), (x-1, y), (x, y-1)]
        for i, j in nexts:
            if 0 <= i and i < H and 0 <= j and j < W:
                if board[i][j] == BLACK:
                    continue

                if board[i][j] == WHITE:
                    board[i][j] = p+1
                    heapq.heappush(q, (p+1, i, j))
                    continue

                if board[i][j] > p+1:
                    board[i][j] = p+1
                    heapq.heappush(q, (p+1, i, j))
                    continue

    if is_reachable:
        blacks = 0
        for i in range(H):
            for j in range(W):
                if board[i][j] == BLACK:
                    blacks += 1
        ans = H*W - blacks - board[H-1][W-1] - 1
        print(ans)
    else:
        print(-1)


m()
### BUGGY CODE ###

#初期入力
import sys
input = sys.stdin.readline
import random
N = int(input())
connection   ={i:set() for i in range(1,N+1)}
A            ={i:tuple() for i in range(1,N+1)}
for i in range(N-1):
    a,b = (int(x) for x in input().split())
    connection[a].add(b) # つながりを逆向きも含めて入力
    connection[b].add(a) # 
    A[i]=a,b             #色を出力するため

#色の数(各頂点の最大値)
color_max =0
for i in connection.values():
    color_max =max(color_max, len(i) )

#各頂点に色を準備⇒辺の色決定
A_sort =sorted(A)
color_node ={i:[] for i in range(1,N+1)} #頂点に使った色の管理
color_edge =[0]*(N-1)

#color_all =set(j for j in range(color_max) ) #0～color_max-1
for i in range(N-1):
    color =0
    while True:
        q,color =divmod(color,color_max)
        v_a,v_b = A[i] #i番目の辺とつながっている頂点
      
        if color not in color_node[v_a] and color not in color_node[v_b]: 
            color_edge[i] =color+1          #辺の色を出力用に決める。1～color_max
            color_node[v_a].append(color)    #前の頂点に使った色を追加
            color_node[v_b].append(color)    #先の頂点に使った色を追加
            break
        else:
            color +=1      
#出力
print(color_max)
print(*color_edge, sep="\n")

### FIXED CODE ###

"""
参考    yy4さん 2019-11-24 21:24:43
516 ms          PyPy3 (2.4.0)
"""
#def solve():
from collections import deque
import sys

input = sys.stdin.readline

n = int(input())

g = tuple(set() for _ in range(n))
for idx in range(n - 1):
    a, b = (int(x) - 1 for x in input().split())
    g[a].add((b, idx))
    g[b].add((a, idx))

q = deque()
q.append((0, -1, -1))

e = [-1] * n  # e[-1]は使わない
used = [False] * n
used[0] = True
while q:
    v, v_idx, prev_color = q.popleft()
    curr = 1 if prev_color != 1 else 2
    for u, u_idx in g[v]:
        if used[u]:
            continue
        used[u] = True
        e[u_idx] = curr
        q.append((u, u_idx, curr))
        curr += 1
        if curr == prev_color:
            curr += 1

ret = e[:-1]
#return len(set(ret)), ret

    
#l, ret = solve()
l=len(set(ret))
print(l)
print(*ret, sep='\n')
### BUGGY CODE ###

class Dijkstra():
    """ ダイクストラ法
    重み付きグラフにおける単一始点最短路アルゴリズム

    * 使用条件
        - 負のコストがないこと
        - 有向グラフ、無向グラフともにOK

    * 計算量はO(E*log(V))

    * ベルマンフォード法より高速なので、負のコストがないならばこちらを使うとよい
    """
    class Edge():
        """ 重み付き有向辺 """
        def __init__(self, _to, _cost):
            self.to = _to
            self.cost = _cost

    def __init__(self, V):
        """ 重み付き有向辺
        無向辺を表現したいときは、_fromと_toを逆にした有向辺を加えればよい

        Args:
            V(int): 頂点の数
        """
        self.G = [[] for i in range(V)]  # 隣接リストG[u][i] := 頂点uのi個目の隣接辺
        self._E = 0  # 辺の数
        self._V = V  # 頂点の数

    @property
    def E(self):
        """ 辺数
        無向グラフのときは、辺数は有向グラフの倍になる
        """
        return self._E

    @property
    def V(self):
        """ 頂点数 """
        return self._V

    def add(self, _from, _to, _cost):
        """ 2頂点と、辺のコストを追加する """
        self.G[_from].append(self.Edge(_to, _cost))
        self._E += 1

    def shortest_path(self,s):

        import heapq
        que=[]
        D=[(10**15,L)] * self.V
        D[s]=(0,0)
        heapq.heappush(que,((0,0),s))

        while len(que)!=0:
            cost,v=heapq.heappop(que)
            a,b=cost
            c,d=D[v]

            if a>c:
                continue
            elif a==c and b>d:
                continue

            for i in range(len(self.G[v])):
                e=self.G[v][i]
                a,b=D[e.to]
                nokori=L-cost[1]
                if nokori>=e.cost:
                    c,d=cost[0],cost[1]+e.cost
                else:
                    c,d=cost[0]+1,e.cost
                if a>c or (a==c and b>d):
                    D[e.to]=(c,d)
                    heapq.heappush(que,(D[e.to],e.to))

        return D

import sys

input=sys.stdin.readline

N,M,L=map(int,input().split())
city=Dijkstra(N)
for i in range(0,M):
    a,b,c=map(int,input().split())
    if L>=c:
        city.add(a-1,b-1,c)
        city.add(b-1,a-1,c)

ans=[city.shortest_path(i) for i in range(0,N)]

Q=int(input())
for i in range(0,Q):
    s,t=map(int,input().split())
    if ans[s-1][t-1]!=(10**15,L):
        print(ans[s-1][t-1][0])
    else:
        print(-1)

### FIXED CODE ###

import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix

N,M,L=map(int,input().split())
d=[[0 for i in range(0,N)] for i in range(0,N)]
for i in range(0,M):
    a,b,c=map(int,input().split())
    d[a-1][b-1]=c
    d[b-1][a-1]=c

csr1=csr_matrix(d)

a=floyd_warshall(csr1)

d=[[0 for i in range(0,N)] for j in range(0,N)]
for i in range(0,N):
    for j in range(0,N):
        if L>=a[i][j]:
            d[i][j]=1


csr2=csr_matrix(d)

data=floyd_warshall(csr2)
ans=[]
Q=int(input())
for i in range(0,Q):
    s,t=map(int,input().split())
    if data[s-1][t-1]!=float('inf'):
        ans.append(int(data[s-1][t-1])-1)
    else:
        ans.append(-1)

for i in range(Q):
    print(ans[i])
### BUGGY CODE ###

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

for _ in range(Q):
    a, b = map(int, input().split())
    ans = S[a-1:b].count('AC')
    print(ans)


### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
s = S[:2]
ans = 'AC'
lst = [0]
count = 0
for i in range(N-1):
    s = S[i] + S[i + 1]
    count += (s == ans)
    lst.append(count)

for _ in range(Q):
    a, b = map(int, input().split())
    print(lst[b - 1] - lst[a - 1])
### BUGGY CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
S = input()
cnt = 0

for i in range(N-2):
	for j in range(i+1, N-1):
		if S[i] != S[j]:
			for k in range(j+1, N):
				if S[j] != S[k] and S[i] != S[k] and j-i != k-j:
					cnt += 1

print(cnt)

### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
 
N = INT()
S = list(input())
 
r = S.count("R")
g = S.count("G")
b = S.count("B")
 
 
A = list(range(len(S)))
cnt = 0
for x, y in combinations(A, 2):
	if (x+y)//2 == (x+y)/2:
		z = (x+y)//2
		if S[x] != S[y] and S[x] != S[z] and S[y] != S[z]:
			cnt += 1
 
print(r*g*b-cnt)
### BUGGY CODE ###

sn,bn=map(int,input().split(" "))
fubensa=[int(sn*(sn-1)/2)]
if bn>1:
    br=[]
    for _ in range(bn):
        br.append(list(map(int, input().split(" "))))
    br=br[::-1]
    sg=[0 for n in range(sn+1)]
    sg[br[0][0]]=1
    sg[br[0][1]]=1
    gn=1
    fubensa.append(fubensa[0]-1)
    sgc=[0,2]

    for bri in range(1,bn-1):
        si1=br[bri][0]
        si2=br[bri][1]
        sg1=sg[si1]
        sg2=sg[si2]
        if sg1+sg2==0:
            gn+=1
            sg[si1],sg[si2]=gn,gn
            sgc.append(2)
            fubensa.append(fubensa[bri]-1)
        elif sg1==0:
            fubensa.append(fubensa[bri] - sgc[sg2])
            sg[si1]=sg2
            sgc[sg2]+=1
        elif sg2==0:
            fubensa.append(fubensa[bri] - sgc[sg1])
            sg[si2]=sg1
            sgc[sg1] += 1
        elif sg1!=sg2:
            fubensa.append(fubensa[bri] - sgc[sg1]*sgc[sg2])
            sgc[sg1]+=sgc[sg2]
            sg=[sg1 if x==sg2 else x for x in sg]
        else:
            fubensa.append(fubensa[bri])
for x in fubensa[::-1]:
    print(x)

### FIXED CODE ###

sn,bn=map(int,input().split(" "))
fu=[int(sn*(sn-1)/2)]
gr_si=[n for n in range(sn+1)]
siL_gr=[[n] for n in range(sn+1)]
siL_br=[]
for _ in range(bn):
    siL_br.append(list(map(int, input().split(" "))))
siL_br=siL_br[::-1]

for bri in range(bn-1):
    si1,si2=siL_br[bri]
    gr1 = gr_si[si1]
    gr2 = gr_si[si2]
    if gr1==gr2:
        fu.append(fu[bri])
    else:
        lengr1 = len(siL_gr[gr1])
        lengr2 = len(siL_gr[gr2])
        if lengr1<lengr2:
            gr1,gr2=gr2,gr1
        fu.append(fu[bri]-lengr1*lengr2)
        for si in siL_gr[gr2]:
            gr_si[si]=gr1
        siL_gr[gr1]+=siL_gr[gr2]
        siL_gr[gr2]=[]

print(*fu[::-1],sep="\n")
### BUGGY CODE ###

import sys
input=sys.stdin.readline   #input高速化 １文字の時の改行文字に注意+

d={i:0 for i in range(3001)}
db={i:0 for i in range(3001)}

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

x=[tuple(map(int,input().split()))for i in range(n)]

dp=[]
dp2=[]
for time,value in x:
    for k,v in d.copy().items():
        if k+time<t:
            if d[k+time]<v+value:
                d[k+time]=v+value
    l=[0]
    for i in range(1,t+1):
        if d[i]>l[-1]:
            l.append(d[i])
        else:
            l.append(l[-1])

    dp.append(l)    
        
for time,value in x[::-1]:
    for k,v in db.copy().items():
        if k+time<t:
            if db[k+time]<v+value:
                db[k+time]=v+value
    l=[0]
    for i in range(1,t+1):
        if db[i]>l[-1]:
            l.append(db[i])
        else:
            l.append(l[-1])
        
    dp2.append(l)
dp=[[0]*t,[0]*t]+dp
dp2=([[0]*t,[0]*t]+dp2)[::-1]

ans=0

for i in range(len(dp)):
    for j in range(t):
        if i==0 or i==len(dp)-1:
            tmp=dp[i][j]+dp2[i][t-j-1]
            if ans<tmp:
                ans=tmp
        else:
            tmp=dp[i][j]+dp2[i][t-j-1]+x[i-1][1]
            if tmp>ans:
                ans=tmp
print(ans)

### FIXED CODE ###

import sys
input=sys.stdin.readline   #input高速化 １文字の時の改行文字に注意+

d={i:0 for i in range(3001)}
db={i:0 for i in range(3001)}

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

x=[tuple(map(int,input().split()))for i in n*[0]]
x.sort()
dp=[]
dp2=[]
for time,value in x:
    for k,v in d.copy().items():
        if k+time<t:
            if d[k+time]<v+value:
                d[k+time]=v+value
        else:
            break
    l=[0]
    for i in range(1,t+1):
        if d[i]>l[-1]:
            l.append(d[i])
        else:
            l.append(l[-1])

    dp.append(l)    
        
for time,value in x[::-1]:
    for k,v in db.copy().items():
        if k+time<t:
            if db[k+time]<v+value:
                db[k+time]=v+value
        else:
            break

    l=[0]
    for i in range(1,t+1):
        if db[i]>l[-1]:
            l.append(db[i])
        else:
            l.append(l[-1])
        
    dp2.append(l)
dp=[[0]*t,[0]*t]+dp
dp2=([[0]*t,[0]*t]+dp2)[::-1]

ans=0

for i in range(len(dp)):
    for j in range(t):
        if i==0 or i==len(dp)-1:
            tmp=dp[i][j]+dp2[i][t-j-1]
            if ans<tmp:
                ans=tmp
        else:
            tmp=dp[i][j]+dp2[i][t-j-1]+x[i-1][1]
            if tmp>ans:
                ans=tmp
print(ans)
### BUGGY CODE ###

n=int(input())
S=list(input())

ans=0
for v in range(1000):
  v=str(v).zfill(3)
  idx,cnt=0,0
  for i in range(n):
    if S[i]==v[idx]:
      idx+=1
    else:
      cnt+=1
    if idx>=3:
      ans+=1
      break
print(ans)

### FIXED CODE ###

n=int(input())
S=input()

ans=0
for i in range(10):
  for j in range(10):
    for k in range(10):
      idxi=S.find(str(i))
      if idxi==-1:
        continue
      idxj=S.find(str(j),idxi+1)
      if idxj==-1:
        continue
      idxk=S.find(str(k),idxj+1)
      if idxk==-1:
        continue
      ans+=1
print(ans)