פרופסור JOI, המומחה המוביל לחקר ההיסטוריה של מדינת IOI, קיבל יומן שנכתב לכאורה בידי תושב מדינת IOI בעת העתיקה. כדי לחקור באמצעות היומן את החיים במדינת IOI העתיקה, החליט הפרופסור לבחון את האירועים המתוארים בו.

ביומן מתוארים אירועים שהתרחשו במשך $N$ ימים, אירוע אחד בכל יום. האירועים מסווגים לכמה סוגים. סוג האירוע ביום ה-$i$ ($1\le i\le N$) מיוצג על ידי המספר השלם $X_i$. ככל שהערך $X_i$ גדול יותר, האירוע נחשב רחב היקף יותר.

פרופסור JOI החליט לנתח את היומן באופן הבא.

1. בוחרים כמה ימים רצופים מתוך $N$ ימי היומן בתור התקופה לניתוח.
2. מגדירים את החשיבות של סוג אירוע $t$ כמכפלה של $t$ במספר האירועים מסוג $t$ בתקופה זו.
3. מחשבים את החשיבות של כל סוגי האירועים ומוצאים את הערך המרבי ביניהם.

פרופסור JOI ביקש מכם לכתוב תוכנית לצורך הניתוח. התוכנית צריכה למצוא את ערך החשיבות המרבי עבור תקופה נתונה לניתוח.

משימה

בהינתן סוגי האירועים לאורך $N$ ימי היומן ו-$Q$ שאילתות המתארות תקופות ביומן, כתבו תוכנית המוצאת עבור כל שאילתה את ערך החשיבות המרבי של סוג אירוע.

קלט

קראו את הנתונים הבאים מהקלט הסטנדרטי.

• השורה הראשונה מכילה את המספרים השלמים $N,Q$ המופרדים ברווח. פירוש הדבר שהיומן כולל $N$ ימים ושנתונות $Q$ שאילתות.
• השורה הבאה מכילה $N$ מספרים שלמים $X_1,\ldots,X_N$ המופרדים ברווחים. $X_i$ ($1\le i\le N$) מציין את סוג האירוע ביום ה-$i$.
• השורה ה-$j$ ($1\le j\le Q$) מתוך $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