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

from scipy.sparse import csr_matrix #pypyだとエラーになるので、pythonを使うこと
from scipy.sparse.csgraph import shortest_path

import sys
def input():
	return sys.stdin.readline().strip()

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

graph = csr_matrix((N, N))

for i in range(M):
	A, B, C = list(map(int, input().split()))
	graph[A - 1, B - 1] = C
	graph[B - 1, A - 1] = C


dist = shortest_path(graph, method='FW')
graph2 = csr_matrix((N, N))
for i in range(N):
	for j in range(N):
		if dist[i, j] <= L:
			graph2[i, j] = 1
graph2 = csr_matrix(graph2)
num = shortest_path(graph2, method="FW")


Q = int(input())
for q in range(Q):
	s, t = list(map(int, input().split()))
	if num[s - 1][t - 1] < 10000000:
		print(int(num[s - 1][t - 1] - 1))
	else:
		print(-1)

### FIXED CODE ###


import sys
from collections import deque, defaultdict
import copy
import bisect
sys.setrecursionlimit(10 ** 9)
import math
import heapq
from itertools import product, permutations,combinations
import fractions
from operator import itemgetter

import sys
def input():
	return sys.stdin.readline().strip()

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

graph = [[] for _ in range(N)]

for i in range(M):
	A, B, C = list(map(int, input().split()))
	if C <= L:
		graph[A - 1].append((B - 1, C))
		graph[B - 1].append((A - 1, C))

num_matrix = [[0]*N for i in range(N)]


for start in range(N):
	dist = [(1000000, 0)]*N
	que = []
	heapq.heappush(que, (0, 0, start))
	dist[start] = (0, 0)
	while len(que) > 0:

		node = heapq.heappop(que)
		#print(start, que, node)
		if node[0] == dist[node[2]][0] and node[1] == dist[node[2]][1]:
			#print(1)
			for edge in graph[node[2]]:
				#print(edge)
				#print(edge[1] + dist[node[2]][1] )
				if edge[1] + dist[node[2]][1] > L:
					next_dist = (dist[node[2]][0] + 1, edge[1], edge[0])
				else:
					next_dist = (dist[node[2]][0], dist[node[2]][1] + edge[1], edge[0])
				if dist[edge[0]][0] > next_dist[0]:
					dist[next_dist[2]] = (next_dist[0], next_dist[1])
					heapq.heappush(que, next_dist)
				elif dist[edge[0]][0] == next_dist[0] and dist[edge[0]][1] > next_dist[1]:
					heapq.heappush(que, next_dist)
					dist[next_dist[2]] = (next_dist[0], next_dist[1])
	for i in range(N):
		num_matrix[start][i] = dist[i][0]

#print(num_matrix)

Q = int(input())
for q in range(Q):
	s, t = list(map(int, input().split()))
	if num_matrix[t - 1][s - 1] < 1000:
		print(num_matrix[t - 1][s - 1])
	else:
		print(-1)
### BUGGY CODE ###

N, K = list(map(int,input().split()))
A = [int(a) for a in input().split()]

import itertools

B = list(itertools.combinations(A,K))


ansA=[]
for i in range(0, len(B)):
    ans = max(B[i])-min(B[i])
    if ans !=0:
        ansA.append(ans)

print(sum(ansA)%(10**9+7))


### FIXED CODE ###

import math
N, K = map(int, input().split())
A = [int(a) for a in input().split()]

A.sort()

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
Ne = 10**5
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, Ne + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )



maxi = 0
for i in range(K-1,N):
    maxi += A[i]*cmb(i, K-1, mod)

mini = 0
A.sort(reverse=True)
for j in range(K-1,N):
    mini += A[j]*cmb(j, K-1, mod)

print((maxi-mini)%mod)
### BUGGY CODE ###

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

AB = []
for i in range(M):
    l = list(map(int, input().split()))
    AB.append(l)

adj_mat = [[False] * N for i in range(N)]
friends_list = [1] * N 

for i in range(M):
    a, b = AB[i][0], AB[i][1]
    a -= 1;
    b -= 1;

    if (not adj_mat[a][b]):
        friends_list[a] += 1
    if (not adj_mat[b][a]):
        friends_list[b] += 1

    adj_mat[a][b] = True
    adj_mat[b][a] = True

max_friends = 0
for f_num in friends_list:
    max_friends = max(f_num, max_friends)

print(max_friends)


### FIXED CODE ###

class UFTree:
    def __init__(self, N):
        self.nodes = [Node(i) for i in range(N)]
        self.N = N

    def find_max_child_num(self):
        result = 0
        for i in range(self.N):
            result = max(result, self.nodes[i].child_num)
        return result

class Node:
    def __init__(self, ID):
        self.ID = ID
        self.parent = None
        self.child_num = 0
        self.rank = 1

    def get_root(self):
        if self.parent is None:
            return self
        
        return self.parent.get_root()

    def is_in_same_tree(self, another):
        return self.get_root().ID == another.get_root().ID

    def concat(self, another):
        if self.is_in_same_tree(another):
            return

        sr = self.get_root()
        ar = another.get_root()

        if sr.rank > ar.rank:
            parent, child = sr, ar
        else:
            parent, child = ar, sr

        parent.child_num += child.child_num + 1
        parent.rank = max(parent.rank, child.rank + 1)
        child.parent = parent

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

AB = []
for i in range(M):
    l = list(map(int, input().split()))
    AB.append(l)

for i in range(M):
    a, b = AB[i][0], AB[i][1]
    a -= 1;
    b -= 1;

    tree.nodes[a].concat(tree.nodes[b])

# # for debug
# for i in range(N):
#     n = tree.nodes[i]
#     if n.parent is None:
#         print(i + 1, "is root")
#     else:
#         print("parent of", i + 1, "is", n.parent.ID + 1)

print(tree.find_max_child_num() + 1)
### BUGGY CODE ###

N, M, Q = map(int, input().split())
LR = [list(map(int, input().split())) for _ in range(M)]
pq = [list(map(int, input().split())) for _ in range(Q)]

XY = [[0 for _ in range(N)] for _ in range(N)]
for l, r in LR:
    XY[l - 1][r - 1] += 1

for i in range(N):
    for j in range(N - 1):
        XY[i][j + 1] += XY[i][j]

for p, q in pq:
    count = 0
    for i in range(p - 1, q):
        if p - 2 >= 0:
            count += XY[i][q - 1] - XY[i][p - 2]
        else:
            count += XY[i][q - 1] - 0
    print(count)


### FIXED CODE ###

N, M, Q = map(int, input().split())
LR = [list(map(int, input().split())) for _ in range(M)]
pq = [list(map(int, input().split())) for _ in range(Q)]

XY = [[0 for _ in range(N)] for _ in range(N)]
for l, r in LR:
    XY[l - 1][r - 1] += 1

for i in range(N):
    for j in range(N):
        if i == 0 and j == 0:
            pass
        elif i == 0:
            XY[i][j] += XY[i][j - 1]
        elif j == 0:
            XY[i][j] += XY[i - 1][j]
            pre_im1_j = XY[i - 1][j]
        else:
            if XY[i - 1][j] == pre_im1_j:
                XY[i][j] += XY[i][j - 1]
            else:
                XY[i][j] += XY[i][j - 1] + XY[i - 1][j] - pre_im1_j
                pre_im1_j = XY[i - 1][j]

for p, q in pq:
    if p != 1:
        print(XY[q - 1][q - 1] + XY[p - 2][p - 2] - XY[p - 2][q - 1] - XY[q - 1][p - 2])
    else:
        print(XY[q - 1][q - 1])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 7)
# 深さ優先探索で各直線を考える


def dfs(v, p):
    for u in tree[v]:
        if u == p:
            continue
        # 累積和の計算
        ans[u] += ans[v]
        dfs(u, v)


n, q = map(int, input().split())
# tree[i]: 頂点i+1の子どもたち
tree = [[] for i in range(n)]
ans = [0] * n

for _ in range(0, n - 1):
    a, b = map(int, input().split())
    tree[a - 1].append(b - 1)
    tree[b - 1].append(a - 1)

for _ in range(q):
    p, x = map(int, input().split())
    ans[p - 1] += x

# 根ノードの頂点 1 から開始
dfs(0, -1)

print(*ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
# 深さ優先探索で各直線を考える


def main():
    def dfs(v, p):
        for u in tree[v]:
            if u == p:
                continue
            # 累積和の計算
            ans[u] += ans[v]
            dfs(u, v)

    n, q = map(int, input().split())
    # tree[i]: 頂点i+1の子どもたち
    tree = [[] for i in range(n)]
    ans = [0] * n

    for _ in range(0, n - 1):
        a, b = map(int, input().split())
        tree[a - 1].append(b - 1)
        tree[b - 1].append(a - 1)

    for _ in range(q):
        p, x = map(int, input().split())
        ans[p - 1] += x

    # 根ノードの頂点 1 から開始
    dfs(0, -1)

    print(*ans)


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

n = int(input())
l = list(map(int,input().split()))
count = 0
ll = [l[0]]
for i in range(n):
  m = l[i]
  ll.append(m)
  if min(ll) == m:
    count = count + 1
print(count)
    

### FIXED CODE ###

n = int(input())
l = list(map(int,input().split()))
count = 0
f = l[0]
count = 0
for i in range(n):
  m = l[i]
  if f >= m :
    count += 1
    f = m
print(count)
### BUGGY CODE ###

# https://atcoder.jp/contests/agc039/submissions/7877660
from collections import deque

INF = float('inf')


def bfs(n, es):
    parity = [-1] * n
    parity[0] = 0

    dq = deque()
    dq.append(0)
    while dq:
        v = dq.popleft()
        nxt_par = parity[v] ^ 1
        for u in es[v]:
            if parity[u] == -1:
                parity[u] = nxt_par
                dq.append(u)
            else:
                if parity[u] != nxt_par:
                    return False
                    # bipartite = False
    return True
    # bipartite = True


def warshall_floyd(n, g):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                g[i][j] = min(g[i][j], g[i][k] + g[k][j])
    return g


def solve():
    n = int(input())
    es = tuple(set() for _ in range(n))
    g = []
    for v in range(n):
        s = input()
        for u, is_adj in enumerate(map(int, s)):
            if is_adj:
                es[v].add(u)
                es[u].add(v)
        g.append(list(map(int, s)))
    for r, row in enumerate(g):
        for c, cell in enumerate(row):
            if cell == 0 and r != c:
                g[r][c] = INF
        # 隣接頂点間: 1
        # 同一頂点間: 0
        # その他: INF
    # print(es)
    # print(g)

    # 二部グラフ判定
    bipartite = bfs(n, es)
    if not bipartite:
        return -1

    # 最遠点対間距離を求める
    g = warshall_floyd(n, g)
    d = max(max(row) for row in g)
    return d + 1


if __name__ == '__main__':
    print(solve())


### FIXED CODE ###

# https://atcoder.jp/contests/agc039/submissions/7877660
from collections import deque

INF = float('inf')


def bfs(n, es):
    parity = [-1] * n
    parity[0] = 0

    dq = deque()
    dq.append(0)
    while dq:
        v = dq.popleft()
        nxt_par = parity[v] ^ 1
        for u in es[v]:
            if parity[u] == -1:
                parity[u] = nxt_par
                dq.append(u)
            else:
                if parity[u] != nxt_par:
                    return False
                    # bipartite = False
    return True
    # bipartite = True


def warshall_floyd(n, g):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                g[i][j] = min(g[i][j], g[i][k] + g[k][j])
    return g


def solve():
    n = int(input())
    es = tuple(set() for _ in range(n))
    g = []
    for v in range(n):
        s = input()
        for u, is_adj in enumerate(map(int, s)):
            if is_adj:
                es[v].add(u)
                es[u].add(v)
        g.append(list(map(int, s)))
    for r, row in enumerate(g):
        for c, cell in enumerate(row):
            if cell == 0 and r != c:
                g[r][c] = INF
        # 隣接頂点間: 1
        # 同一頂点間: 0
        # その他: INF
    # print(es)
    # print(g)

    # 二部グラフ判定
    bipartite = bfs(n, es)
    if not bipartite:
        return -1

    # 最遠点対間距離を求める
    g = warshall_floyd(n, g)
    d = max(max(row) for row in g)
    return d + 1


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

# https://beta.atcoder.jp/contests/agc025/tasks/agc025_b
from functools import reduce
import operator as op

MOD = 998244353
mod_inv_dp = [0, 1]


def mod_inv(n):
    if len(mod_inv_dp) >= n + 1:
        return mod_inv_dp[n]
    else:
        ans = MOD - (MOD // n) * mod_inv(MOD % n) % MOD
        mod_inv_dp.append(ans)
        return ans


def nCr(n, r):
    r = min(r, n - r)
    ans = 1
    for i in range(n, n - r, -1):
        ans = (ans * i) % MOD
    for i in range(1, r + 1):
        ans = mod_inv(i) * ans % MOD
    return ans


def gcd(a, b):
    """ requires a>=b """
    if b == 0:
        return a
    return gcd(b, a % b)


def main():
    n, a, b, k = map(int, input().split())

    gcdab = gcd(a, b)
    solutions = []

    if n==0:
        print(1)
        return

    if k % gcdab != 0:
        print(0)
        return

    for x in range(0, n + 1):
        yb = k - a*x
        if yb >= 0 and yb % b == 0: # and x + yb//b <= n:
            solutions.append([x, yb // b])

    ways = 0
    for x, y in solutions:
        for z in range(0, min(x, y) + 1):
            ways += nCr(n, z) * nCr(n - z, x - z) * nCr(n - x, y - z)
            ways %= MOD

    print(ways)


if __name__ == "__main__":
    main()


### FIXED CODE ###

# https://beta.atcoder.jp/contests/agc025/tasks/agc025_b
from functools import reduce
import operator as op

MOD = 998244353
mod_inv = [0, 1]


def init_mod_inv(n):
    for i in range(2, n + 1):
        ans = MOD - (MOD // i) * mod_inv[MOD % i] % MOD
        mod_inv.append(ans)


def main():
    n, a, b, k = map(int, input().split())

    init_mod_inv(n)
    nCr = [0] * (n + 1)
    nCr[0] = 1
    for i in range(1, n+1):
        nCr[i] = (nCr[i - 1] * (n - i + 1) * mod_inv[i]) % MOD

    ways = 0
    for x in range(0, n + 1):
        yb = k - a * x
        if yb >= 0 and yb % b == 0 and yb // b <= n:
            ways += nCr[x] * nCr[yb // b]
            ways %= MOD
    print(ways)


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

import numpy as np
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, M = map(int, readline().split())
ST = np.array(read().split(), dtype=np.int64)
S = ST[::2]
T = ST[1::2]

edge = np.zeros((N + 1, N + 1), dtype=np.int64)
edge[S, T] = 1
edge_sum = np.sum(edge, axis=1) # edge_sum[i] = iから出ている道の本数

dp = np.zeros(N + 1, dtype = np.float64) # dp[i]はiからNへの距離の期待値
dp[N - 1] = 1.0
# 道を塞がない場合
for i in range(N - 2, 0, - 1):
    dp[i] = (edge_sum[i] + (edge[i][i + 1:]*dp[i + 1:]).sum())/edge_sum[i]

E = dp[1]


for j in range(M):
    s, t = S[j], T[j]
    # jから道が1本しか出ていない時道を塞ぐことはできない
    if edge_sum[s] == 1:
        continue
    # 道s→tを塞ぐ時
    edge[s][t] = 0
    edge_sum[s] -= 1
    for i in range(N - 2, 0, - 1):
        dp[i] = (edge_sum[i] + (edge[i][i + 1:]*dp[i + 1:]).sum())/edge_sum[i] # ここの計算量ってN?
    E = min(E, dp[1])
    edge[s][t] = 1
    edge_sum[s] += 1
    
print(E)

### FIXED CODE ###

N, M = map(int, input().split())
edge_out = [[] for i in range(N)] #edge_out[i]はiから出ている道
edge_in = [[] for i in range(N + 1)] # edge_in[i]はiに行く道
for i in range(M):
    s, t = map(int, input().split())
    edge_out[s].append(t)
    edge_in[t].append(s)

edge_sum = [len(edge_out[i]) for i in range(N)] # edge_sum[i] = iから出ている道の本数

dp = [0.0]*(N + 1) # dp[i]はiからNへの距離の期待値
dp[N - 1] = 1.0
# 道を塞がない場合
for i in range(N - 2, 0, - 1):
    dp[i] = 1 + sum(dp[j] for j in edge_out[i])/edge_sum[i]
    
p_to_i = [0]*(N + 1) # p_to_i[i]は1から各iへ到達する確率
p_to_i[1] = 1
for i in range(2, N + 1):
    p_to_i[i] = sum(p_to_i[j]/edge_sum[j] for j in edge_in[i])


t = 0

for i in range(1, N - 1):
    if edge_sum[i] == 1:
        continue
        # iから出ている道の先にある部屋のうち、その部屋からNまでの距離の期待値が最も大きいものへ通ずる道を塞ぐ
    t = max(t, p_to_i[i]*(dp[i] - 1- ((dp[i] - 1)*edge_sum[i] - max(dp[j] for j in edge_out[i]))/(edge_sum[i] - 1)))
    
print(dp[1] - t)
### BUGGY CODE ###

n=int(input())
sl=list([input() for i in range(n)])
sum=0
for i in range(n):
    sl1 = list(sl[i])
    sl1.sort()
    s1 = ''.join(sl1)
    for j in range(i+1,n):
        sl2 = list(sl[j])
        sl2.sort()
        s2 = ''.join(sl2)
        if s1==s2:
            sum+=1
print(sum)

### FIXED CODE ###

n=int(input())
sl=list([input() for i in range(n)])
def sort_str(s):
    cl = list(s)
    cl.sort()
    return ''.join(cl)
m={}
sum=0
for i in range(n):
    s = sort_str(sl[i])
    if not s in m:
        m[s]=0
    else:
        m[s]+=1
        sum+=m[s]
print(sum)
### BUGGY CODE ###

import collections
n, k = map(int, input().split())
list = [int(i) for i in input().split()]
c_list = collections.Counter(list)
sorted_c_list = sorted(c_list.values())
for i in range(len(sorted_c_list)):
  if len(sorted_c_list[i:])==k:
    print(sum(sorted_c_list[:i]))
    break
else:
  print(0)

### FIXED CODE ###

import collections
n, k = map(int, input().split())
list = input().split()
c_list = collections.Counter(list)
sorted_c_list = sorted(c_list.values(),reverse=True)
print(sum(sorted_c_list[k:]))
### BUGGY CODE ###

def median(lista):
  lista = sorted(lista)
  return lista[int((len(lista)+ 1)/ 2)- 1]

N = int(input())
lista = list(map(int, input().split()))

for i in range(N):
  if(i == 0):
    newlista = lista[1:]
  elif(i == N- 1):
    newlista = lista[:N- 1]
  else:
  	newlista = lista[:i]+ lista[i+ 1:]
   
  print(median(newlista))

### FIXED CODE ###

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

lowermedian = newlista[int(len(lista)/ 2- 1)]
highermedian = newlista[int(len(lista)/2)]

for i in range(N):
  if(lista[i] <= lowermedian):
    print(highermedian)
  else:
    print(lowermedian)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

r, g, b, n = map(int, input().split())



cnt = 0
for i in range(int(n/r) + 1):
    for j in range(int((n-r*i)/g) + 1):

        if (n - (r*i + g*j))%b==0 and n - (r*i + g*j) >= 0:
            cnt += 1
print(cnt)

### FIXED CODE ###

import sys
input = sys.stdin.readline

r, g, b, n = map(int, input().split())



cnt = 0
for i in range(int(n/r) + 1):
    for j in range(int((n-r*i)/g) + 1):

        if (n - (r*i + g*j))%b==0 and n - (r*i + g*j) >= 0:
            cnt += 1
print(cnt)
### BUGGY CODE ###

#!/usr/bin/env python3

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

for i in range(N):
    A[i] -= 1

b = bin(K)
D = {0:list(range(N))} # ダブリングマトリクス
d = []
for i in range(N):
    d.append(A[D[0][i]])
D[1] = d


for i in range(1, len(b)-2):
    d = []
    for j in range(N):
        d.append(D[2**(i-1)][D[2**(i-1)][j]])
    D[2**i] = d


n = 2**(len(b[2:])-1)
S = D[n][0] # 初期状態
keta = len(b[2:]) - 2
for j in range(len(b[3:])):
    k = 2**keta
    if b[j+3] == '1':
        S = D[k][S]
    keta -= 1

print(S+1)


### FIXED CODE ###

#!/usr/bin/env python3

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

for i in range(N):
    A[i] -= 1

tele = [0]
#tele = [0,A[0]-1]
z = 0
s = 0
#B = {0:0,A[0]-1:1}
B = {0:0}
for i in range(N):
    if A[tele[-1]] in B and len(B) != 1:
        s = B[A[tele[-1]]]
        break
    B[A[tele[-1]]] = i+1
    tele.append(A[tele[-1]])
    z = tele[-1]

if K <= s:
    print(tele[K]+1)
else:
    K -= s
    amari = K%(len(tele[s:len(tele)]))
    tele = tele[s:len(tele)]*2
    print(tele[amari]+1)
### BUGGY CODE ###

def main():
  import sys
  input = sys.stdin.readline
  ans = []
  ans_append = ans.append
  s = input()
  t = input()
  a = len(s)
  b = len(t)
  dp = [[0]*(b+1) for _ in range(a+1)]
  prev_w = [[0]*(b+1) for _ in range(a+1)]
  for i in range(a):
    for j in range(b):
      if s[i]==t[j]:
        if dp[i][j]+1>dp[i+1][j+1]:
          dp[i+1][j+1] = dp[i][j]+1
          prev_w[i+1][j+1] = [i,j]
      else:
        if dp[i+1][j]>dp[i][j+1]:
          dp[i+1][j+1]=dp[i+1][j]
          prev_w[i+1][j+1] = (i+1,j)
        else:
          dp[i+1][j+1]=dp[i][j+1]
          prev_w[i+1][j+1] = (i,j+1)
  #print(dp[a][b])
  #print(prev_w[1][3])
  while a!=0 and b !=0:
    l = dp[a][b]
    a,b=prev_w[a][b]
    if l>dp[a][b]:
      ans_append(s[a])
  ans ="".join(ans)
  ans =ans[::-1]
  print(ans)
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
  import sys
  input = sys.stdin.readline
  ans = []
  ans_append = ans.append
  s = input()
  t = input()
  a = len(s)
  b = len(t)
  dp = [[0]*(b+1) for _ in range(a+1)]
  prev_w = [[None]*(b+1) for _ in range(a+1)]
  for i in range(a):
    for j in range(b):
      if s[i]==t[j]:
        if dp[i][j]+1>dp[i+1][j+1]:
          dp[i+1][j+1] = dp[i][j]+1
          prev_w[i+1][j+1] = (i,j)
      else:
        if dp[i+1][j]>dp[i][j+1]:
          dp[i+1][j+1]=dp[i+1][j]
          prev_w[i+1][j+1] = (i+1,j)
        else:
          dp[i+1][j+1]=dp[i][j+1]
          prev_w[i+1][j+1] = (i,j+1)
  while a!=0 and b !=0:
    l = dp[a][b]
    a,b=prev_w[a][b]
    if l>dp[a][b]:
      ans_append(s[a])
  ans ="".join(ans)
  ans =ans[::-1]
  print(ans)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

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

inverse = 1
for i in range(q):
    query = list(map(str, input().split()))
    if query[0] == '1':
        inverse *= -1
    if query[0] == '2':
        if query[1] == '1' and inverse == 1:
            s = query[2] + s
        elif query[1] == '2' and inverse == 1:
            s = s + query[2]
        elif query[1] == '1' and inverse == -1:
            s = s + query[2]
        elif query[1] == '2' and inverse == -1:
            s = query[2] + s
if inverse == 1:
    print(s)
else:
    for i in range(len(s)):
        print(s[-i-1], end='')
    print()


### FIXED CODE ###

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

inverse = 1
left = ''
right = ''
for i in range(q):
    query = list(map(str, input().split()))
    if query[0] == '1':
        inverse *= -1
    if query[0] == '2':
        if query[1] == '1' and inverse == 1:
            left += query[2]
        elif query[1] == '2' and inverse == 1:
            right += query[2]
        elif query[1] == '1' and inverse == -1:
            right += query[2]
        elif query[1] == '2' and inverse == -1:
            left += query[2]
s = left[::-1]+s+right
if inverse == 1:
    print(s)
else:
    print(s[::-1])
### BUGGY CODE ###

island, ship = map(int, input().split())
startTo, fromGoal = [], []
for i in range(ship):
  a, b = map(int, input().split())
  if a == 1:
    startTo.append(b)
  elif b == 1:
    startTo.append(a)
  elif a == island:
    fromGoal.append(b)
  elif b == island:
    fromGoal.append(a)
check = False
if len(startTo) < len(fromGoal):
  for i in range(len(startTo)):
    check = startTo[i] in fromGoal
    if check:
      break
else:
  for i in range(len(fromGoal)):
    check = fromGoal[i] in startTo
    if check:
      break
if check:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

### FIXED CODE ###

island, ship = map(int, input().split())
startTo, fromGoal = [False] * island, [False] * island
for i in range(ship):
  a, b = map(int, input().split())
  if a == 1:
    startTo[b - 1] = True
  elif b == 1:
    startTo[a - 1] = True
  elif a == island:
    fromGoal[b - 1] = True
  elif b == island:
    fromGoal[a - 1] = True
check = False
for i in range(island):
  if startTo[i] and fromGoal[i]:
    check = True
    break
if check:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")
### BUGGY CODE ###

import sys
input = sys.stdin.readline
import numpy as np

from math import factorial
import itertools

def permutations_count(n, r):
    ''' 順列 '''
    return factorial(n) // factorial(n - r)

def combinations_count(n, r):
    ''' 組み合わせ '''
    return factorial(n) // (factorial(n - r) * factorial(r))

n = int(input())
*s, = map(int, list(input().split()[0]))

ans = 0
for i in range(1000):
    num_str = str(i)
    if i < 100:
        num_str = '0'+num_str
    if i<10:
        num_str = '0'+num_str
    idx = 0
    for j in s:
        # print(j, idx)
        if j == int(num_str[idx]):
            idx += 1
            if idx==3:
                break
    if idx == 3:
        ans += 1
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

n = int(input())
s = input().split()[0]

ans = 0
for i in range(1000):
    num_str = str(i).zfill(3)
    a = s.find(num_str[0])
    if a==-1:
        continue
    b = s[a+1:].find(num_str[1])
    if b==-1:
        continue
    b += a+1
    c = s[b+1:].find(num_str[2])
    if c!=-1:
        ans += 1
print(ans)