F. Xor-множество
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам заданы два множества: $$$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$$$).

В $$$i$$$-й из следующих $$$n_A$$$ строк записаны два целых числа $$$l_i$$$ и $$$r_i$$$ ($$$1 \le l_i \le r_i \le 10^{18}$$$), описывающих отрезок значений из множества $$$A$$$.

Во второй строке записано целое число $$$n_B$$$ ($$$1 \le n_B \le 100$$$).

В $$$i$$$-й из следующих $$$n_B$$$ строк записаны два целых числа $$$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$$$.

Примеры
Входные данные
2
3 5
5 8
3
1 2
1 9
2 9
Выходные данные
112
Входные данные
1
1 9
2
2 4
2 10
Выходные данные
120
Примечание

В первом примере можно заметить, что множество $$$C = \{0,1,\dots,15\}$$$, что означает, что все числа от $$$0$$$ до $$$15$$$ могут быть представлены в виде $$$a \oplus b$$$.