Buses (1000 points)

There are N bus routes in our city, each going around a polygon shaped path with fixed schedule. We would like to know the shortest path between two given points in the city.

You can get off from a bus at any time and then wait there until some other bus gets close enough. You can take a bus if it is not more than R distance away.

Starting from a given (X0,Y0) point, the goal is to get within R distance to a given (X1,Y1) destination point.

  

Input

The first line of the input contains six integers: X0 Y0 X1 Y1 R N.

The following N lines describe the bus routes: the first integer is P, the number of vertices in the route, the second integer is the time it takes for the bus to finish one side of the polygon (a side is an edge of the polygon and each of them takes the same amount of time, no matter how long that edge is, but within the edge the bus travels at constant velocity), then 2P integer follows, the (X,Y) coordinates of the vertices of the polygon in the order the bus visits them in one round. Each bus starts at the first given vertex at time 0.

Output

The first line of the output contains two numbers: the overall time to reach the destination and K the number of buses it takes to get there.

The following K lines contain three numbers: the index of the bus to take, the time when one should get on that bus and the time when one should get off.

Note that the numbers in the input are all integers, but time parameters in the output are reals. We will check the output with 0.0001 precision. The overall time should be optimal. Buses are indexed from 0 in the order they appear in the input.

Example input

0 0 3 0 1 3
3 1 0 2 1 1 0 1
3 3 1 2 2 0 1 0
4 1 2 2 2 1 4 1 4 2

Example output

5.5000 2
0 2.0000 4.0000
2 5.0000 5.5000

Scoring

Each solved input is worth 100 points.