J. Leo's Daily Training
time limit per test
3.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Leo is excited about the upcoming ICPC Programadores de América and is preparing a training plan to be ready for the competition. The training plan consists of selecting a list of problems from the popular site HuronCoder.

The site has $$$N$$$ problems numbered from $$$1$$$ to $$$N$$$ and $$$M$$$ tags numbered from $$$1$$$ to $$$M$$$. Each problem can be tagged with any subset of tags (including the empty subset or the set with all the tags). It takes an average of $$$a_i$$$ seconds to solve the $$$i$$$-th problem.

Leo will select a list of problems such that the sum of the average time to solve the problems in the list is exactly $$$s$$$. The list may have repeated problems. We say that the $$$j$$$-th tag is covered by the list if there is at least one problem on it that is tagged with the $$$j$$$-th topic.

As there is a huge number of lists of problems that Leo can choose, so he wants to know the number of lists that he can select to cover each subset of tags. For each subset of tags, help him find the number of lists that cover exactly that subset of tags.

Input

The first line contains three integers $$$N$$$, $$$M$$$, and $$$s$$$ ($$$1 \leq N \leq 10^5$$$, $$$1 \leq M \leq 12$$$ and $$$1 \leq s \leq 10^{18}$$$) – the number of problems in the site and the number of tags.

The following $$$N$$$ contains the descriptions of the problems. The description of a problem contains a bitmask $$$b_i$$$ of length $$$M$$$, followed by an integer $$$a_i$$$ ($$$1 \leq a_i \leq 39$$$) – the tags of the problem and the average seconds it takes to solve it. The $$$j$$$-th bit of $$$b_i$$$ (read from right to left) is $$$1$$$ if the $$$i$$$-th problem is tagged with the $$$j$$$-th tag, and $$$0$$$ otherwise.

Output

Print $$$2^M$$$ integers in a single line. The $$$i$$$-th integers should be the number of lists that cover exactly the subset represented by $$$(i-1)$$$ as a mask (the $$$j$$$-th tag is included in the subset if and only if the $$$j$$$-th least significant bit of $$$(i-1)$$$ is set to $$$1$$$).

As the number of lists is huge, print the answer modulo $$$998244353$$$.

Examples
Input
4 2 2
11 2
10 1
10 2
00 1
Output
1 0 4 1
Input
5 5 20
10000 1
01000 1
00100 1
00010 1
00001 1
Output
0 1 1 1048574 1 1048574 1048574
488905617 1 1048574 1048574 488905617
1048574 488905617 488905617 479169913
1 1048574 1048574 488905617 1048574
488905617 488905617 479169913 1048574
488905617 488905617 479169913 488905617
479169913 479169913 847940114
Note

The second case output is broken into multiple lines so it fits in the output box, but you should print it in a single line.