## Bitmask Magic

View as PDF

Points: 15 (partial)
Time limit: 3.5s
Memory limit: 256M

Author:
Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

As the Supreme Overdeity of Informatics of the William Collegiate Institute, 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 and queries . For each query , he wants you to find the minimum number of operations to transform it from to any integer in the range (or 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:
• 100 -> [1]100:
• 100 -> 100[1]:

Important note: leading s are not counted.

As you want to prove to Allan that you are the true Supreme Overdeity of Informatics at WCI, you've decided to attempt the question.

#### Constraints

For all subtasks:

##### Subtask 3 [55%]

No additional constraints.

#### Input Specification

The first line contains the integers .

The next lines contain the queries with 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:
• so this query is impossible.
• is 1010 in binary and is 10001 in binary. It can be shown that this query is impossible to complete.
• 1000 -> 1000[1]:
• 10001 -> 10001:
• 1 -> [1000]1:

## Comments

There are no comments at the moment.