xjy 的后花园有一个神秘的水池，每次她投进一个装有若干金币的袋子，看袋子在水中浮浮沉沉，金币数量不断的改变。

记开始袋子中金币数为 $n$，袋子第 $i$ 次浮出水面时的金币数为 $a_{i,n}$ ，她敏锐的发现三个性质：

1：对于任意自然数 $i$ ，$a_{i+1,n}≥a_{i,n}$

2：存在一个正整数 $m$ ，满足对于任意自然数 $i$，任意初始袋子里的金币数 $n$ ，$a_{i+m−1,n}=m×a_{i,n}$

3: 对于任意 $N>n$ ，任意自然数 $i$ ，$a_{i,N}>a_{i,n}$

现在 xjy 把 $m$ 的值告诉了 Democlight，并进行了 $q$ 次询问，每次询问形如：如果将一袋 $n$ 个金币的袋子投进水池，第 $k$ 次浮出后拿出水面，袋子中金币的数量是多少。

但是 Democlight 怕自己算错了会让 xjy 讨厌他，便发消息想和你对答案，所以你只需要告诉每次 Democlight 金币数的值的异或和。

特别地，我们规定初始丢下去袋子中金币数量为第 $0$ 次浮出水面金币数量。