Elevator

A high-rise apartment building has N floors and M elevators. The elevators are numbered from 1 to M.

To reduce maintenance costs, each elevator stops only on certain floors. Elevator i first stops on floor Xi, and after that it stops every Yi floors. For instance, if Xi = 4 and Yi = 3, it stops on floors 4, 7, 10, ... .

Cheolsu lives on floor A and wants to visit a friend on floor B. He wants to take elevators as few times as possible.

Suppose the building has 12 floors and 3 elevators as shown below.

To go from floor 10 to floor 8, he could take elevators 1, 2, and 3 in that order, or he could take only elevators 1 and 3. In either case, the minimum number of elevator rides is 2.

Given N, M, and the operating information for every elevator, find the minimum number of elevator rides needed to go from floor A to floor B, and output one corresponding sequence of elevators.

The first line contains N and M separated by a space.

Each of the next M lines contains Xi and Yi for one elevator, in elevator-number order.

The last line contains the starting floor A and the destination floor B.

N is a positive integer at most 100,000, and M is a positive integer at most 100. Xi, Yi, A, and B are positive integers at most N. A and B are different.

On the first line, output the minimum number of elevator rides needed to go from floor A to floor B.

If the trip is possible, then on the following lines output the elevator numbers to take, one per line, in order. If there are multiple possible sequences, output any one of them.

If floor B cannot be reached from floor A, output only -1 on the first line.