Tích Chập OR · canuc80k4606 · Thuật toán Canuc80k

Hai dãy $a$ và $b$ được đánh chỉ số bởi mọi mask $n$ bit. Hãy tạo dãy $c$ sao cho $c_{k}$ là tổng $a_{i}, b_{j}$ trên tất cả cặp có $i ∣ j = k$ .

Input

Dòng đầu chứa $n$ . Dòng thứ hai chứa $2^{n}$ số của dãy $a$ theo chỉ số tăng dần. Dòng thứ ba chứa $2^{n}$ số của dãy $b$ .

Output

In $2^{n}$ giá trị $c_{0}, c_{1}, \dots, c_{2^{n} - 1}$ , mỗi giá trị modulo $998244353$ .

Constraints

$0 \leq n \leq 20$ .
$0 \leq a_{i}, b_{i} < 998244353$ .

Scoring

Subtask $1$ ( $50%$ số điểm): $n \leq 5$ .
Subtask $2$ ( $50%$ số điểm): Không có giới hạn bổ sung.

Example

Test 1

Input

2
1 2 3 4
5 6 7 8

Output

5 28 43 184

Giải thích: Chẳng hạn $c_{0} = 1 \times 5 = 5$ . Với mask $1$ , các cặp chỉ số có OR bằng $1$ là (0,1),(1,0),(1,1), cho $c_{1} = 1 \times 6 + 2 \times 5 + 2 \times 6 = 28$ .

Phân tích: OR-convolution trở thành phép nhân điểm sau subset zeta. Thật vậy, tổng zeta của c tại m gom mọi c[k] với k subseteq m, tương đương gom mọi cặp i,j subseteq m; tổng này bằng tích hai tổng zeta của a và b.
Thuật toán: Chạy subset zeta cho a và b, nhân hai giá trị tương ứng modulo 998244353, rồi chạy subset Möbius trên tích để thu c.
Chứng minh đúng đắn: Gọi Za[m]=sum_{i subseteq m}a[i] và tương tự. Khi nhân, Za[m]Zb[m] chứa đúng mọi cặp (i,j) có i subseteq m và j subseteq m, tức i|j subseteq m. Do đó tích này bằng sum_{k subseteq m} c[k], chính là subset zeta của OR-convolution cần tìm. Möbius đảo zeta, nên dãy cuối cùng đúng từng c[k].
Độ phức tạp: O(n·2^n) thời gian và O(2^n) bộ nhớ.