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

n = int(input())
sl = list(input())

q = int(input())
kl = list(map(int,input().split()))

for k in kl:
    # i文字目までのdとmとdmの数

    dp = [[0, 0, 0] for i in range(n+1)]
    ans = 0
    for i, s in enumerate(sl):
        if i - k >= 0:
            if sl[i-k] == "D":
                dp[i][0] -= 1
                dp[i][2] -= dp[i][1]
            if sl[i-k] == "M":
                dp[i][1] -= 1
        if s == "D":
            dp[i+1][0] = dp[i][0] + 1
        else:
            dp[i+1][0] = dp[i][0]
        if s == "M":
            dp[i+1][1] = dp[i][1] + 1
            dp[i+1][2] = dp[i][2] + dp[i][0]
        else:
            dp[i+1][1] = dp[i][1]
            dp[i + 1][2] = dp[i][2]
        if s == "C":
            ans += dp[i][2]

    print(ans)









### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    N = int(input())
    S = input()
    Q = int(input())
    x = tuple(map(int,input().split()))
    for k in x:
        d,m,dm,dmc = 0,0,0,0
        for i in range(N):
            if S[i] == "D":
                d += 1
            elif S[i] == "M":
                m += 1
                dm += d
            elif S[i] == "C":
                dmc += dm
            if i >= k-1:
                if S[i-k+1] == "D":
                    dm -= m
                    d -= 1
                elif S[i-k+1] == "M":
                    m -= 1
        print(dmc)
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

S = str(input())
T = str(input())
alp = "abcdefghijklmnopqrstuvwxyz"
for i in range(0,min(len(S),len(alp)**2)):
  if S[i] != T[i]:
    S = S.translate(str.maketrans({S[i]:T[i], T[i]:S[i]}))
  else:
    pass
  if S == T:
    print("Yes")
    exit()
print("No")

### FIXED CODE ###

S = str(input())
T = str(input())
alp = "abcdefghijklmnopqrstuvwxyz"
for i in range(0,min(len(S),len(alp)*2)):
  if S[i] != T[i]:
    S = S.translate(str.maketrans({S[i]:T[i], T[i]:S[i]}))
  else:
    pass
  if S == T:
    print("Yes")
    exit()
print("No")
### BUGGY CODE ###

import sys,queue,math,copy,itertools,bisect,collections
from heapq import *

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**3
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    N = NI()
    P = LI()

    path = [[0] * N for _ in range(N)]
    seat = [[1] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            path[i][j] = min(min(i,N-1-i),min(j,N-1-j))

    ans = 0
    for a in P:
        i = (a-1) % N
        j = (a-1) // N
        ans += path[i][j]

        seat[i][j] = 0

        q = collections.deque()
        q.append((i,j,path[i][j]))
        while q:
            x,y,z = q.popleft()
            if path[x][y] < z: continue
            z += seat[x][y]
            for dx,dy in ((0,1),(1,0),(0,-1),(-1,0)):
                if 0 <= x+dx < N and 0 <= y+dy < N:
                    if path[x+dx][y+dy] > z:
                        path[x+dx][y+dy] = z
                        q.append((x+dx,y+dy,z))
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N = NI()
    P = LI()

    s = []
    for i in range(N):
        for j in range(N):
            s.append(min(i,N-1-i,j,N-1-j))

    r = [1] * (N*N)

    ans = 0
    q = []
    for p in P:
        p -= 1
        ans += s[p]
        r[p] = 0
        q.append(p)
        while q:
            a = q.pop()
            nc = s[a] + r[a]

            if a >= N:
                if s[a-N] > nc:
                    s[a-N] = nc
                    q.append(a-N)
            if a + N < N*N:
                if s[a+N] > nc:
                    s[a+N] = nc
                    q.append(a+N)
            if a % N:
                if s[a-1] > nc:
                    s[a-1] = nc
                    q.append(a-1)
            if a % N < N -1:
                if s[a+1] > nc:
                    s[a+1] = nc
                    q.append(a+1)

    print(ans)

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

data = list(input())[::-1]

count = 0
i = 0
while 1:
    for i in range(len(data)-1):
        if data[i] == 'W' and data[i + 1] == 'B':
            count += 1
            data[i], data[i+1] = 'B', 'W'
            break
    else:
        break
print(count)


### FIXED CODE ###

data = list(input())

count = 0
# i = 0
# while 1:
count_b = 0
for i in range(len(data)):
    # print(i)
    if data[i] == 'W':
        count += count_b
        # count += 1
        # data[i], data[i+1] = 'B', 'W'
        # break
    else:
        count_b += 1
    # else:
    #     break
print(count)
### BUGGY CODE ###

from sys import stdin
from sys import setrecursionlimit

setrecursionlimit(10 ** 7)

n,m,k = map(int,stdin.readline().rstrip().split())
mod = 998244353
point = 0

def combination(n,r,mod=mod):
    r=min(r,n-r)
    up,down=1,1
    for i in range(r):
        up=up*(n-i)%mod
        down=down*(i+1)%mod
    return up*pow(down,mod-2,mod)%mod

col = m
for i in range(n-1,-1,-1):
    now = col
    now *= combination(n-1,i)%mod
    if i <= k:
        point += now%mod
    col *= m-1
    col %= mod

print(point%mod)

### FIXED CODE ###

from sys import stdin
from sys import setrecursionlimit

setrecursionlimit(10 ** 7)

n,m,k = map(int,stdin.readline().rstrip().split())
mod = 998244353
wariate = 1
point = 0

def prepare(n, MOD=mod):
    facts = [1]*(n+1)
    for i in range(1, n+1):
        facts[i] = facts[i-1]*i%MOD
    invs = [1]*(n+1)
    invs[n] = pow(facts[n], MOD-2, MOD)
    for i in range(0, n)[::-1]:
        invs[i] = invs[i+1] * (i+1) % MOD
    return facts, invs
facts, invs = prepare(n, mod)
for i in range(n-1,-1,-1):
    now = m
    if i != n-1:
        wariate *= m-1
        wariate %= mod
    now *= wariate%mod

    now *= facts[n-1]*invs[n-1-i]*invs[i]
    if i <= k:
        point += now%mod

print(point%mod)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
MOD = 1000000007
SUM = 0
for i in range(N-1):
    for j in range(i+1,N):
        SUM += (A[i]*A[j]) % MOD
print(SUM % MOD)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
MOD = 1000000007
S = sum(A) % MOD
ans = 0

for x in A:
    S -= x
    S %= MOD
    ans += S * x
    ans %= MOD
ans %= MOD
print(ans)
### BUGGY CODE ###

N=int(input())
A=[int(x) for x in input().split()]
ans=1
for i in range(0,N):
    ans=ans*A[i]
if ans>1000000000000000000:
    ans=-1
print(ans)


### FIXED CODE ###

N=int(input())
A=[int(x) for x in input().split()]
ans=1
if 0 in A:
    ans=0
else:
    for i in range(0,N):
        ans=ans*A[i]
        if ans>1000000000000000000:
            ans=-1
            break
print(ans)
### BUGGY CODE ###

import sys
from collections import Counter
N = int(sys.stdin.readline().rstrip())
A = list(map(int, sys.stdin.readline().rstrip().split()))
A.sort()
A_counters = Counter(A)

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n // i)
    return set(divisors)

nums = set()
ans = 0
for a in A:
    a_divs = make_divisors(a)
    if len(nums & a_divs) == 0 and A_counters[a] == 1:
        ans += 1
    nums.add(a)
print(ans)

### FIXED CODE ###

import sys
from collections import Counter
N = int(sys.stdin.readline().rstrip())
A = list(map(int, sys.stdin.readline().rstrip().split()))
A_counters = Counter(A)
A.sort()
A_set = set(A)
ans = 0
for a in A:
    if a in A_set:
        if A_counters[a] == 1:
            ans += 1
        for i in range(1, A[-1] // a + 1):
            if a * i in A_set:
                A_set.remove(a * i)
print(ans)
### BUGGY CODE ###

N = int(input())
s = []

for _ in range(N):
  s.append(str(input()))
  
cnt = 0
for i in range(N):
  delete = []
  s1 = s.pop()
  s1list = list(s1)
  same = 1
  
  for j in range(len(s)-1, -1, -1):
    s2 = s[j]
    s2list = list(s2) 
    if sorted(s1list) == sorted(s2list):
      delete.append(s2)
      same += 1
  if same != 1:
    cnt += same * (same - 1) / 2
  for x in delete:
    s.remove(x)
  if not s:
    break
print(int(cnt))




### FIXED CODE ###

from collections import Counter
N = int(input())
s = []
cnt = 0
for _ in range(N):
  a = str(input())
  alist = sorted(list(a))
  s.append(str(''.join(alist)))
  
l = Counter(s)
for i in l.values():
  if i > 1:
    cnt += (i - 1) * i / 2
print(int(cnt))
### BUGGY CODE ###

from collections import defaultdict
from fractions import Fraction

N = int(input())

MOD = 1000000007
d_plus = defaultdict(int)  # + or ∞
d_minus = defaultdict(int)  # - or 0
ans = 1
ans_00 = 0
for i in range(N):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        ans_00 += 1
    elif a == 0:
        d_minus[0] += 1
    elif b == 0:
        d_plus[float('inf')] += 1
    elif a * b > 0:
        d_plus[Fraction(a, b)] += 1
    else:
        d_minus[Fraction(a, b)] += 1


def pair(p):
    if p == 0:
        return float('inf')
    elif p == float('inf'):
        return 0
    else:
        return -1 / p


for m in d_minus:
    d_plus[pair(m)]
for p in d_plus:
    ans *= (pow(2, d_plus[p], MOD) + pow(2, d_minus[pair(p)], MOD) - 1)
    ans %= MOD
print((ans - 1 + ans_00) % MOD)


### FIXED CODE ###

from collections import defaultdict
from math import gcd

N = int(input())

MOD = 1000000007
d_plus = defaultdict(int)  # + or ∞
d_minus = defaultdict(int)  # - or 0
ans = 1
ans_00 = 0
for i in range(N):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        ans_00 += 1
    elif a == 0:
        d_minus[0] += 1
    elif b == 0:
        d_plus[float('inf')] += 1
    else:
        g = gcd(a, b)
        if (a > 0) ^ (b > 0):
            d_plus[(abs(a // g), abs(b // g))] += 1
        else:
            d_minus[(abs(a // g), -abs(b // g))] += 1


def pair(p):
    if p == 0:
        return float('inf')
    elif p == float('inf'):
        return 0
    else:
        a, b = -p[1], p[0]
        if a < 0:
            a, b = -a, -b
        return a, b


for m in d_minus:
    d_plus[pair(m)]
for p in d_plus:
    ans *= (pow(2, d_plus[p], MOD) + pow(2, d_minus[pair(p)], MOD) - 1)
    ans %= MOD
print((ans - 1 + ans_00) % MOD)
### BUGGY CODE ###

N = str(input())
N = int(N)
Lines = input().split(" ")
Lines = list(map(int, Lines))
answer = 0

for lineI in range(N):
    for lineJ in range(lineI+1,N):
        for lineK in range(lineJ+1,N):
             if (Lines[lineI] + Lines[lineJ] > Lines[lineK]) and (Lines[lineK] + Lines[lineJ] > Lines[lineI]) and (Lines[lineK] + Lines[lineI] > Lines[lineJ]):
                answer += 1
print(answer)


### FIXED CODE ###

N = int(input())
Lines = list(map(int, input().split(" ")))
Lines.sort()
answer = 0
 
import bisect
 
for lineI in range(N):
    for lineJ in range(lineI+1,N):
    	answer += bisect.bisect_left(Lines,Lines[lineI]+Lines[lineJ])-lineJ-1
print(answer)
### BUGGY CODE ###

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

# 各数字の個数を格納
dict = {}
for a in A:
    if a in dict:
        dict[a] += 1
    else:
        dict[a] = 1

# k番目の値を除いたlistで同じ数字を引く回数を出力
for k in range(N):
    dict_work = dict.copy()
    ans = 0
    dict_work[A[k]] -= 1
    for d in dict_work.values():
        if d > 1:
            ans += (d * (d - 1)) // 2
    print(ans)


### FIXED CODE ###

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

# 各数字の個数を格納
dict = {}
for a in A:
    if a in dict:
        dict[a] += 1
    else:
        dict[a] = 1

# k番目の値を消さない場合の場合分けの個数
ans = 0
for d in dict.values():
    if d > 1:
        ans += (d * (d - 1)) // 2

# k番目の値を除いた場合に減る場合の数を引いて答えを出力
for k in range(N):
    w = dict[A[k]]
    # 減る数
    decrease = 0
    if w == 1:
        pass
    elif w == 2:
        decrease = -1
    elif w > 2:
        decrease = ((w - 1) * (w - 2) // 2) - (w * (w - 1) // 2 )
    print(ans + decrease)
### BUGGY CODE ###

#input
H, N = map(int, input().split())
A = [0]*N
B = [0]*N
for i in range(N):
    A[i], B[i] = map(int, input().split())

#output
M = max(A)
inf = 10**10
dp = [inf]*(H+(M+1))
dp[0] = 0
for i in range(N):
    for j in range(A[i], H+M):
        dp[j] = min(dp[j], dp[j-A[i]] + B[i])

answer = min(dp[H:(H+M+1)])
print(answer)

### FIXED CODE ###

#input
H, N = map(int, input().split())
A = [0]*N
B = [0]*N
for i in range(N):
    A[i], B[i] = map(int, input().split())

#output
M = max(A)
inf = 10**10
dp = [inf]*(H+(M+1))
dp[0] = 0
for i in range(N):
    for j in range(A[i], H+M):
        dp[j] = min(dp[j], dp[j-A[i]] + B[i])

answer = min(dp[H:(H+M+1)])
print(answer)
### BUGGY CODE ###

n = int(input())
s = str(input())
r, g, b = 0, 0, 0
for i in range(n):
    if s[i] == 'R':
        r += 1
    if s[i] == 'G':
        g += 1
    if s[i] == 'B':
        b += 1
ans = r*g*b


def rgb(k, i):
    se = set()
    se.add(s[i])
    se.add(s[i+k])
    se.add(s[i+2*k])
    if len(se) == 3:
        return True
    return False


for k in range(1, n):
    for i in range(n):
        if i+2*k >= n:
            break
        if rgb(k, i):
            ans -= 1
print(ans)


### FIXED CODE ###

n = int(input())
s = str(input())
r = s.count('R')
g = s.count('G')
b = s.count('B')
ans = r*g*b

for k in range(1, n//2+1):
    for i in range(n):
        if i+2*k >= n:
            break
        if s[i] != s[i+k] and s[i] != s[i+2*k] and s[i+k] != s[i+2*k]:
            ans -= 1
print(ans)
### BUGGY CODE ###

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

def median(x, i):
    x = sorted(x)
        
    return(x[i])

def algo(x):
    l = len(x)
    t = (l + 1) // 2
    while True:
        p = x[len(x) // 2]
        a = []
        b = []
        for i in x:
            if i <= p:
                a.append(i)
            else:
                b.append(i)
        if len(a) == 0:
            return median(b, t - 1)
        elif len(b) == 0:
            return median(a, t - 1)
        elif len(a) >= t:
            x = a
        else:
            x = b
            t = t - len(a)


for i in range(n):
    a = x.pop(i)
    print(algo(x))
    x.insert(i, a)

### FIXED CODE ###

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

y = sorted(x)

for i in x:
    if i < y[len(y) // 2]:
        print(y[len(y) // 2])
    else:
        print(y[len(y) // 2 - 1])
### BUGGY CODE ###

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

# print(n, k, s)

prevcCt = 0 # 前に連続逆立ちの数
nextCnt = 0 # 後ろに連続逆立ちの数

# "00010" ⇒ [-3, 1, -1]のような配列に変換

val = 0
vals = []
for i in range(len(s)):
	if s[i] == "0":
		val -= 1
	else:
		val += 1

	#print(i, val, s[i], s[i+1])
	# print(i,len(s))
	if i == len(s) - 1 or s[i] != s[i+1]:
		vals.append(val)
		val = 0

#print(vals)

#操作しやすいようにマイナス要素が偶数になるように先頭に0を追加
if vals[0] < 0:
	vals.insert(0,0)

vals.append(0)
vals.append(0)

#print(vals)

vals = list(map(abs, vals))
#print(vals)


# K回操作できるということは連続した2k+1個の要素の最大値を求めればよい
max = 0

loopCnt = len(vals) - k
if  loopCnt < 1:
	loopCnt = 1

for i in range(loopCnt):
	#print(i, len(vals), k)
	# 偶数の時だけ判定
	if i%2 == 0:
		# print(vals[i:i + 2*k + 1])

		sumVal = sum(vals[i:i + 2*k + 1])
		# for e in vals[i:i + 2*k + 1]:
		# 	sumVal += abs(e)
		if sumVal > max:
			max = sumVal

print(max)


### FIXED CODE ###

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

# print(n, k, s)

prevcCt = 0 # 前に連続逆立ちの数
nextCnt = 0 # 後ろに連続逆立ちの数

# "00010" ⇒ [-3, 1, -1]のような配列に変換

val = 0
vals = []
for i in range(len(s)):
	if s[i] == "0":
		val -= 1
	else:
		val += 1

	#print(i, val, s[i], s[i+1])
	# print(i,len(s))
	if i == len(s) - 1 or s[i] != s[i+1]:
		vals.append(val)
		val = 0

#print(vals)

#操作しやすいようにマイナス要素が偶数になるように先頭に0を追加
if vals[0] < 0:
	vals.insert(0,0)

vals.append(0)
vals.append(0)

#print(vals)

vals = list(map(abs, vals))
#print(vals)


# K回操作できるということは連続した2k+1個の要素の最大値を求めればよい
max = 0

loopCnt = len(vals) - k
if  loopCnt < 1:
	loopCnt = 1


# 最初の要素をベースとする
sumVal = sum(vals[0:2*k + 1])
max = sumVal

# print(vals)
# print(max)

for i in range(loopCnt):
	#print(i, len(vals), k)
	# 偶数の時だけ判定
	if i%2 == 0 and i>0:
		# 外れた要素の合計値
		outVal = sum(vals[i-2:i])
		# 新たに加わった要素の合計値
		inVal = sum(vals[i + 2*k -1:i + 2*k + 1])
	
		sumVal = sumVal - outVal + inVal

		#print(i, vals[i-2:i], outVal, vals[i + 2*k -1:i + 2*k + 1], inVal, sumVal)
		# print(vals[i:i + 2*k + 1])

		#sumVal = sum(vals[i:i + 2*k + 1])
		# for e in vals[i:i + 2*k + 1]:
		# 	sumVal += abs(e)
		if sumVal > max:
			max = sumVal

print(max)
### BUGGY CODE ###

n,s = map(int,input().split())
A = list(map(int,input().split()))
mod = 998244353
dp = [[0 for i in range(s+1)] for j in range(n+1)]
dp[0][0] = 1
for i in range(n):
    for j in range(s+1):
        if j - A[i] >= 0:
            dp[i+1][j]=(dp[i][j]*2+dp[i][j-A[i]])%mod
        else:
            dp[i+1][j]=(dp[i][j]*2)%mod
print(dp[n][s])

### FIXED CODE ###

n,s = map(int,input().split())
A = list(map(int,input().split()))
mod = 998244353
dp = [[0 for i in range(s+1)] for j in range(n+1)]
dp[0][0] = 1
for i in range(n):
    for j in range(s+1):
        if j - A[i] >= 0:
            dp[i+1][j]=(dp[i][j]*2+dp[i][j-A[i]])%mod
        else:
            dp[i+1][j]=(dp[i][j]*2)%mod
print(dp[n][s])
### BUGGY CODE ###

N, A, B, C, D, E= [float(input()) for _ in range(6)]
cities = [A, B, C, D, E]
P = [N, 0, 0, 0, 0, 0]
t = 0
while True:
  t += 1
  for i in range(5)[::-1]:
    if P[i] > 0:
      s = P[i] - cities[i]
      if s < 0 :
        P[i+1] += P[i]
        P[i] = 0
      else :
        P[i+1] += cities[i]
        P[i] = s
  if(N <= P[5]):
    break
print(t)

### FIXED CODE ###

N, A, B, C, D, E= [float(input()) for _ in range(6)]
cities = [A, B, C, D, E]
P = [N, 0, 0, 0, 0, 0]
t = 0
while True:
  for i, c in enumerate(cities):
    s = P[i] - c
    if s < 0 :
      P[i+1] += P[i]
      P[i] = 0
    else :
      P[i+1] += c
      P[i] = s
    t += 1
  if(P[5] > 0):
    break
print(int(-(-N//P[5]) + t - 1))
### BUGGY CODE ###

import networkx as nx

def main():
  N,M=map(int,input().split())
  S = [list(input()) for _ in range(N)]

  if N == M == 1:
    print(0)
    print(S[0][0])
    exit()

  index = lambda i,j: i*M+j

  G=nx.DiGraph()
  G.add_node('source')
  G.add_node('sink')
  dx,dy=(1,0),(0,1)
  E = []
  for i in range(N):
    for j in range(M):
      if S[i][j]=='#':continue
      if (i+j) %2:
        E.append((index(i,j),'sink'))
      else:
        E.append(('source',index(i,j)))
      for k in range(2):
        v1,v2 = index(i,j),index(i+dx[k],j+dy[k])
        if not (0<=i+dx[k]<N and 0<=j+dy[k]<M):
          continue
        if S[i+dx[k]][j+dy[k]] == '#': continue
        if (i+j) % 2:
          E.append((v2,v1))
        else:
          E.append((v1,v2))
     
  G.add_edges_from(E,capacity=1)
  flow_value, flow_dict = nx.maximum_flow(G, "source", "sink")

  for v1 in flow_dict.keys():
    if v1 in ('sink','source'):continue
    for v2 in flow_dict[v1].keys():
      if v2 in ('sink','source'):continue
      if flow_dict[v1][v2]:
        i1,j1 = divmod(v1,M)
        i2,j2 = divmod(v2,M)
        if i1 > i2 or j1 > j2:
          (i1,j1),(i2,j2) = (i2,j2),(i1,j1)
        if i1 < i2:
          S[i1][j1] = 'v'
          S[i2][j2] = '^'
        else:
          S[i1][j1] = '>'
          S[i2][j2] = '<'

  print(flow_value)
  for i in range(N):
    print(''.join(S[i]))
    
if __name__ == "__main__":
  main()

### FIXED CODE ###

import networkx as nx

def main():
  N,M=map(int,input().split())
  S = [list(input()) for _ in range(N)]

  if N == M == 1:
    print(0)
    print(S[0][0])
    exit()

  index = lambda i,j: i*M+j

  G=nx.Graph()
  dx,dy=(1,0),(0,1)
  E = []
  n1,n2 = [],[]
  for i in range(N):
    for j in range(M):
      if S[i][j]=='#':continue
      if (i+j)%2:
        n1.append(index(i,j))
      else:
        n2.append(index(i,j))
      for k in range(2):
        v1,v2 = index(i,j),index(i+dx[k],j+dy[k])
        if not (0<=i+dx[k]<N and 0<=j+dy[k]<M):
          continue
        if S[i+dx[k]][j+dy[k]] == '#': continue
        if (i+j) % 2:
          E.append((v2,v1))
        else:
          E.append((v1,v2))
     
  G.add_nodes_from(n1, bipartite=0)
  G.add_nodes_from(n2, bipartite=1)
  G.add_edges_from(E)
  u = [n for n in G.nodes if G.nodes[n]['bipartite'] == 0]
  match = nx.bipartite.maximum_matching(G, top_nodes=u)
  match = {v:match[v] for v in match.keys() if v < match[v]}
 
  for v in match.keys():
    i1,j1 = divmod(v,M)
    i2,j2 = divmod(match[v],M)
    if i1 > i2 or j1 > j2:
      (i1,j1),(i2,j2) = (i2,j2),(i1,j1)
    if i1 < i2:
      S[i1][j1] = 'v'
      S[i2][j2] = '^'
    else:
      S[i1][j1] = '>'
      S[i2][j2] = '<'

  print(len(match))
  for i in range(N):
    print(''.join(S[i]))
    
if __name__ == "__main__":
  main()
### BUGGY CODE ###

import functools

n = int(input())
xs = input().split()

def foldSum(acc, x):
    return acc*int(x)

if 0 in xs:
    print(0)
else:
    res = functools.reduce(foldSum, xs, 1)

    if res > 1e18:
        print(-1)
    else:
        print(res)



### FIXED CODE ###

import functools

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

def foldMulti(acc, x):
    return acc*x

if 0 in xs:
    print(0)
elif len([x for x in xs if x > 1]) >= 60:
    print(-1)
else:
    res = functools.reduce(foldMulti, xs, 1)

    if res > 1e18:
        print(-1)
    else:
        print(res)
### BUGGY CODE ###

n, m, k = map(int, input().split())

GRAPH = [[0]*n for _ in range(n)]
BLOCK = [[0]*n for _ in range(n)]

for _ in range(m):
    a, b = map(lambda x: int(x)-1, input().split())
    GRAPH[a][b] = GRAPH[b][a] = 1

for _ in range(k):
    a, b = map(lambda x: int(x)-1, input().split())
    BLOCK[a][b] = BLOCK[b][a] = 1

def make_dfs():
    visited = [0]*n

    def dfs(v):
        visited[v] = 1
        for v2 in range(n):
            if not GRAPH[v][v2]:
                continue
            if visited[v2]:
                continue
            dfs(v2)
        return visited
    return dfs


ans = []
for i in range(n):
    f = make_dfs()
    friends = f(i)
    follow = GRAPH[i]
    block = BLOCK[i]
    bl = sum(f and b for f, b in zip(friends, block))

    ans.append(sum(friends) - (sum(follow)+bl)-1)

print(*ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

n, m, k = map(int, input().split())

class UnionFind:
    def __init__(self, n):
        self.p = [-1]*n
        self.c = None

    def find(self, x):
        if self.p[x] < 0:
            return x
        else:
            self.p[x] = self.find(self.p[x])
            return self.p[x]

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

    def count_member(self, x):
        return -self.p[self.find(x)]


uf = UnionFind(n)

ab = []
for i in range(m):
    a, b = map(lambda x: int(x)-1, input().split())
    ab.append((a, b))
    uf.union(a, b)

cd = [list(map(lambda x: int(x)-1, input().split())) for _ in range(k)]
ans = [uf.count_member(i)-1 for i in range(n)]

for a, b in ab:
    if uf.find(a) == uf.find(b):
        ans[a] -= 1
        ans[b] -= 1

for c, d in cd:
    if uf.find(c) == uf.find(d):
        ans[c] -= 1
        ans[d] -= 1

print(*ans)