يعيش الخروف الصغير في قرية صيد صغيرة على ضفاف مضيق بحري (فيورد)، وقد سجّل ارتفاع مستوى سطح البحر خلال $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$.