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

inputs=lambda:map(int,raw_input().split())
n, m = inputs()
es = [inputs()[::-1] for i in xrange(m)]
es.sort()
parent = range(n+1)
def root(x):
    if x == parent[x]:
        return x
    parent[x] = root(parent[x])
    return parent[x]
def unite(x, y):
    px = root(x)
    py = root(y)
    if px < py:
        parent[py] = px
    else:
        parent[px] = py
su = 0
g = [[] for i in xrange(n+1)]
for c, a, b in es:
    if root(a) != root(b):
        unite(a, b)
        su += c
        g[a].append((b, c))
        g[b].append((a, c))

import sys
sys.setrecursionlimit(100000)
dic = {}
def dfs(s, v, prev, cost):
    dic[s,v] = cost
    for e, c in g[v]:
        if prev != e:
            dfs(s, e, v, max(cost, c))
for i in xrange(n):
    dfs(i+1, i+1, -1, 0)
for i in xrange(input()):
    s, t = inputs()
    print su-dic[s,t]


### FIXED CODE ###

from collections import deque
import sys
sys.setrecursionlimit(10**5)

N, M = map(int, input().split())
E = []
for i in range(M):
    a, b, c = map(int, input().split())
    E.append((c, a-1, b-1))
E.sort()

*p, = range(N)
def root(x):
    if x == p[x]:
        return x
    p[x] = y = root(p[x])
    return y

L = 2*N-1
G = [[]] * L
C = [0]*L
*lb, = range(N)
cur = N

s = 0
for c, a, b in E:
    pa = root(a); pb = root(b)
    if pa == pb:
        continue
    s += c
    chds = [lb[pa], lb[pb]]
    if pa < pb:
        p[pb] = pa
        lb[pa] = cur
    else:
        p[pa] = pb
        lb[pb] = cur
    C[cur] = c
    G[cur] = chds
    cur += 1

H = [0]*L
prv = [-1]*L
def dfs(v):
    s = 1; heavy = -1; m = 0
    for w in G[v]:
        prv[w] = v
        c = dfs(w)
        if m < c:
            heavy = w
            m = c
        s += c
    H[v] = heavy
    return s
dfs(L-1)

SS = []
D = []
LB = [0]*L
I = [0]*L
que = deque([(L-1, 0)])
while que:
    v, d = que.popleft()
    S = []
    k = len(SS)
    while v != -1:
        I[v] = len(S)
        S.append(v)
        LB[v] = k
        h = H[v]
        for w in G[v]:
            if h == w:
                continue
            que.append((w, d+1))
        v = h
    SS.append(S)
    D.append(d)


def query(u, v):
    lu = LB[u]; lv = LB[v]
    dd = D[lv] - D[lu]
    if dd < 0:
        lu, lv = lv, lu
        v, u = u, v
        dd = -dd

    for _ in range(dd):
        v = prv[SS[lv][0]]
        lv = LB[v]

    while lu != lv:
        u = prv[SS[lu][0]]
        lu = LB[u]

        v = prv[SS[lv][0]]
        lv = LB[v]

    return u if I[u] < I[v] else v


def gen():
    Q = int(input())
    for i in range(Q):
        u, v = map(int, input().split())
        w = query(u-1, v-1)
        yield "%d\n" % (s - C[w])
ans = list(gen())
sys.stdout.writelines(ans)
### BUGGY CODE ###

import numpy as np
N, Q = list(map(int, input().split()))
S = input()
l = [0]*Q
r = [0]*Q
for i in range(Q):
    l[i], r[i] = list(map(int, input().split()))

s = list(S)
ac = []

for i in range(N-1):
    if s[i] == 'A':
        if s[i+1] == 'C':
            s[i] = "AC"
            ac.append(i)



for i in range(Q):
    cnt = 0
    for k in ac:
        if k< r[i]-1 and k >= l[i]-1:
            cnt += 1
    print(cnt)



### FIXED CODE ###

import sys  
from itertools import accumulate
input = sys.stdin.readline  

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

l = [None]*Q
r = [None]*Q
for i in range(Q):
    l[i], r[i] = list(map(int, input().split()))

s = list(S)
ac = [0] * N

for i in range(N-1):
    if s[i] == 'A':
        if s[i+1] == 'C':
            s[i] = "AC"
            ac[i] += 1

ans = list(accumulate(ac))
ans = [0] + ans


for i in range(Q):
    print(ans[r[i]-1]- ans[l[i]-1])
### BUGGY CODE ###

N = int(input())
numList = list(map(int, input().split()))
product = 1
for i in numList:
    product *= i
if product > 10**18:
    print(-1)
else:
    print(product)

### FIXED CODE ###

N = int(input())
numList = list(map(int, input().split()))
product = 1
toPrint = True
isZero = False
for j in numList:
    if j == 0:
        isZero = True
if not isZero:
    for i in numList:
        product = product * i
        if product > 10**18:
            toPrint = False
            break
if isZero:
    print(0)
else:
    if toPrint:
        print(product)
    else:
        print(-1)
### BUGGY CODE ###

n = int(input())
lst = [int(input()) for _ in range(n)]
blst = []
i = 1
n = 0
while i not in blst:
    blst.append(i)
    i = lst[i - 1]
    n += 1
    if i == 2:
        print(n)
        quit()
print(-1)

### FIXED CODE ###

n = int(input())
lst = [int(input()) for _ in range(n)]
i = 1
c = 0
for _ in range(n):
    i = lst[i - 1]
    c += 1
    if i == 2:
        print(c)
        quit()
print(-1)
### BUGGY CODE ###

num = int(input())
num2 = list(input().split())
for i in range(num):
  print(num2.count(str(i + 1)))

### FIXED CODE ###

num = int(input())
li = list(int(x) for x in input().split())
li2 = [0] * num
num = len(li)
for i in li:
  li2[i - 1] = li2[i - 1] + 1
for j in range(num + 1):
  print(li2[j])
### BUGGY CODE ###

n = int(input())
a = list(int(x) for x in input().split())
x = 0

for i in range(n):
    if (a.pop() in a) is True:
        print("NO")
        x = 1
        break

if x == 0:
    print("YES")


### FIXED CODE ###

n = int(input())
a = list(int(x) for x in input().split())
x = 0
 
a.sort()
for i in range(n-1):
    if a[-1] - a[-2] == 0:
        print("NO")
        x = 1
        break
    a.pop()
 
if x == 0:
    print("YES")
### BUGGY CODE ###

n = int(input())
s = input()
change_direction = []
for i in range(len(s)):
    count = 0
    for j in range(len(s)):
        if j < i and s[j] == 'W':
            count += 1
            continue
        if i < j and s[j] == 'E':
            count += 1
            continue
    change_direction.append(count)
print(min(change_direction))


### FIXED CODE ###

n = int(input())
s = input()
count = s.count('E')
m = count
for i in s:
    if i == 'E':
        m -= 1
    else:
        m += 1
    count = min(count, m)
print(count)
### BUGGY CODE ###

#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
  def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

  K = int(input())
  ans = 0
  for a in range(1,K+1):
    for b in range(1,K+1):
      g = gcd(a,b)
      for c in range(1,K+1):
        ans += gcd(g,c)
  print(ans)
  return
  
  
#Solve
if __name__ == "__main__":
    solve()


### FIXED CODE ###

#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]
 
sys.setrecursionlimit(1000000)
mod = 1000000007
 
def solve():
    def gcd(a,b):
        if a == 0:
            return b
        return gcd(b%a, a)
    k = I()
    ans = 0
    for a in range(1,k+1):
        for b in range(1,k+1):
            g = gcd(a,b)
            for c in range(1,k+1):
                ans += gcd(g,c)
    print(ans)
    return
 
#Solve
if __name__ == "__main__":
    solve()
### BUGGY CODE ###

import collections
N = int(input())
A = [int(_) for _ in input().split()]


class Prime:
    @staticmethod
    def trial_division(x):
        if x % 2 == 0:
            return True
        for p in range(3, int(x**0.5 + 1), 2):
            if x % p == 0:
                return False
        return True

    @staticmethod
    def factorization(x):
        ret = {}
        i = 0
        while True:
            if x % 2:
                break
            x //= 2
            i += 1
        if i:
            ret[2] = i
        for p in range(3, int(x**0.5 + 1), 2):
            i = 0
            while True:
                if x % p:
                    if i:
                        ret[p] = i
                    break
                x //= p
                i += 1
        if x > 1:
            ret[x] = 1
        return ret

    @staticmethod
    def miller_rabin(n):
        def suspect(a, t, n):
            x = pow(a, t, n)
            n1 = n - 1
            while t != n1 and x != 1 and x != n1:
                x = pow(x, 2, n)
                t <<= 1
            return t & 1 or x == n1

        if n == 2:
            return True
        if n < 2 or n % 2 == 0:
            return False
        d = (n - 1) >> 1
        while d & 1 == 0:
            d >>= 1

        if n < 2**32:
            check_list = (2, 7, 61)
        elif n < 2**48:
            check_list = (2, 3, 5, 7, 11, 13, 17, 19, 23)
        else:
            check_list = (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37)

        for i in check_list:
            if i >= n:
                break
            if not suspect(i, d, n):
                return False
        return True


c = collections.defaultdict(int)
for a in A:
    for p in Prime.factorization(a):
        c[p] += 1
ans = 'pairwise coprime'
if c:
    x = max(c.values())
    if x == 1:
        ans = 'pairwise coprime'
    elif x == N:
        ans = 'not coprime'
    else:
        ans = 'setwise coprime'
print(ans)


### FIXED CODE ###

import collections
N = int(input())
A = [int(_) for _ in input().split()]


def prime_factorize(n):
    a = set()
    while n % 2 == 0:
        a.add(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.add(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.add(n)
    return a


d = collections.defaultdict(int)
for a in A:
    for x in prime_factorize(a):
        d[x] += 1
if len(d):
    e = max(d.values())
if len(d) == 0 or e == 1:
    ans = 'pairwise coprime'
elif e == N:
    ans = 'not coprime'
else:
    ans = 'setwise coprime'
print(ans)
### BUGGY CODE ###

from sys import stdin

n = int(stdin.readline().rstrip())
li = list(map(int,stdin.readline().rstrip().split()))
li.sort()

from itertools import combinations

lin = list(combinations(li, 3))

point = 0
ima = lin[0][0]
for i in range(len(lin)):
    if lin[i][0] == ima:
        if lin[i][2] < lin[i][0] + lin[i][1]:
            point += 1
        else:
            continue
    else:
        ima = lin[i][0]
        if lin[i][2] < lin[i][1] + lin[i][0]:
            point += 1

print(point)

### FIXED CODE ###

from sys import stdin
import bisect

n = int(stdin.readline().rstrip())
li = list(map(int,stdin.readline().rstrip().split()))

li.sort()

point = 0

for i in range(n-2):
    for j in range(i+1,n-1):
        bi = bisect.bisect_left(li,li[i]+li[j])
        point += bi-j-1
print(point)
### BUGGY CODE ###

def resolve():
    s = input()
    q = int(input())
    qall = []
    for _ in range(q):
        inp = input()
        if inp == "1":
            s = s[::-1]
        else:
            z = inp.split()
            b = int(z[1])
            c = z[2]
            if b == 1:
                s = c + s
            else:
                s = s + c
    print(s)
resolve()

### FIXED CODE ###

def resolve():
    from collections import deque
    s = deque(input())
    q = int(input())
    qlist = [input().split() for i in range(q)]
    flip = False
    for j in range(q):
        if qlist[j][0] == "1":
            flip = not flip
        elif qlist[j][1] == "1":
            if flip:
                s.append(qlist[j][2])
            else:
                s.appendleft(qlist[j][2])
        elif qlist[j][1] == "2":
            if flip:
                s.appendleft(qlist[j][2])
            else:
                s.append(qlist[j][2])
    if not flip:
        print("".join(s))
    else:
        s.reverse()
        print("".join(s))
resolve()
### BUGGY CODE ###

import sys
from itertools import permutations, combinations
from collections import defaultdict, Counter
from math import factorial
import fractions
div = 10**9 + 7

sys.setrecursionlimit(10**7)
N = int(input())
A = list(map(int, input().split()))

val = 1
def lcm(a, b):
    ret = fractions.gcd(a, b)
    ret = a*b//ret
    return ret

val = A[0]
for a in A[1:]:
    val = lcm(val, a)

sumB = 0
for a in A:
    sumB += val//a
    sumB %= div

print(sumB)

### FIXED CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]
from fractions import gcd
div = 10**9 + 7

def main():
    N = int(input())
    A = list(map(int, input().split()))
    sA = list(set(A))

    val = 1
    def lcm(a, b):
        ret = gcd(a, b)
        ret = a*b//ret
        return ret

    val = sA[0]
    for a in sA[1:]:
        val = lcm(val, a)

    B = [val//a for a in A]
    sumB = sum(B)
    sumB %= div

    print(sumB)

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

def div2(n):
  i=n
  a=0
  while True:
    if i%2!=0:
      return a
    i%=2
    a+=1

n=int(input())
a=list(map(int,input().split()))
ans=0
for i in a:
  ans+=div2(i)
print(ans)

### FIXED CODE ###

def div2(n):
  i=n
  a=0
  while True:
    if i%2!=0:
      return a
    i//=2
    a+=1

n=int(input())
a=list(map(int,input().split()))
ans=0
for i in a:
  ans+=div2(i)
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

from copy import copy


def solve():
    N = int(input())
    A = []
    count = 0
    for _ in range(N):
        A.append(int(input()))
    while A:
        a = A.pop()
        count += 1
        B = []
        while A:
            b = A.pop()
            if b >= a:
                B.append(b)
                continue
            a = b
        A = B[::-1]
    return count
  

def main():
    print(solve())


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import bisect as bi


def solve():
    N = int(input())
    A = []
    heads = []
    for _ in range(N):
        A.append(int(input()))
    a = A.pop()
    bi.insort(heads, a)
    while A:
        a = A.pop()
        if a < heads[-1]:
            j = bi.bisect(heads, a)
            del heads[j]
        bi.insort(heads, a)
    return len(heads)
  

def main():
    print(solve())


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

n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]

d = dict()
key_all = []
for i in range(n):
    a = ab[i][0]
    b = ab[i][1]

    if a not in key_all:
        d[a] = [b]
        key_all.append(a)
    else:
        d[a].append(b)

key_all.sort()

ans = 0
l = []
import bisect

for i in range(1, m+1):
    if key_all != []:
        if i == key_all[0]:
            for v in d[i]:
                bisect.insort(l, v)

            key_all.pop(0)

    # print(l)

    if l != []:
        ans += l.pop()

print(ans)


### FIXED CODE ###

n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]

import heapq
import collections

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

key_all = list(set(a_all))
key_all.sort()

d = dict()
for k in key_all:
    d[k] = []

for i in range(n):
    a = ab[i][0]
    b = ab[i][1]
    d[a].append(b)

ans = 0
l = []
for i in range(1, m+1):
    if key_all != []:
        if i == key_all[0]:
            for v in d[i]:
                heapq.heappush(l, -1 * v)

            heapq.heappop(key_all)

    if l != []:
        ans += heapq.heappop(l) * -1

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

import queue
height,width=map(int,input().split())

graph=[]
for _ in range(height):
    graph.append(input())

diff=[[0,-1],[0,1],[-1,0],[1,0]]
max_step=[]
for h in range(height):
    for w in range(width):
        if graph[h][w]=='#':
            continue

        route = [[-1]*width for _ in range(height)]

        # start x,y,経路数
        q = queue.Queue()
        q.put([w,h,0])

        while not q.empty():
            nx,ny,nn = q.get()
            route[ny][nx] = nn

            for dx,dy in diff:
                x = nx+dx
                y = ny+dy
                if   width<=x \
                  or height<=y \
                  or x < 0 \
                  or y < 0 \
                  or graph[y][x]=='#' \
                  or route[y][x]>-1:
                    continue
                q.put([x, y, nn+1])
        
        max_step.append(max(max(step) for step in route))
        
print(max(max_step))


### FIXED CODE ###

import queue
height,width=map(int,input().split())

graph=[input() for _ in range(height)]

dxs = [0, 0, 1, -1]
dys = [1, -1, 0, 0]
max_step=[]
for h in range(height):
    for w in range(width):
        if graph[h][w]=='#':
            continue

        route = [[-1]*width for _ in range(height)]
        route[h][w] = 0

        # start x,y,経路数
        q = queue.Queue()
        q.put([w,h,0])

        while not q.empty():
            nx,ny,nn = q.get()

            for dx,dy in zip(dxs, dys):
                x = nx+dx
                y = ny+dy
                if   width<=x \
                  or height<=y \
                  or x < 0 \
                  or y < 0 \
                  or graph[y][x]=='#' \
                  or route[y][x]!=-1:
                    continue
                route[y][x] = nn + 1
                q.put([x, y, nn+1])
        
        max_step.append(max(max(step) for step in route))
        
print(max(max_step))
### BUGGY CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

n = INT()
l = 0
r = n - 1
print(l)
ltmp = STR()
if ltmp == 'Vacant':
    exit()
for i in range(2, 20):
    c = (l + r) // 2
    print(c)
    tmp = STR()
    if tmp == 'Vacant':
        exit()
    if c % 2 == l % 2:
        if tmp == ltmp:
            l = c
        else:
            r = c
    else:
        if tmp == ltmp:
            r = c
        else:
            l = c

### FIXED CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

n = INT()
l = 0
r = n - 1
print(l, flush=True)
ltmp = STR()
if ltmp == 'Vacant':
    exit()
print(r, flush=True)
rtmp = STR()
if rtmp == 'Vacant':
    exit()
for i in range(2, 20):
    c = (l + r) // 2
    print(c, flush=True)
    tmp = STR()
    if tmp == 'Vacant':
        exit()
    if c % 2 == l % 2:
        if tmp == ltmp:
            l = c
            ltmp = tmp
        else:
            r = c
    else:
        if tmp == ltmp:
            r = c
        else:
            l = c
            ltmp = tmp
### BUGGY CODE ###

import numpy as np

N = int(input())
xy = []
x  = []
y  = []

for i in range(N):
  xy.append(list(map(int, input().split())))
  x.append(xy[i][0])
  y.append(xy[i][1])

x = np.array(x)
y = np.array(y)

ans = 0

for i in range(N-1):
  x_temp = np.abs((x[i] - x[i+1:]))
  y_temp = np.abs((y[i] - y[i+1:]))
  xy_temp = x_temp + y_temp
  temp = np.max(xy_temp)
  if temp > ans:
    ans = temp
  
print(ans)

### FIXED CODE ###

N = int(input())
z =[]
w = []
for i in range(N):
  x,y = map(int, input().split())
  z.append(x+y)
  w.append(x-y)
print(max(max(z)-min(z),max(w)-min(w)))
### BUGGY CODE ###

numbers = []
while True:
    n = input()
    if n == '0':
        break
    numbers.append(n)
leng = len(numbers) + 1
for i in range(1,leng):
    for n in numbers:
        print('Case ' + str(i) + ': ' + n)

### FIXED CODE ###

num = []
while True:
    n = int(input())
    if n == 0:
        break
    else:
        num.append(n)


for i, n in enumerate(num):
    i = i+1
    print('Case '+ str(i) + ': ' + str(n))
### BUGGY CODE ###

k, s = list(map(int, input().split()))
ct = 0
for x in range(k+1):
    for y in range(min(k+1, s-x+1)):
        if x + y > s:
            break;
        for z in range(min(k+1,s-x-y+1)):
            if x + y + z == s:
                ct += 1
                break;
print(ct)

### FIXED CODE ###

k, s = list(map(int, input().split()))
ct = 0
for x in range(k+1):
    for y in range(k+1):
        z = s - x - y
        if 0 <= z <= k:
            ct += 1
print(ct)
### BUGGY CODE ###

N = int(input())
H = list(map(int, input().split()))
c = 0
ans = 0
for i in range(1,N):
    buff = i
    while True:
        if buff < N:
            if H[buff]<=H[buff-1]:
                c += 1
            else:
                break
        else:
            break
        buff += 1

    ans = max(c, ans)
    c = 0

print(ans)

### FIXED CODE ###

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

buff = [0 for i in range(N)]
c = 0
for i in range(1,N):
    if H[i] <= H[i-1]:
        buff[i] = 1

# print(buff)

ans = 0
c = 0
a = 0
for i in range(N):
    if buff[i]:
        c+= 1
        a += 1
        # print(a, c)
    else:
        ans = max(c, ans)
        c = 0

    ans = max(c, ans)
print(ans)
### BUGGY CODE ###

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

for i in range(1,N + 1):
	pi = p[i - 1]
	if all(pi <= j for j in p[:i]):
		count += 1

print(count)

### FIXED CODE ###

N = int(input())
p = list(map(int, input().split()))
count = 0
min = p[0]

for i in range(N):
	if p[i] <= min:
		count += 1
		min = p[i]

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

N = int(input())

rate=1

for i in range(1,N+1):
    rate*=i


print(rate%(10**9+7))
  

### FIXED CODE ###

from math import factorial

N = int(input())

print(factorial(N)%(10**9+7))
### BUGGY CODE ###

N=int(input())
import sys
input=sys.stdin.readline
S=input()
D_stack=[]
D,C=[-1]*(N+1),[-1]*(N+1)
m=0
for i in range(N):
  if S[i]=="D":
    D_stack.append((i,m))
    D[i]=m
  if S[i]=="C":
    C[i]=m
  if S[i]=="M":
    m+=1
Q=int(input())
K=[int(i) for i in input().split()]
for q in range(Q):
  ans=0
  k=K[q]
  r,c,s,pre_m=0,1,0,0
  for p,m in D_stack:
    if r<=p:
      r=p+1
      c,s=1,0
    else:
      s-=(c-1)*(m-pre_m)
      c-=1
    pre_m=m
    while r-p<k and r<=N:
      if C[r]>=0:
        ans+=c*(C[r]-m)-s
      if D[r]>=0:
        c+=1
        s+=D[r]-m
      r+=1
  print(ans)


### FIXED CODE ###

N=int(input())
import sys
input=sys.stdin.readline
S=input()
C_stack=[]
D=[0]*(N+1)
M=[0]*(N+1)
DM=[0]*(N+1)
m=0
for i in range(1,N+1):
  if S[i-1]=="D":
    D[i]=D[i-1]+1
  else:
    D[i]=D[i-1]
  if S[i-1]=="C":
    C_stack.append(i)
  if S[i-1]=="M":
    DM[i]=DM[i-1]+D[i-1]
    M[i]=M[i-1]+1
  else:
    DM[i]=DM[i-1]
    M[i]=M[i-1]

Q=int(input())
K=[int(i) for i in input().split()]
for q in range(Q):
  ans=0
  k=K[q]
  for c in C_stack:
    ans+=DM[c]-DM[max(0,c-k)]-D[max(0,c-k)]*(M[c]-M[max(0,c-k)])
  print(ans)