مجموعة قوية
Problem
هناك مصفوفة من الأعداد الطبيعية a
1 ، & thinsp؛ a
2 ، & thinsp؛ ...، & thinsp؛ a
n . ضع في اعتبارك بعض المصفوفات الفرعية a
l ، & thinsp؛ a
l & thinsp؛ + & thinsp؛ 1 ، & thinsp؛ ...، & thinsp؛ a
r ، حيث 1 & thinsp؛ & le؛ & thinsp؛ l & thinsp؛ & le؛ & thinsp؛ r & thinsp؛ & le؛ & thinsp؛ n ولكل رقم طبيعي s يُرمز إليه بـ K
s عدد مرات ظهور الرقم s في هذه المجموعة الفرعية. دعنا نطلق على أصل مجموعة فرعية مجموع المنتجات K
s & middot؛ K
s & middot؛ s فوق جميع الأعداد الصحيحة المميزة s. نظرًا لأن عدد الأرقام المختلفة في المصفوفة محدود ، فإن المجموع يحتوي فقط على عدد محدود من المصطلحات غير الصفرية.
من الضروري حساب العناصر الأساسية لكل من المصفوفات الفرعية t المحددة.
إدخال
يحتوي السطر الأول على عددين صحيحين n و t (1 & thinsp؛ & le؛ & thinsp؛ n، & thinsp؛ t & thinsp؛ & le؛ & thinsp؛ 200000) & mdash؛ طول المصفوفة وعدد الطلبات على التوالي.
يحتوي السطر الثاني على n أعداد طبيعية ai (1 & thinsp؛ & le؛ & thinsp؛ a i & thinsp؛ & le؛ & thinsp؛ 10 6 ) & mdash؛ عناصر المصفوفة.
السطور t التالية تحتوي على رقمين صحيحين موجبين l و r (1 & thinsp؛ & le؛ & thinsp؛ l & thinsp؛ & le؛ & thinsp؛ r & thinsp؛ & le؛ & thinsp؛ n) & mdash؛ فهارس الطرفين الأيمن والأيسر للمصفوفة الفرعية المقابلة.
بصمة
طباعة سطور t ، حيث يحتوي السطر الأول على الرقم الطبيعي الوحيد & [مدش] ؛ العلاقة الأساسية للمصفوفة الفرعية للاستعلام من الدرجة الأولى.
أمثلة:
نبسب ؛
<الجسم>
| إدخال |
الإخراج |
3 2
1 2 1
1 2
1 3
| 3
6 |
8 3
1 1 2 2 1 3 1 1
27
16
27 |
20
20
20 |