CF2096H Wonderful XOR Problem

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](https://en.wikipedia.org/wiki/Bitwise_operation#XOR).

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 $ .