# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Joker has a sequence **P** of **n** integers. Each two elements in the sequence are **pairwise distinct**.

He defines the strength of the sequence as the **expected value** of the greatest common divisor (**gcd**) of any **two** randomly chosen **distinct** numbers from the sequence.

Joker will perform **q** updates on the sequence. The updates will be of the form :**1 x** : Add **x** to the sequence. It is guaranteed that **x** does not exist in the sequence.**2 x** : Remove **x** from the sequence. It is guaranteed that **x** exists in the sequence.

To save Gotham from Joker, you must answer him the strength of the sequence after each update.

First line of input contains **n** - denoting the initial length of the sequence (1 ≤ n ≤ 10^{6}).

Second line contains **n** space separated integers - the initial elements of the sequence (1 ≤ P_{i} ≤ 10^{6}).

Third line contains **q** - denoting the number of updates (1 ≤ q ≤ 10^{6}).

Each of the next **q** lines describes an update of the form : either **1 x** or **2 x** (1 ≤ x ≤ 10^{6}).

There will be at least one **Add** and one **Remove** update.**The sequence will always contain at least two elements at any point.**

For each update, output in a single line the strength of the sequence after the update.

It can be shown that the strength can be always expressed as a fraction P / Q, where P and Q are coprime integers, P ≥ 0, Q > 0 and Q is co-prime with **998244353**. You should compute **P ⋅ Q ^{−1} modulo 998244353**, where

Input | Output |
---|---|

3 1 3 5 5 1 2 2 3 1 4 2 1 1 3 | 1 1 166374060 332748119 166374060 |

80% Solution Ratio

tmwilliamlin168Earliest,

YouKnowWhoFastest, 2.4s

tmwilliamlin168Lightest, 123 MB

tmwilliamlin168Shortest, 2696B

Login to submit