There are $n$ communication stations in space, numbered $1 \sim n$. Each station $i$ ($1 \le i \le n$) has two parameters: a transmission coefficient $a_i$ and a reception coefficient $b_i$.

If station $i$ ($1 \le i \le n$) transmits a signal to station $j$ ($1 \le j \le n$), a bidirectional signal connection is established between these two stations with a cost of $a_i b_j$. Since stations may absorb energy from cosmic rays, the cost can be negative. To establish a bidirectional signal connection between stations $i$ and $j$ ($1 \le i, j \le n$), one can choose either station as the transmitter to initiate the connection, so the minimum cost is $\min(a_i b_j, a_j b_i)$. When a signal connection is established directly between two stations, or indirectly through other stations, these two stations can join the same communication system.

To reduce costs, often only a subset of stations are in operation. You need to determine, for stations with indices in the range $l \sim r$, the minimum cost to join all these stations into the same communication system by establishing the fewest possible bidirectional signal connections when only these stations can establish signal connections.

Implementation Details

You do not need to, and should not, implement the main function.

You must ensure that your submitted program includes the header file signal.h by adding the following code at the beginning of your program:

#include "signal.h"

You need to implement the following two functions in your submitted source file:

void signal(int n, std::vector<int> a, std::vector<int> b);

• $n$ represents the number of communication stations.
• For $1 \le i \le n$, $a_i$ represents the transmission coefficient of station $i$, and $b_i$ represents the reception coefficient of station $i$. Note: $a$ and $b$ are two sequences of length $n+1$, where $a_0$ and $b_0$ have no actual meaning.
• Note: For each test case, this function may be called multiple times by the interactor.

long long mincost(int l, int r);

• $l, r$ represent the range of indices of the stations that are in operation.
• This function needs to return the minimum cost to join all these stations into the same communication system using the fewest possible bidirectional signal connections.
• Note: The transmission and reception coefficients of the stations are the parameters passed during the most recent call to the signal function.
• All calls to this function occur after at least one call to the signal function.

Note: In any case, the execution time of the interactor will not exceed 0.1 seconds, and the memory used is fixed and will not exceed 64 MiB.

Examples

Input 1

2
2 3 1
3 1 1 4
4 5 1 4
5 1 3
6 5 2
7 3 1 4 -1 -5
8 9 2 -6 5 -3
9 1 4
10 2 5

Output 1

5
-33 -47

Note

The example contains two test cases. For the first test case, all stations are in operation during the query. One can transmit signals from station 1 to stations 2 and 3, with a cost of $1 \times 1 + 1 \times 4 = 5$. At this point, all stations can join the same communication system.

Subtasks

Let $N, Q$ denote the sum of $n, q$ across all test cases in a single test point. For all test cases:

• $1 \le t \le 10^5$;
• $1 \le n, q \le 10^5$, $N, Q \le 10^5$;
• For all $1 \le i \le n$, $|a_i|, |b_i| \le 10^6$;
• $1 \le l \le r \le n$.

Special Property A: For all $1 \le i \le n$, $a_i, b_i > 0$. Special Property B: For all $1 \le i \le n$, $a_i b_i < 0$.