Noodle Median XOR Problem

Yazid loves eating wide noodles. He has m bowls of noodles. The i-th bowl (1 ≤ i ≤ m) contains n_i noodles with widths \(A_{i,1},A_{i,2},\dots,A_{i,n_i}\).

When mixing bowl \(u\) and bowl \(v\), we obtain a super bowl by combining all noodles from both bowls. Let \(f(u,v)\) be the \(\left\lfloor \frac{n_u+n_v+1}{2} \right\rfloor\)-th smallest noodle width from the merged sorted collection (here, \(\lfloor x \rfloor\) denotes the floor of \(x\)).

Your task is to compute, for every bowl \(u\) (1 ≤ u ≤ m), the value:

\( R(u)=\bigoplus_{v=1}^{m} \Big(f(u,v)+u+v\Big) \)

where \(\oplus\) denotes the bitwise XOR operation.

Output the values \(R(1), R(2), \dots, R(m)\) in a single line separated by spaces.

inputFormat

The first line contains an integer \(m\), the number of bowls.

For each bowl, the first number is an integer \(n_i\) representing the number of noodles in that bowl, followed by \(n_i\) space-separated integers \(A_{i,1}, A_{i,2}, \dots, A_{i,n_i}\) representing the widths of the noodles.

outputFormat

Output a single line containing \(m\) integers: \(R(1) R(2) \dots R(m)\), where each \(R(u)\) is computed as described above.

sample

2
3 1 3 5
2 2 4

7 4