The Remainder Game

Let’s play a game. Given an initial number and two sequences , , you should get from to 0 as fast as possible. On each step, you are allowed to pick an index i and apply the following operation on the current number:
This way, you’ll obtain the next number. You should find the minimum number of operations that would get you from to 0.

Input

The first line of the input contains 3 integers n, m, and (0 ≀ n ≀ 10, 0 ≀ m ≀ 100 000, and 0 < < m).
The next n lines contain a pair of integers (0 ≀ , ≀ ).

Output

The program should print the minimum number of operations to get from to 0. If it’s impossible to get to 0, the program should print Impossible.

Examples

Input
Output
2 5 1 3 1 2 1
2
Β 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue