H. Удивительная задача на XOR
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы гордый... не важно, просто решите эту задачу.

Даны $$$n$$$ отрезков $$$[l_1, r_1], [l_2, r_2], \ldots [l_n, r_n]$$$. Для каждого $$$x$$$ от $$$0$$$ до $$$2^m - 1$$$ найдите количество, по модулю $$$998\,244\,353$$$, последовательностей $$$a_1, a_2, \ldots a_n$$$, таких что:

  • $$$l_i \leq a_i \leq r_i$$$ для всех $$$i$$$ от $$$1$$$ до $$$n$$$;
  • $$$a_1 \oplus a_2 \oplus \ldots \oplus a_n = x$$$, где $$$\oplus$$$ обозначает побитовую операцию XOR.
Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$, $$$1 \leq m \leq 18$$$).

$$$i$$$-я из следующих $$$n$$$ строк содержит два целых числа $$$l_i$$$ и $$$r_i$$$ ($$$0 \leq l_i \leq r_i \lt 2^m$$$).

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$, а сумма $$$2^m$$$ по всем наборам входных данных не превышает $$$2^{18}$$$.

Выходные данные

Для каждого $$$x$$$ от $$$0$$$ до $$$2^m - 1$$$, пусть:

  • $$$f_x$$$ — количество допустимых последовательностей, по модулю $$$998\,244\,353$$$;
  • $$$g_x = f_x \cdot 2^x \mod 998\,244\,353$$$.

Здесь $$$f_x$$$ и $$$g_x$$$ — целые числа в отрезке $$$[0, 998\,244\,352]$$$.

Пусть $$$h = g_0 \oplus g_1 \oplus \ldots \oplus g_{2^m - 1}$$$.

Выведите единственное целое число — значение самого $$$h$$$. Не выполняйте операцию по модулю.

Пример
Входные данные
4
2 2
0 2
1 3
5 3
3 7
1 3
0 2
1 5
3 6
10 14
314 1592
653 5897
932 3846
264 3383
279 5028
841 9716
939 9375
105 8209
749 4459
230 7816
1 5
0 29
Выходные данные
22
9812
75032210
1073741823
Примечание

Для первого набора входных данных значения $$$f_x$$$ следующие:

  • $$$f_0 = 2$$$, потому что существует $$$2$$$ допустимые последовательности: $$$[1, 1]$$$ и $$$[2, 2]$$$;
  • $$$f_1 = 2$$$, потому что существует $$$2$$$ допустимые последовательности: $$$[0, 1]$$$ и $$$[2, 3]$$$;
  • $$$f_2 = 2$$$, потому что существует $$$2$$$ допустимые последовательности: $$$[0, 2]$$$ и $$$[1, 3]$$$;
  • $$$f_3 = 3$$$, потому что существует $$$3$$$ допустимые последовательности: $$$[0, 3]$$$, $$$[1, 2]$$$ и $$$[2, 1]$$$.

Значения $$$g_x$$$ следующие:

  • $$$g_0 = f_0 \cdot 2^0 = 2 \cdot 2^0 = 2$$$;
  • $$$g_1 = f_1 \cdot 2^1 = 2 \cdot 2^1 = 4$$$;
  • $$$g_2 = f_2 \cdot 2^2 = 2 \cdot 2^2 = 8$$$;
  • $$$g_3 = f_3 \cdot 2^3 = 3 \cdot 2^3 = 24$$$.

Таким образом, значение для вывода равно $$$2 \oplus 4 \oplus 8 \oplus 24 = 22$$$.

Для второго набора входных данных значения $$$f_x$$$ следующие:

  • $$$f_{0} = 120$$$;
  • $$$f_{1} = 120$$$;
  • $$$f_{2} = 119$$$;
  • $$$f_{3} = 118$$$;
  • $$$f_{4} = 105$$$;
  • $$$f_{5} = 105$$$;
  • $$$f_{6} = 106$$$;
  • $$$f_{7} = 107$$$.