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