← 返回题目列表

Codeforces · 1261/F

F. 异或集

中文机器翻译题面 查看原题

给你两组整数:$$$A$$$ 和 $$$B$$$。您需要输出集合中元素的总和 $$$C = \{x | x = a \oplus b, a \in A, b \in B\}$$$ 模 $$$998244353$$$,其中 $$$\oplus$$$ 表示按位异或运算。每个数字只能计算一次。

例如,如果 $$$A = \{2, 3\}$$$ 和 $$$B = \{2, 3\}$$$,您应该只计算整数 $$$1$$$ 一次,尽管事实上您可以将其作为 $$$3 \oplus 2$$$ 和 $$$2 \oplus 3$$$ 获得。因此,本例的答案等于 $$$1 + 0 = 1$$$。

我们将一个段称为 $$$[l; r]$$$ 一组整数 $$$\{l, l+1, \dots, r\}$$$。

集合 $$$A$$$ 作为 $$$n_A$$$ 段的并集给出,集合 $$$B$$$ 作为 $$$n_B$$$ 段的并集给出。

输入

第一行包含一个整数 $$$n_A$$$ ($$$1 \le n_A \le 100$$$)。

接下来的 $$$n_A$$$ 行的第 $$$i$$$ 行包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$1 \le l_i \le r_i \le 10^{18}$$$),描述集合 $$$A$$$ 的一段值。

下一行包含一个整数 $$$n_B$$$ ($$$1 \le n_B \le 100$$$)。

接下来的 $$$n_B$$$ 行的第 $$$i$$$ 行包含两个整数 $$$l_j$$$ 和 $$$r_j$$$ ($$$1 \le l_j \le r_j \le 10^{18}$$$),描述集合 $$$B$$$ 的一段值。

请注意,两组中的线段可能相交。

输出

打印一个整数 - 集合 $$$C = \{x | 中所有元素的总和x = a \oplus b, a \in A, b \in B\}$$$ 模 $$$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

注意

在第二个例子中,我们可以发现集合$$$C = \{0,1,\dots,15\}$$$,这意味着$$$0$$$到$$$15$$$之间的所有数字都可以表示为$$$a \oplus b$$$。