Sharing Chocolate

George loves chocolate, so he bought a large rectangular bar to share with his family.

While absentmindedly watching TV, he carelessly cut out and ate several rectangular pieces from the interior of the chocolate. Now George is left with a large rectangular chocolate bar that may contain several rectangular holes. These holes may overlap, creating more complex empty regions inside the chocolate.

George wants to divide the remaining chocolate among the K members of his family using K - 1 vertical cuts, so that the resulting pieces have areas as equal as possible.

He asked for your help to find the x-coordinates of the vertical cuts that divide the chocolate into K strips of equal area.

Input

The first line contains four real numbers x1 y1 x2 y2: the coordinates of the bottom-left (~x_1, y_1~) and top-right (~x_2, y_2~) corners of the original rectangular chocolate bar.

The second line contains an integer M: the number of rectangular pieces that George has already eaten.

Each of the next M lines contains four real numbers a b c d: the coordinates of the bottom-left (~a, b~) and top-right (~c, d~) corners of the i-th rectangular piece that was removed.

The last line contains an integer K: the number of family members.

Constraints

• ~0 \le x_1 < x_2 \le 10^{18}~
• ~0 \le y_1 < y_2 \le 10^{18}~`
• ~0 \le M \le 10^{5}~
• ~x_1 \le a < c \le x_2~
• ~y_1 \le b < d \le y_2~
• ~2 < K < 10 ^ {5}~

Output

Print K - 1 real numbers, each corresponding to the x-coordinate of a vertical cut.

The numbers must:

• be printed in increasing order
• divide the remaining chocolate into K pieces of equal area

Scoring

Your solution will be tested on the following subtasks:

A solution is considered correct for a test case if the relative error of each cut compared to the expected cut is at most ~10^{-6}~.

Examples

Input (STDIN)

0 0 9 7
4
2 2 8 3
3 1 5 6
6 4 7 6
1 4 2 5
3

Output (STDOUT)

2.38888889
6.41666667

Input (STDIN)

0 0 10 10
2
2 2 7 8
5 5 9 9
4

Output (STDOUT)

1.50000000
4.50000000
8.16666667

Explanation of the second example: