小T在上网冲浪时发现了一组操作序列，潜意识告诉他根据上面的信息操作会有意向不到的事情发生。
操作规则是，对于一个数N，将其二进制下的某一位的1移动至另一个位置，如果原位置不为1则忽略，如果目标位置原先也为1，则进位。依次操作改变N的值。

本题为多样例测试。
首行输入两个整数N、T，分别代表原始数字和样例数,0 < N < 1e9，T 不超过100000。
下面T行，每行输入两个整数x、y，代表将第x位向左移y位，0<x<31，-x<y<31 - x。

对于每次操作，输出操作后的数，单独占一行，题目保证答案不会超出int范围。