Xay likes to jump around. He also likes to have order. So he designed a rule to help him jump on : If he is standing on number x, after the next jump he will be on x+popcount(x), where popcount(x) indicates the number of bits that is 1 in x's binary representation.

Xay is currently on number a, and he wants to go to b. Since he can't always land exactly on b, he wants to know how close he could be. Formally, Xay wants to know the smallest number  he could be on.

You should use the following code to generate input. The format is written below.

ull myRand(ull &k1, ull &k2) {
    ull k3 = k1, k4 = k2;
    k1 = k4;
    k3 ^= (k3 << 23);
    k2 = k3 ^ k4 ^ (k3 >> 17) ^ (k4 >> 26);
    return k2 + k4;
}
ull rnd(){
	for(;;){
		ull x=myRand(a1,a2);
		if(x)return x;
	}
}

输入描述:

Input contains two integers q,tp().
If tp=1,the next line contains two integers a1,a2 respectively().
The queries are generated in the following way:
Run the code above 2q times to generate a sequence  in the order they are generated. It's guranteed that.
There are q queries. 
In the i-th query, .
If tp=2, q lines follow. Each line contains two integers a and b().
It's guaranteed that  when .

输出描述:

Let the answer for the i-th query be .
You should output .

3 2
1 2
3 6
4 1002

3034

The answers are 2,7,1006.