Farmer John מאמין בפריצת דרך: אלגוריתם כמעט ליניארי ל־3SUM, הידועה בכך שאין פתרון מוכר מהיר משמעותית מזמן ריבועי. ניסוח אחד: למערך שלמים $s_1,\dots,s_m$, לספור שלשות לא מסודרות של אינדקסים שונים $i,j,k$ שעבורם $s_i+s_j+s_k=0$.

Bessie בודקת זאת במערך $A$ של $N$ שלמים ($1\leq N\leq5000$) ו־$Q$ שאילתות ($1\leq Q\leq10^5$), בכל אחת $1\leq a_i\leq b_i\leq N$. יש לפתור 3SUM על כל תת־מערך $A[a_i\dots b_i]$.

לצערו FJ גילה פגם. הוא בטוח שיוכל לתקן, אך בינתיים מבקש עזרה לעבור את הבדיקה של Bessie!

קלט

שורה ראשונה: שלמים $N,Q$ מופרדים ברווחים. שנייה: איברי $A_1,\dots,A_N$ מופרדים ברווחים. כל אחת מ־$Q$ השורות הבאות מכילה שלמים $a_i,b_i$ מופרדים ברווחים, לשאילתה.

כל איבר מקיים $-10^6\leq A_i\leq10^6$.

פלט

$Q$ שורות; שורה $i$ מכילה שלם אחד, תשובת שאילתה $i$. השתמשו בשלמים של 64 ביט כדי למנוע גלישה.

דוגמאות

קלט 1

7 3
2 0 -1 1 -2 3 3
1 5
2 4
1 7

פלט 1

2
1
4

Note

השלשות בשאילתה הראשונה הן $(A_1,A_2,A_5)$ ו־$(A_2,A_3,A_4)$.

תתי־משימות

• מקרים 2–4: $N\le500$.
• מקרים 5–7: $N\le2000$.
• מקרים 8–15: ללא מגבלות נוספות.

מחבר הבעיה: Dhruv Rohatgi