Triple
Contest: Codeforces Global Round 2
Difficulty rating: 3200
Tags: fft, math

You have received your birthday gifts — $$$n$$$ triples of integers! The $$$i$$$-th of them is $$$\lbrace a_{i}, b_{i}, c_{i} \rbrace$$$. All numbers are greater than or equal to $$$0$$$, and strictly smaller than $$$2^{k}$$$, where $$$k$$$ is a fixed integer.

One day, you felt tired playing with triples. So you came up with three new integers $$$x$$$, $$$y$$$, $$$z$$$, and then formed $$$n$$$ arrays. The $$$i$$$-th array consists of $$$a_i$$$ repeated $$$x$$$ times, $$$b_i$$$ repeated $$$y$$$ times and $$$c_i$$$ repeated $$$z$$$ times. Thus, each array has length $$$(x + y + z)$$$.

You want to choose exactly one integer from each array such that the XOR (bitwise exclusive or) of them is equal to $$$t$$$. Output the number of ways to choose the numbers for each $$$t$$$ between $$$0$$$ and $$$2^{k} - 1$$$, inclusive, modulo $$$998244353$$$.

Input format:
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 10^{5}$$$, $$$1 \leq k \leq 17$$$) — the number of arrays and the binary length of all numbers.

The second line contains three integers $$$x$$$, $$$y$$$, $$$z$$$ ($$$0 \leq x,y,z \leq 10^{9}$$$) — the integers you chose.

Then $$$n$$$ lines follow. The $$$i$$$-th of them contains three integers $$$a_{i}$$$, $$$b_{i}$$$ and $$$c_{i}$$$ ($$$0 \leq a_{i} , b_{i} , c_{i} \leq 2^{k} - 1$$$) — the integers forming the $$$i$$$-th array.

Output format:
Print a single line containing $$$2^{k}$$$ integers. The $$$i$$$-th of them should be the number of ways to choose exactly one integer from each array so that their XOR is equal to $$$t = i-1$$$ modulo $$$998244353$$$.

Constraints:
Time limit: 1.5 s
Memory limit: 256.0 MB

Note:
In the first example, the array we formed is $$$(1, 0, 0, 1, 1, 1)$$$, we have two choices to get $$$0$$$ as the XOR and four choices to get $$$1$$$.

In the second example, two arrays are $$$(0, 1, 1, 2)$$$ and $$$(1, 2, 2, 3)$$$. There are sixteen $$$(4 \cdot 4)$$$ choices in total, $$$4$$$ of them ($$$1 \oplus 1$$$ and $$$2 \oplus 2$$$, two options for each) give $$$0$$$, $$$2$$$ of them ($$$0 \oplus 1$$$ and $$$2 \oplus 3$$$) give $$$1$$$, $$$4$$$ of them ($$$0 \oplus 2$$$ and $$$1 \oplus 3$$$, two options for each) give $$$2$$$, and finally $$$6$$$ of them ($$$0 \oplus 3$$$, $$$2 \oplus 1$$$ and four options for $$$1 \oplus 2$$$) give $$$3$$$.

Example input:
1 1
1 2 3
1 0 1

Example output:
2 4

Example input:
2 2
1 2 1
0 1 2
1 2 3

Example output:
4 2 4 6

Editorial:
If we form $$$n$$$ arrays, $$$i$$$-th of them is $$$F_{i}$$$, and set $$$F_{i,A_{i}}=a$$$, $$$F_{i,B_{i}}=b$$$, $$$F_{i,C_{i}}=c$$$ and others zero. It's easy to find that the xor-convolution of all the arrays is the answer we want.
Implementation with the Fast Walsh-Hadamard Transform works in $$$O(n \times 2^{k} \times k)$$$, this is too slow.
To make it easier, we set $$$A_{i} = 0$$$, $$$B_{i} = B_{i} xor A_{i}$$$, $$$C_{i} = C_{i} xor A_{i}$$$. The answer won't change if we xor all $$$x$$$ by the xor sum of all $$$A_{i}$$$.
That is $$$F_{i,0}=a$$$, $$$F_{i,B_{i} xor A_{i}}=b$$$, $$$F_{i,C_{i} xor A_{i}}=c$$$.
Note we only have $$$4$$$ values in each array after FWHT of the array: $$$a+b+c$$$, $$$a+b-c$$$, $$$a-b+c$$$, $$$a-b-c$$$. Let's fix some position, let the occurrences of them in all $$$n$$$ arrays be $$$x,y,z,w$$$. Obviously, $$$x+y+z+w = n$$$. For each position, if we can figure out the values of $$$x,y,z,w$$$, it's easy to count the final answer by FWHT.
If we add all arrays together and make a FWHT, we can form a new equation. $$$(a+b+c) \cdot x + (a+b-c) \cdot y + (a-b+c) \cdot z + (a-b-c) \cdot w = p$$$, where $$$p$$$ is the value we get in this position.
Take two different $$$(a,b,c)$$$ to form 2 equations. Now we have 3 equations in total, including $$$(x+y+z+w=n)$$$ .
More equations formed by this operation (take $$$a,b,c$$$ and compute FWHT) are useless because the equation $$$x,y,z,w$$$ lies in the same linear span, so we already have three equations.
However, if we set up a new array, $$$F_{i,B_{i} xor C_{i}} += 1$$$, other is zero, and do the FWHT (add them together of course). We can get a new equation $$$x - y - z + w = p$$$. The equation can be easily proved.
Now we can solve a system of $$$4$$$ equations to calculate $$$x,y,z,w$$$ for each position and get the final array. Then do the reverse FWHT and get the answer.