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

n, m = map(int, input().split())
node = [[] for _ in range(n + 1)]
for i in range(m):
    a, b = map(int, input().split())
    node[a].append(b)
    node[b].append(a)

q = int(input())
node_color = [0 for _ in range(n + 1)]
for j in range(q):
    v, d, c = map(int, input().split())

    now = [v]
    paint = {v}
    for dist in range(d):
        buff = []
        for k in now:
            paint |= set(node[k])
            buff.extend(node[k])
        now.extend(buff)

    for l in paint:
        node_color[l] = c

for m in range(n):
    print(node_color[m + 1])


### FIXED CODE ###

n, m = map(int, input().split())
node = [[] for _ in range(n + 1)]
for i in range(m):
    a, b = map(int, input().split())
    node[a].append(b)
    node[b].append(a)

q = int(input())
node_color = [0 for _ in range(n + 1)]
vdc = [list(map(int, input().split())) for _ in range(q)]

vdc = vdc[::-1]
painted = set()
visited = [[0] * 11 for _ in range(n + 1)]


def dfs(now, dist, color):
    if dist < 0:
        return
    if visited[now][dist]:
        return

    visited[now][dist] += 1
    if not node_color[now]:
        node_color[now] = color

    for x in node[now]:
        dfs(x, dist - 1, color)


for i in vdc:
    v, d, c = i
    dfs(v, d, c)

for m in range(n):
    print(node_color[m + 1])
### BUGGY CODE ###

import sys
Input = sys.stdin.readline

H, W, D = map(int, Input().split())
A = [list(map(int, Input().split())) for _ in range(H)]
Q = int(Input())
LR = [list(map(int, Input().split())) for _ in range(Q)]
num_pos = {}

for y, line in enumerate(A):
    for x, num in enumerate(line):
        num_pos[num] = (x, y)

cost_table = {i: {} for i in num_pos.keys()}
for num1 in range(1, H*W+1):
    for num2 in range(num1, H*W+1, D):
        if num1 == num2:
            cost_table[num1][num2] = 0
        else:
            i, j = num_pos[num2-D]
            x, y = num_pos[num2]
            cost_table[num1][num2] = abs(i - x) + abs(j - y) + cost_table[num1][num2-D]

for l, r in LR:
    print(cost_table[l][r])

### FIXED CODE ###

import sys
Input = sys.stdin.readline

H, W, D = map(int, Input().split())
A = [list(map(int, Input().split())) for _ in range(H)]
Q = int(Input())
LR = [list(map(int, Input().split())) for _ in range(Q)]
num_pos = {}

for y, line in enumerate(A):
    for x, num in enumerate(line):
        num_pos[num] = (x, y)

cost_table = {}
for num in range(1, H*W+1):
    if num <= D:
        cost_table[num] = 0
    else:
        i, j = num_pos[num-D]
        x, y = num_pos[num]
        cost_table[num] = abs(i - x) + abs(j - y) + cost_table[num-D]

for l, r in LR:
    print(cost_table[r] - cost_table[l])
### BUGGY CODE ###

import sys
import numpy as np
from scipy.sparse import coo_matrix
from scipy.sparse.csgraph import dijkstra


def main():
    n = int(input())
    U = [0]
    V = [0]
    W = [0]
    for i in range(n-1):
        u, v, w = [int(x) for x in input().split()]
        U.append(u)
        V.append(v)
        W.append(w)
    graph = coo_matrix((W, (U, V)), shape=(n+1, n+1)).tocsr()
    q, k = [int(x) for x in input().split()]
    dist = dijkstra(csgraph=graph, directed=False, indices=k, unweighted=False)
    for j in range(q):
        l, r = [int(x) for x in input().split()]
        print(int(dist[l]+dist[r]))


main()


### FIXED CODE ###

import sys
import collections

n = int(input())
adj = [[] for i in range(n + 1)]
for i in range(n - 1):
    a, b, c = [int(x) for x in input().split()]
    adj[a].append((b, c))
    adj[b].append((a, c))
q, k = [int(x) for x in input().split()]
dist = [0] * (n + 1)
queue = collections.deque()
queue.append(k)
while len(queue) > 0:
    u = queue.popleft()
    for v, weight in adj[u]:
        if dist[v] == 0:
            queue.append(v)
            dist[v] = dist[u] + weight
for j in range(q):
    l, r = [int(x) for x in input().split()]
    print(dist[l] + dist[r])
# print(*data, sep='\n')
### BUGGY CODE ###

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

cnt = 0
for idx in range(n):
    is_ok = True
    for j in range(idx):
        if p[idx] > p[j]:
            is_ok = False
            break
    if is_ok:
        cnt += 1

print(cnt)



### FIXED CODE ###

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

ok = n + 1
cnt = 0
for i in p:
    if i <= ok:
        cnt += 1
        ok = i
print(cnt)
### BUGGY CODE ###

N,K = map(int,input().split())
h = list(map(int,input().split()))
h.insert(0,0)

dp = [10**10] * (N+1)
dp[0],dp[1] = 0,0

for i in range(2,N+1):
    for j in range(min(K,i)):
        dp[i] = min(dp[i] , dp[i-j-1] + abs(h[i] - h[i-j-1]))
print(dp[N])


### FIXED CODE ###

N,K = map(int,input().split())
h = list(map(int,input().split()))
h.insert(0,0)

dp = [10**10] * (N+1)
dp[0],dp[1] = 0,0

for i in range(2,N+1):
    for j in range(min(K,i)):
        if i - j - 1 == 0:
            break
        dp[i] = min(dp[i] , dp[i-j-1] + abs(h[i] - h[i-j-1]))
print(dp[N])
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
MOD=10**9+7
c=0
for i in range(len(A)):
  c+=A[i]*(sum(A)-A[i]%MOD)
print(c//2%MOD)



### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
c=0
d=sum(A)
for i in range(0,N-1):
    d-=A[i]
    c+=A[i]*d
    if(c>10**9+7):
        c%=(10**9+7)
print(c)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n, m, s, t = map(int,input().split())
C = [list(map(int,input().split())) for i in range(m)]

s -= 1
t -= 1

# O((V + E)log(V))
# Cは [[スタート頂点, ゴール頂点, 重み], ...] のリスト

for i in range(m):
    for j in range(2):
        C[i][j] -= 1

M = [[] for i in range(n)]
for i in range(len(C)):
    M[C[i][0]].append([C[i][1], C[i][2]])  # 無向グラフなら両方追加
    M[C[i][1]].append([C[i][0], C[i][2]])  # 無向グラフなら両方追加

N = [[] for i in range(n)]
for i in range(len(C)):
    N[C[i][0]].append([C[i][1], C[i][3]])  # 無向グラフなら両方追加
    N[C[i][1]].append([C[i][0], C[i][3]])  # 無向グラフなら両方追加

import heapq

def dijkstra(s, M):
    D = [10**16] * n  # 頂点0からの距離
    P = [-1] * n  # 頂点0からの最短距離において、そこの直前の頂点(経路復元に利用)
    D[s] = 0
    V = [0] * n  # その頂点のD[i]が最短距離と確定したら1
    Q = []  # 優先度付きキュー
    for v in range(n):
        heapq.heappush(Q, [D[v], v])

    le = len(Q)
    while le > 0:
        q = heapq.heappop(Q)
        u = q[1]
        du = q[0]
        if V[u] == 0:
            V[u] = 1
            le -= 1
            for i in range(len(M[u])):
                v = M[u][i][0]
                luv = M[u][i][1]
                if V[v] == 0:
                    alt = du + luv
                    if D[v] > alt:
                        D[v] = alt
                        P[v] = u
                        heapq.heappush(Q, [alt, v])
    return D, P

Ds, _ = dijkstra(s, M)
Dt, _ = dijkstra(t, N)

ANS = [0] * n

# print(Ds,Dt)

ans = 10**16
for i in range(n-1, -1, -1):
    ans = min(ans, Ds[i] + Dt[i])
    ANS[i] = ans

for i in range(n):
    print(10**15 - ANS[i])

### FIXED CODE ###

import sys
input = sys.stdin.readline
n, m, s, t = map(int,input().split())
C = [list(map(int,input().split())) for i in range(m)]

s -= 1
t -= 1

# O((V + E)log(V))
# Cは [[スタート頂点, ゴール頂点, 重み], ...] のリスト

M = [[] for i in range(n)]
for i in range(len(C)):
    M[C[i][0]-1].append([C[i][1]-1, C[i][2]])  # 無向グラフなら両方追加
    M[C[i][1]-1].append([C[i][0]-1, C[i][2]])  # 無向グラフなら両方追加

N = [[] for i in range(n)]
for i in range(len(C)):
    N[C[i][0]-1].append([C[i][1]-1, C[i][3]])  # 無向グラフなら両方追加
    N[C[i][1]-1].append([C[i][0]-1, C[i][3]])  # 無向グラフなら両方追加

import heapq

def dijkstra(s, M):
    D = [10**16] * n  # 頂点0からの距離
    P = [-1] * n  # 頂点0からの最短距離において、そこの直前の頂点(経路復元に利用)
    D[s] = 0
    V = [0] * n  # その頂点のD[i]が最短距離と確定したら1
    Q = []  # 優先度付きキュー
    for v in range(n):
        heapq.heappush(Q, [D[v], v])

    le = len(Q)
    while le > 0:
        q = heapq.heappop(Q)
        u = q[1]
        du = q[0]
        if V[u] == 0:
            V[u] = 1
            le -= 1
            for i in range(len(M[u])):
                v = M[u][i][0]
                luv = M[u][i][1]
                if V[v] == 0:
                    alt = du + luv
                    if D[v] > alt:
                        D[v] = alt
                        P[v] = u
                        heapq.heappush(Q, [alt, v])
    return D, P

Ds, _ = dijkstra(s, M)
Dt, _ = dijkstra(t, N)

ANS = [0] * n

# print(Ds,Dt)

ans = 10**16
for i in range(n-1, -1, -1):
    ans = min(ans, Ds[i] + Dt[i])
    ANS[i] = ans

for i in range(n):
    print(10**15 - ANS[i])
### BUGGY CODE ###

from itertools import permutations
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
ans = -1

def chk(a):
    for i in range(N-1):
        if a[i] > a[i+1]:
            return False
    return True

def cnt(idx):
    res = 0
    for i in range(N):
        res += abs(idx[i] - i)
    return res // 2

for idx in permutations(range(N)):
    # print(idx)
    a = []
    for i in range(N):
        if (idx[i] % 2) ^ (i%2):
            a.append(B[idx[i]])
        else:
            a.append(A[idx[i]])
    # print(a)
    if chk(a):
        if ans == -1:
            ans = cnt(idx)
        else:
            ans = min(ans, cnt(idx))

print(ans)


### FIXED CODE ###

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

v = [[0, 0] for _ in range(N)]
s = []
ans = 500

for i in range(1<<N):
    tmp = 0
    for j in range(N):
        if ((i>>j)&1): v[j] = [B[j], j]
        else:          v[j] = [A[j], j]
    for j in range(N):
        p = j
        while (p and v[p][0] < v[p-1][0]):
            v[p], v[p-1] = v[p-1], v[p]
            tmp += 1
            p -= 1
    for j in range(N):
        if (((i>>v[j][1])+v[j][1]-j)&1):
            s.append(v[j][0]*500+j)
    if (len(s)&1):
        tmp = 500
        s.pop()
    while s:
        p = s.pop()
        q = s.pop()
        if ((p-q)&1): tmp += p-q
        else:         tmp += 500
    ans = min(ans, tmp)

if ans < 500:
    print(ans)
else:
    print(-1)
### BUGGY CODE ###

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

for i in range(n):
    if i == 0:
        x = r[i]
    else:
        x = x * r[i]
    
if x > 10**18:
    x = -1

print(int(x))

### FIXED CODE ###

import math
n = int(input())
r = list(map(int,input().split()))

lim = math.pow(10,18)

for i in range(n):
    if i == 0:
        x = r[i]
    else:
        x = x * r[i]

    if x > 1000000000000000000:
        break

if x > 1000000000000000000:
    x = -1

if 0 in r:
    x = 0

print(math.floor(x))
### BUGGY CODE ###

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

for i in range(n):
    print(len([j for j in a if j == i + 1]))

### FIXED CODE ###

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

lis = [0] * n
for i in a:
    lis[i-1] += 1
for i in lis:
    print(i)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import fractions


def tri_gcd(p, q, r):
    tmp_gcd = fractions.gcd(p, q)
    return fractions.gcd(tmp_gcd, r)


k = int(input())
res = 0
for a in range(1, k+1):
    for b in range(a, k+1):
        for c in range(b, k+1):
            tk = tri_gcd(a, b, c)
            if (a == b) & (b == c):
                res += tk
            elif (a!=b) & (b!=c) & (c!=a):
                res += tk*6
            else:
                res += tk*3

print(res)

### FIXED CODE ###

# -*- coding: utf-8 -*-
import fractions
gcd_map = [[0 for i in range(401)] for i in range(401)]


def mem_gcd(p, q):
    if gcd_map[p][q] == 0:
        gcd_map[p][q] = fractions.gcd(p, q)
    return gcd_map[p][q]


k = int(input())
res = 0
for a in range(1, k+1):
    for b in range(a, k+1):
        tmp_gcd = mem_gcd(a, b)
        for c in range(b, k+1):
            tk = mem_gcd(tmp_gcd, c)
            if a == b:
                if b == c:
                    res += tk
                else:
                    res += tk * 3
            else:
                if b == c:
                    res += tk*3
                else:
                    res += tk*6

print(res)
### BUGGY CODE ###

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

x = []
y = []

for i, elem in enumerate(a):
    x.append(i+a[i])
    y.append(i-a[i])

ans = 0

for i in x:
    ans += y.count(i)

print(ans)


### FIXED CODE ###

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

x = []
y = {}

for i, elem in enumerate(a):
    x.append(i+a[i])
    y[i-a[i]] = y.get(i-a[i], 0) + 1

ans = 0

for i in x:
    ans += y.get(i, 0)

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

h, w = map(int, input().split())
S = [["#"] * (w + 2)]
for i in range(h):
  S.append(["#"] + list(input()) + ["#"])
S.append(["#"] * (w + 2))

def serch(S, x, y):
  ans = []
  cand = [[x-1, y], [x+1, y], [x, y-1], [x, y+1]]
  for pos in cand:
    a, b = pos
    if S[a][b] == ".":
      ans.append(pos)
  return ans

def length(S, i, j):
  S[i][j] = 0
  temp = serch(S, i, j)
  counter = 0
  while len(temp) != 0:
    next_temp = []
    counter += 1
    for pos in temp:
      x, y = pos
      S[x][y] = counter
      next_temp += serch(S, x, y)
    else:
      temp = next_temp
  return counter

import copy
max_l = 0
for i in range(1, h + 1):
  for j in range(1, w + 1):
    if S[i][j] == ".":
      T = copy.deepcopy(S)
      max_l = max(length(T, i, j), max_l)
print(max_l)

### FIXED CODE ###

h, w = map(int, input().split())
S = [["#"] * (w + 2)]
for i in range(h):
  S.append(["#"] + list(input()) + ["#"])
S.append(["#"] * (w + 2))

def serch(S, x, y, next_temp):
  ans = []
  cand = [[x-1, y], [x+1, y], [x, y-1], [x, y+1]]
  for pos in cand:
    a, b = pos
    if S[a][b] == "." and pos not in next_temp:
      ans.append(pos)
  return ans

def length(S, i, j):
  S[i][j] = 0
  temp = serch(S, i, j, [])
  counter = 0
  while len(temp) != 0:
    next_temp = []
    counter += 1
    for pos in temp:
      x, y = pos
      S[x][y] = counter
      next_temp += serch(S, x, y, next_temp)
    else:
      temp = next_temp
  return counter

import copy
max_l = 0
for i in range(1, h + 1):
  for j in range(1, w + 1):
    if S[i][j] == ".":
      T = copy.deepcopy(S)
      max_l = max(length(T, i, j), max_l)
print(max_l)
### BUGGY CODE ###

from bisect import bisect_left as bl, bisect_right as br, insort
import sys
import heapq
# from math import *
from collections import defaultdict as dd, deque
def data(): return sys.stdin.readline().strip()
def mdata(): return map(float, data().split())
out = sys.stdout.write
# sys.setrecursionlimit(100000)
INF = int(1e9)
mod = int(1e9) + 7

n = int(data())
P = list(mdata())
dp = [0.0] * (n // 2 + 2)
dp[1] = float(1)
for i in range(n):
    for j in range(len(dp) - 1, 0, -1):
        dp[j] = dp[j - 1] * (1 - P[i]) + dp[j] * (P[i])
print(sum(dp))

### FIXED CODE ###

from bisect import bisect_left as bl, bisect_right as br, insort
import sys
import heapq
#from math import *
from collections import defaultdict as dd, deque
def data(): return sys.stdin.buffer.readline().strip().decode()
def mdata(): return map(float, data().split())
out=sys.stdout.write
#sys.setrecursionlimit(100000)
INF=int(1e9)
mod=int(1e9)+7


n=int(data())
P=list(mdata())
dp=[0]*(n//2+2)
dp[1]=1
for i in range(n):
    dp1=dp[:]
    for j in range(1,len(dp)):
        k=dp[j-1]*(1-P[i])+dp[j]*(P[i])
        dp1[j]=k
    dp=dp1[:]
print(sum(dp))
### BUGGY CODE ###

# import numpy as np
n=int(input())
# a=np.array(list(map(int,input().split())))
a=list(map(int,input().split()))

ans=0
mod=10**9+7
for i in range(60):
    x=0
    for j in range(n):
        if (a[j] >>i&1) :x+=1

    now = x*(n-x) % mod

    for j in range(i):
        now = now*2 % mod
    ans += now
    ans %= mod

print(ans)

### FIXED CODE ###

# import numpy as np
n=int(input())
# a=np.array(list(map(int,input().split())))
a=list(map(int,input().split()))

ans=0
mod=10**9+7
for i in range(60):
    x=0
    for j in range(n):
        if (a[j] >>i&1) :x+=1

    now = x*(n-x) % mod

    for j in range(i):
        now = now*2 % mod
    ans += now
    ans %= mod

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

def solve(ns, k):
    n = len(ns)
    tot = 1
    for i in xrange(k):
        tot *= ns[i]
    res = []
    pre = tot
    for i in xrange(k, n):
        tot /= ns[i - k]
        tot *= ns[i]
        if tot > pre:
            res.append(True)
        else:
            res.append(False)
        pre = tot
    return res

assert solve([96, 98, 95, 100, 20], 3) == [True, False]
assert solve([1001, 869120, 1001], 2) == [False]
assert solve([3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9], 7) == [True, True, False, True, True, False, True, True]


n, k = map(int, raw_input().split())
ns = map(int, raw_input().split())

res = solve(ns, k)
for item in res:
    print 'Yes' if item else 'No'




### FIXED CODE ###

def solve(ns, k):
    n = len(ns)
    tot = 1
    for i in xrange(k):
        tot += ns[i]
    res = []
    pre = tot
    for i in xrange(k, n):
        a = ns[i - k]
        b = ns[i]
        if a > b:
            # tot = tot / a * b
            tot = tot - 1
        elif a < b:
            tot = tot + 1
        else:
            pass
        if tot > pre:
            res.append(True)
        else:
            res.append(False)
        pre = tot
    return res

assert solve([1001, 869120, 1001], 2) == [False]
assert solve([96, 98, 95, 100, 20], 3) == [True, False]
assert solve([3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9], 7) == [True, True, False, True, True, False, True, True]


n, k = map(int, raw_input().split())
ns = map(int, raw_input().split())

res = solve(ns, k)
for item in res:
    print 'Yes' if item else 'No'
### BUGGY CODE ###

import math
k=int(input())
a=0
for i in range(1,k+1):
  for j in range(1,k+1):
    for h in range(1,k+1):
      a+=math.gcd(math.gcd(i,j),h)
    
print(a)

### FIXED CODE ###

import math
k=int(input())
a=0
for i in range(1,k+1):
  for j in range(1,k+1):
    for h in range(1,k+1):
      a+=math.gcd(math.gcd(i,j),h)
    
print(a)
### BUGGY CODE ###

n,m = map(int,input().split(" "))
a=[-100] * m
ans = 1
for i in range(m):
    a[i] = int(input())
    if a[i]-1 == a[i-1]:
        ans = 0

if ans == 1:
    for j in range(n,-1,-1):
        if j in a:
            ans *= 1
        elif j+1 in a or j+2 in a:
            ans *= 1
        elif j+2 > n:
            ans *= 1
        elif not(j+3 in a) and not(j+3 > n):
            temp = ans
            ans += t
            t = temp
        else:
            t = ans
            ans *= 2

print(ans % 1000000007)


### FIXED CODE ###

n,m = map(int,input().split(" "))
a=[0] * (n+1)
mod = 10 ** 9 + 7
for i in range(m):
    a[int(input())] = 1

dp = [0] * (n+1)
for j in range(n+1):
    if a[j] == 1:
        dp[j] = 0
    elif j == 1 or j == 0:
        dp[j] = 1
    else:
        dp[j] = (dp[j-1] + dp[j-2]) % mod

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

# https://atcoder.jp/contests/abc143/tasks/abc143_d

N = int(input())
L_list = list(map(int, input().split()))
L_list = sorted(L_list)
count = 0

for a in range(N-2):
    for b in range(a + 1, N-1):
        c_min = max(L_list[a] - L_list[b], L_list[b] - L_list[a], L_list[b])
        
        c_max = L_list[a] + L_list[b]
        count_c = len([i for i in L_list if ((c_min < i) and (i < c_max))])
        count += count_c

print(count)

### FIXED CODE ###

# https://atcoder.jp/contests/abc143/tasks/abc143_d

import bisect

N = int(input())
L_list = list(map(int, input().split()))
L_list = sorted(L_list)
count = 0

for a in range(N-2):
    for b in range(a + 1, N-1):
        c_min = L_list[b + 1]
        c_max = L_list[a] + L_list[b]
        c_max_idx = bisect.bisect_left(L_list, c_max)
        c_count = c_max_idx - (b + 1)
        count += c_count

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

import itertools
n=int(input())
l=list(map(int,input().split()))
ans=0
for i in list(itertools.combinations(l,3)):
    if i[0]+i[1]>i[2] and i[1]+i[2]>i[0] and i[2]+i[0]>i[1]:
        #print(i)
        ans+=1
print(ans)        
    


### FIXED CODE ###

import bisect

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

l.sort()
ans=0
for i in range(n-1,1,-1):
    for j in range(i-1,0,-1):
        c=bisect.bisect_right(l,l[i]-l[j])
        #print(l[i],l[j],i,j,c)
        if j-c > 0:
            ans+=(j-c)
            
print(ans)
### BUGGY CODE ###

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


### FIXED CODE ###

from collections import deque

s = deque(input())
q = int(input())
flag = True
for _ in range(q):
    query = input().split()
    if query[0] == "1":
        flag = not flag
    else:
        if (query[1] == "1" and flag) or (query[1] == "2" and not flag):
            s.appendleft(query[2])
        else:
            s.append(query[2])
if not flag:
    s.reverse()
print(''.join(s))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

n=ii()
s=list(ss())
ans=[]
for i in range(n-2):
    for j in range(i+1,n-1):
        for k in range(j+1,n):
            ans.append(s[i]+s[j]+s[k])
            

print(len(list(set(ans))))

### FIXED CODE ###

n=int(input())
S = input()
 
ans = 0
for i in range(1000):
    a, b, c = map(str, list(str(i).zfill(3)))
    mode = 'a'
    for j in S:
        if mode == 'a' and j == a:
            mode = 'b'
        elif mode == 'b' and j == b:
            mode = 'c'
        elif mode == 'c' and j == c:
            ans += 1
            break
print(ans)