Practice on Toph

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

Joker's GCD Test

By imAnik · Limits 4s, 1.0 GB

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.

Input

First line of input contains n - denoting the initial length of the sequence (1 ≤ n ≤ 106).
Second line contains n space separated integers - the initial elements of the sequence (1 ≤ Pi ≤ 106).
Third line contains q - denoting the number of updates (1 ≤ q ≤ 106).
Each of the next q lines describes an update of the form : either 1 x or 2 x (1 ≤ x ≤ 106).
There will be at least one Add and one Remove update.
The sequence will always contain at least two elements at any point.

Output

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 Q−1 denotes the multiplicative inverse of Q modulo 998244353.

Sample

InputOutput
3
1 3 5
5
1 2
2 3
1 4
2 1
1 3
1
1
166374060
332748119
166374060

Discussion

Statistics


80% Solution Ratio

tmwilliamlin168Earliest, 4w ago

YouKnowWhoFastest, 2.4s

tmwilliamlin168Lightest, 123 MB

tmwilliamlin168Shortest, 2696B

Submit

Login to submit

Related Contests

NSTU ICE Fest Regional Programming Contest 2020 Ended at 2020-01-24 07:15:00 +0000 UTC
Mirror of NSTU ICE Fest Regional Programming Contest 2020 Ended at 2020-01-24 08:15:00 +0000 UTC