Вам заданы два множества: \(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\) отрезков.
Выходные данные
Выведите одно целое число, сумму элементов в множестве \(C = \{x | x = a \oplus b, a \in A, b \in B\}\) по модулю \(998244353\).
Примечание
В первом примере можно заметить, что множество \(C = \{0,1,\dots,15\}\), что означает, что все числа от \(0\) до \(15\) могут быть представлены в виде \(a \oplus b\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
3 5
5 8
3
1 2
1 9
2 9
|
112
|
|
2
|
1
1 9
2
2 4
2 10
|
120
|