给你两组整数:$$$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$$$。