Xor-Set

题意翻译

给出两个整数集合$A,B$，求所有使得存在$a \in A,b \in B$且$a \oplus b=c$的整数$c$之和取模$998244353$的值，其中$\oplus$表示按位异或，即`xor`。 对于$A$，给出$n_A$，然后给出$n_A$个区间$[l_i,r_i]$，表示对于所有满足$l_i \le a \le r_i$的整数$a$都有$a \in A$（即$[l_i,r_i] \in A$）。对于$B$以同样方式给出其中的元素。 $A,B$都是不重集，即每个整数至多在集合中出现一次（虽然对题意没有影响）。 数据范围：$1 \le n_A,n_B \le 100,1 \le l_i,r_i \le 10^{18}$。 样例$2$: Input: ``` 1 1 9 2 2 4 2 10 ``` Output: ``` 120 ``` 解释： $A$为$\{1,2,3,4,5,6,7,8,9\}$，$B$为$\{2,3,4,5,6,7,8,9,10\}$，所有满足条件的$c$组成的集合$C$为$\{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15\}$，总和为$120$。

题目描述

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](https://en.wikipedia.org/wiki/Bitwise_operation#XOR). 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 $ .

输入输出样例

输入样例 #1

2
3 5
5 8
3
1 2
1 9
2 9

输出样例 #1

112

输入样例 #2

1
1 9
2
2 4
2 10

输出样例 #2

120

说明

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