As the best programmer and biggest chad of William Lyon Mackenzie C.I., Allan has now been selected to give a lesson on bitmasks and their operations. While he was creating his lesson plan, he came up with the following question:

You're given the numbers ~Q, L, R~ and ~Q~ queries ~(q_1, x_1), (q_2, x_2), \dots, (q_Q, x_Q)~. For each query ~(q_i, x_i)~, he wants you to find the minimum number of operations to transform it from ~q_i~ to any integer in the range ~[L, \min(q_i + x_i, R)]~ (or ~-1~ if it's impossible). A single operation is defined as inserting a 0 or 1 at any position in the binary representation of an integer.

Here are some examples (note that the digit in square brackets is the newly inserted one):

• 100 -> 10[1]0: ~4 \to 10~
• 100 -> [1]100: ~4 \to 12~
• 100 -> 100[1]: ~4 \to 9~

Important note: leading ~0~s are not counted.

As you want to prove to Allan that you are the king of informatics at WLMAC, you've decided to attempt the question.

Constraints

For all subtasks:

~1 \le Q \le 4 \times 10^6~

~1 \le L \le R \le 5 \times 10^5~

~1 \le q_i, x_i \le 5 \times 10^5~

Subtask 1 [20%]

~L = R~

~x_i = 5 \times 10^5~

~1 \le Q \le 10^4~

Subtask 2 [25%]

~x_i = 5 \times 10^5~

Subtask 3 [55%]

No additional constraints.

Input Specification

The first line contains the integers ~Q, L, R~.

The next ~Q~ lines contain the queries ~(q_1, x_1), (q_2, x_2), \dots, (q_Q, x_Q)~ with ~1~ query per line.

Output Specification

Output the answer to each query on its own line.

Sample Input

6 17 17
5 100
5 11
10 7
8 9
17 1
1 17

Sample Output

2
-1
-1
1
0
4

Sample Explanation

Here are the bitmask representations of the queries (the bits in brackets represent the added bits):

• 101 -> 1[00]01: ~5 \to 17~
• ~17-5 > 11~ so this query is impossible.
• ~10~ is 1010 in binary and ~17~ is 10001 in binary. It can be shown that this query is impossible to complete.
• 1000 -> 1000[1]: ~8 \to 17~
• 10001 -> 10001: ~17 \to 17~
• 1 -> [1000]1: ~1 \to 17~