The only difference between easy and hard versions is constraints.

Nauuo is a girl who loves random picture websites.

One day she made a random picture website by herself which includes $n$ pictures.

When Nauuo visits the website, she sees exactly one picture. The website does not display each picture with equal probability. The $i$-th picture has a non-negative weight $w_i$, and the probability of the $i$-th picture being displayed is $\frac{w_i}{\sum_{j=1}^nw_j}$. That is to say, the probability of a picture to be displayed is proportional to its weight.

However, Nauuo discovered that some pictures she does not like were displayed too often. 

To solve this problem, she came up with a great idea: when she saw a picture she likes, she would add $1$ to its weight; otherwise, she would subtract $1$ from its weight.

Nauuo will visit the website $m$ times. She wants to know the expected weight of each picture after all the $m$ visits modulo $998244353$. Can you help her?

The expected weight of the $i$-th picture can be denoted by $\frac {q_i} {p_i}$ where $\gcd(p_i,q_i)=1$, you need to print an integer $r_i$ satisfying $0\le r_i<998244353$ and $r_i\cdot p_i\equiv q_i\pmod{998244353}$. It can be proved that such $r_i$ exists and is unique.


-----Input-----

The first line contains two integers $n$ and $m$ ($1\le n\le 50$, $1\le m\le 50$) — the number of pictures and the number of visits to the website.

The second line contains $n$ integers $a_1,a_2,\ldots,a_n$ ($a_i$ is either $0$ or $1$) — if $a_i=0$ , Nauuo does not like the $i$-th picture; otherwise Nauuo likes the $i$-th picture. It is guaranteed that there is at least one picture which Nauuo likes.

The third line contains $n$ integers $w_1,w_2,\ldots,w_n$ ($1\le w_i\le50$) — the initial weights of the pictures.


-----Output-----

The output contains $n$ integers $r_1,r_2,\ldots,r_n$ — the expected weights modulo $998244353$.


-----Examples-----
Input
2 1
0 1
2 1

Output
332748119
332748119

Input
1 2
1
1

Output
3

Input
3 3
0 1 1
4 3 5

Output
160955686
185138929
974061117



-----Note-----

In the first example, if the only visit shows the first picture with a probability of $\frac 2 3$, the final weights are $(1,1)$; if the only visit shows the second picture with a probability of $\frac1 3$, the final weights are $(2,2)$.

So, both expected weights are $\frac2 3\cdot 1+\frac 1 3\cdot 2=\frac4 3$ .

Because $332748119\cdot 3\equiv 4\pmod{998244353}$, you need to print $332748119$ instead of $\frac4 3$ or $1.3333333333$.

In the second example, there is only one picture which Nauuo likes, so every time Nauuo visits the website, $w_1$ will be increased by $1$.

So, the expected weight is $1+2=3$.

Nauuo is very naughty so she didn't give you any hint of the third example.

Difficulty: HARD
Tags: Dynamic programming

Probability
Skill types: Dynamic programming

Starter code:

Solutions:
import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, copy, functools
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
eps = 1.0 / 10 ** 10
mod = 998244353
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]

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

def LLI():
	return [list(map(int, l.split())) for l in sys.stdin.readlines()]

def LI_():
	return [int(x) - 1 for x in sys.stdin.readline().split()]

def LF():
	return [float(x) for x in sys.stdin.readline().split()]

def LS():
	return sys.stdin.readline().split()

def I():
	return int(sys.stdin.readline())

def F():
	return float(sys.stdin.readline())

def S():
	return input()

def pf(s):
	return print(s, flush=True)

def pe(s):
	return print(str(s), file=sys.stderr)

def JA(a, sep):
	return sep.join(map(str, a))

def MF(n, d):
	return ModFraction(n, d)

class ModFraction:

	def __init__(self, n, d):
		self.n = n
		self.d = d

	def __add__(self, x):
		xf = ModFraction.xf(x)
		a = self.n * xf.d % mod
		b = xf.n * self.d % mod
		c = self.d * xf.d % mod
		return ModFraction((a + b) % mod, c)

	def __sub__(self, x):
		xf = ModFraction.xf(x)
		a = self.n * xf.d % mod
		b = -xf.n * self.d % mod
		c = self.d * xf.d % mod
		return ModFraction((a + b) % mod, c)

	def __mul__(self, x):
		xf = ModFraction.xf(x)
		a = self.n * xf.n % mod
		b = self.d * xf.d % mod
		return ModFraction(a, b)

	def __truediv__(self, x):
		xf = ModFraction.xf(x)
		a = self.n * xf.d % mod
		b = self.d * xf.n % mod
		return ModFraction(a, b)

	@classmethod
	def xf(cls, x):
		if isinstance(x, int):
			return ModFraction(x, 1)
		return x

	@classmethod
	def inv(cls, x):
		return pow(x, mod - 2, mod)

	def int(self):
		return self.n * ModFraction.inv(self.d) % mod

	def __str__(self):
		return '{} / {}'.format(self.n, self.d)

def main():
	(n, m) = LI()
	a = LI()
	w = LI()
	fm = {}

	def f(c, a, m, p, q):
		if m == 0 or c == 0:
			return MF(c, 1)
		key = (c, a, m, p, q)
		if key in fm:
			return fm[key]
		s = c + p + q
		x = f(c + a, a, m - 1, p, q)
		r = x * MF(c, s)
		if p > 0:
			y = f(c, a, m - 1, p + 1, q)
			r = r + y * MF(p, s)
		if q > 0:
			z = f(c, a, m - 1, p, q - 1)
			r = r + z * MF(q, s)
		fm[key] = r
		return r
	ps = 0
	qs = 0
	for i in range(n):
		if a[i] == 1:
			ps += w[i]
		else:
			qs += w[i]
	r = []
	for i in range(n):
		if a[i] == 1:
			v = f(w[i], 1, m, ps - w[i], qs)
		else:
			v = f(w[i], -1, m, ps, qs - w[i])
		r.append(v.int())
	return JA(r, '\n')
print(main())


P = 998244353
(N, M) = map(int, input().split())
A = [int(a) for a in input().split()]
B = [int(a) for a in input().split()]
li = sum([A[i] * B[i] for i in range(N)])
di = sum([(A[i] ^ 1) * B[i] for i in range(N)])
X = [[] for _ in range(M + 1)]
X[0] = [1]

def calc(L):
	su = sum(L)
	pl = 0
	pd = 0
	RE = []
	for i in range(len(L)):
		a = li + i
		b = di - (len(L) - 1 - i)
		pd = b * L[i] * pow(su * (a + b), P - 2, P)
		RE.append((pl + pd) % P)
		pl = a * L[i] * pow(su * (a + b), P - 2, P)
	RE.append(pl % P)
	return RE
for i in range(M):
	X[i + 1] = calc(X[i])
ne = 0
po = 0
for i in range(M + 1):
	po = (po + X[M][i] * (li + i)) % P
	ne = (ne + X[M][i] * (di - M + i)) % P
for i in range(N):
	print(po * B[i] * pow(li, P - 2, P) % P if A[i] else ne * B[i] * pow(di, P - 2, P) % P)


import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, copy, functools
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
eps = 1.0 / 10 ** 10
mod = 998244353
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]

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

def LLI():
	return [list(map(int, l.split())) for l in sys.stdin.readlines()]

def LI_():
	return [int(x) - 1 for x in sys.stdin.readline().split()]

def LF():
	return [float(x) for x in sys.stdin.readline().split()]

def LS():
	return sys.stdin.readline().split()

def I():
	return int(sys.stdin.readline())

def F():
	return float(sys.stdin.readline())

def S():
	return input()

def pf(s):
	return print(s, flush=True)

def pe(s):
	return print(str(s), file=sys.stderr)

def JA(a, sep):
	return sep.join(map(str, a))

def inv(x):
	return pow(x, mod - 2, mod)

def main():
	(n, m) = LI()
	a = LI()
	w = LI()

	def plus(a, b):
		c = a[0] * b[1] % mod
		d = b[0] * a[1] % mod
		e = a[1] * b[1] % mod
		return [(c + d) % mod, e]

	def sub(a, b):
		c = a[0] * b[1] % mod
		d = -b[0] * a[1] % mod
		e = a[1] * b[1] % mod
		return [(c + d) % mod, e]

	def mul(a, b):
		c = a[0] * b[0] % mod
		d = a[1] * b[1] % mod
		return [c, d]
	fm = {}

	def f(c, a, m, p, q):
		if m == 0 or c == 0:
			return [c, 1]
		key = (c, a, m, p, q)
		if key in fm:
			return fm[key]
		s = c + p + q
		x = f(c + a, a, m - 1, p, q)
		r = mul(x, [c, s])
		if p > 0:
			y = f(c, a, m - 1, p + 1, q)
			r = plus(r, mul(y, [p, s]))
		if q > 0:
			z = f(c, a, m - 1, p, q - 1)
			r = plus(r, mul(z, [q, s]))
		fm[key] = r
		return r
	ps = 0
	qs = 0
	for i in range(n):
		if a[i] == 1:
			ps += w[i]
		else:
			qs += w[i]
	r = []
	for i in range(n):
		if a[i] == 1:
			v = f(w[i], 1, m, ps - w[i], qs)
		else:
			v = f(w[i], -1, m, ps, qs - w[i])
		r.append(v[0] * inv(v[1]) % mod)
	return JA(r, '\n')
print(main())


P = 998244353
(N, M) = map(int, input().split())
A = [int(a) for a in input().split()]
B = [int(a) for a in input().split()]
li = sum([A[i] * B[i] for i in range(N)])
di = sum([(A[i] ^ 1) * B[i] for i in range(N)])
X = [1]
SU = li + di
PO = [0] * (5 * M + 10)
for i in range(-M - 5, 2 * M + 5):
	PO[i] = pow((SU + i) % P, P - 2, P)

def calc(L):
	su = sum(L)
	pl = 0
	pd = 0
	RE = []
	for i in range(len(L)):
		a = li + i
		b = di - (len(L) - 1 - i)
		pd = b * L[i] * PO[a + b - SU]
		RE.append((pl + pd) % P)
		pl = a * L[i] * PO[a + b - SU]
	RE.append(pl % P)
	return RE
for i in range(M):
	X = calc(X)
ne = 0
po = 0
for i in range(M + 1):
	po = (po + X[i] * (li + i)) % P
	ne = (ne + X[i] * (di - M + i)) % P
invli = pow(li, P - 2, P)
invdi = pow(di, P - 2, P)
for i in range(N):
	print(po * B[i] * invli % P if A[i] else ne * B[i] * invdi % P)