F. Xor-Set
bitmasks; divide and conquer; math
You are given two sets of integers: \(A\) and \(B\). You need to output the sum of elements in the set \(C = \{x | x = a \oplus b, a \in A, b \in B\}\) 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 \(3 \oplus 2\) and as \(2 \oplus 3\). 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, \dots, 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.
The first line contains a single integer \(n_A\) (\(1 \le n_A \le 100\)).The \(i\)-th of the next \(n_A\) lines contains two integers \(l_i\) and \(r_i\) (\(1 \le l_i \le r_i \le 10^{18}\)), describing a segment of values of set \(A\).The next line contains a single integer \(n_B\) (\(1 \le n_B \le 100\)).The \(i\)-th of the next \(n_B\) lines contains two integers \(l_j\) and \(r_j\) (\(1 \le l_j \le r_j \le 10^{18}\)), describing a segment of values of set \(B\).Note that segments in both sets may intersect.
Print one integer — the sum of all elements in set \(C = \{x | x = a \oplus b, a \in A, b \in B\}\) modulo \(998244353\).
In the second example, we can discover that the set \(C = \{0,1,\dots,15\}\), which means that all numbers between \(0\) and \(15\) can be represented as \(a \oplus b\).