In this problem, you are required to find minimum steps to change an integer s to integer t using a sequence of k integers and operator + - × ÷. The changing steps should follow some special rules.
1. + means plus, - means minus, × means multiply, ÷ means integer division. So, if you try to apply 3 to initial integer 2
2 + 3 => 5
2 - 3 => -1
2 × 3 => 6
2 ÷ 3 => 0
2. You should never apply ÷ for 0. i.e. 5 ÷ 0 is undefined.
3. You should use the sequence of integers in the same order of input.
4. After all integer in sequence are applied, you should start from the first integer of the sequence and applies again. E.g. if the sequence has only 3 integers a, b and c, then the order of integer you should apply is a, b, c, a, b, c, a, ...
5. After applied every + - × ÷, if the new number is not within 0 to 99906 inclusively ( overflow ), then the number will sum with (d × 99907) where d is integer to make sure the final number is within the range. This kind of sum is NOT count as one step.
For example,
Given sequence ( v1, v2, v3 ),
if Rule5( Rule5( Rule5( Rule5( s × v1 ) - v2 ) ÷ v3 ) + v1 ) = t is the shortest way convert from s to t, then the minimum steps is 4.
There are less than 20 cases in the input file, two lines for each case. First line consist 3 integers 0 ≤ s, t ≤ 99906 and 1 ≤ k ≤ 20. Second line consist k integers 0 ≤ v1, v2, ..., vk ≤ 10000 that you should apply for each step. Process until the end of the file.
Output minimum steps to change from s to t. You can assume it is always possible converting s to t.
6 10 2 0 1 100 100 2 2 1 0 99900 1 2
8 0 4