Joker's GCD Test

imAnik BRACU Traction Inter Univ...
Limits 4s, 1.0 GB

Joker has a sequence PP of nn 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 qq updates on the sequence. The updates will be of the form:

  • 1 x\texttt{1 x}: Add xx to the sequence. It is guaranteed that xx does not exist in the sequence.
  • 2 x\texttt{2 x}: Remove xx from the sequence. It is guaranteed that xx 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 nn - denoting the initial length of the sequence (1n1061 \le n \le 10^6).

Second line contains nn space separated integers - the initial elements of the sequence (1Pi1061 \le P_i \le 10^6).

Third line contains qq - denoting the number of updates (1q1061 \le q \le 10^6).

Each of the next qq lines describes an update of the form : either 1 x\texttt{1 x} or 2 x\texttt{2 x} (1x1061 \le x \le 10^6).

There will be at least one add and one remove operation.

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/QP / Q, where PP and QQ are co-prime integers, P0P \ge 0, Q>0Q > 0 and QQ is co-prime with 998244353998244353. You should compute PQ1mod998244353P ⋅ Q^{-1} \mod 998244353, where Q1Q^{-1} denotes the multiplicative inverse of Qmod998244353Q \mod 998244353.


1 3 5
1 2
2 3
1 4
2 1
1 3


Login to submit.


88% Solution Ratio
tmwilliamlin168Earliest, Jan '20
Sk_SabitFastest, 1.2s
steinumLightest, 82 MB
serotoninShortest, 1059B
Toph uses cookies. By continuing you agree to our Cookie Policy.