وصلت إلى الأستاذ JOI، أحد أبرز الباحثين في تاريخ دولة IOI، يوميات يُقال إن أحد سكان IOI القدماء كتبها. قرر الأستاذ دراسة الأحداث المسجلة فيها للتعرف على الحياة في IOI القديمة.

تسجل هذه اليوميات أحداث $N$ أيام، بواقع حدث واحد لكل يوم. تُصنَّف الأحداث إلى عدة أنواع، ويُمثَّل نوع حدث اليوم $i$ ($1 \le i \le N$) بالعدد الصحيح $X_i$. ويُعتقد أن الحدث يكون أكبر حجمًا كلما كانت قيمة $X_i$ أكبر.

قرر الأستاذ JOI تحليل اليوميات بالطريقة التالية.

1. يختار عدة أيام متتالية من بين أيام اليوميات البالغ عددها $N$ لتكون فترة التحليل.
2. يعرّف أهمية نوع الأحداث $t$ بأنها $t \times (\text{عدد أحداث النوع }t\text{ خلال تلك الفترة})$.
3. يحسب الأهمية لكل أنواع الأحداث، ثم يجد أكبر قيمة بينها.

طلب منك الأستاذ JOI كتابة برنامج للتحليل. نريد أن يتمكن البرنامج من إيجاد أكبر قيمة للأهمية عند إعطائه فترة التحليل.

المهمة

بإعطائك أنواع الأحداث في أيام اليوميات البالغ عددها $N$، و$Q$ استعلامات يمثل كل منها فترة ضمن اليوميات، اكتب برنامجًا يجد أكبر قيمة لأهمية الأحداث لكل استعلام.

الإدخال

اقرأ البيانات التالية من الإدخال القياسي.

• يحتوي السطر الأول على العددين الصحيحين $N$ و$Q$ مفصولين بمسافة. وهذا يعني أن اليوميات تغطي $N$ أيام، وأن هناك $Q$ استعلامات.
• يحتوي السطر التالي على $N$ أعداد صحيحة $X_1,\ldots,X_N$ مفصولة بمسافات. يمثّل $X_i$ ($1 \le i \le N$) نوع حدث اليوم $i$.
• يحتوي السطر $j$ من الأسطر $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 نقطة]

• لا يوجد $i,j$ ($1 \le i \le Q$، $1 \le j \le Q$، $i \ne j$) يحققان $A_i \le A_j \le B_j \le B_i$.

المهمة الفرعية 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

ملاحظة

• تتكون هذه اليوميات من $5$ أيام، وأنواع الأحداث المسجلة فيها هي $7$ أو $8$ أو $9$.
• من اليوم $1$ إلى اليوم $2$، أهمية النوع $7$ هي $7\times0=0$، وأهمية النوع $8$ هي $8\times1=8$، وأهمية النوع $9$ هي $9\times1=9$، لذا فإن أكبر قيمة بينها هي $9$.
• من اليوم $3$ إلى اليوم $4$، أهمية النوع $7$ هي $7\times1=7$، وأهمية النوع $8$ هي $8\times1=8$، وأهمية النوع $9$ هي $9\times0=0$، لذا فإن أكبر قيمة بينها هي $8$.
• في اليوم $4$، أهمية النوع $7$ هي $7\times0=0$، وأهمية النوع $8$ هي $8\times1=8$، وأهمية النوع $9$ هي $9\times0=0$، لذا فإن أكبر قيمة بينها هي $8$.
• من اليوم $1$ إلى اليوم $4$، أهمية النوع $7$ هي $7\times1=7$، وأهمية النوع $8$ هي $8\times2=16$، وأهمية النوع $9$ هي $9\times1=9$، لذا فإن أكبر قيمة بينها هي $16$.
• من اليوم $2$ إلى اليوم $4$، أهمية النوع $7$ هي $7\times1=7$، وأهمية النوع $8$ هي $8\times2=16$، وأهمية النوع $9$ هي $9\times0=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

ملاحظة

يستوفي هذا الإدخال قيود المهمة الفرعية 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