Neko and triangle

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 24 Accepted Submission(s): 0

Problem Description

Neko haves a sequence with

$n$ points, the

$i$ -th point is

$A_{i}$ . And she gets

$m$ key points.
Define the origin point is

$O = (0,0)$ .
For each key point

$P_{k}$ , you need to find a interval

$[l, r]$ to make

$\sum_{i = l} ^ {r} S_{i}$ max.

$S_{i}$ is the directed area of triangle

$\triangle OP_{k}A_{i}$ . There may be a lot of intervals suitable, so you only need output the sum of area.

Input

The first line contains two integers

$n, m(1 \leq n,m \leq 10^{5})$
The next

$n$ line, each line contains two integers

$x, y(0 \leq x,y \leq 10^{5})$ , means the coordinate of the

$i$ -th point

$A_{i}$ .
The next

$m$ line, each line contains two integers

$x, y(0 \leq x,y \leq 10^{5})$ , means the coordinate of the

$i$ -th key point

$P_{i}$ .

Output

For each key point, output the max area in one line. For convenience, please output twice the area.

Sample Input

Sample Output