I. Tiger Textbooks
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The Tiger Little Lu is very interested in biology!

In fact, he owns $$$n$$$ textbooks, with the $$$i$$$th textbook having a textbook topic represented by an integer $$$a_i.$$$ Little Lu enjoys reading certain books more than others. The $$$i$$$th textbook has an enjoyment value of $$$v_i$$$. Note that multiple textbooks can be about the same topic or have the same enjoyment value.

Today, Little Lu is feeling sad as he drinks boba all by himself. To distract himself from this loneliness, the Tiger decides to play a game that his friend Westin taught him.

The game goes as follows: Little Lu will consider all ordered pairs $$$(i,j)$$$, such that $$$L \leq i,j \leq R$$$. Then, for each ordered pair $$$(i,j)$$$:

  • Let $$$c_i$$$ be the number of distinct topics that Little Lu has $$$i$$$ textbooks about, and $$$c_j$$$ be the number of topics that he has $$$j$$$ textbooks about.
  • If $$$c_i \neq c_j$$$, Lu will add 0 to his score.
  • Otherwise, he will choose two indices $$$1 \leq x,y \leq n$$$ , with the highest possible value of $$$v_x \cdot v_y$$$ such that there are exactly $$$i$$$ books with topic $$$a_x$$$ and $$$j$$$ books with topic $$$a_y$$$, and add $$$v_x \cdot v_y$$$ to his score. (If he cannot select such $$$x$$$ and $$$y$$$ to satisfy the constraints, then $$$0$$$ will be added to the score instead.)

Unfortunately, he has forgotten what $$$L$$$ and $$$R$$$ were, so Little Lu will ask you $$$q$$$ questions, each with $$$l_i$$$, and $$$r_i$$$, asking to find the score he will achieve if he plays the game with the given $$$L = l_i$$$ and $$$R = r_i.$$$

He doesn't want to spend all day doing this, so help Lu the Little Tiger solve this problem!

Input

The first line contains two integers, $$$n$$$ and $$$q (1\leq n \leq 5\cdot 10^5, 1\leq q \leq 5\cdot 10^5).$$$

The second line contains $$$n$$$ integers, $$$a_1, a_2, ..... a_n, (1 \leq a_i \leq 10^9)$$$.

The third line contains $$$n$$$ integers, $$$v_1, v_2, ...v_n, (1 \leq v_i \leq 100).$$$

The last $$$q$$$ lines contain two integers, $$$l_i$$$ and $$$r_i (1\leq l_i \leq r_i \leq 10^9)$$$, each pair representing a query.

Output

For each query, print an integer representing the score Little Lu can obtain with the given values of $$$L$$$ and $$$R.$$$

Example
Input
12 6
1 1 2 2 2 3 4 4 6 6 7 7
10 4 9 4 5 2 6 1 8 7 3 2
1 2
1 3
3 3
2 3
1 12
4 4
Output
104
221
81
181
221
0
Note

Query $$$ \mathbf{1}$$$ : the ordered pairs are $$$$$$(1,1), (1,2), (2,1), (2,2).$$$$$$

$$$\mathbf{(1,1)}$$$: Lu can only choose $$$x = 6$$$ and $$$y = 6$$$, because the only textbook such that there is exactly $$$1$$$ book with its topic is textbook $$$6$$$, so $$$v_6 \cdot v_6=4$$$.

$$$\mathbf{(1,2)}$$$: there are $$$4$$$ topics that have exactly $$$2$$$ books about each topic, which are topics $$$1,4,6,7$$$. However, there is $$$1$$$ topic with exactly $$$1$$$ book about that topic, which is topic $$$3$$$. Thus, $$$0$$$ will be added to the score.

$$$\mathbf{(2,2)}$$$: we can choose $$$x = 1$$$, because there are exactly $$$i = 2$$$ books with topic $$$a_1$$$, and choose $$$y = 1$$$, because there are exactly $$$j = 2$$$ books with topic $$$a_1.$$$ It can be proven that the greatest product results from these choices for $$$x$$$ and $$$y$$$. $$$v_x \cdot v_y = 100$$$ will be added to the score.

$$$\mathbf{(2,1)}$$$: the number of topics that have $$$2$$$ books about them are different from the number of topics that have $$$1$$$ book about them, so $$$0$$$ is added to the score. Output for Query $$$ \mathbf{1}$$$ is $$$4+0+100+0 = \mathbf{104} .$$$

Additionally, the queries in sample that use the ordered pair $$$\mathbf {(1,3)} $$$ will add $$$\mathbf{18}$$$. The number of topics with exactly $$$3$$$ books about it and the number of topics with exactly $$$1$$$ book about it are both $$$1,$$$ so Lu can choose $$$x = 6$$$ and $$$y = 3,$$$ because there is exactly $$$1=i$$$ book with topic $$$a_6$$$ and $$$3=j$$$ books with topic $$$a_3$$$, and add $$$v_x \cdot v_y = 18$$$ to his score.