Томская мужийн хүмүүс шидэт томъёололд маш дуртай. Чи доор тэдний заримыг нь харж болно.

Чамд $p_{1}$, $p_{2}$, ..., $p_{n}$ бүхэл тоонуудын дараалал өгөгдсөн байна гэж төсөөлье. Зарим шидэт томьёог бичиж бодъё:

Энд байгаа "$mod$" нь хуваасны дараа үлдэгдлийг авдаг үйлдэл юм.

илэрхийлэл нь $x$ ба $y$ бүхэл тоонуудад $xor$ ("OR"-с гадна) үйлдлийг ашиглана. Энэ өгөгдсөн үйлдэл нь орчин үеийн бүх програмчлалын хэл дээр байдаг. Жишээлбэл: C++ болон Java ба Pascal хэл дээр "$^$"-р дүрслэгдэнэ.

Томская мужийн хүмүүс шидэт томъёололд маш дуртай боловч тэд тооцоолох дургүй юм. Иймээс чамд $p$ дараалал өгөгдсөн ба $Q$-н утгыг тооцоолж гарга.

Оролт

Эхний мөрөнд нэг бүхэл тоо $n$ ($1 ≤ n ≤ 10^{6}$) байна. Дараагийн мөр нь $n$ бүхэл тоонуудыг агуулна: $p_{1}, p_{2}, ..., p_{n}$ ($0 ≤ p_{i} ≤ 2*10^{9}$).

Гаралт

Гаралт нь $Q$-н утга нэг бүхэл тоо л байна.