Trên bảng có $N$ số nguyên. Hãy định nghĩa $A_k$ và $B_k$ như sau:

• $A_k$: Thực hiện $k$ lần thao tác chọn ngẫu nhiên hai số trên bảng, xóa chúng đi và viết tích của hai số đó lên bảng. Giá trị cần tìm là kỳ vọng của tổng các số còn lại trên bảng sau khi thực hiện $k$ lần thao tác.
• $B_k$: Thực hiện $k$ lần thao tác chọn ngẫu nhiên hai số trên bảng, xóa chúng đi và viết tổng của hai số đó lên bảng. Giá trị cần tìm là kỳ vọng của tích các số còn lại trên bảng sau khi thực hiện $k$ lần thao tác.

Khi chọn ngẫu nhiên hai số, xác suất chọn được mọi cặp là như nhau và mọi lần thực hiện là độc lập.

Hãy tính $A_0, \dots, A_{N-1}$ và $B_0, \dots, B_{N-1}$ theo modulo $998\,244\,353$ ($= 119 \times 2^{23} + 1$). Số $998\,244\,353$ là một số nguyên tố.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên $N$ ($1 \le N \le 200\,000$).
• Dòng thứ hai chứa $N$ số nguyên được viết trên bảng, cách nhau bởi dấu cách. Mỗi số không âm và nhỏ hơn $998\,244\,353$.

Dữ liệu ra

• Dòng đầu tiên in ra $A_0, \dots, A_{N-1}$ sau khi chia lấy dư cho $998\,244\,353$, cách nhau bởi dấu cách.
• Dòng thứ hai in ra $B_0, \dots, B_{N-1}$ sau khi chia lấy dư cho $998\,244\,353$, cách nhau bởi dấu cách.

Ví dụ

Dữ liệu vào 1

3
3 6 9

Dữ liệu ra 1

18 39 162
162 66 18

Ghi chú

Khi một số hữu tỉ được biểu diễn dưới dạng phân số tối giản $\frac{a}{b}$, phần dư của số này khi chia cho số nguyên tố $p$ là số nguyên $c$ thỏa mãn $a \equiv c \cdot b \pmod{p}$ và $0 \le c < p$. Giá trị này là duy nhất nếu $b$ không chia hết cho $p$.

Trong bài toán này, có thể chứng minh rằng với mọi dữ liệu đầu vào hợp lệ, $A_0, \dots, A_{N-1}$ và $B_0, \dots, B_{N-1}$ đều là các số hữu tỉ và khi biểu diễn dưới dạng phân số tối giản, mẫu số không chia hết cho $998\,244\,353$.