# Sqrt of Formal Power Series

AC一覧

## Problem Statement問題文

You are given a formal power series $f(x) = \sum_{i=0}^{N-1} a_i x^i \in \mathbb{F}_{998{,}244{,}353}[[x]]$. Calculate the first $N$ terms of a square root of $f(x)$. In other words, find $g(x) = \sum_{i=0}^{N-1} b_i x^i \in \mathbb{F}_{998{,}244{,}353}[[x]]$ such that

$$f(x) \equiv g(x)^2 \pmod{x^N}.$$

$$f(x) \equiv g(x)^2 \pmod{x^N}$$

となる $g(x) = \sum_{i=0}^{N-1} b_i x^i \in \mathbb{F}_{998{,}244{,}353}[[x]]$ を求めてください。

## Constraints制約

• $1 \leq N \leq 500{,}000$
• $0 \leq a_i < 998{,}244{,}353$

## Input入力

$N$
$a_0$ $a_1$ $\cdots$ $a_{N - 1}$


## Output出力

If there are no $g(x)$ satisfying the condition, print

-1


and if such $g(x)$ exists, choose any and print

と出力してください。

$b_0$ $b_1$ $\cdots$ $b_{N - 1}$


と出力してください。

## Sampleサンプル

### # 1

4
0 0 9 12

0 3 2 332748117


### # 2

4
0 0 10 12

-1


Timelimit: 10 secs

Before submitting, please confirm terms and conditions