CF1261F.Xor-Set

给定两个整数集合 $A$ 和 $B$，你需要输出集合 $C = \{x \mid 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 \mid x = a \oplus b,\, a \in A,\, b \in B\}$ 中所有元素的和，对 $998244353$ 取模。

在第二个样例中，可以发现集合 $C = \{0,1,\dots,15\}$，也就是说所有 $0$ 到 $15$ 之间的数字都可以表示为 $a \oplus b$ 的形式。

由 ChatGPT 4.1 翻译