H. Wonderful XOR Problem
bitmasks; combinatorics; dp; fft; math
You 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.
Each 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}\).
For 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.
For 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\).