H. Wonderful XOR Problemtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou are the proud... never mind, just solve this problem.There are $$$n$$$ intervals $$$[l_1, r_1], [l_2, r_2], \ldots [l_n, r_n]$$$. For each $$$x$$$ from $$$0$$$ to $$$2^m - 1$$$, find the number, modulo $$$998\,244\,353$$$, of sequences $$$a_1, a_2, \ldots a_n$$$ such that: $$$l_i \leq a_i \leq r_i$$$ for all $$$i$$$ from $$$1$$$ to $$$n$$$; $$$a_1 \oplus a_2 \oplus \ldots \oplus a_n = x$$$, where $$$\oplus$$$ denotes the bitwise XOR operator. InputEach test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows. The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$, $$$1 \leq m \leq 18$$$).The $$$i$$$-th of the next $$$n$$$ lines contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$0 \leq l_i \leq r_i < 2^m$$$).It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$, and the sum of $$$2^m$$$ over all test cases does not exceed $$$2^{18}$$$.OutputFor each $$$x$$$ from $$$0$$$ to $$$2^m - 1$$$, let: $$$f_x$$$ be the number of valid sequences, modulo $$$998\,244\,353$$$; $$$g_x = f_x \cdot 2^x \mod 998\,244\,353$$$. Here, $$$f_x$$$ and $$$g_x$$$ are both integers in the interval $$$[0, 998\,244\,352]$$$.Let $$$h = g_0 \oplus g_1 \oplus \ldots \oplus g_{2^m - 1}$$$.Output a single integer — the value of $$$h$$$ itself. Do not perform a modulo operation. ExampleInput42 20 21 35 33 71 30 21 53 610 14314 1592653 5897932 3846264 3383279 5028841 9716939 9375105 8209749 4459230 78161 50 29Output22
9812
75032210
1073741823
NoteFor the first test case, the values of $$$f_x$$$ are as follows: $$$f_0 = 2$$$, because there are $$$2$$$ valid sequences: $$$[1, 1]$$$ and $$$[2, 2]$$$; $$$f_1 = 2$$$, because there are $$$2$$$ valid sequences: $$$[0, 1]$$$ and $$$[2, 3]$$$; $$$f_2 = 2$$$, because there are $$$2$$$ valid sequences: $$$[0, 2]$$$ and $$$[1, 3]$$$; $$$f_3 = 3$$$, because there are $$$3$$$ valid sequences: $$$[0, 3]$$$, $$$[1, 2]$$$, and $$$[2, 1]$$$.The values of $$$g_x$$$ are as follows: $$$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$$$.Thus, the value to output is $$$2 \oplus 4 \oplus 8 \oplus 24 = 22$$$.For the second test case, the values of $$$f_x$$$ are as follows: $$$f_{0} = 120$$$; $$$f_{1} = 120$$$; $$$f_{2} = 119$$$; $$$f_{3} = 118$$$; $$$f_{4} = 105$$$; $$$f_{5} = 105$$$; $$$f_{6} = 106$$$; $$$f_{7} = 107$$$.