Youtuber_TWK và kyanh đang tham gia một tiết học về lý thuyết tập hợp.

Có một tập hợp gồm \(n\) phần tử được đánh số từ \(0\) đến \(n-1\) và một mảng \(A\) gồm \(2^n\) phần tử.

Mỗi số nguyên \(x\) từ \(0\) đến \(2^n-1\) biểu diễn một tập con \(S\) của tập \({0,1,\ldots,n-1}\) bằng biểu diễn bitmask:

• bit thứ \(i\) của \(x\) bằng \(1\) khi và chỉ khi \(i \in S\);
• \(A[x]\) là giá trị được gán cho tập con \(S\).

Với hai hàm \(F\) và \(G\) trên các tập con, định nghĩa subset convolution: \((F * G)[S] = \sum_{X \subseteq S} F[X] \cdot G[S \setminus X]\).

Cho ba tập con có thứ tự \((S_1,S_2,S_3)\) của \(S\). Bộ ba này được gọi là một phân chia hợp lệ nếu:

\(S_1 \cap S_2 = S_1 \cap S_3 = S_2 \cap S_3 = \varnothing\) và \(S_1 \cup S_2 \cup S_3 = S\).

Các tập \(S_1,S_2,S_3\) có thể rỗng và thứ tự của chúng được phân biệt.

Trọng số của một phân chia hợp lệ là: \(A[S_1] \cdot A[S_2] \cdot A[S_3]\). Với mỗi tập con \(S\), hãy tính tổng trọng số của tất cả các phân chia hợp lệ của \(S\).

Nói cách khác, cần tính: \(B[S] = \sum A[S_1] \cdot A[S_2] \cdot A[S_3]\) trên mọi bộ ba \((S_1,S_2,S_3)\) thỏa mãn các điều kiện trên.

Tất cả kết quả phải được lấy modulo \(998244353\).

Input

• Dòng đầu tiên chứa một số nguyên \(n\).

• Dòng thứ hai chứa \(2^n\) số nguyên \(A[0], A[1], \ldots, A[2^n-1]\).

• Các giá trị thỏa mãn \(0 \le A[i] < 998244353\).

Output

• In ra \(2^n\) số nguyên \(B[0],B[1],\ldots,B[2^n-1]\).

• Giá trị \(B[x]\) phải là đáp án tương ứng với tập con được biểu diễn bởi bitmask \(x\), lấy modulo \(998244353\).

Constraints

• \(1 \le n \le 20\).
• \(0 \le A[i] < 998244353\).

Example

2
1 2 3 4

1 6 9 48

3
1 2 3 4 5 6 7 8

1 6 9 48 15 78 111 516