Codeforces Round 604 (Div. 1) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

data structures

probabilities

*2400

No tag edit access

The problem statement has recently been changed. View the changes.

×
C. Beautiful Mirrors with queries

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputCreatnx has $$$n$$$ mirrors, numbered from $$$1$$$ to $$$n$$$. Every day, Creatnx asks exactly one mirror "Am I beautiful?". The $$$i$$$-th mirror will tell Creatnx that he is beautiful with probability $$$\frac{p_i}{100}$$$ for all $$$1 \le i \le n$$$.

Some mirrors are called checkpoints. Initially, only the $$$1$$$st mirror is a checkpoint. It remains a checkpoint all the time.

Creatnx asks the mirrors one by one, starting from the $$$1$$$-st mirror. Every day, if he asks $$$i$$$-th mirror, there are two possibilities:

- The $$$i$$$-th mirror tells Creatnx that he is beautiful. In this case, if $$$i = n$$$ Creatnx will stop and become happy, otherwise he will continue asking the $$$i+1$$$-th mirror next day;
- In the other case, Creatnx will feel upset. The next day, Creatnx will start asking from the checkpoint with a maximal number that is less or equal to $$$i$$$.

There are some changes occur over time: some mirrors become new checkpoints and some mirrors are no longer checkpoints. You are given $$$q$$$ queries, each query is represented by an integer $$$u$$$: If the $$$u$$$-th mirror isn't a checkpoint then we set it as a checkpoint. Otherwise, the $$$u$$$-th mirror is no longer a checkpoint.

After each query, you need to calculate the expected number of days until Creatnx becomes happy.

Each of this numbers should be found by modulo $$$998244353$$$. Formally, let $$$M = 998244353$$$. It can be shown that the answer can be expressed as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q \not \equiv 0 \pmod{M}$$$. Output the integer equal to $$$p \cdot q^{-1} \bmod M$$$. In other words, output such an integer $$$x$$$ that $$$0 \le x < M$$$ and $$$x \cdot q \equiv p \pmod{M}$$$.

Input

The first line contains two integers $$$n$$$, $$$q$$$ ($$$2 \leq n, q \le 2 \cdot 10^5$$$) — the number of mirrors and queries.

The second line contains $$$n$$$ integers: $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \leq p_i \leq 100$$$).

Each of $$$q$$$ following lines contains a single integer $$$u$$$ ($$$2 \leq u \leq n$$$) — next query.

Output

Print $$$q$$$ numbers – the answers after each query by modulo $$$998244353$$$.

Examples

Input

2 2 50 50 2 2

Output

4 6

Input

5 5 10 20 30 40 50 2 3 4 5 3

Output

117 665496274 332748143 831870317 499122211

Note

In the first test after the first query, the first and the second mirrors are checkpoints. Creatnx will ask the first mirror until it will say that he is beautiful, after that he will ask the second mirror until it will say that he is beautiful because the second mirror is a checkpoint. After that, he will become happy. Probabilities that the mirrors will say, that he is beautiful are equal to $$$\frac{1}{2}$$$. So, the expected number of days, until one mirror will say, that he is beautiful is equal to $$$2$$$ and the answer will be equal to $$$4 = 2 + 2$$$.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/28/2024 19:34:34 (l3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|