Vale of Eternal

$\space \space$*To ask why we fight?*

$\space \space$*Is to ask why the leaves fall?*

$\space \space$*It is in the nature.*

$\space \space$*Perhaps there is a better question.*

$\space \space$*Why do we fight?*

$\space \space$*To protect home and family,*

$\space \space$*To preserve balance and bring harmony.*

$\space \space$*For my kind,*

$\space \space$*The true question is what is worth fighting for.*

$\space \space \space \space \space \space \space \space\space \space \space \space \space \space \space \space\space \space \space \space \space \space \space \space\space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space\space \space \space \space \space \space \space \space\space \space \space \space \space \space \space \space\space \space \space \space \space \space \space \space$ *——CG《Mists of Pandaria》*

Chen is practicing Kungfu. He uses Chi Burst to make energy points split.

Initially, there are $n$ energy points on the infinite 2D plane, in every second, every energy point will check its four neighbouring positions (up $(0, 1)$, down $(0, -1)$, left $(-1, 0)$, right $(1, 0)$ ) If there is no energy point at that position, a new energy point will be generated at that position.

Chen would like to know the progress of the practice in advance. He will give you $q$ queries, each query consists of a single integer $t$, and you need to find the area of the convex polygon constructed by all energy points after $t$ seconds.

The input consists of multiple test cases.

The first line contains a single integer $T\ (1 \leq T \leq 11)$, denoting the number of test cases.

In each test case, the first line contains two integers $n,q(1 \leq n,q \leq 2*10^5)$, denoting the number of points initially and the number of queries.

The following $n$ lines, the $i$-th line contains two integers $x, y(0 \leq x, y \leq 10^8)$, denoting the coordinate of the $i$-th initial energy point.

Then following $q$ lines, each line contain one integer $t(0 \leq t \leq 10^8)$, denoting the number of seconds.

It's guaranteed that $\sum n \leq 5 * 10^5, \sum q \leq 5 * 10^5$.

For each query, output a single line, denoting the answer, your answer should be rounded to one decimal place.

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

11.0
24.0
41.0
27.0
45.0
67.0

2022“杭电杯”中国大学生算法设计超级联赛（8）