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.

Testing Program Method

The grader.cpp in the problem directory is a reference implementation of the interactor. The interactor used in the actual testing is different from this reference implementation, so the contestant's solution should not rely on the implementation details of the interactor.

Contestants can compile the executable program in the problem directory using the following command:

g++ grader.cpp signal.cpp -o signal -std=gnu++14 -O2 -pipe -static -s

For the compiled executable program:

• The executable program will read data from standard input in the following format:
  • The first line of input contains a positive integer $t$, representing the number of test cases.
  • Then, for each test case in order:
    • The first line contains two positive integers $n, q$, representing the number of communication stations and the number of queries, respectively.
    • The second line contains $n$ integers $a_1, \dots, a_n$, representing the transmission coefficient of each communication station.
    • The third line contains $n$ integers $b_1, \dots, b_n$, representing the reception coefficient of each communication station.
    • The $(i + 3)$-th line ($1 \le i \le q$) contains two positive integers $l, r$, representing the range of indices of the stations that are in operation during the $i$-th query.
• The executable program will output data to standard output in the following format:
  • For each test case, output a line containing $q$ integers, representing the minimum cost to join all the operating communication stations into the same communication system using the fewest possible bidirectional signal connections for each query.

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.

Additional Files

In the additional files:

1. grader.cpp is the provided reference implementation of the interactor.
2. signal.h is the header file, which contestants do not need to worry about its specific content.
3. template_signal.cpp is the provided sample code, which contestants can refer to and use to implement their own code.

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$.

Grading

Note

• Contestants should not obtain internal information of the interactor through illegal means, such as directly interacting with standard input and output streams. Such behavior will be regarded as cheating.
• The final testing interactor is different from the sample interactor implementation.

This problem is first subject to the same constraints as traditional problems. For example, compilation errors will result in 0 points for the entire problem, and runtime errors, exceeding time limits, or exceeding memory limits will result in 0 points for the corresponding test cases. Contestants can only access variables defined by themselves and variables provided by the interactor in the program. Attempting to access other address spaces may lead to compilation errors or runtime errors.

On the basis of the above conditions:

• For each test case, the program receives full score if and only if the answer returned by each call to the mincost function is correct.