405212: GYM101845 I Intense Bit Wheel

There is a new intense giant wheel in UNAL town, in UNAL town the wheels move in counterclockwise direction, also as this wheel has n cabins, everyone and everything can play. In particular, numbers come to this attraction. However, a complete number doesn't fit in one cabin, in fact, each cabin have space only for one bit. For this reason a number splits into its binary from and ride the wheel each bit per cabin. As numbers do not want to mess it up, the bits enter into the attraction in the same order the number is formed. Nonetheless, the wheel moves k times (entering and exiting from the attraction don't count as moves), then when the bits have to get out of the wheel they probably don't do it in the same order they entered, therefore making a different number.

For example, when the number 13 enter in a intense 8-bit it will look like the left side of the image below, after 5 moves the wheel will look like the right side of the image, in this case the number exiting the wheel will be 161.

You as the chief of the numbers in the UNAL town want to know how the wheel can affect the numbers that ride this attraction.

First line of input contains 2 numbers n (1 ≤ n ≤ 50) and m (1 ≤ m ≤ 1000) - the quantity of cabins in the wheel and the quantity of numbers that ride in the wheel, respectively.

Next m lines of input contains each 2 integers num (0 ≤ num < 2ⁿ) and k (1 ≤ k ≤ 10¹⁸) - the number that ride the wheel and the quantity of times the wheel move, respectively.

For each number that ride the wheel print the resulting number after leaving the wheel. Output this number in its decimal form.

8 3
1 1
13 5
17 12

2
161
17

Note that all numbers that ride into the wheel have exactly n bits, for example the number 13 in a 8-cabin wheel is not 1101 but 00001101 (see example).