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

# N問出題, M回提出
N, M = map(int, input().split())

p_S_list = []

WA = 'WA'
AC = 'AC'

for _ in range(M):
    p, S = input().split()
    p_S_list.append([int(p), S])

count_AC = 0
count_WA = 0
for i in range(1, N + 1):
    # i問目の問題について考える
    if [i, AC] in p_S_list:
        count_AC += 1

        first_AC_index = p_S_list.index([i, AC])

        count_WA += p_S_list[:first_AC_index].count([i, WA])

    
ans = str(count_AC) + ' ' + str(count_WA)

print(ans)

### FIXED CODE ###

# N問出題, M回提出
N, M = map(int, input().split())

p_S_list = []

WA = 'WA'
AC = 'AC'

question_list = [False] * N
WA_count_list = [0] * N

count_AC = 0
count_WA = 0

for i in range(M):
    p, S = input().split()
    int_p = int(p)
    
    if S == WA and question_list[int_p - 1] == False:
        WA_count_list[int_p - 1] += 1

    if S == AC and question_list[int_p - 1] == False:
        count_AC += 1
        count_WA += WA_count_list[int_p - 1]
        question_list[int_p - 1] = True

print(str(count_AC) + ' ' + str(count_WA))








'''
first_AC_index_list = []
AC_set = set([])

for j in range(M):
    p, S = input().split()
    int_p = int(p)
    p_S_list.append([int_p, S])

    if S == AC and (int_p not in AC_set):
        first_AC_index_list.append([j, int_p])
        AC_set.add(int_p)

count_AC = len(first_AC_index_list)
count_WA = 0
# for i in range(1, N + 1):
#     # i問目の問題について考える
#     if [i, AC] in p_S_list:
#         count_AC += 1

#         first_AC_index = p_S_list.index([i, AC])

#         count_WA += p_S_list[:first_AC_index].count([i, WA])

for i_list in first_AC_index_list:
    count_WA += p_S_list[:i_list[0]].count([i_list[1], WA])

ans = str(count_AC) + ' ' + str(count_WA)

print(ans)

'''
### BUGGY CODE ###

N=int(input())
A=[]
for i in range(N):
    x=int(input())
    if x in A:
        A.remove(x)
    else:
        A.append(x)

print(len(A))

### FIXED CODE ###

N=int(input())
A=set()
for i in range(N):
    x=int(input())
    if x in A:
        A.remove(x)
    else:
        A.add(x)

print(len(A))
### BUGGY CODE ###

def addbit(i):
    i += 1
    while i <= N:
        BIT[i] += 1
        i += i & (-i)
def getsum(i):
    ret = 0
    i += 1
    while i != 0:
        ret += BIT[i]
        i -= i&(-i)
    return ret
def bit(L):
    global BIT
    BIT=[0] * (N+1)
    re = 0
    for l in L:
        re += getsum(l)
        addbit(l)
    return N*(N-1)//2 - re
def calc(Z):
    Z.sort()
    l, r, lc, rc = -1<<20, 1<<20, N*(N-1)//4+1, N*(N-1)//4+1
    if N <= 10000: l, r = -1<<28, 1<<28
    while r - l > 0.000000001:
        m = (l+r) / 2 if N <= 10000 else (l * rc + r * lc) / (lc + rc)
        A = [a&((1<<16)-1) for a in sorted([(int((s*m+t)*2**(100 if N <= 10000 else 40))<<16)+i for i, (s, t) in enumerate(Z)])]
        c = bit(A)
        if c > N*(N-1)//4:
            l = m
            lc = (c - N*(N-1)//4) * 2
        else:
            r = m
            rc = (N*(N-1)//4 - c) * 2 + 1
    return l

N = int(input())
X, Y = [], []
for _ in range(N):
    a, b, c = map(int, input().split())
    X.append((-a/b, c/b))
    Y.append((-b/a, c/a))
print(calc(X), calc(Y))

### FIXED CODE ###

def addbit(i):
    i += 1
    while i <= N:
        BIT[i] += 1
        i += i & (-i)
def getsum(i):
    ret = 0
    i += 1
    while i != 0:
        ret += BIT[i]
        i -= i&(-i)
    return ret
def bit(L):
    global BIT
    BIT=[0] * (N+1)
    re = 0
    for l in L:
        re += getsum(l)
        addbit(l)
    return N*(N-1)//2 - re
def calc(Z):
    Z.sort()
    l, r, lc, rc = -1<<28, 1<<28, N*(N-1)//4+1, N*(N-1)//4+1
    f = 1
    while (r - l) / max(abs(l), 1) > 0.000000001:
        m = (l+r) / 2 if f else (l * rc + r * lc) / (lc + rc)
        A = [a&((1<<16)-1) for a in sorted([(int((s*m+t)*2**40)<<16)+i for i, (s, t) in enumerate(Z)])]
        c = bit(A)
        if c > N*(N-1)//4:
            l = m
            lc = (c - N*(N-1)//4) * 2
        else:
            r = m
            rc = (N*(N-1)//4 - c) * 2 + 1
        f ^= 1
    return l

N = int(input())
X, Y = [], []
for _ in range(N):
    a, b, c = map(int, input().split())
    X.append((-a/b, c/b))
    Y.append((-b/a, c/a))
print(calc(X), calc(Y))
### BUGGY CODE ###

def solve():
    h, k = read()
    result = think(h, k)
    write(result)


def read():
    n, k = read_int(2)
    return read_int(n), k


def read_int(n):
    return list(map(lambda x: int(x), read_line().split(' ')))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(h, k):
    cost = [0 for x in range(len(h))]
    # element of h <= 10 ** 4, elements <= 10 ** 5, +1 in case
    initial_value_of_cost = 10 ** (4 + 5) + 1
    n = len(h)
    for dst in range(1, n):
        minimum_cost = initial_value_of_cost
        start_point = max(0, dst - k)
        for src in range(start_point, dst):
            minimum_cost = min(minimum_cost, cost[src] + abs(h[src] - h[dst]))
        cost[dst] = minimum_cost
    return cost[n - 1]


def write(result):
    print(result)


if __name__ == '__main__':
    solve()

### FIXED CODE ###

def solve():
    h, k = read()
    result = think(h, k)
    write(result)


def read():
    n, k = read_int(2)
    return read_int(n), k


def read_int(n):
    return list(map(lambda x: int(x), read_line().split(' ')))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(h, k):
    cost = [0 for x in range(len(h))]
    for dst in range(1, len(h)):
        start_point = max(0, dst - k)
        cost[dst] = min([cost[src] + abs(h[src] - h[dst]) for src in range(start_point, dst)])
    return cost[len(h) - 1]


def write(result):
    print(result)


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

from collections import Counter

def main():
    n = int(input())
    d = list(map(int, input().split()))
    
    
    if d[0] != 0:
        print(0)
        return
    
    count = Counter(d)
    #print(count[0])
    #print(len(count))
    #print(count.keys())
    #print(count.items())
    if count[0] != 1:
        print(0)
        return

    ans = 1
    tmp = 1
    for i in range(1, len(d)+1):
        
        ans *= tmp**count[i]
        #print(ans)
        tmp = count[i]


    print(ans%998244353)


if __name__ == '__main__':
    main()



### FIXED CODE ###

from collections import Counter

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

count = Counter(d)

if d[0] != 0:
    print(0)
    


#print(count[0])
#print(len(count))
#print(count.keys())
#print(count.items())
elif count[0] != 1:
    print(0)
    
else:
    ans = 1
    tmp = 1
    max_d = max(d)
    for i in range(1, max_d+1):
        
        ans *= tmp**count[i]
        #print(ans)
        tmp = count[i]


    print(ans%998244353)
### BUGGY CODE ###

from collections import deque
n = int(input())
a = deque()
for _ in range(n):
    a.append(int(input()))

for i in range(n):
    tmp = a.popleft()
    print(max(a))
    a.append(tmp)

### FIXED CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]
sort_a = sorted(a, reverse=True)
amax = sort_a[0]
asecond = sort_a[1]
for i in range(n):
    tmp = a[i]
    if tmp == amax:
        print(asecond)
    else:
        print(amax)
### BUGGY CODE ###

#! /usr/bin/env python3

import sys
from math import gcd
import numpy as np
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

N, *A = map(int, read().split())
A = np.array(A)
cnt = np.zeros(N)
for i, a in enumerate(A):
    acc = (A % a) == 0
    cnt = cnt + acc

print(sum(cnt == 1))


### FIXED CODE ###

#! /usr/bin/env python3

import sys
from math import gcd
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

N, *A = map(int, read().split())
A = sorted(A)
M = pow(10, 6) + 1
divs = [False] * M
cnt = 0
for i, a in enumerate(A):
    if divs[a]:
        continue

    if i == N - 1 or a != A[i + 1]:
        cnt += 1

    acc = a
    while acc < M:
        divs[acc] = True
        acc += a
print(cnt)
### BUGGY CODE ###

if __name__ == '__main__':
    s = input()
    K = int(input())
    # # s = 'aba'
    # s = 'atcoderandatcodeer'
    # K = 5

    candidates = set()
    for start in range(0, len(s)):
        for end in range(start + 1, len(s) + 1):
            candidates |= {s[start:end]}

    candidates = sorted(candidates)
    # print(candidates)
    print(candidates[K - 1])

    #
    # length_to_candidates = defaultdict(list)
    # for length in range(1, len(s) + 1):
    #     for start in range(0, len(s) + 1 - length):
    #         sub = s[start:start + length]
    #         if sub not in length_to_candidates[length]:
    #             length_to_candidates[length].append(sub)
    #         # length_to_candidates |= {s[start:start + length]}
    #
    # all_candidates = []
    # for v in length_to_candidates.values():
    #     all_candidates += list(v)
    #
    # print(all_candidates)
    # print(all_candidates[K - 1])

    # print(length_to_candidates)


### FIXED CODE ###

if __name__ == '__main__':
    s = input()
    K = int(input())
    # s = 'aba'
    # s = 'atcoderandatcodeer'
    # K = 5

    candidates = set()
    for start in range(0, len(s)):
        for length in range(1, K + 1):
            candidates |= {s[start:start + length]}

    candidates = sorted(candidates)
    print(candidates[K - 1])
### BUGGY CODE ###

import math
N=int(input())
ans=[0 for i in range(N)]

for n in range(N):
    nax=int(math.sqrt(n))
    for x in range(1,nax):
        for y in range(1,x+1):
            for z in range(1,y+1):
                temp=x**2+y**2+z**2+x*y+y*z+z*x
                if temp==n+1:
                    ans[n]+=1
                    if x==y and y!=z:
                        ans[n]+=2
                    if y==z and x!=y:
                        ans[n]+=2
                    if x==z and y!=x:
                        ans[n]+=2
                    if x!=y and y!=z and z!=x:
                        ans[n]+=5

for anss in ans:
    print(anss)


### FIXED CODE ###

import math
N=int(input())
ans=[0 for i in range(N)]

nax=int(math.sqrt(N))

for x in range(1,nax):
    for y in range(1,x+1):
        for z in range(1,y+1):
            temp=x**2+y**2+z**2+x*y+y*z+z*x
            if temp<=N:
                if x==y and y!=z:
                    ans[temp-1]+=3
                elif y==z and z!=x:
                    ans[temp-1]+=3
                elif z==x and x!=y:
                    ans[temp-1]+=3
                elif x==y==z:
                    ans[temp-1]+=1
                elif x!=y and y!=z and z!=x:
                    ans[temp-1]+=6

                
                
for anss in ans:
    print(anss)
### BUGGY CODE ###

n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]
s = [1]*(n+1)

if 1 in a:
    s[1] = 0

for i in range(n-1):
    if i+2 in a:
        s[i+2] = 0
        continue
    if i+2 not in a:
        s[i+2] = (s[i+1] + s[i]) % (10**9+7)

print(s[-1])

### FIXED CODE ###

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

s = [1]*(n+1)

if 1 in a:
    s[1] = 0

for i in range(n-1):
    if i+2 in a:
        s[i+2] = 0
        continue
    s[i+2] = (s[i+1] + s[i]) % (10**9+7)
    
print(s[-1])
### BUGGY CODE ###

def main():
    N = int(input())
    a = input().split(" ")
    dict = {}
    for i in range(N):
        dict[int(a[i])] = str(i + 1)
    ans = ""
    for j in range(N):
        ans = ans + dict[j + 1] + " "
    print(ans)


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    N = int(input())
    A = map(int, input().split(" "))
    list = [""] * (N + 1)
    for i, a in enumerate(A, 1):
        list[a] = str(i)
    print(" ".join(list[1:]))


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

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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

from collections import Counter, defaultdict
c = Counter(a)
n1, n2, n3 = c[1], c[2], c[3]
n0 = c[0]
def glist(*l, fill=None):
    if len(l)==1:
        return [fill]*l[0]
    ll = l[1:]
    return [glist(*ll) for _ in range(l[0])]
dp = glist(301, 301, 301)
dp[0][0][0] = 0
count = [0, 0]
def sub(i1,i2,i3):
    count[0] += 1
    if dp[i1][i2][i3] is not None:
        count[1] += 1
        return dp[i1][i2][i3]
    ans = n
    p = 0
    if i1>0:
        ans += i1 * sub(i1-1,i2,i3)
        p += i1
    if i2>0:
        ans += i2 * sub(i1+1,i2-1,i3)
        p += i2
    if i3>0:
        ans += i3 * sub(i1,i2+1,i3-1)
        p += i3
    ans = ans/p
    dp[i1][i2][i3] = ans
    return ans
print(sub(n1,n2,n3))

### FIXED CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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

from collections import Counter, defaultdict
c = Counter(a)
n1, n2, n3 = c[1], c[2], c[3]
n0 = c[0]
def glist(*l, fill=None):
    if len(l)==1:
        return [fill]*l[0]
    ll = l[1:]
    return [glist(*ll) for _ in range(l[0])]

count = 0
S = sum(a)
sub = glist(n1+n2+n3+1,n2+n3+1,n3+1)
sub[0][0][0] = 0
#     for i1 in range(min(n+1, s+1)):
#         for i2 in range(min(n+1, (s-i1)//2+1)):
for i3 in range(n3+1):
    for i2 in range(n2+n3+1-i3):
        for i1 in range(n1+n2+n3 - (i2+i3) + 1):
            if i1==i2==i3==0 or i1+i2+i3>n:
                continue
#             print(i1,i2,i3)
            ans = n
            p = 0
            if i1>0:
                ans += i1 * sub[i1-1][i2][i3]
                p += i1
            if i2>0:
                ans += i2 * sub[i1+1][i2-1][i3]
                p += i2
            if i3>0:
                ans += i3 * sub[i1][i2+1][i3-1]
                p += i3
            ans = ans/p
            sub[i1][i2][i3] = ans
print(sub[n1][n2][n3])
### BUGGY CODE ###

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

cnt = 0

for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            if x+y+z==s:
                cnt += 1
print(cnt)


### FIXED CODE ###

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

cnt = 0
for x in range(k+1):
    for y in range(k+1):
        z = s-x-y
        if 0 <= z <= k:
            cnt += 1
print(cnt)
### BUGGY CODE ###

N = int(input())
a_list = sorted(list(map(int, input().split())))
dp = [True] * N

for i, ai in enumerate(a_list):
  if dp[i] == False:
    continue
  
  for j, aj in enumerate(a_list[i+1:]):
    if ai == aj:
      dp[i] = False
    if aj%ai == 0:
      dp[i+1+j] = False
  if dp[i] > a_list[-1]**0.5+1:
    break
print(sum(dp))

### FIXED CODE ###

N = int(input())
a_list = sorted(list(map(int, input().split())))
a_max = a_list[-1]

count = [0] * (a_max+1)

for a in a_list:
  for j in range(a, a_max+1, a):
    count[j] += 1
  
ans = 0
for a in a_list:
  if count[a] == 1:
    ans += 1
print(ans)
### BUGGY CODE ###

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

INF = 10**9 + 1
L = [INF]*N
L[0] = 0
for i in range(1, N):
    minLi = L[i]
    H_i = H[i]
    for k in range(1, K+1):
        if i - k >= 0:
            minLi = min(minLi, L[i-k] + abs(H_i - H[i-k]))
    L[i] = minLi
print(L[N-1])

### FIXED CODE ###

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

INF = 10**9 + 1
L = [INF]*N
L[0] = 0
for i in range(1, N):
    minLi = L[i]
    H_i = H[i]
    for k in range(1, K+1):
        if i - k >= 0:
            minLi = min(minLi, L[i-k] + abs(H_i - H[i-k]))
    L[i] = minLi
print(L[N-1])
### BUGGY CODE ###

import numpy as np
N = int(input())
M = np.asarray(input().split(), dtype=int)
C = np.arange(1,N+1)
print(np.sum([np.sum(M[i+M[i]+1:]==C[:N-i-M[i]-1]) for i in range(N)]))

### FIXED CODE ###

N = int(input())
M = list(map(int, input().split()))
L = [0] * N
R = [0] * N
for i,m in enumerate(M):
  if i+m >= N:
    continue
  L[i+m] += 1
for i,m in enumerate(M[::-1]):
  if i+m >= N:
    continue
  R[i+m] += 1
R = R[::-1]
#print(L)
#print(R)
print(sum([l*r for l,r in zip(L,R)]))
### BUGGY CODE ###

a,b,x = map(int, input().split())

cnt=0
for num in range(a, b+1, 1):

    if num % x == 0:
        cnt+=1
print(cnt)

### FIXED CODE ###

a,b,x = map(int, input().split())

# a,b,x = map(int, "9 9 2".split())
cnt=0

alfa = b//x + 1
beta = (a-1)//x + 1

print(alfa - beta)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 7)


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

    a.sort()
    f.sort(reverse=True)

    l = -1
    r = 10 ** 13

    def test(x):
        cnt = 0
        for ae, fe in zip(a, f):
            cnt += max(0, ae - x // fe)

        return cnt <= k

    while l + 1 < r:
        m = (l + r) // 2
        if test(m):
            r = m
        else:
            l = m

    ans = r
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)


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

    a.sort()
    f.sort(reverse=True)

    l = -1
    r = 10 ** 13

    def test(x):
        cnt = 0
        for ae, fe in zip(a, f):
            cnt += max(0, ae - x // fe)

        return cnt <= k

    while l + 1 < r:
        m = (l + r) // 2
        if test(m):
            r = m
        else:
            l = m

    ans = r
    print(ans)


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

import sys

def main():
    input = sys.stdin.readline
    n, s = map(int, input().split())
    a = [int(x) for x in input().split()]
    a.sort(reverse=True)
    mod = 998244353
    
    dp = [dict() for _ in range(s+1)]
    
    judge = dict()
    for i in range(n):
        for j in range(s-1, -1, -1):
            if dp[j] != judge and a[i]+j <= s:
                for k, v in dp[j].items():
                    if k+1 in dp[a[i]+j]:
                        dp[a[i]+j][k+1] = (v+dp[a[i]+j][k+1])%mod
                    else:
                        dp[a[i]+j][k+1] = v%mod
            if j == 0 and a[i] <= s:
                if 1 in dp[a[i]]:
                    dp[a[i]][1] = (dp[a[i]][1]+1)%mod
                else:
                    dp[a[i]][1] = 1
    
    ans = 0
    count = 1
    for k in range(n, 0, -1):
        if k in dp[s]:
            ans += (count*dp[s][k])%mod
            ans %= mod
        count *= 2
        count %= mod
    
    print(ans)
    

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
  n, s = map(int, input().split())
  a = [int(x) for x in input().split()]
  mod = 998244353
  
  dp = [[0]*(s+1) for _ in range(n+1)]
  dp[0][0] = 1
  for i in range(1, n+1):
    for j in range(s, -1, -1):
      dp[i][j] += dp[i-1][j]*2
      dp[i][j] %= mod
      if dp[i-1][j] and j+a[i-1] <= s:
        dp[i][j+a[i-1]] += dp[i-1][j]
        dp[i][j+a[i-1]] %= mod

  print(dp[n][s])
  
  
if __name__ == "__main__":
  main()
### BUGGY CODE ###

import math
import itertools

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

C = list(itertools.combinations(A, 2))
C = list(c for c in C if c[0] == c[1])
equal = len(C)

for i in range(n):
    A_tmp = A[: i] + A[i + 1: ]
    equal_i = A_tmp.count(A[i])
    print(equal - equal_i)


### FIXED CODE ###

import math
import collections

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

equal = 0
elements = collections.Counter(A)
equal = sum([v * (v - 1) // 2 for v in elements.values()])

for i in range(n):
    equal_i = elements[A[i]] - 1
    print(equal - equal_i)
### BUGGY CODE ###

# https://atcoder.jp/contests/agc033/tasks/agc033_a

from heapq import heappop, heappush
H, W = map(int, input().split())
M = [list(input()) for _ in range(H)]
dist = [[10000000] * W for _ in range(H)]

def search(h, w):
    queue = [(0, (h, w))]
    while len(queue) > 0:
        cd, (ch, cw) = heappop(queue)
        for (dh, dw) in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            nh, nw = ch + dh, cw + dw
            if nh < 0 or H <= nh or nw < 0 or W <= nw:
                continue
            if dist[nh][nw] > cd + 1:
                dist[nh][nw] = cd + 1
                heappush(queue, (cd + 1, (nh, nw)))


for h in range(H):
    for w in range(W):
        if M[h][w] == '#':
            dist[h][w] = 0
            search(h, w)

ans = 0
for row in dist:
    ans = max(ans, max(row))
print(ans)

### FIXED CODE ###

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

def solve():
    H, W = map(int, input().split())
    M = [[] for _ in range(H)]
    queue = deque()
    for i in range(H):
        M[i] = list(input())
        for j in range(W):
            if M[i][j] == '#':
                queue.append((i, j))
    ans = 0
    while queue:
        # 今の地点から1ステップ変化
        n = len(queue)
        flag = False
        for _ in range(n):
            cy, cx = queue.popleft()
            for dy, dx in ((-1, 0), (0, 1), (1, 0), (0, -1)):
                ny, nx = cy + dy, cx + dx
                if 0 <= nx < W and 0 <= ny < H and M[ny][nx] == '.':
                    M[ny][nx] = '#'
                    flag = True
                    queue.append((ny, nx))
        if flag:
            ans += 1
    print(ans)


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

import bisect
from decimal import Decimal
N, *A = [Decimal(_) for _ in open(0).read().split()]
N = int(N)
c = [[0, 0] for _ in range(N)]
for i, a in enumerate(A):
    a = int(a * 10**9)
    while True:
        if a % 2:
            break
        c[i][0] += 1
        a //= 2
    while True:
        if a % 5:
            break
        c[i][1] += 1
        a //= 5
c.sort()

#cum[i][j]:c[x][1]>=i (j<=x)となるようなxの個数
cum = [[0] * (N + 1) for _ in range(19)]
for i in range(19):
    for j in range(N - 1, -1, -1):
        cum[i][j] = cum[i][j + 1]
        if c[j][1] >= i:
            cum[i][j] += 1
ans = 0
for i, c2c5 in enumerate(c):
    c2, c5 = c2c5
    if c2 > 9 or (c2 == 9 and c5 >= 9):
        i2 = i + 1
    else:
        i2 = bisect.bisect_left(c, [18 - c2, -1])
    ans += cum[18 - c5][i2]
print(ans)


### FIXED CODE ###

import bisect
from decimal import Decimal
N, *A = open(0).read().split()
N = int(N)
c = [[0, 0] for _ in range(N)]
for i, a in enumerate(A):
    if '.' in a:
        p, q = a.split('.')
        q += '0' * (9 - len(q))
    else:
        p = a
        q = '0' * 9
    a = int(p + q)
    while True:
        if a % 2:
            break
        c[i][0] += 1
        a //= 2
    while True:
        if a % 5:
            break
        c[i][1] += 1
        a //= 5
c.sort()

#cum[i][j]:c[x][1]>=i (j<=x)となるようなxの個数
cum = [[0] * (N + 1) for _ in range(19)]
for i in range(19):
    for j in range(N - 1, -1, -1):
        cum[i][j] = cum[i][j + 1]
        if c[j][1] >= i:
            cum[i][j] += 1
ans = 0
for i, c2c5 in enumerate(c):
    c2, c5 = c2c5
    if c2 > 9 or (c2 == 9 and c5 >= 9):
        i2 = i + 1
    else:
        i2 = bisect.bisect_left(c, [18 - c2, -1])
    ans += cum[18 - c5][i2]
print(ans)
### BUGGY CODE ###

k, q = map(int, input().split())
d = [int(x) for x in input().split()]

for _ in range(q):
    n, x, m = map(int, input().split())
    z = 0
    last = x
    ans = 0

    for i in range(k):
        dnum = (n-1-i+(k-1))//k
        last += d[i]%m * dnum
        if d[i]%m == 0:
            z += dnum
        
    ans = (n-1) - (last//m - x//m) - z
    print(ans)


### FIXED CODE ###

k, q = map(int, input().split())
d = [int(x) for x in input().split()]

for _ in range(q):
    n, x, m = map(int, input().split())
    z = 0
    last = x
    ans = 0

    for i in range(k):
        dnum = (n-1-i+(k-1))//k
        last += d[i]%m * dnum
        if d[i]%m == 0:
            z += dnum
        
    ans = (n-1) - (last//m - x//m) - z
    print(ans)