URI Online Judge | 1910

Help Clotilde

By Dâmi Henrique, Inatel BR Brazil

Timelimit: 1

Clotilde loves watching television, but her television control is not conventional. It has only six buttons, the on/off button and five buttons to change channels.

The channel change buttons work as follows: +1 (advances one channel), -1 (subtract one channel), x2 (double the current channel), x3 (triple the current channel) and /2 (goes to the half of the current channel, this button only works if the current channel is even).

help Clotilde

Here’s the Clotilde famous controll.

The Clotilde neighbors often visit her house on weekends, watch television and do not return to channel it was before, causing Clotilde waste lots of time trying to find the channel of her interest again.

Your task is, given the number of the current channel and the number of the channel that Clotilde wants to watch, you must calculate the least amount of button clicks needed to get out of one and get the other. Remeber that as Clotilde is a serious woman, she does not like to go through some specific channels even if you have to press more buttons to get to the destination channel. Another constraint is, there is no channel that is lower or equal to 0 or greater than 105. Ex: If you are in the channel number 55000, you can’t press the button x2 or x3.


There will be several test cases. Each one begins with three integers, O, D and K (1 ≤ O, D ≤ 105, 0 ≤ K ≤ 100), representing, respectively, the source channel, destination, and the amount of channels that Clotilde does not want to pass. The second line contains the K channels banned by Clotilde. It is guaranteed that the source and destination channel will never be banned.

The input ends with O = D = K = 0, which should not be processed.


For each case, output a single line, the least amount of button clicks required to get from the source channel to the destination or -1 if it is impossible to reach the destination channel due to the restrictions of Clotilde.

Input Sample Output Sample

3 8 2

4 5

2 5 5

1 3 10 6 4

13 1 4

15 12 100 5

0 0 0