G. Square Permutation II
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Give two permutations $$$p$$$ and $$$q$$$ of length $$$n$$$. It is guaranteed that $$$n$$$ is an odd number. You must perform exactly one of the following operations for each position $$$i \in [1,n]$$$:

  1. Perform no operation at no cost.
  2. Spend a cost of $$$x$$$ to either modify $$$p_i$$$ to $$$p_i^2$$$ or modify $$$q_i$$$ to $$$q_i^2$$$.
  3. Spend a cost of $$$y$$$ to modify both $$$p_i$$$ to $$$p_i^2$$$ and $$$q_i$$$ to $$$q_i^2$$$.

There are a total of $$$m$$$ groups of queries in this problem. For each query, values of $$$x$$$ , $$$y$$$ , $$$A$$$ and $$$B$$$ are given.Please find the minimum cost required to make the median of array $$$p$$$ equal to $$$A$$$ and the median of array $$$q$$$ equal to $$$B$$$. If it's impossible, output $$$-1$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ $$$(1 \leq t \leq 10^4)$$$ . The description of the test cases follows.

The first line of each test case contains two single integers $$$n,m$$$ $$$(1\leq n,m\leq 10^5)$$$.

The second line gives $$$n$$$ positive integers, representing the permutation $$$p$$$.

The third line gives $$$n$$$ positive integers, representing the permutation $$$q$$$.

The next $$$m$$$ lines each contain four positive integers $$$A$$$, $$$B$$$, $$$x$$$, and $$$y$$$ $$$(1 \leq A,B \leq n^2,1 \leq x \leq y \leq 10^9)$$$.

It is guaranteed that the sum of $$$n$$$ and $$$m$$$ over all test cases does not exceed $$$10^5$$$.

Output

For each set of data, output $$$m$$$ lines. The $$$i$$$-th line contains an integer representing the answer to the $$$i$$$-th query.

Example
Input
1
5 6
1 3 2 5 4
3 2 1 4 5
4 9 1 4
5 9 1 3
5 16 3 3
16 5 3 4
5 5 2 3
9 9 10 11
Output
4
6
-1
-1
8
42