For \(0 \leq i \leq j \leq N\), once the parity of \(X_i\) is determined, \(X_j\) can be expressed using certain constants \(C^{\text{even}}_{i,j}\) and \(C^{\text{odd}}_{i,j}\) as follows:

• When \(X_i\) is even: \(X_i \oplus C^{\text{even}}_{i,j} = X_j\)
• When \(X_i\) is odd: \(X_i \oplus C^{\text{odd}}_{i,j} = X_j\) .

For each query, check whether \(X_0 = C^{\text{even}}_{0,N} \oplus Y\) or \(X_0 = C^{\text{odd}}_{0,N} \oplus Y\) satisfies the parity condition, and output the appropriate result.

These constants \(C^{\text{even}}_{i,j}\) and \(C^{\text{odd}}_{i,j}\) can be efficiently computed using a Segment Tree.

Specific Method

1. From the recurrence relation:

   • \(C^{\text{odd}}_{i-1,i} = A_i\), \(C^{\text{even}}_{i-1,i} = B_i\) .
     

2. If \(C^{\text{odd}}_{l,m}, C^{\text{even}}_{l,m}, C^{\text{odd}}_{m,r}, C^{\text{even}}_{m,r}\) are known, then \(C^{\text{odd}}_{l,r}\) and \(C^{\text{even}}_{l,r}\) can be computed as follows:

   • When \(C^{\text{odd}}_{l,m}\) is odd:
     • \(X_m = X_l \oplus C^{\text{odd}}_{l,m}\) becomes even.
       
     • In this case, \(X_r = X_m \oplus C^{\text{even}}_{m,r} = X_l \oplus C^{\text{odd}}_{l,m} \oplus C^{\text{even}}_{m,r}\) .
       
     • Therefore, \(C^{\text{odd}}_{l,r} = C^{\text{odd}}_{l,m} \oplus C^{\text{even}}_{m,r}\) .
       
   • When \(C^{\text{odd}}_{l,m}\) is even:
     • \(X_m = X_l \oplus C^{\text{odd}}_{l,m}\) becomes odd.
       
     • In this case, \(X_r = X_m \oplus C^{\text{even}}_{m,r} = X_l \oplus C^{\text{odd}}_{l,m} \oplus C^{\text{odd}}_{m,r}\) .
       
     • Therefore, \(C^{\text{odd}}_{l,r} = C^{\text{odd}}_{l,m} \oplus C^{\text{odd}}_{m,r}\) .
       
   • Similarly, by distinguishing the parity of \(C^{\text{even}}_{l,m}\) , \(C^{\text{even}}_{l,r}\) can also be computed.

3. The identity element is \(0\) .

This method allows solving each query with a time complexity of \(O(\log N)\).