Taro loves a game called Vongress. Vongress is a camp game played on a board that is a convex polygon consisting of n vertices.

In this game, m players place one piece each inside the board. The position of the piece is represented by a set of x-coordinate and y-coordinate, and the size of the piece is not considered.

A player's position is an area on the board that consists of the closest piece placed by that person. Players get the area of ​​their base as a score.

Taro always recorded the shape of the board, the position of the placed piece, and the score of each player, but one day he inadvertently forgot to record the position of the piece. Therefore, Taro decided to add the consistent position of the piece from the shape of the board and the score of the player.

Your job is to find the position of the piece that is consistent with each player's score on behalf of Taro.

Input

The input is given in the following format.

n m
x1 y1
x2 y2
::
xn yn
r1
r2
::
rm

n is the number of vertices of the convex polygon that is the board, and m is the number of players. (xi, yi) represents the coordinates of the vertices of the board. r1, ..., rm represent the ratio of scores obtained by each player.

Constraints

• 3 ≤ n ≤ 100
• 1 ≤ m ≤ 100
• −104 ≤ xi, yi ≤ 104
• 1 ≤ rj ≤ 100
• All inputs are integers.
• The vertices (xi, yi) of the convex polygon are given in the counterclockwise order.

Output

Output the positions of m pieces in the following format.

x'1 y'1
x'2 y'2
::
x'm y'm

(x'k, y'k) is the position of the kth player's piece.

The output must meet the following conditions:

• The piece is inside the convex polygon. It may be on the border.
• Both pieces are more than 10-5 apart.
• Let S be the area of ​​the given convex polygon. The absolute or relative error with $\ frac {r_k} {r_1 + ... + r_m} S$ for the area of ​​the kth player's position obtained from the output is less than 10-3.

Sample Input 1

4 5
1 1
-1 1
-1 -1
1 -1
1
1
1
1
1

Output for the Sample Input 1

0.0000000000 0.0000000000
0.6324555320 0.6324555320
-0.6324555320 0.6324555320
-0.6324555320 -0.6324555320
0.6324555320 -0.6324555320

By arranging the pieces as shown in the figure below, all players can get the same score. The black line segment represents the board, the red dot represents the player's piece, and the blue line segment represents the boundary line of the player's position.

Vongress

Sample Input 2

4 3
1 1
-1 1
-1 -1
1 -1
9
14
9

Output for the Sample Input 2

-0.5 -0.5
0 0
0.5 0.5

Arrange the pieces as shown in the figure below.

Vongress

Sample Input 3

8 5
2 0
1 2
-1 2
-twenty one
-twenty one
0 -2
1-2
twenty one
3
6
9
3
Five

Output for the Sample Input 3

1.7320508076 -0.5291502622
1.4708497378 -0.2679491924
-0.4827258592 0.2204447068
-0.7795552932 0.5172741408
-1.0531143674 0.9276127521

Arrange the pieces as shown in the figure below.

Vongress

Example

Input

4 5
1 1
-1 1
-1 -1
1 -1
1
1
1
1
1

Output

0.0000000000 0.0000000000
0.6324555320 0.6324555320
-0.6324555320 0.6324555320
-0.6324555320 -0.6324555320
0.6324555320 -0.6324555320

见题面

见题面