You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

给定两个长度为 $n$ 的排列 $a_1,a_2,\dots,a_n$ 和 $b_1,b_2,\dots,b_n$。有 $q$ 个询问，每个询问给出 $l,r,L,R$，输出：

答案对 $2^{32}$ 取模。

输入格式

第一行两个正整数表示 $n,q$。

接下来两行，每行 $n$ 个正整数表示 $a,b$。

接下来 $q$ 行，每行四个正整数表示 $l,r,L,R$。

输出格式

$q$ 行，每行一个正整数表示答案。

样例

【样例输入】

5 5
4 1 5 3 2
1 2 3 4 5
3 3 2 3
3 4 2 4
3 4 3 4
5 5 1 1
1 1 2 2

【样例输出】

2
14
12
1
4

数据范围

$\color{white}{搬题人没有吗？}$