← Home
write a go solution for Description:
You are given two sets of integers: A and B. You need to output the sum of elements in the set C=x|x=aoplusb,ainA,binB modulo 998244353, where oplus denotes the bitwise XOR operation. Each number should be counted only once.

For example, if A=2,3 and B=2,3 you should count integer 1 only once, despite the fact that you can get it as 3oplus2 and as 2oplus3. So the answer for this case is equal to 1+0=1.

Let's call a segment [l;r] a set of integers l,l+1,...,r.

The set A is given as a union of n_A segments, the set B is given as a union of n_B segments.

Input Format:
The first line contains a single integer n_A (1<=n_A<=100).

The i-th of the next n_A lines contains two integers l_i and r_i (1<=l_i<=r_i<=10^18), describing a segment of values of set A.

The next line contains a single integer n_B (1<=n_B<=100).

The i-th of the next n_B lines contains two integers l_j and r_j (1<=l_j<=r_j<=10^18), describing a segment of values of set B.

Note that segments in both sets may intersect.

Output Format:
Print one integer — the sum of all elements in set C=x|x=aoplusb,ainA,binB modulo 998244353.

Note:
In the second example, we can discover that the set C=0,1,...,15, which means that all numbers between 0 and 15 can be represented as aoplusb.. Output only the code with no comments, explanation, or additional text.