## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

## Mystical Numbers CodeChef Solution | CodeChef Problem Solution 2022

A number $M$ is said to be a Mystical Number with respect to a number $X$ if $\left(M\oplus X\right)>\left(M\mathrm{&}X\right)$.

You are given an array $A$ of size $N$. You are also given $Q$ queries. Each query consists of three integers $L$$R$, and $X$.

For each query, find the count of Mystical Numbers in the subarray $A\left[L:R\right]$ with respect to the number $X$.

Notes:

• $\oplus$ represents the Bitwise XOR operation and $\mathrm{&}$ represents the Bitwise AND operation.
• $A\left[L:R\right]$ denotes the subarray $A\left[L\right],A\left[L+1\right],\dots ,A\left[R\right]$.

### Input Format

• The first line contains a single integer $T$ - the number of test cases. Then the test cases follow.
• The first line of each test case contains an integer $N$ - the size of the array $A$.

• The second line of each test case contains $N$ space-separated integers ${A}_{1},{A}_{2},\dots ,{A}_{N}$ denoting the array $A$.
• The third line of each test case contains an integer $Q$ - denoting the number of queries.
• The ${i}^{th}$ of the next $Q$ lines contains three space-separated integers $L$ , $R$ and $X$.

### Output Format

For each testcase,

• For each query, print in a new line, the count of Mystical Numbers among $A\left[L\right],A\left[L+1\right],\dots ,A\left[R\right]$ with respect to the number $X$.

### Constraints

• $1\le T\le 100$
• $1\le N\le 2\cdot {10}^{5}$
• $0\le {A}_{i}<{2}^{31}$
• $1\le Q\le 2\cdot {10}^{5}$
• $1\le L\le R\le N$
• $0\le X<{2}^{31}$
• Sum of $N$ over all test cases does not exceed $2\cdot {10}^{5}$.
• Sum of $Q$ over all test cases does not exceed $2\cdot {10}^{5}$.

### Sample Input 1

1
5
1 2 3 4 5
2
1 5 4
2 5 2


### Sample Output 1

3
2


### Explanation

Test case $1$:

• Query $1$$L=1,R=5,X=4$.
• ${A}_{1}\oplus X=5,{A}_{1}\mathrm{&}X=0$.
• ${A}_{2}\oplus X=6,{A}_{2}\mathrm{&}X=0$.
• ${A}_{3}\oplus X=7,{A}_{3}\mathrm{&}X=0$.
• ${A}_{4}\oplus X=0,{A}_{4}\mathrm{&}X=4$.
• ${A}_{5}\oplus X=1,{A}_{5}\mathrm{&}X=4$.

Mystical numbers are ${A}_{1},{A}_{2},$ and ${A}_{3}$ with respect to $4$. Therefore, the answer to this query is $3$.

• Query $2$$L=2,R=5,X=2$.
• ${A}_{2}\oplus X=0,{A}_{2}\mathrm{&}X=2$.
• ${A}_{3}\oplus X=1,{A}_{3}\mathrm{&}X=2$.
• ${A}_{4}\oplus X=6,{A}_{4}\mathrm{&}X=0$.
• ${A}_{5}\oplus X=7,{A}_{5}\mathrm{&}X=0$.

Mystical numbers are ${A}_{4}$ and ${A}_{5}$ with respect to $2$. Therefore , the answer to this query is $2$.