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

from collections import defaultdict
import sys

def dfs(visited, graph, grapht, graph2, num, x):
  visited[x] = 1

  for nx in graph[x]:
    if not visited[nx]:
      dfs(visited, graph, grapht, graph2, num, nx)

  t = set()
  if num[x]==1 and len(grapht[x])%2==0:
    for e in grapht[x]:
      graph2[x].add(e)
      t.add(e)
  elif num[x]==-1 and len(grapht[x]) and len(grapht[x])%2==0:
    for e in grapht[x]:
      graph2[x].add(e)
      t.add(e)
    tt = grapht[x].pop()
    graph2[tt].add(x)
    graph2[x].remove(tt)
    num[tt] *= -1
  elif num[x]==1 and len(grapht[x])%2==1:
    for e in grapht[x]:
      graph2[x].add(e)
      t.add(e)
    tt = grapht[x].pop()
    graph2[tt].add(x)
    graph2[x].remove(tt)
    num[tt] *= -1
  else:
    for e in grapht[x]:
      graph2[x].add(e)
      t.add(e)
  for e in t:
    grapht[x].discard(e)
    grapht[e].discard(x)

if __name__ == "__main__":
  sys.setrecursionlimit(1000000)
  input = sys.stdin.readline
  n, m = map(int, input().split())

  if m%2==1:
    print(-1)
    exit()

  graph = defaultdict(set)
  grapht = defaultdict(set)
  for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].add(b)
    graph[b].add(a)
    grapht[a].add(b)
    grapht[b].add(a)

  graph2 = defaultdict(set)
  visited = [0]*n
  num = [1]*n

  dfs(visited, graph, grapht, graph2, num, 0)

  for i in range(n):
    if len(graph2[i])%2==1:
      print(-1)
      exit()

  for i in range(n):
    for e in graph2[i]:
      print(i+1, e+1)

### FIXED CODE ###

from collections import defaultdict
import sys

def dfs(visited, graph, grapht, graph2, num, x):
  visited[x] = 1

  for nx in graph[x]:
    if not visited[nx]:
      dfs(visited, graph, grapht, graph2, num, nx)

  t = set()
  if num[x]==1 and len(grapht[x])%2==0:
    for e in grapht[x]:
      graph2[x].add(e)
      t.add(e)
  elif num[x]==-1 and len(grapht[x]) and len(grapht[x])%2==0:
    for e in grapht[x]:
      graph2[x].add(e)
      t.add(e)
    tt = grapht[x].pop()
    graph2[tt].add(x)
    graph2[x].remove(tt)
    num[tt] *= -1
  elif num[x]==1 and len(grapht[x])%2==1:
    for e in grapht[x]:
      graph2[x].add(e)
      t.add(e)
    tt = grapht[x].pop()
    graph2[tt].add(x)
    graph2[x].remove(tt)
    num[tt] *= -1
  else:
    for e in grapht[x]:
      graph2[x].add(e)
      t.add(e)
  for e in t:
    if e in grapht[x]:
      grapht[x].remove(e)
    if x in grapht[e]:
      grapht[e].remove(x)

if __name__ == "__main__":
  sys.setrecursionlimit(1000000)
  input = sys.stdin.readline
  n, m = map(int, input().split())

  if m%2==1:
    print(-1)
    exit()

  graph = defaultdict(set)
  grapht = defaultdict(set)
  for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].add(b)
    graph[b].add(a)
    grapht[a].add(b)
    grapht[b].add(a)

  graph2 = defaultdict(set)
  visited = [0]*n
  num = [1]*n

  dfs(visited, graph, grapht, graph2, num, 0)

  for i in range(n):
    if len(graph2[i])%2==1:
      print(-1)
      exit()

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

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

H,W=map(int,input().split())
A=[[None]*(W+2)]+\
  [[i=="." for i in "#"+input()+"#"] for _ in range(H)] + \
  [[None]*(W+2)]

q=[[(i,j) for i in range(1,H+1) for j in range(1,W+1) if not A[i][j]]]

for k in range(2000):
    q.append([])
    for i,j in q[k]:
        if A[i-1][j]:
            A[i-1][j]=None
            q[k+1].append((i-1,j))
        if A[i+1][j]:
            A[i+1][j]=None
            q[k+1].append([i+1,j])
        if A[i][j-1]:
            A[i][j-1]=None
            q[k+1].append([i,j-1])
        if A[i][j+1]:
            A[i][j+1]=None
            q[k+1].append([i,j+1])
    if q[k+1]==[]:
        break
print(k)

### FIXED CODE ###

H,W = list(map(int,input().split()))
A = [list(str(input())) for i in range(H)]
 
black = []
 
cnt = 0
 
for i in range(H):
    for j in range(W):
        if A[i][j] == "#":
            black.append([i,j])
 
length = len(black)
            
while (length < H*W):
    gray = []
    for l in black:
        if l[1] != 0:
            c1 = (l[0],l[1]-1)
            if A[c1[0]][c1[1]] == ".":
                gray.append(c1)
                A[c1[0]][c1[1]] = "#"
        if l[1] != W-1:
            c2 = (l[0],l[1]+1)
            if  A[c2[0]][c2[1]] == ".":
                gray.append(c2)
                A[c2[0]][c2[1]] = "#"
        if l[0] != 0:
            c3 = (l[0]-1,l[1])
            if  A[c3[0]][c3[1]] == ".":
                gray.append(c3)
                A[c3[0]][c3[1]] = "#"
        if l[0] != H-1:
            c4 = (l[0]+1,l[1])
            if  A[c4[0]][c4[1]] == ".":
                gray.append(c4)
                A[c4[0]][c4[1]] = "#"
    
    gray = list(set(gray))
    black = [l for l in gray]
    
    cnt += 1
    length += len(black)
    
print(cnt)
### BUGGY CODE ###

h,w,d=map(int,input().split())

board=[0 for _ in range(h*w)]

for i in range(h):
    for j,a in enumerate(input().split()):
        board[i*w+j]=int(a)

q=int(input())


distances=[-1 for _ in range(h*w)]

for _ in range(q):
    l,r=map(int,input().split())


    res=0
    while(l!=r):
        if distances[l]==-1:
            tmp=board.index(l)
            i=tmp//w
            j=tmp%w
            tmp=board.index(l+d)
            x=tmp//w
            y=tmp%w
            distances[l]=abs(i-x)+abs(j-y)
        res+=distances[l]
        l+=d
    print(res)

### FIXED CODE ###

h,w,d=map(int,input().split())

pos=[(0,0) for _ in range(h*w)]

for i in range(h):
    for j,a in enumerate(input().split()):
        pos[int(a)-1]=(i,j)

q=int(input())


distances=[0 for _ in range(h*w)]

for i in range(d,h*w):
    a=h*w-i
    i,j=pos[a-1]
    x,y=pos[a+d-1]
    distances[a-1]=distances[a+d-1]+abs(i-x)+abs(j-y)

for _ in range(q):
    l,r=map(int,input().split())
    print(distances[l-1]-distances[r-1])
### BUGGY CODE ###

N = int(input())
cnt = 0
L = list(map(int,input().split()))
while True:
    try: 
        if L[0] <L[1]>L[2] or L[0] > L[1] <L[2]:
            a0=L.pop(0)
            a1=L.pop(0)
            cnt += 1

        else:
            L.pop(0)
    except:
        break
print(1+cnt)


### FIXED CODE ###

N = int(input())
cnt = 0
tmp = ''
M = list(map(int,input().split()))
L = []
for x in M:
    if x == tmp:
        pass
    else:
        L.append(x)
    tmp = x
    

    
while True:
    try: 
        if L[0] <L[1]>L[2] or L[0] > L[1] <L[2]:
            a0=L.pop(0)
            a1=L.pop(0)
            cnt += 1
        else:
            L.pop(0)
    except:
        break
#    print(L)
print(1+cnt)
### BUGGY CODE ###

N = int(input())
S = list(str(input()))

passwords = []
for i in range(len(S)):
    for j in range(i + 1, len(S)):
        for k in range(j + 1, len(S)):
            password = S[i] + S[j] + S[k]
            passwords.append(password)


# print(len(passwords))
# print(passwords)
# print(set(passwords))
print(len(list(set(passwords))))


### FIXED CODE ###

N = int(input())
S = list(str(input()))

passwords = []
for i in range(0, 10):
    for j in range(0, 10):
        for k in range(0, 10):
            password = str(i) + str(j) + str(k)
            passwords.append(password)

char_hash = {}
for i, char in enumerate(S):
    if char in char_hash.keys():
        char_hash[char].append(i)
    else:
        char_hash[char] = [i]

# print(char_hash

count = 0
for password in passwords:
    exist_keys = char_hash.keys()
    # print(password[0] in char_hash.keys())
    if not(password[0] in exist_keys):
        continue
    if not(password[1] in exist_keys):
        continue
    if not(password[2] in exist_keys):
        continue
    first_index = min(char_hash[password[0]])
    second_indexes = char_hash[password[1]]
    second_index = -1
    for index in second_indexes:
        if index <= first_index:
            continue
        else:
            second_index = index
            break
    third_indexes = char_hash[password[2]]
    third_index = -1
    for index in third_indexes:
        if index <= second_index:
            continue
        else:
            third_index = index
            break
    # print(first_index, second_index, third_index)
    if first_index < second_index and second_index < third_index:
        count += 1

print(count)
# print(len(passwords))
# print(passwords)
# print(set(passwords))
# print(len(list(set(passwords))))
### BUGGY CODE ###

import math
K=int(input())
S=0
for a in range(1,K+1):
    for b in range(1,K+1):
        for c in range(1,K+1):
            x=math.gcd(a,b)
            S+=math.gcd(x,c)
print(S)


### FIXED CODE ###

import math
import itertools
K=int(input())
l=list(itertools.combinations_with_replacement(range(1,K+1),3))
S=0
for i in l:
    a=i[0]
    b=i[1]
    c=i[2]
    x=math.gcd(a,b)
    if a==b==c:
        S+=math.gcd(x,c)
    elif a==b or b==c or c==a:
        S+=math.gcd(x,c)*3
    else:
        S+=math.gcd(x,c)*6   
print(S)
### BUGGY CODE ###

from sys import stdin, setrecursionlimit


def main():
    n, m, k = map(int, stdin.readline().split())
    g = [[[False, False] for _ in range(n)] for _ in range(n)]

    for _ in range(m):
        a, b = map(int, stdin.readline().split())
        g[a - 1][b - 1][0] = True
        g[b - 1][a - 1][0] = True

    for _ in range(k):
        c, d = map(int, stdin.readline().split())
        g[c - 1][d - 1][1] = True
        g[d - 1][c - 1][1] = True

    def dfs(v, seen):
        seen[v] = True

        for nv in range(n):
            if g[v][nv][0]:
                if seen[nv]:
                    continue
                dfs(nv, seen)

    ans = [0] * n
    for i in range(n):
        seen = [False] * n
        dfs(i, seen)
        for j in range(n):
            if g[i][j][0] == False and g[i][j][1] == False and i != j and seen[j]:
                ans[i] += 1

    print(*ans)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

### FIXED CODE ###

from sys import stdin, setrecursionlimit


class UnionFindTree:
    def __init__(self, n):
        self.parent = [-1] * n

    def find(self, x):
        p = self.parent
        while p[x] >= 0:
            x, p[x] = p[x], p[p[x]]
        return x

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        p = self.parent
        if x != y:
            x, y = sorted([x, y])
            p[x], p[y] = p[x] + p[y], x

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def size(self, x):
        return -self.parent[self.find(x)]


def main():
    n, m, k = map(int, stdin.readline().split())

    f = UnionFindTree(n)

    f_or_b = [0] * n

    for _ in range(m):
        a, b = map(int, stdin.readline().split())
        f.union(a - 1, b - 1)
        f_or_b[a - 1] += 1
        f_or_b[b - 1] += 1

    for _ in range(k):
        c, d = map(int, stdin.readline().split())
        if f.same(c - 1, d - 1):
            f_or_b[c - 1] += 1
            f_or_b[d - 1] += 1

    print(*[f.size(i) - f_or_b[i] - 1 for i in range(n)])


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

A,B,N = map(int,input().split())
max_val =0
for x in range(N+1):
    val = (A*x)//B - A*(x//B)
    if max_val < val:
        max_val = val
print(max_val)

### FIXED CODE ###

A,B,N = map(int,input().split())
val = (A*min(N,B-1))//B - A*(min(N,B-1)//B)
print(val)
### BUGGY CODE ###

import sys

N = int(sys.stdin.readline().strip())
X = sys.stdin.readline().strip()

def popcount(n):
    cnt = 0
    while n > 0:
        cnt += n & 1
        n //= 2
    return cnt

def f(n):
    cnt = 0
    while n != 0:
        n = n % popcount(n)
        cnt += 1
    return cnt

nX = int(X, 2)
pcnt = X.count('1')
MOD1 = pcnt + 1
MOD2 = pcnt - 1

nXp = nX % MOD1
if MOD2 != 0:
    nXm = nX % MOD2

delta = 2**(N-1)
pow1 = [1] * N
pow2 = [0] * N
for i in range(1, N):
    pow1[i] = (pow1[i-1] * 2) % MOD1
if MOD2 != 0:
    pow2[0] = 1
    for i in range(1, N):
        pow2[i] = (pow2[i-1] * 2) % MOD2

for i in range(0, N):
    if X[i] == '0':
        k = (nXp + pow1[N-1-i]) % MOD1
        print(f(k) + 1)
    else:
        if MOD2 == 0:
            print(0)
        else:
            k = (nXm - pow2[N-1-i]) % MOD2
            print(f(k) + 1)
    delta //= 2

### FIXED CODE ###

import sys

N = int(sys.stdin.readline().strip())
X = sys.stdin.readline().strip()

def popcount(n):
    cnt = 0
    while n > 0:
        cnt += n & 1
        n //= 2
    return cnt

def f(n):
    cnt = 0
    while n != 0:
        n = n % popcount(n)
        cnt += 1
    return cnt

#nX = int(X, 2)
pcnt = X.count('1')
MOD1 = pcnt + 1
MOD2 = pcnt - 1

nXp = 0
nXm = 0

pow1 = [1] * N
pow2 = [0] * N
for i in range(1, N):
    pow1[i] = (pow1[i-1] * 2) % MOD1
if MOD2 != 0:
    pow2[0] = 1
    for i in range(1, N):
        pow2[i] = (pow2[i-1] * 2) % MOD2

for i in range(N):
    if X[i] == '1':
        nXp += pow1[N-1-i]
nXp %= MOD1

if MOD2 != 0:
    for i in range(N):
        if X[i] == '1':
            nXm += pow2[N-1-i]

    nXm %= MOD2
    

for i in range(0, N):
    if X[i] == '0':
        k = (nXp + pow1[N-1-i]) % MOD1
        print(f(k) + 1)
    else:
        if MOD2 == 0:
            print(0)
        else:
            k = (nXm - pow2[N-1-i]) % MOD2
            print(f(k) + 1)
### BUGGY CODE ###

import sys
input=sys.stdin.readline


def main():
    N, S = map(int, input().split())
    *A, = map(int, input().split())
    dp = [[0]*(3001) for _ in range(N+1)]
    MOD = 998244353
    
    m = pow(2, MOD-2, MOD)
    dp[0][0] = pow(2, N, MOD)

    for i in range(1, N+1):    
        for j in range(3001):
            dp[i][j] += dp[i-1][j]
            if j-A[i-1]>=0:
                dp[i][j] += dp[i-1][j-A[i-1]]*m
            dp[i][j] %= MOD

    print(dp[N][S])


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
input=sys.stdin.readline


def main():
    N, S = map(int, input().split())
    *A, = map(int, input().split())
    dp = [[0]*(3001) for _ in range(N+1)]
    MOD = 998244353
    m = pow(2, MOD-2, MOD)
    dp[0][0] = pow(2, N, MOD)
    for i in range(1, N+1):    
        for j in range(3001):
            dp[i][j] += dp[i-1][j]
            if j-A[i-1]>=0:
                dp[i][j] += dp[i-1][j-A[i-1]]*m
            dp[i][j] %= MOD

    print(dp[N][S])


main()
### BUGGY CODE ###

import itertools


n = int(input())
s = input()

i = [i for i in range(n)]

summ = 0
for i, j, k in itertools.combinations(i, 3):
    if all([s[i] != s[j], s[i] != s[k], s[j] != s[k], j - i != k - j]):
        summ += 1

print(summ)

### FIXED CODE ###

n = int(input())
s = input()

rgb = [[], [], []]

for i, c in enumerate(s):
    rgb[(c > 'G') + (c > 'B')].append(i)

exclude = 0
for i in rgb[0]:
    for j in rgb[1]:
        ii = min(i, j)
        jj = max(i, j)
        d = jj - ii
        if ii - d >= 0 and ii - d in rgb[2]:
            exclude += 1
        if jj + d < n and jj + d in rgb[2]:
            exclude += 1
        if not d % 2 and ii + d // 2 in rgb[2]:
            exclude += 1

summ = len(rgb[0]) * len(rgb[1]) * len(rgb[2])
print(summ - exclude)
### BUGGY CODE ###

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

L.sort()

ans=0
for i in range(N-1):
    for j in range(i+1,N):
        temp=L[i]+L[j]
        for k in range(N):
            f=True
            if k!=i and k!=j:
                if temp<=L[k]:
                    f=False
                elif L[j]+L[k]<=L[i]:
                    f=False
                elif L[k]+L[i]<=L[j]:
                    f=False
                if f:
                    ans+=1


print(ans//3)



### 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,-1,-1):
        temp=L[i]-L[j]
        idx=bisect.bisect_right(L,temp)
        ans+=max(0,j-idx)
print(ans)
### BUGGY CODE ###

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


BIG = pow(10,9)+7

dp = [BIG]*(N+1)

dp[0] = 0

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


### FIXED CODE ###

n, k = map(int, input().split())
h = [int(i) for i in input().split()]

def chmin(a, b):
    if a > b:
        return b
    else:
        return a
f_inf = pow(10,9)+99

dp = [f_inf] * (10**5+10)
dp[0] = 0
for i in range(1, n):
    for j in range(1, k+1):
        if i - j >= 0:
            dp[i] = chmin(dp[i], dp[i-j]+ abs(h[i] - h[i - j]))
print(dp[n-1])
### BUGGY CODE ###

n = int(input())
l = []
for i in range(n):
    s = input()
    if s not in l:
        l.append(s)
print(len(l))

### FIXED CODE ###

n = int(input())
l = set()
for i in range(n):
    s = input()
    if s not in l:
        l.add(s)
print(len(l))
### BUGGY CODE ###

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


def change(list,before,after):
    for j in range(n):
        if list[j] == before:
            list[j] = after
    print(sum(list))
    return list


for i in range(q):
    b,c = list(map(int,input().split()))
    a = change(a,b,c)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
q = int(input())
count = 0
s = sum(a)

L = [0] * (10**5+1)
for aa in a:
    L[aa] += 1
for _ in range(q):
    b, c = list(map(int, input().split()))
    L[c] += L[b]
    s += L[b] * (c-b)
    L[b] = 0
    print(s)
### BUGGY CODE ###

n, k, q = map(int, input().split())
A = [int(input()) for _ in range(q)]

score = [k]*n
for i in A:
    score = list(map(lambda x: x-1, score))
    score[i-1] = score[i-1]+1

for s in score:
    if s > 0:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

n, k, q = map(int, input().split())
A = [int(input()) for _ in range(q)]

score = [k-q]*n
for i in A:
    score[i-1] = score[i-1]+1

for s in score:
    if s > 0:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###


h, w = list(map(int, input().split()))

s = []
for i in range(h):
    line = input()
    s.append(line)

ans = []
for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            continue

        for k in range(i, h):
            for l in range(w):
                if s[k][l] == '#' or i == k and j == l:
                    continue
                start = (i, j)
                goal = (k, l)
                d = [[1<<10 for x in range(w)] for y in range(h)]

                stack = []
                stack.append((start[0], start[1]))
                d[start[0]][start[1]] = 0
                while stack:
                    y, x = stack.pop()
                    if y == goal[0] and x == goal[1]:
                        continue
                    if y > 0 and s[y-1][x] == '.' and d[y-1][x] > d[y][x]+1:
                        d[y-1][x] = d[y][x] + 1
                        stack.append((y-1, x))
                    if x < w-1 and s[y][x+1] == '.' and d[y][x+1] > d[y][x]+1:
                        d[y][x+1] = d[y][x] + 1
                        stack.append((y, x+1))
                    if y < h-1 and s[y+1][x] == '.' and d[y+1][x] > d[y][x]+1:
                        d[y+1][x] = d[y][x] + 1
                        stack.append((y+1, x))
                    if x > 0 and s[y][x-1] == '.' and d[y][x-1] > d[y][x]+1:
                        d[y][x-1] = d[y][x] + 1
                        stack.append((y, x-1))
                ans.append(d[goal[0]][goal[1]])
ans.sort()
print(ans[-1])


### FIXED CODE ###

import collections
h, w = list(map(int, input().split()))

s = []
for i in range(h):
    line = input()
    s.append(line)

ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            continue
        d = [[False for x in range(w)] for y in range(h)]

        stack = collections.deque()
        stack.append((i, j, 0))
        d[i][j] = True
        while stack:
            y, x, score = stack.popleft()
            if y > 0 and s[y-1][x] == '.' and not d[y-1][x]:
                stack.append((y-1, x, score+1))
                d[y-1][x] = True
            if x < w-1 and s[y][x+1] == '.' and not d[y][x+1]:
                stack.append((y, x+1, score+1))
                d[y][x+1] = True
            if y < h-1 and s[y+1][x] == '.' and not d[y+1][x]:
                stack.append((y+1, x, score+1))
                d[y+1][x] = True
            if x > 0 and s[y][x-1] == '.' and not d[y][x-1]:
                stack.append((y, x-1, score+1))
                d[y][x-1] = True
            if score > ans:
                ans = score
print(ans)
### BUGGY CODE ###

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

ans = ''
for i in range(N):
    ans += str(A.index(i + 1) + 1) + ' '

print(ans.strip())


### FIXED CODE ###

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

arr = [0] * N
for i in range(N):
    arr[A[i] - 1] = i + 1

print(*arr)
### BUGGY CODE ###

x,y = map(int,input().split())

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

res = [float('inf')]*x
res[0] = 0

for i in range(x):
    for j in range(i-y, i):
        if j < 0:
            continue
        res[i] = min(res[i], res[j]+abs(t[i]-t[j]))

print(res[-1])

### FIXED CODE ###

x,y = map(int,input().split())
 
t = list(map(int,input().split()))
 
res = [100000000000000000000]*x
res[0] = 0
 
for i in range(x):
    for j in range(i-y, i):
        if j < 0:
            continue
        res[i] = min(res[i], res[j]+abs(t[i]-t[j]))
 
print(res[-1])
### BUGGY CODE ###

import scipy as sp

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

nD = S.count("D")
nC = S.count("C")
if nD < nC:
    S = S[::-1].replace("D","c").replace("C","d").upper()

S = "A" + S
D = sp.cumsum([s=="D" for s in S])
cntM = sp.cumsum([s=="M" for s in S])
sumM = sp.cumsum([d if s=="M" else 0 for s,d in zip(S,D)])
ans = sp.zeros(Q,int)

for i,s in enumerate(S[1:]):
    if s=="C":
        for j,k in enumerate(K):
            ik = max(0,i-k+1)
            d = D[ik]
            ans[j] += (sumM[i]-sumM[ik]) - d*(cntM[i]-cntM[ik])
for out in ans:
    print(out)

### FIXED CODE ###

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

nD = S.count("D")
nC = S.count("C")
if nD < nC:
    S = S[::-1].replace("D","c").replace("C","d").upper()

D = [0]*(N+1)
cntM = [0]*(N+1)
sumM = [0]*(N+1)
ans = [0]*Q
for i,s in enumerate(S):
    D[i+1] = D[i]
    cntM[i+1] = cntM[i]
    sumM[i+1] = sumM[i]
    if s=="D":
        D[i+1] += 1
    elif s=="M":
        cntM[i+1] += 1
        sumM[i+1] += D[i]
    elif s=="C":
        for j,k in enumerate(K):
            ik = max(0,i-k+1)
            d = D[ik]
            ans[j] += (sumM[i]-sumM[ik]) - d*(cntM[i]-cntM[ik])
for out in ans:
    print(out)