Xor-Set
Contest: Codeforces Round 602 (Div. 1, based on Technocup 2020 Elimination Round 3)
Difficulty rating: 3100
Tags: 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.

Input format:
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.

Output format:
Print one integer — the sum of all elements in set $$$C = \{x | x = a \oplus b, a \in A, b \in B\}$$$ modulo $$$998244353$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
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$$$.

Example input:
2
3 5
5 8
3
1 2
1 9
2 9

Example output:
112

Example input:
1
1 9
2
2 4
2 10

Example output:
120

Editorial:
Consider a segment tree over the interval $$$[0,2^{60}-1]$$$, a node representing a segment of length $$$2^n$$$ would represent all numbers with the first $$$60-n$$$ bits same, with all possible last n bits. In other words, the binary representation of any number in the segment would be $$$a_1a_2a_3\ldots a_{59-n}a_{60-n}x_1x_2x_3\ldots x_n$$$, where all $$$a_i$$$ and $$$x_i$$$ is either 0 or 1. $$$a_1$$$ to $$$a_{60-n}$$$ would be fixed and all $$$x_i$$$s can be arbitrarily chosen.
We can observe that if we have two segments $$$A$$$ and $$$B$$$ in the tree, all possible numbers that equals the xor sum of a number in $$$A$$$ and a number in $$$B$$$ also forms a segment in the tree, with the length of $$$\max(|A|,|B|)$$$, and the unchanging bits is equal to the xor sum of the two segment's unchanging bits.
Using this observation we would get an $$$O( (n^2 \log^2 10^{18}) \log (n^2 \log^2 10^{18}))$$$ or $$$O( n^2 \log^2 10^{18}) $$$ algorithm, depending on the sorting method. First, we get all segments that compose the intervals in $$$A$$$ and $$$B$$$, we can get $$$O( n^2 \log^2 10^{18})$$$ resulting segments. Then we are left with evaluating the sum in the combination of segments. We can sort these segments to get the answer. This algorithm will get an MLE in practice since the number of resulting segments could easily exceed $$$10^8$$$.
To improve this algorithm, we can make another observation that when segments of different sizes are combined as described above, the smaller segment is equivalent to the ancestor of the same size as the bigger segment. Let's call all the segments in the decomposition of the input the "real" segments, and all segments with a "real" segment in the subtree as "auxiliary" segments. Then we could iterate over 60 possible values of the size of the segment, and for each value, we could iterate over the "real" segments of set $$$A$$$ and "auxiliary" segments of set $$$B$$$ and add the results to the set. We can prove that the number of both "real" and "auxiliary" segments of any size is not greater than $$$4n$$$. Thus, the solution runs at $$$O( (n^2 \log 10^{18}) \log (n^2 \log 10^{18}))$$$ or $$$O( n^2 \log 10^{18}) $$$ algorithm, depending on the sorting method.