题目描述
你收到了生日礼物——n 个整数三元组!第 i 个三元组为 {ai,bi,ci}。所有数字都大于等于 0,且严格小于 2k,其中 k 是一个固定的整数。
有一天,你玩三元组玩累了,于是你想出了三个新整数 x、y、z,然后构造了 n 个数组。第 i 个数组由 ai 重复 x 次、bi 重复 y 次、ci 重复 z 次组成。因此,每个数组的长度为 x+y+z。
你想从每个数组中恰好选出一个整数,使得它们的异或和(按位异或)等于 t。请输出对于每个 t 从 0 到 2k−1,恰好选出一个数使异或和为 t 的方案数,结果对 998244353 取模。
输入格式
第一行包含两个整数 n 和 k(1≤n≤105,1≤k≤17)——数组的个数和所有数字的二进制长度。
第二行包含三个整数 x、y、z(0≤x,y,z≤109)——你选择的整数。
接下来 n 行,每行包含三个整数 ai、bi、ci(0≤ai,bi,ci≤2k−1)——构成第 i 个数组的整数。
输出格式
输出一行共 2k 个整数。第 i 个数表示恰好选出一个数使异或和为 t=i−1 的方案数,对 998244353 取模。
输入输出样例 #1
输入 #1
1 1
1 2 3
1 0 1
输出 #1
2 4
输入输出样例 #2
输入 #2
2 2
1 2 1
0 1 2
1 2 3
输出 #2
4 2 4 6
输入输出样例 #3
输入 #3
4 3
1 2 3
1 3 7
0 2 5
1 0 6
3 3 2
输出 #3
198 198 126 126 126 126 198 198
说明/提示
在第一个样例中,构造出的数组为 (1,0,0,1,1,1),有两种方式使异或和为 0,有四种方式使异或和为 1。
在第二个样例中,两个数组分别为 (0,1,1,2) 和 (1,2,2,3)。一共有十六种选择(4⋅4),其中 4 种(1⊕1 和 2⊕2,每种各有两种方式)异或和为 0,2 种(0⊕1 和 2⊕3)异或和为 1,4 种(0⊕2 和 1⊕3,每种各有两种方式)异或和为 2,最后 6 种(0⊕3、2⊕1 以及 1⊕2 的四种方式)异或和为 3。