Professor Joy, en ledande forskare i IOI-nationens historia, har fått en dagbok som tros ha skrivits av en forntida invånare i IOI-nationen. För att studera livet i den forntida IOI-nationen bestämde sig professor Joy för att undersöka händelserna som är nedtecknade i dagboken.

Dagboken innehåller anteckningar om händelser som inträffade under $N$ dagar, med en händelse noterad för varje dag. Händelser klassificeras i flera typer. Typen av händelse på dag $i$ ($1 \le i \le N$) representeras av ett heltal $X_i$. Man tror att ju större värdet på $X_i$ är, desto större är händelsens omfattning.

Professor Joy bestämde sig för att analysera dagboken med följande metod:

1. Välj ett antal på varandra följande dagar inom dagbokens $N$ dagar som analysperiod.
2. Betydelsen av en händelsetyp $t$ definieras som $t \times (\text{the number of events of type } t \text{ in that period})$ (dvs. $t$ multiplicerat med antalet händelser av typ $t$ under den perioden).
3. Beräkna betydelsen för alla händelsetyper och hitta det största värdet.

Du har fått i uppdrag av professor Joy att skapa ett program för denna analys. Programmet ska kunna hitta den största betydelsen när det ges en analysperiod.

Uppgift

Givet händelsetyperna för de $N$ dagarna i dagboken och $Q$ frågor som representerar perioder i dagboken, skriv ett program som hittar den största betydelsen av händelser för varje fråga.

Indata

Läs följande data från standard inmatning:

• Den första raden innehåller två heltal $N$ och $Q$ separerade med ett mellanslag, vilket anger att dagboken täcker $N$ dagar och att det finns $Q$ frågor.
• Nästa rad innehåller $N$ heltal $X_1, \dots, X_N$ separerade med mellanslag, där $X_i$ ($1 \le i \le N$) representerar händelsetypen på dag $i$.
• Var och en av de följande $Q$ raderna (för $1 \le j \le Q$) innehåller två heltal $A_j$ och $B_j$ ($1 \le A_j \le B_j \le N$) separerade med ett mellanslag, vilket anger att den $j$-te frågan gäller perioden från dag $A_j$ till dag $B_j$.

Utdata

Skriv ut $Q$ rader till standard utmatning. Den $j$-te raden ($1 \le j \le Q$) ska innehålla ett heltal som representerar den största betydelsen för den $j$-te frågan.

Begränsningar

All indata uppfyller följande villkor:

• $1 \le N \le 100\,000$.
• $1 \le Q \le 100\,000$.
• $1 \le X_i \le 1\,000\,000\,000$ ($1 \le i \le N$).

Deluppgifter

Deluppgift 1 [5 poäng]

• $N \le 100$.
• $Q \le 100$.

Deluppgift 2 [10 poäng]

• $N \le 5\,000$.
• $Q \le 5\,000$.

Deluppgift 3 [25 poäng]

• Det finns inga $i, j$ ($1 \le i \le Q, 1 \le j \le Q, i \neq j$) sådana att $A_i \le A_j \le B_j \le B_i$.

Deluppgift 4 [60 poäng]

• Inga ytterligare begränsningar.

Exempel

Indata 1

5 5
9 8 7 8 9
1 2
3 4
4 4
1 4
2 4

Utdata 1

9
8
8
16
16

Förklaring 1

• Denna dagbok består av 5 dagar, och de noterade händelsetyperna är 7, 8 eller 9.
• För perioden från dag 1 till dag 2 är betydelsen av händelsetyp 7 lika med $7 \times 0 = 0$, händelsetyp 8 är $8 \times 1 = 8$ och händelsetyp 9 är $9 \times 1 = 9$. Det största av dessa är 9.
• För perioden från dag 3 till dag 4 är betydelsen av händelsetyp 7 lika med $7 \times 1 = 7$, händelsetyp 8 är $8 \times 1 = 8$ och händelsetyp 9 är $9 \times 0 = 0$. Det största av dessa är 8.
• För dag 4 är betydelsen av händelsetyp 7 lika med $7 \times 0 = 0$, händelsetyp 8 är $8 \times 1 = 8$ och händelsetyp 9 är $9 \times 0 = 0$. Det största av dessa är 8.
• För perioden från dag 1 till dag 4 är betydelsen av händelsetyp 7 lika med $7 \times 1 = 7$, händelsetyp 8 är $8 \times 2 = 16$ och händelsetyp 9 är $9 \times 1 = 9$. Det största av dessa är 16.
• För perioden från dag 2 till dag 4 är betydelsen av händelsetyp 7 lika med $7 \times 1 = 7$, händelsetyp 8 är $8 \times 2 = 16$ och händelsetyp 9 är $9 \times 0 = 0$. Det största av dessa är 16.

Indata 2

8 4
9 9 19 9 9 15 9 19
1 4
4 6
3 5
5 8

Utdata 2

27
18
19
19

Förklaring 2

Denna indata uppfyller begränsningarna för Deluppgift 3.

Indata 3

12 15
15 9 3 15 9 3 3 8 16 9 3 17
2 7
2 5
2 2
1 12
4 12
3 6
11 12
1 7
2 6
3 5
3 10
7 10
1 4
4 8
4 8

Utdata 3

18
18
9
30
18
15
17
30
18
15
18
16
30
15
15