Module: मो एल्गोरिथ्म

Problem

प्राकृत संख्याओं की एक सारणी है a₁, a₂, ..., a_n। इसके कुछ उपसरणियों पर विचार करें a_l, a_l + 1, ..., a_r, जहाँ 1 ≤ l ≤ r ≤ n, और प्रत्येक प्राकृतिक संख्या s के लिए K_s द्वारा निरूपित करता है, इस उपश्रेणी में संख्या s की घटनाओं की संख्या। आइए एक उपश्रेणी की प्रमुखता को सभी अलग-अलग पूर्णांकों में K_s·K_s·s के गुणनफलों का योग कहते हैं। चूंकि सरणी में विभिन्न संख्याओं की संख्या परिमित है, योग में गैर-शून्य पदों की केवल एक परिमित संख्या होती है।

दिए गए प्रत्येक उपसरणियों की प्रमुखताओं की गणना करना आवश्यक है।

इनपुट
पहली पंक्ति में दो पूर्णांक n और t (1 ≤ n, t ≤ 200000) — सरणी की लंबाई और अनुरोधों की संख्या, क्रमशः।
दूसरी पंक्ति में n प्राकृतिक संख्याएँ हैं ai (1 ≤ a_i ≤ 10⁶) — सरणी तत्व।
अगली t पंक्तियों में दो धनात्मक पूर्णांक l और r (1 ≤ l ≤ r ≤ n) — संबंधित उपसरणी के बाएँ और दाएँ सिरों की अनुक्रमणिका।

छाप
प्रिंट टी लाइनें, जहां i-वें लाइन में केवल प्राकृतिक संख्या होती है — i-वें क्वेरी उपसरणी की प्रमुखता।

उदाहरण:
  <तालिका सीमा = "1" सेलपैडिंग = "1" सेलस्पेसिंग = "1" शैली = "चौड़ाई: 500 पीएक्स;"> <शरीर> इनपुट आउटपुट 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