Background

 If the evening sun shines into the corner of a cold room.
 In the corner of an icy room, it is filled with the glow of the sunset.
 Even if you get closer, there are no feelings, and there is no betrayal.
 No matter how close you get, there are no emotions, and there are no changes.

 Today and tomorrow, I am alone, and surely that is something normal.
 Even if I am alone from now on, it is just an ordinary thing.
 Without any words to exchange, when the day comes to an end.
 Even talking cannot change the ending of this day.

 For example, how much warmth is “kindness”.
 For example, what exactly is gentleness like.
 Without even knowing what warmth might be.
 Without even knowing how to obtain warmth.
 It is not that easy, not that easy.
 So, so, it is not that simple.
 The distance between hearts.
 The distance of the heart.

 In the corner of a cold room, staying small as it is.
 In the corner of an icy room, just stay small like this.

Problem Description

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$, compute:

$\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}]$ equals $1$ when the condition $\mathrm{cond}$ is true, otherwise it equals $0$.

Input Format

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 Format

Output $m$ lines, each containing one integer, the answer to the corresponding query.

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

0
1
1
0

Hint

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

For $100\%$ of the testdata, $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 $20\%$ of the testdata, $n, m\le 100$.

For $40\%$ of the testdata, $n, m\le 5000$.

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

Translated by ChatGPT 5