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

import sys
input = sys.stdin.readline

def resolve():
  N = int(input())
  X = input()

  if N == 1:
    if X.count("1"):
      print(0)
    else:
      print(1)
    return True

  base_1_count = X.count("1")
  if base_1_count == 0:
    for _ in range(N):
      print(1)
    return True

  X_int = int(X, 2)
  X_int_p = X_int%(base_1_count + 1)

  # RE 対策
  if base_1_count == 1:
    for i in range(N):
      if X[i] == "1":
        print(0)
      else:
        if i == N - 1:
          Xi = X_int_p + 1
        else:
          Xi = X_int_p
        count = 1
        while Xi != 0:
          Xi %= bin(Xi).count("1")
          count += 1
        print(count)
    return True

  X_int_m = X_int%(base_1_count - 1)
  for i in range(N):
    # 初期値計算を高速にやる
    if X[i] == "1":
      temp_1_count = base_1_count-1
      pow_2 = 2**(N-i-1)%(base_1_count-1)
      if X_int_m <= pow_2:
        Xi = X_int_m - pow_2 + base_1_count-1
      else:
        Xi = X_int_m - pow_2
    else:
      temp_1_count = base_1_count+1
      Xi = X_int_p + 2**(N-i-1)%(base_1_count+1)
      while Xi >= base_1_count+1:
        Xi %= base_1_count+1

    # print("1_c={0}".format(temp_1_count))
    if temp_1_count == Xi:
      print(1)
      continue

    count = 1
    while Xi != 0:
      num_of_1 = bin(Xi).count("1")
      Xi %= num_of_1
      count += 1
    print(count)

if __name__ == "__main__":
    resolve()

### FIXED CODE ###

def resolve():
  N = int(input())
  X = input()

  if N == 1:
    if X.count("1"):
      print(0)
    else:
      print(1)
    return True

  base_1_count = X.count("1")
  if base_1_count == 0:
    for _ in range(N):
      print(1)
    return True

  X_int = int(X, 2)
  X_int_p = X_int%(base_1_count + 1)

  # RE 対策
  if base_1_count == 1:
    for i in range(N):
      if X[i] == "1":
        print(0)
      else:
        if i == N - 1:
          Xi = X_int_p + 1
        else:
          Xi = X_int_p
        count = 1
        while Xi != 0:
          Xi %= bin(Xi).count("1")
          count += 1
        print(count)
    return True

  X_int_m = X_int%(base_1_count - 1)
  for i in range(N):
    # 初期値計算を高速にやる
    if X[i] == "1":
      temp_1_count = base_1_count-1
      pow_2 = pow(2, N-i-1, base_1_count-1)
      if X_int_m <= pow_2:
        Xi = X_int_m - pow_2 + base_1_count-1
      else:
        Xi = X_int_m - pow_2
    else:
      temp_1_count = base_1_count+1
      Xi = X_int_p + pow(2, N-i-1, base_1_count+1)
      while Xi >= base_1_count+1:
        Xi %= base_1_count+1

    # print("1_c={0}".format(temp_1_count))
    if temp_1_count == Xi:
      print(1)
      continue

    count = 1
    while Xi != 0:
      num_of_1 = bin(Xi).count("1")
      Xi %= num_of_1
      count += 1
    print(count)

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

s = input()
mod = 2019
ls = len(s)
cnt = 0
for i in range(ls-3):
    st = int(s[i:i+2])
    if st%2!=0:
        continue
    for j in range(i+3,ls):
        c = int(s[i:j+1])
        if c%mod ==0:
            cnt+=1
print(cnt)

### FIXED CODE ###

s = input()
res = 0
m = 1
p =[0]*2019
for i in map(int,s[::-1]):
    res +=i*m
    res %=2019
    p[res] +=1
    m *=10
    m %=2019
print(p[0]+sum([i*(i-1)//2 for i in p]))
### BUGGY CODE ###

from collections import deque
H,W=map(int,input().split())
Ch,Cw=map(int,input().split())
Dh,Dw=map(int,input().split())
Ch-=1
Cw-=1
Dh-=1
Dw-=1

S=[]
for i in range(H):
  s=list(input())
  S.append([-1 if i =="." else i for i in s])

dq = deque()
dq.append((Ch,Cw))
S[Ch][Cw]=0

while dq:
  a=dq.pop()
  for i in range(5):
    for j in range(5):
      if a[0]-2+i>=0 and a[0]-2+i<H and a[1]-2+j>=0 and a[1]-2+j<W and abs(i-2)+abs(j-2)==1 and (S[a[0]-2+i][a[1]-2+j]==-1 or (S[a[0]-2+i][a[1]-2+j]!="#" and S[a[0]-2+i][a[1]-2+j]>S[a[0]][a[1]])):
        S[a[0]-2+i][a[1]-2+j]=S[a[0]][a[1]]
        dq.appendleft((a[0]-2+i,a[1]-2+j))
      elif a[0]-2+i>=0 and a[0]-2+i<H and a[1]-2+j>=0 and a[1]-2+j<W and (S[a[0]-2+i][a[1]-2+j]==-1 or (S[a[0]-2+i][a[1]-2+j]!="#" and S[a[0]-2+i][a[1]-2+j]>S[a[0]][a[1]]+1)):
        S[a[0]-2+i][a[1]-2+j]=S[a[0]][a[1]]+1
        dq.append((a[0]-2+i,a[1]-2+j))

print(S[Dh][Dw])

### FIXED CODE ###

from collections import deque
H,W=map(int,input().split())
Ch,Cw=map(int,input().split())
Dh,Dw=map(int,input().split())
Ch-=1
Cw-=1
Dh-=1
Dw-=1

S=[]
for i in range(H):
  s=list(input())
  S.append([10**10 if i =="." else -1 for i in s])
visit=[[False for i in range(W)] for j in range(H)]

dq = deque()
dq.append((Ch,Cw,0))
S[Ch][Cw]=0
counter=0

while dq:
  a=dq.popleft()
  if visit[a[0]][a[1]]==True:
    continue
  elif S[a[0]][a[1]]==counter:
    visit[a[0]][a[1]]=True
  elif a[2]==counter+1:
    visit[a[0]][a[1]]=True
    counter+=1
  for i in range(5):
    for j in range(5):
      if a[0]-2+i>=0 and a[0]-2+i<H and a[1]-2+j>=0 and a[1]-2+j<W:
        if abs(i-2)+abs(j-2)==1 and S[a[0]][a[1]]<S[a[0]-2+i][a[1]-2+j] and visit[a[0]-2+i][a[1]-2+j]==False:
          S[a[0]-2+i][a[1]-2+j]=counter
          dq.appendleft((a[0]-2+i,a[1]-2+j,counter))
        elif S[a[0]][a[1]]+1<S[a[0]-2+i][a[1]-2+j] and visit[a[0]-2+i][a[1]-2+j]==False:
          S[a[0]-2+i][a[1]-2+j]=counter+1
          dq.append((a[0]-2+i,a[1]-2+j,counter+1))
  #print(visit,counter,a,dq,"\n")
if S[Dh][Dw]==10**10:
  print(-1)
else:
  print(S[Dh][Dw])
### BUGGY CODE ###

from itertools import accumulate
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
N, C = map(int, input().split())

posDist = []
posVal = []
for _ in range(N):
    d, v = list(map(int, input().split()))
    posDist.append(d)
    posVal.append(v)

negDist = []
negVal = []
for d, v in zip(reversed(posDist), reversed(posVal)):
    negDist.append(C-d)
    negVal.append(v)


posDist = [0]+posDist
negDist = [0]+negDist

posVal = [0]+list(accumulate(posVal))
negVal = [0]+list(accumulate(negVal))
# print(posDist)
# print(negDist)
# print(posVal)
# print(negVal)
for i, d in enumerate(posDist):
    posVal[i] -= d
for i, d in enumerate(negDist):
    negVal[i] -= d
ans = 0

# print("after")
# print(posVal)
# print(negVal)
for l in range(N+1):
        if negVal[l] < 0:
            continue
        for r in range(N-l+1):
            tmp = posVal[r]+negVal[l]-min(posDist[r], negDist[l])
            #print("l,r->", l, r, tmp)
            ans = max(tmp, ans)
print(ans)


### FIXED CODE ###

# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
N, C = map(int, input().split())
sushis = [list(map(int, input().split())) for _ in range(N)]

# Aを時計回り,Bを反時計回りとする
# O->Aと0->A->Oのコストを計算
valA = []
valArev = []
sumV = 0
tmpMax = -float('inf')

for d, v in sushis:
    sumV += v
    valArev.append(sumV-2*d)
    tmpMax = max(tmpMax, sumV-d)
    valA.append(tmpMax)

valB = []
valBrev = []
sumV = 0
tmpMax = -float('inf')
for d, v in reversed(sushis):
    sumV += v
    revD = C-d
    valBrev.append(sumV-2*revD)
    tmpMax = max(tmpMax, sumV-revD)
    valB.append(tmpMax)


# 折り返しなしの場合の値
ans = max(valA+valB+[0])
# O->A->O->B
for i in range(N-1):
    ans = max(ans, valArev[i]+valB[N-i-2])

# O->B->O->A
for i in range(N-1):
    ans = max(ans, valBrev[i]+valA[N-i-2])
print(ans)
### BUGGY CODE ###

import sys
import numpy as np
import math
import copy
input = sys.stdin.readline
 
N = int(input())
A = np.array(list(map(int,input().split())))
r = np.array(list(range(1,N+1)))
B = np.array(sorted(A-r))
bmin = B[N*2//5]
bmax = B[N*3//5]
ans = float('inf')
for bi in range(bmin,bmax+1):
    ans = min(ans,sum(list(map(abs,B - bi))))
print(ans)

### FIXED CODE ###

import sys
import numpy as np
import math
import copy
input = sys.stdin.readline
 
N = int(input())
A = np.array(list(map(int,input().split())))
if N ==1:
    ans = 0
else:
    r = np.array(list(range(1,N+1)))
    B = np.array(sorted(A-r))
    ans = float('inf')
    for i in range(max(N//2-1,0),min(N//2+2,N)):
        c = list(map(abs,(B - B[i])))
        ans = min(ans,sum(c))
print(ans)
### BUGGY CODE ###

import sys
N,K=map(int,input().split())
nums = []
for _ in range(N):
  a,b = map(int,sys.stdin.readline().split())
  nums += [a for _ in range(b)]
nums.sort()
print(nums[K-1])

### FIXED CODE ###

import sys
N,K=map(int,input().split())
nums = {}
for _ in range(N):
  a,b = map(int,sys.stdin.readline().split())
  if a in nums:
    nums[a] += b
  else:
    nums[a] = b

cnt = 0
for key in sorted(nums.keys()):
  cnt += nums[key]
  if cnt >= K:
    print(key)
    exit()
### BUGGY CODE ###

N=int(input())
A=list( map(int,input().split()))
B=int(1)
for i in A:
  B*=i
if(B>10**18):
  B=-1
print(B)

### FIXED CODE ###

N=int(input())
A=list( map(int,input().split()))
A.sort()
B=int(1)
for i in A:
  B*=i
  if(B>10**18):
    B=-1
    break
print(B)
### BUGGY CODE ###

N = int(input())
P = list(map(int, input().split()))
count = 0
while True:
    for i in range(N-1):
        if i + 1 == P[i]:
            P[i], P[i+1] = P[i+1], P[i]
            count += 1
    flag = True
    for i in range(1, N+1):
        if i == P[i-1]:
            flag = False
            break
    if flag:
        break

print(count)

### FIXED CODE ###

N = int(input())
P = list(map(int, input().split()))
count = 0
for i in range(N-1):
    if i + 1 == P[i]:
        P[i], P[i+1] = P[i+1], P[i]
        count += 1

if N == P[N-1]:
    count += 1
print(count)
### BUGGY CODE ###

A, B = map(int, input().split())

ans = 0
for i in range(A, B+1):
#    print(i)
    ans = ans ^ i
    
print(ans)

### FIXED CODE ###

def f_n(n):
    if n % 2 == 0:
        return(n // 2 % 2 ^ n)
    else:
        return((n+1) // 2 % 2)

def f_ab(A, B):
    return(f_n(A-1) ^ f_n(B))
    
    
A, B = map(int, input().split())

print(f_ab(A, B))
### BUGGY CODE ###

N = int(input())
Alist = [int(x) for x in input().split()]
M = max(Alist)
A0 = ['NotUse']
Abool = A0 + [0 for x in range(M)]
Alist.sort()
ans = 0

for i in Alist:
    for j in range(M+1):
        if j == 0:
            None
        elif Abool[j] >= 2:
            None
        else:
            if j % i == 0:
                Abool[j] += 1
    
for i in Alist:
    if Abool[i] == 1:
        ans += 1

print(ans)

### FIXED CODE ###

N = int(input())
Alist = [int(x) for x in input().split()]
M = max(Alist)
A0 = ['NotUse']
Abool = A0 + [0 for x in range(M)]
Alist.sort()
ans = 0

for i in Alist:
    for j in range(i,M+1,i):
        if Abool[j] >= 2:
            None
        else:
            Abool[j] += 1
    
for i in Alist:
    if Abool[i] == 1:
        ans += 1
print(ans)
### BUGGY CODE ###

import math
a=int(input())
b=input()
R=[]
L=0
mod=10**9+7
if b[0]=="W" or b[-1]=="W":
  print(0)
  exit()
for i in range(2*a):
  if i==0:
    L+=1
    fr="L"
  else:
    if b[i]==b[i-1]:
      if fr=="L":
        R.append(L)
        fr="R"
      else:
        L+=1
        fr="L"
    else:
      if fr=="L":
        L+=1
      else:
        R.append(L)
    
if L!=len(R):
  print(0)
  exit()

ans=1
for i,k in enumerate(R):
  ans=ans*(k-i)
  
print(ans*math.factorial(a)%mod)
  
  

### FIXED CODE ###

def main():
  import math
  import sys
  imput=sys.stdin.readline
  a=int(input())
  b=input()
  R=0
  L=0
  ans=1
  mod=10**9+7
  if b[0]=="W" or b[-1]=="W":
    print(0)
    exit()
  for i in range(2*a):
    if i==0:
      L+=1
      fr="L"
    else:
      if b[i]==b[i-1]:
        if fr=="L":
          ans=ans*(L-R)%mod
          R+=1
          fr="R"
        else:
          L+=1
          fr="L"
      else:
        if fr=="L":
          L+=1
        else:
          ans=ans*(L-R)%mod
          R+=1
    
  if L!=R:
    print(0)
    exit()


  
  print(ans*math.factorial(a)%mod)
  

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

n,k = map(int,input().split())
h = list(map(int,input().split()))
k = min(k,n-1)
ans = [0]*(k+1)
temp_min = 10**10
for i in range(1,k+1):
    ans[i] = abs(h[0]-h[i])
for i in range(k+1,n):
    temp_min = 10**10
    for j in range(1,k+1):
        temp_min = min(temp_min,ans[i-j]+abs(h[i]-h[i-j]))
    ans.append(temp_min)
print(ans[-1])

### FIXED CODE ###

n,k = map(int,input().split())
ls_h = list(map(int,input().split()))
temp_min = 99999999
ls_cos = [0]*n
ls_cos[1] = abs(ls_h[1]-ls_h[0])
# print(ls_h)
for i in range(min(k,n)):
    ls_cos[i] = abs(ls_h[i]-ls_h[0])

k = min(k,n)
for i in range(k,n):
    temp_min = 10**11
    for j in range(1,k+1):
        # print(i,j)
        temp_min = min(temp_min,ls_cos[i-j]+abs(ls_h[i]-ls_h[i-j]))
    ls_cos[i] = temp_min
#     print(ls_cos)
# print(ls_cos)
# if 99999999 in ls_cos:
#     print(ls_cos[9999999])
print(ls_cos[-1])
### BUGGY CODE ###

N = int(input())
A = []
for i in range(N):
    row = list(map(int, input().split()))
    row = [r - 1 for r in row]
    A.append(row)

A.append([1000] * N)

counter = [0] * (N + 1)
finish = 0

ans = 0
check_done = set()
while finish < N * (N - 1) // 2:
    checked = set()
    ans += 1

    exit_flg = True
    for n in range(N):
        # ある日程ですでにnは戦っている
        if n in checked:
            continue
        checked.add(n)

        # nの対戦は終了
        if counter[n] == N - 1:
            continue

        n_match = A[n][counter[n]]  # nの対戦相手
        n_match_match = A[n_match][counter[n_match]]  # nの対戦相手の対戦相

        # nの対戦相手はある日の試合をすでに終えている
        if n_match in checked:
            continue

        # マッチング成立
        if n == n_match_match:
            exit_flg = False

            checked.add(n_match)

            finish += 1
            counter[n] += 1
            counter[n_match] += 1

    # 一つも組み合わせられなかった
    if exit_flg:
        print(-1)
        exit()

print(ans)


### FIXED CODE ###

N = int(input())

# 初期化
G = [None] * (10 ** 6 + 1)  # グラフ
for i in range(10 ** 6 + 1):
    G[i] = set()
U = [None] * (10 ** 6 + 1)  # 入次数
D = [0] * (10 ** 6 + 1)  # 根からの距離


# 変換用
def x(i, j):
    return j + 1000 * i


# グラフを構築
for i in range(1, N + 1):
    A = list(map(int, input().split()))
    for j in range(N - 2):
        fv1, fv2 = min(i, A[j]), max(i, A[j])
        tv1, tv2 = min(i, A[j + 1]), max(i, A[j + 1])
        G[x(fv1, fv2)].add(x(tv1, tv2))
        U[x(fv1, fv2)] = 0
        U[x(tv1, tv2)] = 0


# 入次数をカウント
for i in range(10 ** 6 + 1):
    for v in G[i]:
        U[v] += 1

        
# トポロジカルソート
U_zero_nodes = []
for i in range(10 ** 6 + 1):
    if U[i] is None:
        continue

    if U[i] == 0:
        U_zero_nodes.append(i)


topological_order = []
while U_zero_nodes:
    n = U_zero_nodes.pop()
    topological_order.append(n)

    for v in G[n]:
        U[v] -= 1
        if U[v] == 0:
            U_zero_nodes.append(v)


# 不可能判定
if len(topological_order) != N * (N - 1) // 2:
    print(-1)
    exit()


# 最長経路を計算
for t_n in topological_order:
    for v in G[t_n]:
        D[v] = max(D[v], D[t_n] + 1)
print(max(D) + 1)
### BUGGY CODE ###

import itertools

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

p = list(itertools.combinations(range(n), 2))

ans = 0
for i in p:
    ans += a[i[0]] * a[i[1]]

ans = int(ans % (10**9+7))
print(ans)

### FIXED CODE ###

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

a_sum = sum(a)
ans = 0
for i in range(n):
    a_sum -= a[i]
    ans += a[i] * a_sum

ans = int(ans % (10**9+7))
print(ans)
### BUGGY CODE ###

from queue import Queue
N, X, Y = map(int, input().split())

X -= 1
Y -= 1

q = Queue()

ans = [0] * N

def BFS(x, cnt):
    if dist[x] != (N + 1):
        return
    cnt += 1
        
    dist[x] = cnt
    if x + 1 < N:
        q.put((x + 1, cnt))
    if x - 1 >= 0:
        q.put((x - 1, cnt))
    if x == X:
        q.put((Y, cnt))
    if x == Y:
        q.put((X, cnt))


for x in range(N):
    dist = [N + 1] * N
    q.put((x, -1))
    while not q.empty():
        BFS(*q.get())

    for i in range(N):
        ans[dist[i]] += 1

for x in range(1, N):
    print(ans[x] // 2)






### FIXED CODE ###

from collections import deque
N, X, Y = map(int, input().split())

X -= 1
Y -= 1

q = deque()

ans = [0] * N

def BFS(x, cnt):
    if dist[x] != (N + 1):
        return
    cnt += 1
        
    dist[x] = cnt
    if x + 1 < N:
        q.append((x + 1, cnt))
    if x - 1 >= 0:
        q.append((x - 1, cnt))
    if x == X:
        q.append((Y, cnt))
    if x == Y:
        q.append((X, cnt))


for x in range(N):
    dist = [N + 1] * N
    q.append((x, -1))
    while q:
        BFS(*q.popleft())

    for i in range(N):
        ans[dist[i]] += 1

for x in range(1, N):
    print(ans[x] // 2)
### BUGGY CODE ###

N,A,B=map(int,input().split())
ans=0
count=0
Flag=False
waru=N//(A+B)
amari=N%(A+B)
for i in range (10**18):
    if amari==0:
        break
    for j in range(A):
        ans+=1
        count+=1
        if count==amari:
            Flag=True
            break
    for k in range(B):
        if Flag:
            break
        count+=1
        if count==amari:
            Flag=True
            break
    if Flag:
        break
print(ans+waru*A)

### FIXED CODE ###

N,A,B=map(int,input().split())
ans=0
count=0
Flag=False
waru=N//(A+B)
amari=N%(A+B)
if amari>A:
    print(waru*A+A)
else:
    print(waru*A+amari)
### BUGGY CODE ###

n,k=map(int,input().split())
a=[int(x) for x in input().rstrip().split()]
ruiseki=[a[0]]
for i in range(1,n):
    if k<=i:
        ruiseki.append((a[i]*ruiseki[i-1])//(a[i-k]))
    else:
        ruiseki.append((a[i]*ruiseki[i-1]))

for i in range(k,n):
    if ruiseki[i-1]<ruiseki[i]:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

n,k=map(int,input().split())
a=[int(x) for x in input().rstrip().split()]

ruiseki=[a[0]]
for i in range(k,n):
    if a[i-k]<a[i]:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

N=int(input())
C=[int(input()) for _ in range(N)]
mod = int(1e9+7)

memo={}
new_C=[]

pre = 1.5
i=0
for c in C:
    if c!= pre:
        new_C.append(c)
        memo.setdefault(c,[]).append(i)
        i+=1
    pre=c

answer = [0]*len(new_C)
answer[0] = 1

for i in range(1, len(new_C)):
    try:
        prev_index = i-1 - new_C[i-1::-1].index(new_C[i])
        answer[i] = (answer[i-1] + answer[prev_index]) %mod
    except:
        answer[i] = answer[i-1]

print(answer[-1])

### FIXED CODE ###

N = int(input())
C = [int(input()) for _ in range(N)]
mod = int(1e9+7)

from itertools import groupby
x = [0] + [k for k, g in groupby(C)]

dp = [0]*(len(x)) # i個目までで何通りあるか
dp[0] = 1
memo = {}

for i in range(1, len(x)):
    c = x[i]
    memo[c] = (memo.get(c,0) + dp[i-1])%mod
    dp[i] = memo[c]

print(dp[-1])
### BUGGY CODE ###

#!/usr/bin/env python3

def judge(x,a,b,k):
    return x < a+k or b-k < x

def main():
    a,b,k = map(int,input().split())

    l = list(filter(lambda x: judge(x,a,b,k),range(a,b+1)))
    for s in l:
        print(s)


if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin/env python3

def main():
    a,b,k = map(int,input().split())
    s = list(set(range(a,min(a+k,b+1))) | set(range(max(b-k+1,a),b+1)))
    s = sorted(s)

    for i in range(len(s)):
        print(s[i])


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

import copy
n = int(input())
a = list(map(int, input().split()))
mod_a = [i%(10**9 + 7) for i in a]
cop = copy.deepcopy(mod_a)
res = 0
for i in cop:
  b = i
  #print(b)
  #cop[i]
  #print(mod_a)
  if len(mod_a)!=1:
  	mod_a.remove(i)
  	#mod_b = [j*b%(10**9 + 7) for j in mod_a]
  	res += (sum(mod_a)*b)%(10**9 + 7)
  	#print(res)
print(res%(10**9 + 7))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
#mod_a = [i%(10**9 + 7) for i in a]
res = 0
sum_a = sum(a)
b = 0
t = 0
for i in range(0, len(a)-1):
  t = a[i]
  b += a[i]
  res += (sum_a - b)*t%(10**9 + 7)
print(res%(10**9 + 7))
### BUGGY CODE ###

a,b,c,d = map(int,input().split())
mod = 998244353
dp = [[0]*(d+1) for _ in range(c+1)]
dp[a][b] = 1
for i in range(a+1,c+1):
    dp[i][b] = dp[i-1][b]*b
    dp[i][b] %= mod
for i in range(a,c+1):
    for j in range(b+1,d+1):
        dp[i][j] += dp[i][j-1]*i+dp[i-1][j]*j-dp[i-1][j-1]*(i-1)*(j-1)
        dp[i][j] %= mod
print(dp[c][d])

### FIXED CODE ###

a,b,c,d = map(int,input().split())
mod = 998244353
dp = [[0]*(d+1) for _ in range(c+1)]
dp[a][b] = 1
for i in range(a+1,c+1):
    dp[i][b] = dp[i-1][b]*b
    dp[i][b] %= mod
for i in range(a,c+1):
    for j in range(b+1,d+1):
        dp[i][j] += dp[i][j-1]*i+dp[i-1][j]*j-dp[i-1][j-1]*(i-1)*(j-1)
        dp[i][j] %= mod
print(dp[c][d])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
n = int(raw_input())
s = [ raw_input() for  _ in range(n) ]
x = [ ''.join(sorted(i)) for i in s ]
_x = sorted(x)
count = 0
for i in range(n-1):
    tmp = _x[i]
    for j in range(i+1,n):
        if tmp == _x[j]:
            count += 1
        else:
            break
print(count)

### FIXED CODE ###

# -*- coding: utf-8 -*-
n = int(raw_input())
d = {}
ans = 0
for i in range(n):
    si = ''.join(sorted(raw_input()))
    if si in d:
        ans += d[si]
        d[si] += 1
    else:
        d[si] = 1
print(ans)
### BUGGY CODE ###

# https://atcoder.jp/contests/abc138/tasks/abc138_d

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


class Graph:
    def __init__(self, n, dictated=False, edge=[]):
        self.n = n
        self.dictated = dictated
        self.conj = [set() for _ in range(self.n)]
        self.visit = set()
        self.second_visit = set()
        for x, y in edge:
            self.add_edge(x,y)

    def add_edge(self,x,y):
        self.conj[x].add(y)
        if self.dictated == False:
            self.conj[y].add(x)

    def dfs2(self, info, p=0, goal=None, use_visit=False):
        """
        引継ぎが必要な場合に使う再帰関数版の dfs
        :param info: 各頂点の付加情報。[x]*N のリストで与えられる
        :param p: スタート地点
        :param goal: ゴール地点
        :param use_visit: 前回の探索結果を保持するかどうか
        :return: 引継ぎ後の info
        """
        if use_visit==False:
            self.visit = set()
            self.second_visit = set()

        def rec(p, past_p, t):
            self.visit.add(p)
            for q in self.conj[p]:
                if q == past_p:
                    # 逆流した際の処理
                    continue
                if q in self.second_visit:
                    # 帰り道に訪れた際の処理
                    continue
                if q in self.visit:
                    continue
                if q == goal:
                    # ゴール時の処理
                    # return t+1
                    continue
                # p から q への引継ぎ処理
                info[q] += info[p]

                rec(q, p, t+1)
            self.second_visit.add(p)
            # 帰り際の処置（壊した道を元に戻す等)
            # visit.discard(p)
            return info

        past_p = None
        t = 0
        return rec(p, past_p, t)


######################################################################################################

N, Q = map(int, input().split())  # N:頂点数, Q: クエリの数
M = N-1

graph = Graph(N, dictated=False)

for _ in range(M):
    x, y = map(int, input().split())
    x -= 1                                    # デクリメントが不要な場合は消す
    y -= 1
    graph.add_edge(x,y)

info = [0] * N
for _ in range(Q):
    p, x = map(int, input().split())
    info[p - 1] += x

print(*graph.dfs2(info, p=0))

# 6 2
# 1 2
# 1 3
# 2 4
# 3 6
# 2 5
# 1 10
# 1 10

### FIXED CODE ###

import sys

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

N, Q = map(int, input().split())

branch = [[] for _ in range(N)] # [[]]*N だと参照渡しになってしまう
X = [0,]*N
root = [None]*N
t = 0

for _ in range(N - 1):
    a, b = map(int, input().split())
    branch[a-1].append(b)
    branch[b-1].append(a)

for _ in range(Q):
    p, x = map(int, input().split())
    X[p-1] += x


def search(p):
    global t
    root[p-1] = t
    t += 1
    for q in branch[p-1]:
        if root[q-1] != None:
            continue
        X[q - 1] += X[p - 1]
        search(q)
    t -= 1



search(1)
print(*X)