IOI елінің тарихын зерттеуші жетекші ғалым профессор Джой ежелгі IOI елінің тұрғыны жазған деп есептелетін күнделікті алды. Ежелгі IOI еліндегі өмірді зерттеу үшін профессор Джой күнделікте жазылған оқиғаларды зерттеуді ұйғарды.

Күнделікте $N$ күн ішінде болған оқиғалар туралы жазбалар бар, әр күн үшін бір оқиға тіркелген. Оқиғалар бірнеше түрге бөлінеді. $i$-ші күнгі ($1 \le i \le N$) оқиғаның түрі бүтін сан $X_i$ арқылы беріледі. $X_i$ мәні неғұрлым үлкен болса, оқиғаның ауқымы соғұрлым үлкен болған деп есептеледі.

Профессор Джой күнделікті келесі әдіспен талдауды шешті:

1. Талдау кезеңі ретінде күнделіктегі $N$ күннің ішінен қатарынан бірнеше күнді таңдау.
2. $t$ оқиға түрінің маңыздылығы $t \times (\text{the number of events of type } t \text{ in that period})$ ретінде анықталады (яғни, $t$ санын сол кезеңдегі $t$ типті оқиғалар санына көбейту).
3. Барлық оқиға түрлері үшін маңыздылықты есептеп, ең үлкен мәнді табу.

Профессор Джой сізге осы талдауға арналған программа құруды тапсырды. Программа талдау кезеңі берілгенде ең үлкен маңыздылықты таба алуы керек.

Тапсырма

Күнделіктің $N$ күніндегі оқиға түрлері және күнделіктегі кезеңдерді білдіретін $Q$ сұраныс берілген, әр сұраныс үшін оқиғалардың ең үлкен маңыздылығын табатын программа жазыңыз.

Кіріс деректер

Стандартты кірістен келесі деректерді оқыңыз:

• Бірінші жолда бос орынмен бөлінген екі бүтін сан $N$ және $Q$ берілген, бұл күнделік $N$ күнді қамтитынын және $Q$ сұраныс бар екенін білдіреді.
• Келесі жолда бос орынмен бөлінген $N$ бүтін сан $X_1, \dots, X_N$ берілген, мұндағы $X_i$ ($1 \le i \le N$) $i$-ші күнгі оқиға түрін білдіреді.
• Келесі $Q$ жолдың әрқайсысында ($1 \le j \le Q$ үшін) бос орынмен бөлінген екі бүтін сан $A_j$ және $B_j$ ($1 \le A_j \le B_j \le N$) берілген, бұл $j$-ші сұраныс $A_j$-ші күннен $B_j$-ші күнге дейінгі кезеңге арналғанын білдіреді.

Шығыс деректер

Стандартты шығысқа $Q$ жол шығарыңыз. $j$-ші жолда ($1 \le j \le Q$) $j$-ші сұраныс үшін ең үлкен маңыздылықты білдіретін бүтін сан болуы керек.

Шектеулер

Барлық кіріс деректер келесі шарттарды қанағаттандырады:

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

Ішкі тапсырмалар

Ішкі тапсырма 1 [5 ұпай]

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

Ішкі тапсырма 2 [10 ұпай]

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

Ішкі тапсырма 3 [25 ұпай]

• $A_i \le A_j \le B_j \le B_i$ болатындай $i, j$ ($1 \le i \le Q, 1 \le j \le Q, i \neq j$) жоқ.

Ішкі тапсырма 4 [60 ұпай]

• Қосымша шектеулер жоқ.

Мысалдар

Кіріс 1

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

Шығыс 1

9
8
8
16
16

Ескертпе 1

• Бұл күнделік 5 күннен тұрады және тіркелген оқиға түрлері — 7, 8 немесе 9.
• 1-ші күннен 2-ші күнге дейінгі кезең үшін 7-ші оқиға түрінің маңыздылығы $7 \times 0 = 0$, 8-ші оқиға түрінікі $8 \times 1 = 8$, ал 9-шы оқиға түрінікі $9 \times 1 = 9$. Олардың ішіндегі ең үлкені — 9.
• 3-ші күннен 4-ші күнге дейінгі кезең үшін 7-ші оқиға түрінің маңыздылығы $7 \times 1 = 7$, 8-ші оқиға түрінікі $8 \times 1 = 8$, ал 9-шы оқиға түрінікі $9 \times 0 = 0$. Олардың ішіндегі ең үлкені — 8.
• 4-ші күн үшін 7-ші оқиға түрінің маңыздылығы $7 \times 0 = 0$, 8-ші оқиға түрінікі $8 \times 1 = 8$, ал 9-шы оқиға түрінікі $9 \times 0 = 0$. Олардың ішіндегі ең үлкені — 8.
• 1-ші күннен 4-ші күнге дейінгі кезең үшін 7-ші оқиға түрінің маңыздылығы $7 \times 1 = 7$, 8-ші оқиға түрінікі $8 \times 2 = 16$, ал 9-шы оқиға түрінікі $9 \times 1 = 9$. Олардың ішіндегі ең үлкені — 16.
• 2-ші күннен 4-ші күнге дейінгі кезең үшін 7-ші оқиға түрінің маңыздылығы $7 \times 1 = 7$, 8-ші оқиға түрінікі $8 \times 2 = 16$, ал 9-шы оқиға түрінікі $9 \times 0 = 0$. Олардың ішіндегі ең үлкені — 16.

Кіріс 2

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

Шығыс 2

27
18
19
19

Ескертпе 2

Бұл кіріс Ішкі тапсырма 3 шектеулерін қанағаттандырады.

Кіріс 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

Шығыс 3

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