Xor-Set

2000ms

262144K

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 = 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:

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:

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

Sample Input:

Sample Output:

Sample Input:

Sample Output:

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

Informação

Provedor Codeforces

Código CF1261F