Divisor Roads

Time limit2sMemory limit512 MB

Summary

A one-way road runs from X to Y when some A_i divides X and B_i divides Y; find the shortest distance from S to T.

Level: Hard8 of 10
Topics: Graph, BFS, Math, Number theory
Solved: No attempts yet

Problem

A country has N cities numbered from 1 to N. Some pairs of cities are joined by a one way road of length 1. The distance from city X to city Y is the smallest number of roads on a walk that starts at X and ends at Y.

Two sequences A and B of length M determine the road network. A one way road runs from X to Y if and only if at least one index i satisfies both conditions, that $A_i$ divides X and that $B_i$ divides Y.

For example, with $N = 7$ , $M = 1$ , $A = [2]$ and $B = [3]$ there are 7 cities and the roads are 2 -> 3, 2 -> 6, 4 -> 3, 4 -> 6, 6 -> 3, 6 -> 6.

Given two integers S and T, write a program that computes the distance from S to T.

Input

The first line contains N, S, T and M. ( $2 \le N \le 10^9$ , $1 \le S, T \le N$ , $1 \le M \le 1000$ )

The second line contains the sequence A and the third line contains the sequence B. ( $1 \le A_i, B_i \le N$ ) The same pair $(A_i, B_i)$ is never given more than once.

Output

Print the distance from S to T on the first line. Print -1 if T cannot be reached from S.

Hint

In the first example the roads are (3, 5), (3, 10), (6, 5), (6, 10), (9, 5), (9, 10), (10, 2), (10, 4), (10, 6), (10, 8), (10, 10). The shortest walk from city 9 to city 6 is 9 -> 10 -> 6.

In the second example the first element of A and the first element of B are both 1, so a road runs between every pair of cities.

The shortest walk in the fourth example is 10 -> 56 -> 26 -> 34 -> 62.

Examples4

Example 1
Input
```
11 9 6 2
3 10
5 2
```
Expected output
```
2
```
Example 2
Input
```
123456789 18 12 3
1 42 50
1 17 3
```
Expected output
```
1
```
Example 3
Input
```
60 30 8 3
16 15 12
2 20 5
```
Expected output
```
-1
```

Example 4

Input

77 10 62 6
2 5 7 4 17 26
25 7 11 13 31 34

Expected output