MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }}); blockquote { font-family: Menlo, Monaco, "Courier New", monospace; color: #333333; display: block; padding: 8.5px; margin: 0 0 9px; font-size: 12px; line-height: 18px; background-color: #f5f5f5; border: 1px solid #ccc; border: 1px solid rgba(0, 0, 0, 0.15); -webkit-border-radius: 4px; -moz-border-radius: 4px; border-radius: 4px; white-space: pre; white-space: pre-wrap; word-break: break-all; word-wrap: break-word; }

Problem Statement

太郎君はVongressと呼ばれるゲームが大好きである． Vongressとは，$n$ 頂点からなる凸多角形である盤の上で行われる陣取りゲームである．

このゲームでは，$m$ 人のプレイヤーが，盤の内側にそれぞれ1つ駒を置く． 駒の位置は $x$ 座標と $y$ 座標の組で表され，駒の大きさは考えない．

あるプレイヤーの陣地とは，盤上でその人が置いた駒が最も近くにあるような場所からなる領域である． プレイヤーは，自分の陣地の面積をスコアとして得る．

太郎君はいつも盤の形状，置かれた駒の位置，各プレイヤーのスコアを記録していたが， ある日うっかり駒の位置を記録するのを忘れてしまった． そこで太郎君は，盤の形状とプレイヤーの得点から，矛盾のない駒の位置を書き加えることにした．

あなたの仕事は，太郎君に代わって各プレイヤーの得点と矛盾しない駒の位置を求めることである．

Input

入力は以下の形式で与えられる．

$n$ $m$
$x\_1$ $y\_1$
$x\_2$ $y\_2$
:
:
$x\_n$ $y\_n$
$r\_1$
$r\_2$
:
:
$r\_m$

$n$ は盤である凸多角形の頂点数，$m$ はプレイヤーの数を表す． $(x\_i,y\_i)$ は盤の頂点の座標を表す． $r\_1,\\ldots,r\_m$ は各プレイヤーが得たスコアの比を表す．

Constraints

• $3\\le n \\le 100$
• $1\\le m \\le 100$
• $-10^4 \\le x\_i,y\_i \\le 10^4$
• $1\\le r\_j \\le 100$
• 入力は全て整数である．
• 凸多角形の頂点 $(x\_i,y\_i)$ は反時計回りの順番で与えられる．

Output

$m$ 個の駒の位置を以下の形式で出力せよ．

$x'\_1$ $y'\_1$
$x'\_2$ $y'\_2$
:
:
$x'\_m$ $y'\_m$

$(x'\_k,y'\_k)$は，$k$番目のプレイヤーの駒の位置である．

出力は次の条件を満たさなければならない．

• 駒が凸多角形の内側にある．境界線上にあってもよい．
• どの2つの駒も $10^{-5}$ 以上距離が離れている．
• 与えられる凸多角形の面積を $S$ とする． 出力から求まる $k$ 番目のプレイヤーの陣地の面積について， $\\frac{r\_k}{r\_1+\\cdots+r\_m}S$ との絶対誤差または相対誤差が $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

```plain
0.0000000000 0.0000000000
0.6324555320 0.6324555320
-0.6324555320 0.6324555320
-0.6324555320 -0.6324555320
0.6324555320 -0.6324555320```

下図のように駒を配置すれば，全プレイヤーが同じスコアを得られる． 黒い線分が盤，赤い点がプレイヤーの駒，青い線分がプレイヤーの陣地の境界線をそれぞれ表す．

![](/img/other/jag2014_summer_day4/sample1.png)

* * *

### Sample Input 2

```plain
4 3
1 1
-1 1
-1 -1
1 -1
9
14
9```

### Output for the Sample Input 2

```plain
-0.5 -0.5
0 0
0.5 0.5```

下図のように駒を配置すればよい．

![](/img/other/jag2014_summer_day4/sample2.png)

* * *

### Sample Input 3

```plain
8 5
2 0
1 2
-1 2
-2 1
-2 -1
0 -2
1 -2
2 -1
3
6
9
3
5```

### Output for the Sample Input 3

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

下図のように駒を配置すればよい．

![](/img/other/jag2014_summer_day4/sample3.png)

* * *