Today Veijo tried out the following function $f(x)$:

unsigned f(unsigned x) {
     unsigned a = 28;
     unsigned b = 6;
     unsigned c = 2017;
     x += a;
     x ^= (x >> b);
     x *= c;
     return x;
}

(Note that here all variables are unsigned integers, so all arithmetic is done modulo $2^{32}$.)

Veijo discovered that $f(x)$ is actually reversible: for any value $y$ there is exactly one value $x$ with $y = f(x)$. There really has to be something magic about the date 2017-06-28, as this didn't seem to work if you use e.g. 2016 instead of 2017!

So Veijo thought you could maybe use $f(x)$ for encryption; if it is reversible, it is at least in principle possible to do decryption. But $f(x)$ alone looks a bit weak, so for extra obfuscation Veijo defined $g(x,m)$, which is $m$ iterations of fuction $f$: for example, $g(x,0) = x$, $g(x,1) = f(x)$, $g(x,2) = f(f(x))$, $g(x,3) = f(f(f(x)))$, and so on.

Now your task is to write a program that calculates the $g(x,m)$ values.

Input

The first line contains two numbers, $n$ and $m$. Then follows $n$ lines. Line $i$ contains just one number, $x_i$.

Output

Print $n$ lines of output. Line $i$ should contain just one number, $g(x_i, m)$.

Limits

• $1 \le n \le 100$
• $1 \le m \le 10^7$
• $0 \le x_i \le 2^{32}-1$

Example

Input:

2 3
3280387012
1095513148

Output:

3347635925
1977414679

Here, for example, $f(f(f(3280387012))) = 3347635925$.