Burak and Birkan are travelling around the globe with planes. For simplicity, we will model our planet as a perfect sphere of 1 unit radius in this problem. Some areas on the planet are restricted for air transport and no flight can cross such areas.

There are \(\mathbf{N}\) airports on the planet numbered from \(\mathbf{1}\) to \(\mathbf{N}\). An airport is a point on the sphere defined by its latitude and longitude. A flight between two airports always takes the shortest path on the sphere. No two airports are placed on antipodal points(exact opposite points on the sphere).

There are \(\mathbf{M}\) restricted areas. Defined by two non-antipodal points on the sphere, a restricted area is the shortest path connecting them. There is a flight between a pair of airports if and only if the shortest path connecting the airports does not cross any of the restricted areas. Note that it can not even touch a restricted area endpoint.

Burak and Birkan are in airport \(\mathbf{S}\) and would like to get to airport \(\mathbf{T}\). What is the shortest possible total distance they have to travel?

Input

The first line contains integer \(\mathbf{N}\). Each of the next \(\mathbf{N}\) lines contains two integers separated by a single space which are an airport latitude and longitude respectively. The following line contains integer \(\mathbf{M}\). Each of the following \(\mathbf{M}\) lines contains four integers separated by single spaces: the latitude and longitude of the first restricted area endpoint followed by the latitude and longitude of the second endpoint. The last line contains two integers \(\mathbf{S}\) and \(\mathbf{T}\) separated by a single space.

Output

If it is impossible to get from airport \(\mathbf{S}\) to airport T print −1. Otherwise print the shortest total distance between them. An output is considered correct if its absolute or relative error does not exceed \(10^{-4}\).

Constraints

• \(1 ≤ \mathbf{N}, \mathbf{M} ≤ 100\)
• \(1 ≤ \mathbf{S}, \mathbf{T} ≤ N\)
• \(−90 ≤ latitude ≤ 90\)
• \(0 ≤ longitude ≤ 359\)
• No two airports are antipodal.
• No airport is located in a restricted area.
• For each restricted area, its endpoints are not antipodal.

Examples

Input:

3
89 0
-89 0
0 180
1
0 10 0 350
1 2

Output:

3.1764992386