给定两个长度为 $n$ 的排列 $p$ 和 $q$。保证 $n$ 是一个奇数。对于每个位置 $i \in [1, n]$，你必须执行以下操作中的恰好一种：

• 不进行任何操作，代价为 $0$。
• 花费 $x$ 的代价，将 $p_i$ 修改为 $p_i^2$，或者将 $q_i$ 修改为 $q_i^2$。
• 花费 $y$ 的代价，同时将 $p_i$ 修改为 $p_i^2$ 且将 $q_i$ 修改为 $q_i^2$。

本题共有 $m$ 组询问。对于每次询问，会给出 $x, y, A$ 和 $B$ 的值。请计算使得数组 $p$ 的中位数等于 $A$ 且数组 $q$ 的中位数等于 $B$ 所需的最小总代价。如果无法实现，则输出 $-1$。

输入格式

每个测试点包含多个测试用例。第一行包含一个整数 $t$ ($1 \le t \le 10^4$)，表示测试用例的数量。

接下来是每个测试用例的描述。

每个测试用例的第一行包含两个整数 $n, m$ ($1 \le n, m \le 10^5$)。

第二行包含 $n$ 个正整数，表示排列 $p$。

第三行包含 $n$ 个正整数，表示排列 $q$。

接下来的 $m$ 行，每行包含四个正整数 $A, B, x$ 和 $y$ ($1 \le A, B \le n^2$, $1 \le x \le y \le 10^9$)。

保证所有测试用例中 $n$ 的总和与 $m$ 的总和均不超过 $10^5$。

输出格式

对于每组数据，输出 $m$ 行。第 $i$ 行包含一个整数，表示第 $i$ 次询问的答案。

样例

样例输入 1

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

样例输出 1

4
6
-1
-1
8
42