Given $n, m$, a sequence $a_1, a_2, \dots, a_n$, and a permutation $y_1, y_2, \dots, y_n$ of $1, 2, \dots, n$, you need to answer $m$ queries.

For each query, given $l, r$, calculate:

$$\sum\limits_{i=1}^n\sum\limits_{j=i+1}^n [a_i=a_j]\cdot\prod_{k=i}^j [l\le y_k\le r]$$

where $[\mathrm{cond}]$ is $1$ if the condition $\mathrm{cond}$ is true, and $0$ otherwise.

Input

The first line contains two integers $n, m$.

The second line contains $n$ integers $a_1, \dots, a_n$.

The third line contains $n$ integers $y_1, \dots, y_n$.

The next $m$ lines each contain two integers $l, r$ representing a query.

Output

Output $m$ lines, each containing an integer representing the corresponding answer.

Examples

Input 1

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

Output 1

0
1
1
0

Subtasks

Idea: Ynoi&nzhtl1477, Solution: Ynoi&ccz181078, Code: ccz181078, Data: ccz181078

For $100\%$ of the data, $1\le n, m\le 5\times 10^5$; $1\le a_i\le n$; $1\le y_i\le n$, and all $y_i$ are distinct; for each query, $1\le l\le r\le n$.

For $25\%$ of the data, $n, m\le 100$.

For $50\%$ of the data, $n, m\le 5000$.

For $75\%$ of the data, $n, m\le 2\times 10^5$.