Harryxun/stf_run huggingface dataset:
# coding: utf-8
import os
import time
import re
import math


def main():
    global N,M,A,mod,memo
    N,M=map(int,input().split())
    A=[int(input()) for  a in range(M)] #a (1段~N-1段)
    start=time.time();#
    memo=[-1]*(N+1)
    
    mod=1000000007
    print(dp(0))
    #print("{}ms".format(math.floor(time.time()*1000-start*1000)))#

def dp(index):
    if(index>N):return 0
    if(index==N):memo[index]=1
    if(A.count(index)>0):memo[index]=0
    if memo[index]==-1:
        memo[index]=(dp(index+1)%mod+dp(index+2)%mod)%mod
    return memo[index]

main()


### FIXED CODE ###

# coding: utf-8
import os
import time
import re
import math


def main():
    N,M=map(int,input().split())
    A=[int(input()) for  a in range(M)] #a (1段~N-1段)
    start=time.time();#
    memo=[0]*(N+1)
    memo[0]=1
    ban=[False]*(N+1)
    for a in A:
        ban[a]=True
    mod=1000000007
    for a in range(1,N+1):
        if ban[a]:
            memo[a]=0
        else:
            if a>1:
                memo[a]=(memo[a-1]+memo[a-2])%mod
            else:
                memo[a]=1



    print(memo[-1]%mod)
    #print("{}ms".format(math.floor(time.time()*1000-start*1000)))#


main()
a = int(input())
b = int(input())
print(2*a+b,a*b)


### FIXED CODE ###

a,b = map(int,input().split())
print(a*b,2*(a+b))
n, k = map(int, input().split())
C = [[1], [1,1]]
for i in range(2, n+10):
  C.append([1] + [C[i-1][j-1] + C[i-1][j] for j in range(1, i)] + [1])
for i in range(1, k+1):
  print(C[n-k+1][i] * C[k-1][i-1])
  


### FIXED CODE ###

n, k = map(int, input().split())
mod = 10**9+7
C = [[1], [1,1]]
for i in range(2, n+10):
  C.append([1] + [(C[i-1][j-1] + C[i-1][j])%mod for j in range(1, i)] + [1])
for i in range(1, k+1):
  if n-k+1 < i or k < i:
    print(0)
  else:
    print((C[n-k+1][i] * C[k-1][i-1])%mod)
a=int(input())
b=list(map(int, input().split()))

if len(seq) != len(set(seq)):
    print('NO')
else:
    print('YES')

### FIXED CODE ###

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

if len(b) != len(set(b)):
    print('NO')
else:
    print('YES')
a = int(input())
b = int(input())
c = int(input())
x = int(input())

#%%

n = 0
for fiveHundred in a:
    for hundred in b:
        for fifty in c:
            if x == 500*fiveHundred + 100*hundred + 50*fifty:
                n +=1

print(n)

### FIXED CODE ###

a = int(input())
b = int(input())
c = int(input())
x = int(input())

n = 0
for fiveHundred in range(a+1):
    for hundred in range(b+1):
        for fifty in range(c+1):
            if x == 500*fiveHundred + 100*hundred + 50*fifty:
                n +=1

print(n)
import fractions
N = int(input())
A = list(map(int,input().split()))
mod = 10 ** 9 + 7
def mul(a, b):
    return ((a % mod) * (b % mod)) % mod
def div(a, b):
    return mul(a, pow(b,mod-2,mod))
lcm = A[0] * A[1] // fractions.gcd(A[0],A[1])
for i in range(2,N):
    lcm = div((lcm * A[i]),fractions.gcd(lcm,A[i]))
ans = 0
for i in range(N):
    b = div(lcm,A[i])
    ans += b 
    ans %= mod 
    #print(ans)
#print(lcm)
print(ans)


### FIXED CODE ###

import fractions
N = int(input())
A = list(map(int,input().split()))
mod = 10 ** 9 + 7
def mul(a, b):
    return ((a % mod) * (b % mod)) % mod
def div(a, b):
    return mul(a, pow(b,mod-2,mod))
if N == 1:
    ans = 1
else:
    lcm = A[0] * A[1] // fractions.gcd(A[0],A[1])
    for i in range(2,N):
        #lcm = div((lcm * A[i]),fractions.gcd(lcm,A[i]))
        lcm = lcm * A[i] // fractions.gcd(lcm,A[i])
    ans = 0
    for i in range(N):
        b = div(lcm,A[i])
        ans += b 
        ans %= mod 
    #print(ans)
    #print(lcm)
print(ans)
N,A,B=map(input().split())
if A-B%2==0:
  print("Alice")
else:
  print("Borys")

### FIXED CODE ###

N,A,B=map(int,input().split())
if (A-B)%2==0:
  print("Alice")
else:
  print("Borys")
N, M = map(int,input().split())
A = list(map(int,input().split()))
if N == 1:
    while A[0] > 0:
        A[0] = A[0]//2
    print(0)
    sys.exit()

list.sort(A,reverse = True)
for i in range(M):
    while A[0] >= A[1]:
        A[0] = A[0]//2
    for i in range(0,M-1):
        if A[i] < A[i+1]:
            A[i] , A[i+1] = A[i+1] , A[i]

print(sum(A))

### FIXED CODE ###

import sys
import os
import math
import heapq

N, M = map(int,input().split())
A = list(map(int,input().split()))
#大きいものから取り出したいので-1倍してqueueに入れる

Q = []
for a in A:
    heapq.heappush(Q,-a)

for i in range(M):
    first = -heapq.heappop(Q)
    first = first//2
    heapq.heappush(Q,-first)

print(-sum(Q))
s=input()
l=len(s)
a=[0 for i in range(l)]

for i in range(l):
  a[i]=int(s[i])
  
ichi=0
zero=0

for i in range(l):
  if a[i]==1:
    ichi+=1
  else:
    zero+=1
    
print(2*min(ichi.zero))

### FIXED CODE ###

s=input()
l=len(s)
a=[0 for i in range(l)]

for i in range(l):
  a[i]=int(s[i])
  
ichi=0
zero=0

for i in range(l):
  if a[i]==1:
    ichi+=1
  else:
    zero+=1
    
print(2*min(ichi,zero))
N, M = map(int, input().split())

broken = []
for _ in range(M):
  broken.append(int(input()))

mod = 10 ** 9 + 7
f2, f1 = 0, 1
for i in range(1, N + 1):
  if i in broken:
    if i - 1 in broken:
      print(0)
      exit()
    f2 = f1
    f1 = 0
    continue
  f = f2 + f1
  f2 = f1
  f1 = f
print(f % mod)N, M = map(int, input().split())

broken = []
for _ in range(M):
  broken.append(int(input()))

mod = 10 ** 9 + 7
f2, f1 = 0, 1
for i in range(1, N + 1):
  if i in broken:
    if i - 1 in broken:
      print(0)
      exit()
    f2 = f1
    f1 = 0
    continue
  f = f2 + f1
  f2 = f1
  f1 = f
print(f % mod)

### FIXED CODE ###

import sys
 
n, m = list(map(int, input().split()))
if m > 0:
    aaa = set(map(int, sys.stdin))
else:
    aaa = set()
dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1 if 1 not in aaa else 0
MOD = 10 ** 9 + 7
 
for i in range(2, n + 1):
    if i in aaa:
        continue
    dp[i] = (dp[i - 2] + dp[i - 1]) % MOD
print(dp[n])
# -*- coding: utf-8 -*-
from sys import stdin

# import numpy as np
from itertools import accumulate
from bisect import bisect_right

# import sys
# sys.setrecursionlimit(10**4)


def _li():
    return list(map(int, stdin.readline().split()))


def _li_():
    return list(map(lambda x: int(x) - 1, stdin.readline().split()))


def _lf():
    return list(map(float, stdin.readline().split()))


def _ls():
    return stdin.readline().split()


def _i():
    return int(stdin.readline())


def _f():
    return float(stdin.readline())


def _s():
    return stdin.readline()[:-1]


def search(cum1, cum2, iter_max):
    ans = 0
    for i in range(iter_max):
        if cum1[i] > K:
            break
        cand = bisect_right(cum2, K - cum1[i])
        ans = max(i + 1 + cand, ans)
    return ans


N, M, K = _li()
A_list = _li()
B_list = _li()

cum_a = list(accumulate(A_list))
cum_b = list(accumulate(B_list))

ans = 0
if cum_a[0] < cum_b[0]:
    print(search(cum_a, cum_b, N))
else:
    print(search(cum_b, cum_a, N))


### FIXED CODE ###

# -*- coding: utf-8 -*-
from sys import stdin

# import numpy as np
from itertools import accumulate
from bisect import bisect_right

# import sys
# sys.setrecursionlimit(10**4)


def _li():
    return list(map(int, stdin.readline().split()))


def _li_():
    return list(map(lambda x: int(x) - 1, stdin.readline().split()))


def _lf():
    return list(map(float, stdin.readline().split()))


def _ls():
    return stdin.readline().split()


def _i():
    return int(stdin.readline())


def _f():
    return float(stdin.readline())


def _s():
    return stdin.readline()[:-1]


def search(cum1, cum2, iter_max, limit):
    ans = 0
    for (i,) in range(iter_max):
        if cum1[i] > limit:
            cur = 0
        else:
            cur = i
        cand = bisect_right(cum2, limit - cum1[i])
        ans = max(cur + cand, ans)
    return ans


N, M, K = _li()
A_list = _li()
B_list = _li()

cum_a = [0] + list(accumulate(A_list))
cum_b = list(accumulate(B_list))

ans = 0
for i, a in enumerate(cum_a):
    if a > K:
        cur = 0
    else:
        cur = i
    cand = bisect_right(cum_b, K - a)
    ans = max(cur + cand, ans)

print(ans)
h,w=map(int,input().split())
if h == 1 or w == 1:
    print(1)
else:
    m = math.ceil(w/2) * math.ceil(h/2) + math.floor(w/2) * math.floor(h/2)
    print(m)

### FIXED CODE ###

from math import floor,ceil
h,w=map(int,input().split())
if h == 1 or w == 1:
    print(1)
else:
    m =ceil(w/2) * ceil(h/2) + floor(w/2) * floor(h/2)
    print(m)
N,K = map(int,input().split())
print(int(K * ((K-1) ** (N-1))))

### FIXED CODE ###

mylist = input().split()
print(len(set(mylist)))
n=int(input())
li=list(map(int,input().split()))

ans=[]
for i in range(n-1,n//2-1,-1):
  if li[i]==1:
    ans.append(i+1)

for i in range(n//2,0,-1):
  count=0
  for j in ans:
    if j%i==0:
      count+=1
  if count%2==0:
    ans.append(i)
ans.reverse()
print(len(ans))
L=[str(a) for a in ans]
L=" ".join(L)
if len(L)!=0:
  print(L)

### FIXED CODE ###

n=int(input())

n=n*n*3
print(n)
import fractions

input()
A=set([int(i) for i in input().split()])

ans=1
if len(A)==1:
    ans=10**9
elif len(A)==2:
    ans=max(A)
else:  
    for a in A:
        A2=A-{a}
        print(A)
        ans=max(ans,fractions.gcd(*A2))

print(ans)

### FIXED CODE ###

import sys

sys.setrecursionlimit(1000000)

import fractions
from functools import reduce

N=int(input())
A=[int(i) for i in input().split()]

def mygcd(a,b):
    if a==0:
        return b
    elif b==0:
        return a
    else:
        return fractions.gcd(a,b)

L=[0]*N
for i in range(1,N):
    L[i]=mygcd(L[i-1],A[i-1])

R=[0]*N
for i in range(N-2,-1,-1):
    R[i]=mygcd(R[i+1],A[i+1])

ans=1
for i in range(N):
    c=mygcd(L[i],R[i])
    ans=max(ans,c)

print(ans)
import fractions

n = int(input())
a = list(map(int, input().split( )))
ans = 0
for i in range(n):
    ans = math.gcd(ans,a[i])
print(ans)

### FIXED CODE ###

import fractions

n = int(input())
a = list(map(int, input().split( )))
ans = 0
for i in range(n):
    ans = fractions.gcd(ans,a[i])
print(ans)
n = int(input())
m = list(map(int,input().split()))
m.sort()
for i in range(n):
  if m[i] == m[i+1]:
    print('NO')
    exit()
    
print('YES')

### FIXED CODE ###

n = int(input())
m = list(map(int,input().split()))
m.sort()
for i in range(n-1):
  if m[i] == m[i+1]:
    print('NO')
    exit()
    
print('YES')
import numpy as np
ans=0
D=int(input())
C=np.array(list(map(int,input().split())))
last_day=np.array([-1 for _ in range(26)])
score=np.array([list(map(int,input().split())) for _ in range(D)])
 
for day in range(D):
    today_point=C*(day-last_day)
    S_today=sum(today_point)
    for k in range(26):
        today_point[k]=score[day][k]-S_today+today_point[k]
 
    if day!=D-1:
        max_score=-1*float("inf")
        for k in range(26):
            nday_point=C*((day+1)-last_day)
            S_nday=sum(nday_point)-C[k]*(day-last_day[k])
            
            for i in range(26):
                if k!=i:
                    nday_point[i]=score[day+1][i]-S_nday+nday_point[i]
                else:
                    nday_point[i]=score[day+1][i]-S_nday+C[i]
 
                if today_point[k]+nday_point[i]>max_score:
                    max_score=today_point[k]+nday_point[i]
                    idx=k
    else:
        idx=np.argmax(today_point)
 
    last_day[idx]=day
    output[day]=idx+1
print(*output)

### FIXED CODE ###

import numpy as np
ans=0
D=int(input())
C=np.array(list(map(int,input().split())))
last_day=np.array([0 for _ in range(26)])

for day in range(1,D+1):
    score=np.array(list(map(int,input().split())))
    tmp=C*(last_day-day)
    #今回行うコンテストで得られる
    idx=np.argmax(tmp+score)
    # ans=ans+score[idx]+np.sum(tmp)+abs(tmp[idx])
    last_day[idx]=day
    print(idx+1)
N,T=map(int,input().split())
list=[input() for _ in range(N)]

list1=[]
for i in range(N):
    X,Y=map(int,list[i].split(" "))
    if Y <= T:
        list1.append(X)
print(min(list1))

### FIXED CODE ###

N,T=map(int,input().split())
list=[input() for _ in range(N)]

list1=[]
for i in range(N):
    X,Y=map(int,list[i].split(" "))
    if Y <= T:
        list1.append(X)
print(min(list1) if list1 != [] else "TLE")
a,op,b = map(str, input(),split())

if op == "-":
    print(int(a) - int(b))
else:
    print(int(a) + int(b))

### FIXED CODE ###

a,op,b = map(str, input().split())
if op == "+":
    print(int(a) + int(b))
else:
    print(int(a) - int(b))
N, K = map(int, input().split())
A = list(map(int, input().split()))

if N == 1:
    if A[0] == K:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")
    exit()

if K > max(A):
    print("IMPOSSIBLE")
    exit()

A = list(set(A))
N = len(A)
A.sort()

min_diff = min([A[i] - A[i-1] for i in range(1,N)])

for i in range(N):
    if abs(A[i]-K) % min_diff == 0:
        print("POSSIBLE")
        break
else:
    print("IMPOSSIBLE")

### FIXED CODE ###

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

A = list(set(A))
N = len(A)
A.sort()

if K > max(A):
    print("IMPOSSIBLE")
    exit()

if N == 1:
    if A[0] == K:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")
    exit()

min_diff = min([A[i] - A[i-1] for i in range(1,N)])

for i in range(N):
    if abs(A[i]-K) % min_diff == 0:
        print("POSSIBLE")
        break
else:
    print("IMPOSSIBLE")
# -*- coding: utf-8 -*-
# 個数の入力
N = input()
# スペース区切りの色の入力
S = raw_input().split()
# 出力
if 'Y' in S:
	print('Four')
else:
	print('Three')

### FIXED CODE ###

# -*- coding: utf-8 -*-
# 個数の入力
N = input()
# スペース区切りの色の入力
S = input().split()
# 出力
if "Y" in S:
	print('Four')
else:
	print('Three')
price, hate = input().split()
no_num = set([x for x in input().split()])
ok_num = sorted(list({'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'} - no_num))

result = []
f = True
exe = True
for i in price:
    f = True
    for j in ok_num:
        if i <= j:
            result.append(j)
            f = False
            break
    if f and exe:
        exe = False
        result[-1] = str(int(result[-1]) + 1)
        for i in ok_num:
            if result[-1] < i:
                result[-1] = i
                break
        result.append(ok_num[-1])

print(''.join(result))


### FIXED CODE ###

kingaku, n = input().split()
no_num = input().split()
result = []
ok_num = []
kuriage_num = [-1, 0]

def kuriage(l):
    for i in ok_num:
        if result[l] < i:
            kuriage_num = [l, i]
            return
    if l <= 0:
        return
    return kuriage(l-1)

#使える数字のリストを作成
for i in range(10):
    if not str(i) in no_num:
        ok_num.append(str(i))

set_flg = False
for i in kingaku:
    set_flg = True
    for j in ok_num:
        if i == j:
            set_flg = False
            result.append(j)
            break
        elif i < j:
            result.append(j)
            print("".join(result).ljust(len(kingaku), ok_num[0]))
            exit()
            break
    
    if set_flg:
        n = 0
        if ok_num[0] == '0':
            n = 1
        print(ok_num[n].ljust(len(kingaku)+1, ok_num[0]))
        exit()

print(''.join(result))
def editarr(x,y,arr):
  if abs(x)>=abs(y):
    for i in range(len(arr)):
      arr[i][0],arr[i][1]=arr[i][1],arr[i][0]
  if x<0:
    for i in range(len(arr)):
      arr[i][0]*=-1
  if y<0:
    for i in range(len(arr)):
      arr[i][1]*=-1

k=int(input())
x,y=map(int,input().split())
ans=[]
tx=abs(x)
ty=abs(y)
if tx>=ty:
  tx,ty=ty,tx
if k%2==0 and (tx+ty)%2!=0:
  print(-1)
else:
  if tx+ty<k:
    if (tx+ty)%2==0:
      m=(ty-tx)//2
      ans.append([k-m,m])
    else:
      td=k-(tx+ty)
      ans.append([tx,ty+td])
      ans.append([tx+(k-td//2),ty+td//2])
    ans.append([tx,ty])
  elif ty+tx%k<2*k:
  else:
    ans.append([0,0])
    for _ in range(x//k):
      ans.append([ans[-1][0]+k,0])
    if ans[-1][0]!=tx:
      ans.append([tx,k-ans[-1][0]])
    if (ty-ans[-1][1])%k==0:
      flag=True
    else:
      flag=False
    for _ in range((ty-ans[-1][1])//k):
      if flag==False and (ty-ans[-1][1])%2==0 and (ty-ans[-1][1])<=2*k:
        break
      ans.append([tx,ans[-1][1]+k])
    if ans[-1][1]!=ty:
      td=(ty-ans[-1][1])
      ans.append([tx+(k-td//2),ty+td//2])
      ans.append([tx,ty])
    ans.pop(0)
  editarr(x,y,ans)
  print(len(ans))
  for a,b in ans:
    print(a,b)

### FIXED CODE ###

def editarr(x,y,arr):
  if abs(x)>=abs(y):
    for i in range(len(arr)):
      arr[i][0],arr[i][1]=arr[i][1],arr[i][0]
  if x<0:
    for i in range(len(arr)):
      arr[i][0]*=-1
  if y<0:
    for i in range(len(arr)):
      arr[i][1]*=-1

k=int(input())
x,y=map(int,input().split())
ans=[]
tx=abs(x)
ty=abs(y)
if tx>=ty:
  tx,ty=ty,tx
if k%2==0 and (tx+ty)%2!=0:
  print(-1)
else:
  if tx+ty<k:
    if (tx+ty)%2==0:
      m=(ty-tx)//2
      ans.append([k-m,m])
    else:
      td=k-(tx+ty)
      ans.append([tx,ty+td])
      ans.append([tx+(k-td//2),ty+td//2])
    ans.append([tx,ty])
    n=len(ans)
  elif ty-(k-tx%k)<k and (ty-(k-tx%k))%2!=0:
    if tx<k and ty<k:
      if (2*k-(tx+ty))%2==0:
        td=2*k-(tx+ty)
        ans.append([tx+td//2,k-(tx+td//2)])
        ans.append([tx,ty])
      else:
        ans.append([tx,k-tx])
        td=ty-(k-tx)
        ans.append([tx+(k-td//2),ans[-1][1]+td//2])
        ans.append([tx,ty])
      n=len(ans)
    else:
      if tx+ty<2*k:
        if (2*k-(tx+ty))%2==0:
          td=2*k-(tx+ty)
          ans.append([tx+td//2,k-(tx+td//2)])
          ans.append([tx,ty])
        else:
          ans.append([tx,k-tx])
          td=ty-(k-tx)
          ans.append([tx+(k-td//2),ans[-1][1]+td//2])
          ans.append([tx,ty])
        n=len(ans)
      else:
        ans.append([0,0])  
  else:
    ans.append([0,0])
    for i in range(tx//k):
      ans.append([ans[-1][0]+k,0])
    if ans[-1][0]!=tx:
      ans.append([tx,k-abs(tx-ans[-1][0])])
    td=ty-ans[-1][1]
    if td%k==0:
      flag=True
    else:
      flag=False
    for i in range(td//k):
      if flag==False and (ty-ans[-1][1])%2==0 and (ty-ans[-1][1])<=2*k:
          break
      ans.append([tx,ans[-1][1]+k])
    if ans[-1][1]!=ty:
      td=ty-ans[-1][1]
      ans.append([tx+(k-td//2),ans[-1][1]+td//2])
      ans.append([tx,ty])
    ans.pop(0)
    n=len(ans)
  editarr(x,y,ans)
  print(n)
  for a,b in ans:
    print(a,b)
s = input().strip()
x,y = map(int,input().split())
AX = []
AY = []
flag = 0
cnt = 0
for i in range(len(s)):
    if s[i]=="F":
        cnt += 1
    else:
        if flag==0:
            AX.append(cnt)
            cnt = 0
            flag = 1
        else:
            AY.append(cnt)
            cnt = 0
            flag = 0
if cnt>0 and flag==0:
    AX.append(cnt)
if cnt>0 and flag==1:
    AY.append(cnt)
Nx = sum(AX)
dpX = [[0 for _ in range(2*Nx+1)] for _ in range(len(AX)+1)]
if s[0]=="F":
    dpX[1][Nx+AX[0]] = 1
    for i in range(1,len(AX)):
        for j in range(2*Nx+1):
            if 0<=j+AX[i]<=2*Nx:
                dpX[i+1][j+AX[i]] = dpX[i+1][j+AX[i]] or dpX[i][j]
            if 0<=j-AX[i]<=2*Nx:
                dpX[i+1][j-AX[i]] = dpX[i+1][j-AX[i]] or dpX[i][j]
else:
    dpX[0][Nx] = 1
    for i in range(len(AX)):
        for j in range(2*Nx+1):
            if 0<=j+AX[i]<=2*Nx:
                dpX[i+1][j+AX[i]] = dpX[i+1][j+AX[i]] or dpX[i][j]
            if 0<=j-AX[i]<=2*Nx:
                dpX[i+1][j-AX[i]] = dpX[i+1][j-AX[i]] or dpX[i][j]
Ny = sum(AY)
dpY = [[0 for _ in range(2*Ny+1)] for _ in range(len(AY)+1)]
dpY[0][Ny] = 1
for i in range(len(AY)):
    for j in range(2*Ny+1):
        if 0<=j+AY[i]<=2*Ny:
            dpY[i+1][j+AY[i]] = dpY[i+1][j+AY[i]] or dpY[i][j]
        if 0<=j-AY[i]<=2*Ny:
            dpY[i+1][j-AY[i]] = dpY[i+1][j-AY[i]] or dpY[i][j]
if dpX[len(AX)][Nx+x]==1 and dpY[len(AY)][Ny+y]==1:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

s = input().strip()
x,y = map(int,input().split())
C = {}
cur = 0
cnt = 0
for i in range(len(s)):
    if s[i]=="F":
        cnt += 1
    else:
        C[cur] = cnt
        cur += 1
        cnt = 0
C[cur] = cnt
AX = []
AY = []
for a in C:
    if a>0 and a%2==0 and C[a]>0:
        AX.append(C[a])
    elif a%2==1 and C[a]>0:
        AY.append(C[a])
cntx = sum(AX)
dpx = [[0 for _ in range(2*cntx+1)] for _ in range(len(AX)+1)]
dpx[0][cntx] = 1
if cntx>0:
    dpx[1][cntx-AX[0]] = 1
    dpx[1][cntx+AX[0]] = 1
    for i in range(2,len(AX)+1):
        for j in range(-cntx,cntx+1):
            if -cntx<=j-AX[i-1]:
                dpx[i][j+cntx] = dpx[i-1][j-AX[i-1]+cntx]
                if j+AX[i-1]<=cntx:
                    dpx[i][j+cntx] = max(dpx[i][j+cntx],dpx[i-1][j+AX[i-1]+cntx])
            elif j+AX[i-1]<=cntx:
                dpx[i][j+cntx] = dpx[i-1][j+AX[i-1]+cntx]
cnty = sum(AY)
dpy = [[0 for _ in range(2*cnty+1)] for _ in range(len(AY)+1)]
dpy[0][cnty] = 1
if cnty>0:
    dpy[1][cnty-AY[0]] = 1
    dpy[1][cnty+AY[0]] = 1
    for i in range(2,len(AY)+1):
        for j in range(-cnty,cnty+1):
            if -cnty<=j-AY[i-1]:
                dpy[i][j+cnty] = dpy[i-1][j-AY[i-1]+cnty]
                if j+AY[i-1]<=cnty:
                    dpy[i][j+cnty] = max(dpy[i][j+cnty],dpy[i-1][j+AY[i-1]+cnty])
            elif j+AY[i-1]<=cnty:
                dpy[i][j+cnty] = dpy[i-1][j+AY[i-1]+cnty]
if C[0]-cntx<=x<=C[0]+cntx and dpx[len(AX)][x-C[0]+cntx]==1 and -cnty<=y<=cnty and dpy[len(AY)][y+cnty]==1:
    print("Yes")
else:
    print("No")
N, M = list(map(int, raw_input().split()))
K = []

array = []
for i in xrange(M): array.append(0)
for i in xrange(N):
    inputs = list(map(int, raw_input().split()))
    K = inputs[0]
    for j in xrange(K):
        array[inputs[j+1]] += 1

count = 0
for i in xrange(M):
    if array[i] == N: count += 1

print str(count)

### FIXED CODE ###

N, M = list(map(int, raw_input().split()))
K = []

array = []
for i in xrange(M): array.append(0)
for i in xrange(N):
    inputs = list(map(int, raw_input().split()))
    K = inputs[0]
    for j in xrange(K):
        array[inputs[j+1]-1] += 1

count = 0
for i in xrange(M):
    if array[i] == N: count += 1

print str(count)
n=int(input())
s={}
for i in range(n):
  tmp=list(input().strip()).sort()
  tmp="".join(tmp)
  s[tmp]=s.get(tmp,0)+1
  
ans=0
for key in s.keys():
  v=s[key]
  if v<2:
    continue
  cmb=v*(v-1)
  cmb=cmb//2
  ans+=cmb
print(ans)

### FIXED CODE ###

n=int(input())
s={}
for i in range(n):
  tmp=list(input().strip())
  tmp.sort()
  tmp="".join(tmp)
  s[tmp]=s.get(tmp,0)+1
  
ans=0
for key in s.keys():
  v=s[key]
  if v<2:
    continue
  cmb=v*(v-1)
  cmb=cmb//2
  ans+=cmb
print(ans)
#include<algorithm>
#include <iostream>
#include<vector>
#include<string>
#include <iomanip>
#include <queue> 
using namespace std;

int main(){
    int n,Q;
    cin>>n>>Q;

    vector<vector<int>> adj(n+1);

    for(int i=1;i<n;i++){
        int p,c;
        cin>>p>>c;
        adj[p].push_back(c);
    }

    vector<long long> cost(n+1,0);

    for(int i=0;i<Q;i++){
        int v,c;
        cin>>v>>c;
        cost[v] += c;
    }

    queue <int> q;

    int a = 0;
    for(int i=0;i<adj.size();i++)
        if(adj[i].size()>0){
            a=i;
            break;
        }
    q.push(a);
    // vector<bool> vis(n+1,0);
    // vis[a] = 1;
    while(!q.empty()){
        int nc = q.size();
        
        while(nc>0){
            int pa = q.front();
            q.pop();
            nc--;
            long long pc = cost[pa];
            for(int i=0;i<adj[pa].size();i++){
                
                    // vis[adj[pa][i]]==1;
                    q.push(adj[pa][i]);
                    cost[adj[pa][i]] += pc;
                
            }
        }
    }

    for(int i=1;i<n+1;i++)
        cout<<cost[i]<<" ";
    cout<<endl;
}

### FIXED CODE ###

import collections

n,q=map(int,input().split())
cnt=[0]*(n+1)
g=[[] for _ in range(n+1)]
for _ in range(n-1): #木グラフの隣接リストを作成
 a,b=map(int,input().split())
 g[a].append(b)
 g[b].append(a)
for _ in range(q): #各頂点についてcount[v]を計算
 v,val=map(int,input().split())
 cnt[v]+=val
q=collections.deque()
q.append(1) #DFSのスタックによる実装、まずスタックに始点1を積む
checked=[0]*(n+1) #各頂点を見たかどうかのフラグを持っておく
while q:
 v=q.pop()
 checked[v]=1 #頂点を見たかどうかのフラグを更新する
 for u in g[v]:
   if checked[u]==1: #vの子ノードuについて、まだ見ていない頂点であればcount[u]をcount[u]+=count[v]として更新する
     continue
   cnt[u]+=cnt[v]
   q.append(u) #スタックに子ノードuを積む
print(*cnt[1:]) #各頂点のcountが答えとなる
ans = [105,135,165,189,195]
n = input()
if n < 105:
  print(0)
elif n < 135:
  print(1)
elif n < 165:
  print(2)
elif n < 189:
  print(3)
elif n < 195:
  print(4)
else:
  print(5)

### FIXED CODE ###

ans = [105,135,165,189]
n = int(input())
if n < 105:
  print(0)
elif n < 135:
  print(1)
elif n < 165:
  print(2)
elif n < 189:
  print(3)
elif n < 195:
  print(4)
else:
  print(5)