يعتقد 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

ملاحظة

ثلاثيتا الاستعلام الأول هما $(A_1,A_2,A_5)$ و$(A_2,A_3,A_4)$.

المهام الفرعية

• الحالات 2–4: $N\le500$.
• الحالات 5–7: $N\le2000$.
• الحالات 8–15: لا قيود إضافية.

صاحب المسألة: Dhruv Rohatgi