This is the hard version of the problem. The only difference between the easy and hard versions is that in the hard version, (a_i, b_i \leq 10^6). Renako is stuck between a rock and a hard place... and by that, of course, I mean Ajisai and Mai! Both of them want to hang out with her, and she just can't decide! So Ajisai and Mai have decided to play the XOR game. Ajisai and Mai are given arrays (a) and (b) of length (n) ((0\leq a_i, b_i\leq {\color{red}{10^6}})). They will play a game that lasts for (n) turns, where Ajisai moves on odd-numbered turns and Mai moves on even-numbered turns. On the (i)-th turn, the player to move may choose to swap (a_i) and (b_i), or pass. Note that if a swap occurs, the index that is being swapped must match the turn number . For example, on the first turn, Ajisai may choose to swap (a_1) and (b_1), or pass. On the second turn, Mai may choose to swap (a_2) and (b_2), or pass. This continues for (n) turns. Thus, only Ajisai can swap odd indices, and only Mai can swap even indices. At the end of the game, Ajisai achieves a score of (a_1 \oplus a_2 \oplus \dots \oplus a_n), and Mai achieves a score of (b_1 \oplus b_2 \oplus \dots \oplus b_n)(^{\text{∗}}). The player with the higher score wins. If the players have the same score, the game ends in a tie. Determine the outcome of the game with optimal play. More formally, one player is considered to win with optimal play if there exists a strategy for them such that they always win, regardless of their opponent's choices. The game is considered a tie with optimal play if neither player has such a strategy. (^{\text{∗}})(\oplus) denotes the bitwise XOR operation The first line contains a single integer (t) ((1\leq t\leq 10^4)) — the number of test cases. The first line of each test case contains a single integer (n) ((1\leq n\leq 2\cdot 10^5)). The second line of each test case contains $$$n$