Joker has a sequence of 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 updates on the sequence. The updates will be of the form:
To save Gotham from Joker, you must answer him the strength of the sequence after each update.
First line of input contains - denoting the initial length of the sequence ().
Second line contains space separated integers - the initial elements of the sequence ().
Third line contains - denoting the number of updates ().
Each of the next lines describes an update of the form : either or ().
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 , where and are co-prime integers, , and is co-prime with . You should compute , where denotes the multiplicative inverse of .
Input | Output |
---|---|
3 1 3 5 5 1 2 2 3 1 4 2 1 1 3 | 1 1 166374060 332748119 166374060 |