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

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

dp = [[0] * (s+1) for i in range(n+1)]
dp[0][0] = 1

for i in range(n):
    a = A[i]
    for j in range(s+1):
        if j < s:
            dp[i+1][j] = (dp[i+1][j] + 2*dp[i][j])%mod
        if j+a<s+1:
            dp[i+1][j+a] = (dp[i+1][j+a] + dp[i][j])%mod

ans = 0
for i in range(1, n+1):
    ans = (ans + dp[i][s] * pow(2, n-i, mod)) % mod
print(ans)




### FIXED CODE ###

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

dp = [[0] * (s+1) for i in range(n+1)]
dp[0][0] = 1

for i in range(n):
    a = A[i]
    for j in range(s+1):
        if j < s:
            dp[i+1][j] = (dp[i+1][j] + 2*dp[i][j])%mod
        if j+a<s+1:
            dp[i+1][j+a] = (dp[i+1][j+a] + dp[i][j])%mod

ans = 0
for i in range(1, n+1):
    ans = (ans + dp[i][s] * pow(2, n-i, mod)) % mod
print(ans)
### BUGGY CODE ###

from fractions import gcd
import sys
input = sys.stdin.readline

N,M=map(int,input().split())
List=list(map(lambda x:int(x)/2,map(int, set(input().split()))))

def main():
    LCM=1

    for i in List:
        LCM*=i/gcd(LCM,i)

    for i in List:
        if LCM/i%2==0:
            print(0)
            exit()

    print(int(M//(LCM*2)+M%(LCM*2)//LCM))


if __name__ == '__main__':
    main()

### FIXED CODE ###

from fractions import gcd
import sys
input = sys.stdin.readline

N,M=map(int,input().split())
List=list(map(lambda x:int(x)//2,map(int, set(input().split()))))

def main():
    LCM=1

    for i in List:
        LCM*=i//gcd(LCM,i)

    for i in List:
        if LCM//i%2==0:
            print(0)
            exit()

    print(int(M//(LCM*2)+M%(LCM*2)//LCM))


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

### 動的計画法のテーブルを用意
# dp(n) は頂点nを始点として時の最大有効パスの長さ

def get_inputs():
    N, M = map(int, input().split())

    # グラフgを初期化
    g = [[] for _ in range(N)]

    # 辺情報を読み込みgに追加
    for _ in range(M):
        x, y = map(lambda c: int(c) - 1, input().split())
        g[x].append(y)

    return N, M, g


def getlp(x, depth):
    global dp, g

    if depth >= MAX_DEPTH:
        return -1
    elif dp[x] != -1:
        return dp[x]
    elif len(g[x]) == 0:
        dp[x] = 0
        return dp[x]
    else:
        mxp = 0
        for y in g[x]:
            yp = getlp(y, depth + 1)
            if yp == -1:
                return -1
            elif yp > mxp:
                mxp = yp
        dp[x] = mxp + 1
        return dp[x]


N, M, g = get_inputs()
MAX_DEPTH = 800

dp = [-1] * N
nodes = list(range(N))
ans = 0

while len(nodes) > 0:
    tmp_nodes = []
    for x in range(N):
        if dp[x] == -1:
            t = getlp(x, 0)
            if t == -1:
                tmp_nodes.append(x)
            else:
                ans = max(ans, t)
        else:
            ans = max(ans, dp[x])

    nodes = list(tmp_nodes)

print(ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**5)

def get_inputs():
    N, M = map(int, input().split())
    
    # グラフgを初期化
    g = [[] for _ in range(N)]
    
    # 辺情報を読み込みgに追加
    for _ in range(M):
        x, y = map(lambda c: int(c) - 1, input().split())
        g[x].append(y)
    
    return N, M, g


def getlp(x):
    global dp, g
    
    if dp[x] != -1:
        return dp[x]
    elif len(g[x]) == 0:
        dp[x] = 0
        return dp[x]
    else:
        dp[x] = max([getlp(y) for y in g[x]]) + 1
        return dp[x]


N, M, g = get_inputs()

dp = [-1] * N
ans = 0
for x in range(N):
    ans = max(ans, getlp(x))

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

n=int(input())
a=list(map(int,input().split( )))
ans=1
for i in range(n):
    ans*=a[i]
if ans>10**18:
    ans=-1
print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split( )))
ans=1
for i in range(n):
    if a[i]==0:
        ans=0
        break
if ans==0:
    print(0)
else: 
    for i in range(n):
        ans*=a[i]
        if ans>10**18:
            ans=-1
            break
    print(ans)
### BUGGY CODE ###

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 998244353

N, S = MAP()
A = LIST()

dp = list2d(N+1, S+1, 0)
dp[0][0] = 1
for i, a in enumerate(A):
    for j in range(S+1):
        dp[i+1][j] += dp[i][j] * 2
        dp[i+1][j] %= MOD
        if j+a <= S:
            dp[i+1][j+a] += dp[i][j]
            dp[i+1][j+a] %= MOD
ans = dp[N][S]
print(ans)


### FIXED CODE ###

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 998244353

N, K = MAP()
A = LIST()

dp = list2d(N+1, K+1, 0)
dp[0][0] = 1
for i, a in enumerate(A):
    for j in range(K+1):
        dp[i+1][j] += dp[i][j] * 2
        dp[i+1][j] %= MOD
        if j+a <= K:
            dp[i+1][j+a] += dp[i][j]
            dp[i+1][j+a] %= MOD
ans = dp[N][K]
print(ans)
### BUGGY CODE ###

import sys


def main():
        n = sys.stdin.readline()

        astr = sys.stdin.readline()
        bstr = sys.stdin.readline()
        cstr = sys.stdin.readline()

        a = map(int, astr.strip().split(' '))
        b = map(int, bstr.strip().split(' '))
        c = map(int, cstr.strip().split(' '))

        a.sort()
        b.sort()
        c.sort()

        cnt = 0

        for ai in a:
                bt = b[binary(ai, b):]
                for bi in bt:
                        ct = c[binary(bi, c):]
                        cnt = cnt + len(ct)

        print(cnt)


def binary(x, li):
    upper = len(li)
    lower = -1
    index = (upper + lower) / 2


    while upper - lower > 1:
        if (x < li[index]):
            upper = index
        else:
            lower = index
        index = (upper + lower)/2
    
    return upper


main()

### FIXED CODE ###

import sys

import time


def main():
        n = sys.stdin.readline()

        astr = sys.stdin.readline()
        bstr = sys.stdin.readline()
        cstr = sys.stdin.readline()

        a = list(map(int, astr.strip().split(' ')))
        b = list(map(int, bstr.strip().split(' ')))
        c = list(map(int, cstr.strip().split(' ')))

        a.sort()
        b.sort()
        c.sort()

        cnt = 0

        bc = []
        sum = 0
        timesum = 0
        for bi in reversed(b):
                sum += len(c) - binary(bi,c)
                bc.append(sum)
        bc.reverse()

        cnt = 0
        for ai in a:
                bi = binary(ai, b)
                if(bi < len(bc)):
                    cnt += bc[bi]

        print(cnt)


def binary(x, li):
    upper = len(li)
    lower = -1
    index = int((upper + lower) / 2)

    while upper - lower > 1:
        if (x < li[index]):
            upper = index
        else:
            lower = index
        index = int((upper + lower)/2)
    
    return upper


main()
### BUGGY CODE ###

N,K=map(int,input().split())
s=1
lis=list(range(N+1))

def tousa(l,r):
    return((l+r)*(r-l+1)//2)


for i in range(K,N+1):
    s+=(tousa(lis[-i:][0], lis[-i:][-1])-tousa(lis[:i][0], lis[:i][-1])+1)
# print(s)
print(s%(10**9+7))

### FIXED CODE ###

N,K=map(int,input().split())
s=1

def tousa(l,r):
    return((l+r)*(r-l+1)//2)

for i in range(K,N+1):
    s+= (tousa(N-i+1, N) - tousa(0, i-1) + 1)
# print(s)
print(s%(10**9+7))
### BUGGY CODE ###

import sys
input=sys.stdin.readline

def main():
  h,w=map(int,input().split())
  a=[list(map(int,input().split())) for i in range(h)]
  b=[list(map(int,input().split())) for i in range(h)]
  
  c=[[0]*w for i in range(h)]
  for i in range(h):
    for j in range(w):
      c[i][j]=abs(a[i][j]-b[i][j])
  
  dp=[[[] for i in range(w)] for j in range(h)]
  dp[0][0].append(c[0][0])
  for i in range(h):
    for j in range(w):
      for k in dp[i-1][j]:
        dp[i][j].append(abs(k-c[i][j]))
        dp[i][j].append(k+c[i][j])
      for k in dp[i][j-1]:
        dp[i][j].append(abs(k-c[i][j]))
        dp[i][j].append(k+c[i][j])
      dp[i][j]=list(set(dp[i][j]))
  print(min(dp[h-1][w-1]))

if __name__=='__main__':
  main()

### FIXED CODE ###

import sys
input=sys.stdin.readline

def main():
  h,w=map(int,input().split())
  a=[list(map(int,input().split())) for i in range(h)]
  b=[list(map(int,input().split())) for i in range(h)]
  dp=[[[0]*(80*(h+w+1)+1) for i in range(w)] for j in range(h)]
  dp[0][0][abs(a[0][0]-b[0][0])]=1
  for i in range(h):
    for j in range(w):
      c=abs(a[i][j]-b[i][j])
      if i!=0 or j!=0:
        for k in range(80*(i+j+1)+1):
          dp[i][j][k]=dp[i-1][j][abs(k-c)]|dp[i-1][j][k+c]|dp[i][j-1][abs(k-c)]|dp[i][j-1][k+c]
  for i in range(80*(h+w+1)+1):
    if dp[h-1][w-1][i]==1:
      print(i)
      break

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

N = int(input())
A = [int(x) for x in input().split()]
for i in range(N):
    n = A.count(i+1)
    print(n)
    if i+1 in A:
        A.remove(i+1)

### FIXED CODE ###

N = int(input())
A = [int(x) for x in input().split()]
B = [0] * N
for i in range(N-1):
    B[(A[i]-1)] += 1

for j in range(N):
    print(B[j])
### BUGGY CODE ###

import numpy as np
import math
N, K = map(int, input().split())
A = list(map(int, input().split()))

def leng(n, f):
    return math.ceil(n / f) - 1

logs = np.array(A)
vleng = np.vectorize(leng)

#めぐる式二分探索
def is_ok(i):
    if sum(vleng(logs, i)) <= K:
        return True
    else:
        return False

def meguru_bisect(ng, ok):
    '''
    初期値のng,okを受け取り,is_okを満たす最小(最大)のokを返す
    まずis_okを定義すべし
    ng ok は  とり得る最小の値-1 とり得る最大の値+1
    最大最小が逆の場合はよしなにひっくり返す
    '''
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return ok

print(meguru_bisect(0, max(A) + 1))

### FIXED CODE ###

import numpy as np
import math
N, K = map(int, input().split())
A = list(map(int, input().split()))

#めぐる式二分探索
def is_ok(i):
    su = 0
    for a in A:
        su += (a-1) // i
    if su <= K:
        return True
    else:
        return False

def meguru_bisect(ng, ok):
    '''
    初期値のng,okを受け取り,is_okを満たす最小(最大)のokを返す
    まずis_okを定義すべし
    ng ok は  とり得る最小の値-1 とり得る最大の値+1
    最大最小が逆の場合はよしなにひっくり返す
    '''
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return ok

print(meguru_bisect(0, max(A) + 1))
### BUGGY CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
Q = []
for i in range(N):
  Q.append(max(A))
  A.remove(max(A))
for j in range(M):
  Q[0] //= 2
  for k in range(1, N-1):
    if Q[0] <= Q[k] and Q[0] >= Q[k+1]:
      Q.insert(k+1, Q[0])
      Q.remove(Q[0])
    if Q[0] < Q[N-1]:
      Q.append(Q[0])
      Q.remove(Q[0])
S = 0
for k in range(N):
  S += Q[k]
print(S)

### FIXED CODE ###

import heapq
pq = []

N, M = map(int, input().split())
A = list(map(int, input().split()))
for i in A:
  heapq.heappush(pq, -i)
for i in range(M):
  x = pq[0]
  heapq.heappop(pq)
  heapq.heappush(pq, -((-x)//2))
print(-sum(pq))
### BUGGY CODE ###

N,M = map(int,input().split())
gcd = M // N
gcd_tmp = 0
for gcd in range(gcd,0,-1):
 if M % gcd == 0:
  gcd_tmp = gcd
  break
 gcd = gcd - 1
print(gcd_tmp)

### FIXED CODE ###

def calc():
 N,M = map(int,input().split())
 for gcd in range(M // N,0,-1):
  if M % gcd == 0:
   break
 return(gcd)
print(calc())
### BUGGY CODE ###

# -*- coding: utf-8 -*-
N = int(input())
L = list(map(int,input().split()))
count = 0

L.sort(reverse = True)
for i in range(0,N-2):
    for j in range(i+1,N-1):
        for k in range(j+1,N):
            if L[k] >= L[i] +L[j]:
                break
            if L[i] < L[j] +L[k] and L[j] < L[k] + L[i]:
                count += 1
            else: 
                break
                
print(count)

### FIXED CODE ###

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

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

count = 0
L.sort()
for i in range(N-2):
    for j in range(i+1,N-1):
        k = bisect.bisect_left(L,L[i]+L[j])
        count += k - j - 1 
        
print(count)
### BUGGY CODE ###

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

for i in range(n):
	cnt = 0
	for h in range(n):
		if h % 2 == 0:
			cnt += a[h]
		else:
			cnt -= a[h]
	print(cnt,end=' ')
	a.append(a.pop(0))

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
x1 = sum([a[h] if h%2==0 else -a[h] for h in range(n)])
print(x1,end = ' ')

for i in range(n-1):
	if i == 0:
		b = a[i]*2 - x1
		print(b,end=' ')
	else:
		print(a[i]*2 - b,end=' ')
		b = a[i]*2 - b
### BUGGY CODE ###

S = input()
Q = int(input())

direction = 1

for i in range(Q):
    q = input()
    if q[0] == "1":
        direction *= (-1)
        #S = S[::-1]
    elif q[0] == "2":
        if direction > 0:
            if q[2] == "1":
                S = q[4] + S
            elif q[2] == "2":
                S = S + q[4]
        elif direction < 0:
            if q[2] == "1":
                S = S + q[4]
            elif q[2] == "2":
                S = q[4] + S 

if direction < 0:
    S = S[::-1]           

print(S)

### FIXED CODE ###

S = input()
Q = int(input())

head = ''
back = ''
direction = 1

for i in range(Q):
    q = list(map(str, input().split())) 
    if q[0] == "1":
        direction *= (-1)
        #S = S[::-1]
    else:
        if q[1] == "1":
            if direction == 1:
                head = head + q[2]
            else:
                back = back + q[2]
        else:
            if direction == 1:
                back = back + q[2]
            else:
                head = head + q[2]

if direction == 1:
    print(head[::-1]+S+back)
else:
    print(back[::-1]+S[::-1]+head)
### BUGGY CODE ###

MOD = 998244353
n, s = map(int, input().split())
A = map(int, input().split())
dp = [0]*(s+1)
dp[0] = 1
inv_2 = (MOD+1)//2
for a in A:
    for j in reversed(range(s+1)):
        if j-a < 0:
            continue
        dp[j] += dp[j-a]*inv_2
        dp[j] %= MOD

print(dp[-1]*pow(2, n, MOD) % MOD)


### FIXED CODE ###

n, s = map(int, input().split())
A = list(map(int, input().split()))
MOD = 998244353
W_MAX = s
dp = [0]*(W_MAX+1)
dp[0] = 1
inv_2 = pow(2, MOD-2, MOD)
for a in A:
    for j in reversed(range(W_MAX+1)):
        if W_MAX < j+a:
            continue
        dp[j+a] += dp[j]*inv_2
        dp[j+a] %= MOD

print(dp[-1]*pow(2, n, MOD) % MOD)
### BUGGY CODE ###

import sys
for i in sys.stdin:
    n = int(i)
    arr = [i for i in range(0,n+1)]
    for i in range(2, len(arr)):
        if arr[i] != 0:
            j = 2
            while i*j <= n:
                if arr[i*j] != 0:
                    arr[i*j] = 0
                j += 1
    primNum = 0
    for i in arr:   
        if i > 1:
            primNum += 1
    print(primNum)

### FIXED CODE ###

import sys
prime = [0]
isPrime = [1 for i in range(1000000)]
isPrime[0] = 0
isPrime[1] = 0
for i in sys.stdin:
    n = int(i)
    if prime[len(prime)-1] < n:
        for i in range(prime[len(prime)-1]+1,n+1):
            if isPrime[i] == 1:
                prime.append(i)
                for j in range(i*2, 1000000, i):
                    isPrime[j] = 0
    print(sum(isPrime[:n+1]))
### BUGGY CODE ###

n,m,q = map(int, input().split())
m_start = []
m_end = []
for i in range(m):
  s,e = map(int, input().split())
  m_start .append(s)
  m_end.append(e)
for i in range(q):
  s,e = map(int, input().split())
  cnt = 0
  for j in range(m):
    if m_start[j] < s : continue
    if m_end[j] <= e : cnt += 1
  else:
    print(cnt)

### FIXED CODE ###

n,m,q = map(int, input().split())
mmap = [ [ 0 for j in range(n+1) ] for i in range(n+1) ]
for i in range(m):
  s,e = map(int, input().split())
  mmap[s][e] += 1
for i in range(n+1):
  for j in range(1,n+1):
    mmap[i][j] = mmap[i][j] + mmap[i][j-1]
for j in range(n+1):
  for i in range(n-1,0,-1):
    mmap[i][j] = mmap[i][j] + mmap[i+1][j]
for i in range(q):
  s,e = map(int, input().split())
  print(mmap[s][e])
### BUGGY CODE ###

N = int(input())
L = list(map(int,input().split()))
cnt = 0
L.sort()
for i in range(N):
    for j in range(i+1,N):
        for k in range(j+1,N):
            if L[i] + L [j] > L[k]:
                cnt += 1
print(cnt)

### FIXED CODE ###

import bisect
n=int(input())
l = list(map(int,input().split()))
l.sort()
うんち = 0
for i in range(1,n):
    for j in range(i):
        p = l[i] + l[j]
        q = bisect.bisect_left(l,p)
        うんち += q-i-1
print(うんち)
### BUGGY CODE ###

def getinputdata():

    # 配列初期化
    array_result = []
    
    data = input()
    
    array_result.append(data.split(" "))

    flg = 1

    try:

        while flg:

            data = input()

            if(data != ""):
                
                array_result.append(data.split(" "))

            else:

                flg = 0
    finally:

        return array_result

arr_data = getinputdata()

n = int(arr_data[0][0])
arr=[int(x) for x in arr_data[1]]

m = int(arr_data[2][0])
arr_problem=[int(x) for x in arr_data[3]]

chkflg=True

for v in arr_problem:
    
    if v in arr:
        
        arr.pop(arr.index(v))
    else:
        
        chkflg=False
        break
        
        
print("YES" if chkflg else "NO")

### FIXED CODE ###

from collections import defaultdict
def getinputdata():

    # 配列初期化
    array_result = []
    
    data = input()
    
    array_result.append(data.split(" "))

    flg = 1

    try:

        while flg:

            data = input()

            if(data != ""):
                
                array_result.append(data.split(" "))

            else:

                flg = 0
    finally:

        return array_result

arr_data = getinputdata()

n = int(arr_data[0][0])
arr=[int(x) for x in arr_data[1]]

numbers = defaultdict(lambda: 0)
for v in arr:
    numbers[v] += 1
hash01=dict(numbers)

m = int(arr_data[2][0])
arr_problem=[int(x) for x in arr_data[3]]

numbers_problem = defaultdict(lambda: 0)
for v in arr_problem:
    numbers_problem[v] += 1
hash02=dict(numbers_problem)

chkflg=True

for k,v in hash02.items():
    
    if not k in hash01 or v>hash01[k]:
    
        chkflg=False
    
print("YES" if chkflg else "NO")
### BUGGY CODE ###

from fractions import gcd
import time
n = int(input())
a = list(map(int, input().split()))
t1 = time.time()
mod = 10**9+7
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)
g = 1
flag = 1
for i in range(n):
    g = a[i] * g // gcd(a[i], g)
    #g %= mod
    t2 = time.time()
    if t2 - t1 > 0.5:
        flag = 0
        break

if flag == 1:
    ans = 0
    for i in range(n):
        ans += g * modinv(a[i])
        ans %= mod
    print(ans)

else:
    ans = 0

    for i in range(n):
        g = 1
        for j in range(n):
            if i == j:
                continue
            else:
                g *= a[j]
                g %= mod
        ans += g
        ans %= mod
    print(ans)


### FIXED CODE ###

from fractions import gcd #直して
n = int(input())
a = list(map(int, input().split()))

mod = 10**9+7
l = 1
for i in range(n):
    l = a[i] // gcd(l, a[i]) * l
    

def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

d = 0
for i in range(n):
    d += modinv(a[i])

print((l*d) % mod)
### BUGGY CODE ###

# B Multiplication 2
N = int(input())
A = list(map(int, input().split()))
x = 1
for i in A:
    x = x * i

if x > 10 ** 18:
    print(-1)
else:
    print(x)

### FIXED CODE ###

# ABC169
# B Multiplication 2
N = int(input())
A = sorted(list(map(int, input().split())), reverse=True)
x = 1
for i in A:
    if A[-1] == 0:
        print(0)
        exit()
    else:
        x = x * i
        if x > 10 ** 18:
            print(-1)
            exit()
print(x)
### BUGGY CODE ###

import functools
n = int(input())
p = functools.reduce(lambda x,y: x * y, range(1, n+1)) % (10**9 + 7)
print(p)


### FIXED CODE ###

MOD = 10**9 + 7
n = int(input())

p = 1
for i in range(2, n + 1):
    p = p * i % MOD
print(p)
### BUGGY CODE ###

S=int(input())
X1=0
Y1=0

if S<=10**9:
    X2=0
    Y2=1
    X3=S
    Y3=0
elif S%10**9==0:
    X2=0
    Y2=S//10**9
    X3=10**9
    Y3=0
else:
    t=S%(10**9)
    A=10**9-t#x2 , y3
    v=(S+A)//10**9#x3=10**9 , y2=v
    K=A
    while A%2==0:
        A//=2
        if A<=10**9:
            X2=K//A
            Y3=A
        
    i=3
    while True:
        if A==1:
            X2=1
            Y3=1
            break
        
        if A%i==0:
            A//=i
            if A<=10**9:
                X2=K//A
                Y3=A
                break
            
        else:
            i+=2
        
    X3=10**9
    Y2=v
    
L=[X1,Y1,X2,Y2,X3,Y3]
print(" ".join([str(x) for x in L]))


### FIXED CODE ###

S=int(input())
X1=0
Y1=0
flag=True
if S<=10**9:
    X2=0
    Y2=1
    X3=S
    Y3=0
elif S%10**9==0:
    X2=0
    Y2=S//10**9
    X3=10**9
    Y3=0
else:
    t=S%(10**9)
    A=10**9-t#x2 , y3
    v=(S+A)//10**9#x3=10**9 , y2=v
    
    K=A
    if A<=10**9:
        X2=1
        Y3=A
        flag=False
        
    if flag:
        while A%2==0:
            A//=2
            if A<=10**9:
                X2=K//A
                Y3=A
            
        i=3
        while True:
            if A%i==0:
                A//=i
                if A<=10**9:
                    X2=K//A
                    Y3=A
                    break
                
            else:
                i+=2
    
    X3=10**9
    Y2=v
    
L=[X1,Y1,X2,Y2,X3,Y3]
print(" ".join([str(x) for x in L]))
### BUGGY CODE ###

N =int(input())
m = 0
for i in range(N):
    m += i

print(m)

### FIXED CODE ###

N =int(input())
print(int(N*(N-1)//2))
### BUGGY CODE ###

from sys import stdin
import numpy as np

N, M = [int(x) for x in stdin.readline().split()]
A = np.array([int(a) for a in stdin.readline().split()], dtype=np.int64)

B = (np.hstack([0, A]) % M).cumsum() % M

total = 0
for remainder in np.unique(B):
    count = (B == remainder).sum()
    total += count * (count - 1) // 2
print(total)


### FIXED CODE ###

from sys import stdin
from collections import Counter
import numpy as np

N, M = [int(x) for x in stdin.readline().split()]
A = np.array([int(a) for a in stdin.readline().split()], dtype=np.int64)

cum_remainders = (np.hstack([0, A]) % M).cumsum() % M

remainder_counts = Counter(cum_remainders)
combinations = 0
for count in remainder_counts.values():
    combinations += count * (count - 1) // 2
print(combinations)
### BUGGY CODE ###

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

points    = 0
penalties = 0

# 答えのリストの作成
input_lists = []
question_numbers = []
for i in range(m):
  qn, ans = input().split()
  input_list = [int(qn), ans]
  question_numbers.append(int(qn))
  input_lists.append(input_list)

# 問題番号の重複排除
question_numbers = list(set(question_numbers))

# カウント
for qn in question_numbers:
  # print(qn)
  # 問題番号毎に処理
  answers = []
  for input_list in input_lists:
    if(qn == input_list[0]):
      answers.append(input_list[1])
  # print(answers)
  # 配列にACが含まれていればpointsをインクリメント
  if('AC' in answers):
    points = points + 1
  	# ペナルティのカウント
    for answer in answers:
      if(answer == 'WA'):
        penalties = penalties + 1
      else:
        break

print(points, penalties)

### FIXED CODE ###

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

points    = [0] * n
penalty   = [0] * n
penalties = 0

for i in range(m):
  q, ans = input().split()
  q = int(q) - 1
  # まだ正解が出ていない場合
  if(points[q] == 0):
    # 正解の場合
    if(ans == 'AC'):
      points[q] = 1
      penalties += penalty[q]
    # 不正解の場合
    else:
      penalty[q] += 1

print('{} {}'.format(sum(points), penalties))