הכבש הקטן מתגורר בכפר דייגים קטן לצד פיורד, והוא תיעד את גובה פני הים במשך $n$ ימים רצופים; ביום ה-$i$ ($1\leq i\leq n$) גובה פני הים הוא מספר שלם חיובי $h_i$.

עבור תקופה נבחרת מהיום ה-$l$ ועד היום ה-$r$ (כולל $l$ ו-$r$), נגדיר:

• $M$ הוא הערך המקסימלי של גובה פני הים בתקופה זו;
• $A$ הוא מספרו של היום הראשון ב-$[l,r]$ שבו גובה פני הים מגיע ל-$M$;
• $B$ הוא מספרו של היום האחרון ב-$[l,r]$ שבו גובה פני הים מגיע ל-$M$.

אזי ערך הגאות של תקופה זו מוגדר להיות $M\cdot(B-A)$. שימו לב שאם הגובה המקסימלי של פני הים מופיע פעם אחת בלבד, אז $A=B$, ובמקרה זה ערך הגאות הוא $0$.

הכבש הקטן ישאל $q$ שאלות באופן מקוון (אונליין). בכל שאלה יינתנו $l$ ו-$r$, ועליכם לבחור תת-תקופה $[x,y]$ מתוך $[l,r]$ (כלומר $l\leq x\leq y\leq r$) כך שערך הגאות של תקופה זו יהיה מקסימלי.

קלט

השורה הראשונה מכילה שני מספרים שלמים $n$ ו-$q$ ($1\leq n\leq 5\times 10^5$, $1\leq q\leq 3\times10^6$), המייצגים בהתאמה את מספר ימי התצפית הכולל ואת מספר השאילתות.

השורה השנייה מכילה $n$ מספרים שלמים חיוביים $h_1, h_2, \dots, h_n$ ($1\leq h_i\leq 10^9$), המייצגים לפי הסדר את גובה פני הים בכל יום.

השורה השלישית מכילה שני מספרים שלמים $l_1$ ו-$r_1$ ($1\leq l_1\leq r_1\leq n$), המייצגים את הקטע של השאילתה הראשונה.

עבור השאילתה ה-$i$ ($2\leq i\leq q$), נניח כי $lastans$ הוא התשובה לשאילתה הקודמת, ונגדיר: $$ a_i = \left(l_{i-1} + lastans\cdot37\right) \bmod n + 1,\quad b_i = \left(l_{i-1} + r_{i-1} + lastans\cdot53\right) \bmod n + 1 $$

אזי השאילתה ה-$i$ היא למעשה $l_i=\min(a_i,b_i)$, $r_i=\max(a_i,b_i)$.

פלט

יהי $ans_i$ התשובה לשאילתה ה-$i$. הדפיסו מספר שלם אחד: $(ans_1+1) \oplus (ans_2+2) \oplus \cdots \oplus (ans_q+q)$.

שימו לב כי $\oplus$ מייצג את פעולת ה-XOR הביטית.

דוגמאות

קלט 1

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

פלט 1

1

הערה

הקטע של השאילתה הראשונה הוא $[2,7]$, והתקופה האופטימלית היא $[2,4]$, שבה הגובה המקסימלי של פני הים הוא $8$. בתקופה $[2,4]$, הגובה $8$ מופיע לראשונה ביום $2$ ולאחרונה ביום $4$, ולכן ערך הגאות של תקופה זו הוא $8\times(4-2)=16$.

השאילתות שנוצרות בהמשך והתשובות להן לפי הסדר הן: $ [2,3]\to 0,\quad [3,6]\to 0,\quad [2,4]\to 16,\quad [3,7]\to 0. $

לכן סכום ה-XOR הנדרש הוא $(16+1)\oplus (0+2)\oplus (0+3)\oplus (16+4)\oplus (0+5)=1$.