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.