Prófessor Joy, fremsti sérfræðingur í sögu IOI-ríkisins, hefur fengið í hendur dagbók sem talin er hafa verið skrifuð af fornum íbúa IOI-ríkisins. Til að rannsaka lífið í hinu forna IOI-ríki ákvað prófessor Joy að kanna atburðina sem skráðir eru í dagbókina.

Dagbókin inniheldur færslur um atburði sem áttu sér stað á $N$ dögum, þar sem einn atburður er skráður fyrir hvern dag. Atburðir eru flokkaðir í nokkrar gerðir. Gerð atburðar á degi $i$ ($1 \le i \le N$) er táknuð með heiltölu $X_i$. Talið er að því hærra sem gildið á $X_i$ er, því umfangsmeiri hafi atburðurinn verið.

Prófessor Joy ákvað að greina dagbókina með eftirfarandi aðferð:

1. Velja samfelldan fjölda daga innan hinna $N$ daga dagbókarinnar sem greiningartímabil.
2. Mikilvægi atburðargerðar $t$ er skilgreint sem $t \times (\text{the number of events of type } t \text{ in that period})$ (þ.e. $t$ margfaldað með fjölda atburða af gerð $t$ á því tímabili).
3. Reikna mikilvægið fyrir allar atburðargerðir og finna hæsta gildið.

Prófessor Joy hefur falið þér að búa til forrit fyrir þessa greiningu. Forritið á að geta fundið mesta mikilvægið þegar greiningartímabil er gefið.

Verkefni

Gefið atburðargerðirnar fyrir hina $N$ daga dagbókarinnar og $Q$ fyrirspurnir sem tákna tímabil í dagbókinni, skrifið forrit sem finnur mesta mikilvægi atburða fyrir hverja fyrirspurn.

Inntak

Lesið eftirfarandi gögn úr staðalinntaki:

• Fyrsta línan inniheldur tvær heiltölur $N$ og $Q$ aðskildar með bili, sem tákna að dagbókin nái yfir $N$ daga og að það séu $Q$ fyrirspurnir.
• Næsta lína inniheldur $N$ heiltölur $X_1, \dots, X_N$ aðskildar með bilum, þar sem $X_i$ ($1 \le i \le N$) táknar atburðargerðina á degi $i$.
• Hver af næstu $Q$ línum (fyrir $1 \le j \le Q$) inniheldur tvær heiltölur $A_j$ og $B_j$ ($1 \le A_j \le B_j \le N$) aðskildar með bili, sem tákna að $j$-ta fyrirspurnin sé fyrir tímabilið frá degi $A_j$ til dags $B_j$.

Úttak

Skrifið út $Q$ línur í staðalúttak. $j$-ta línan ($1 \le j \le Q$) á að innihalda heiltölu sem táknar mesta mikilvægið fyrir $j$-tu fyrirspurnina.

Takmarkanir

Öll inntaksgögn uppfylla eftirfarandi skilyrði:

• $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$).

Undirverkefni

Undirverkefni 1 [5 stig]

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

Undirverkefni 2 [10 stig]

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

Undirverkefni 3 [25 stig]

• Það eru engin $i, j$ ($1 \le i \le Q, 1 \le j \le Q, i \neq j$) þannig að $A_i \le A_j \le B_j \le B_i$.

Undirverkefni 4 [60 stig]

• Engar frekari takmarkanir.

Dæmi

Inntak 1

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

Úttak 1

9
8
8
16
16

Athugasemd 1

• Þessi dagbók samanstendur af 5 dögum og skráðar atburðargerðir eru 7, 8 eða 9.
• Fyrir tímabilið frá degi 1 til dags 2 er mikilvægi atburðargerðar 7 jafnt og $7 \times 0 = 0$, atburðargerðar 8 er $8 \times 1 = 8$ og atburðargerðar 9 er $9 \times 1 = 9$. Hæsta gildið af þessum er 9.
• Fyrir tímabilið frá degi 3 til dags 4 er mikilvægi atburðargerðar 7 jafnt og $7 \times 1 = 7$, atburðargerðar 8 er $8 \times 1 = 8$ og atburðargerðar 9 er $9 \times 0 = 0$. Hæsta gildið af þessum er 8.
• Fyrir dag 4 er mikilvægi atburðargerðar 7 jafnt og $7 \times 0 = 0$, atburðargerðar 8 er $8 \times 1 = 8$ og atburðargerðar 9 er $9 \times 0 = 0$. Hæsta gildið af þessum er 8.
• Fyrir tímabilið frá degi 1 til dags 4 er mikilvægi atburðargerðar 7 jafnt og $7 \times 1 = 7$, atburðargerðar 8 er $8 \times 2 = 16$ og atburðargerðar 9 er $9 \times 1 = 9$. Hæsta gildið af þessum er 16.
• Fyrir tímabilið frá degi 2 til dags 4 er mikilvægi atburðargerðar 7 jafnt og $7 \times 1 = 7$, atburðargerðar 8 er $8 \times 2 = 16$ og atburðargerðar 9 er $9 \times 0 = 0$. Hæsta gildið af þessum er 16.

Inntak 2

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

Úttak 2

27
18
19
19

Athugasemd 2

Þetta inntak uppfyllir skilyrði Undirverkefnis 3.

Inntak 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

Úttak 3

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