{"raw_statement":[{"iden":"statement","content":"An array of positive integers _a_1, _a_2, ..., _a__n_ is given. Let us consider its arbitrary subarray _a__l_, _a__l_ + 1..., _a__r_, where 1 ≤ _l_ ≤ _r_ ≤ _n_. For every positive integer _s_ denote by _K__s_ the number of occurrences of _s_ into the subarray. We call the _power_ of the subarray the sum of products _K__s_·_K__s_·_s_ for every positive integer _s_. The sum contains only finite number of nonzero summands as the number of different values in the array is indeed finite.\n\nYou should calculate the power of _t_ given subarrays."},{"iden":"input","content":"First line contains two integers _n_ and _t_ (1 ≤ _n_, _t_ ≤ 200000) — the array length and the number of queries correspondingly.\n\nSecond line contains _n_ positive integers _a__i_ (1 ≤ _a__i_ ≤ 106) — the elements of the array.\n\nNext _t_ lines contain two positive integers _l_, _r_ (1 ≤ _l_ ≤ _r_ ≤ _n_) each — the indices of the left and the right ends of the corresponding subarray."},{"iden":"output","content":"Output _t_ lines, the _i_\\-th line of the output should contain single positive integer — the power of the _i_\\-th query subarray.\n\nPlease, do not use _%lld_ specificator to read or write 64-bit integers in C++. It is preferred to use _cout_ stream (also you may use _%I64d_)."},{"iden":"examples","content":"Input\n\n3 2\n1 2 1\n1 2\n1 3\n\nOutput\n\n3\n6\n\nInput\n\n8 3\n1 1 2 2 1 3 1 1\n2 7\n1 6\n2 7\n\nOutput\n\n20\n20\n20"},{"iden":"note","content":"Consider the following array (see the second sample) and its \\[2, 7\\] subarray (elements of the subarray are colored):\n\n<center>![image](https://espresso.codeforces.com/c0d1418a04b13fdf812625d254db5241ce734ac0.png)</center>Then _K_1 = 3, _K_2 = 2, _K_3 = 1, so the power is equal to 32·1 + 22·2 + 12·3 = 20."}],"translated_statement":[{"iden":"statement","content":"给定一个正整数数组 #cf_span[a1, a2, ..., an]。考虑其任意子数组 #cf_span[al, al + 1..., ar]，其中 #cf_span[1 ≤ l ≤ r ≤ n]。对于每个正整数 #cf_span[s]，记 #cf_span[Ks] 为 #cf_span[s] 在该子数组中出现的次数。我们称该子数组的 _幂_ 为对所有正整数 #cf_span[s] 的乘积 #cf_span[Ks·Ks·s] 之和。由于数组中不同值的个数有限，该和中仅有有限个非零项。\n\n你需要计算 #cf_span[t] 个给定子数组的幂。\n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[t] (#cf_span[1 ≤ n, t ≤ 200000])，分别表示数组长度和查询次数。\n\n第二行包含 #cf_span[n] 个正整数 #cf_span[ai] (#cf_span[1 ≤ ai ≤ 106])，表示数组元素。\n\n接下来 #cf_span[t] 行，每行包含两个正整数 #cf_span[l], #cf_span[r] (#cf_span[1 ≤ l ≤ r ≤ n])，分别表示对应子数组的左右端点索引。\n\n请输出 #cf_span[t] 行，第 #cf_span[i] 行应包含一个正整数，表示第 #cf_span[i] 个查询子数组的幂。\n\n请勿在 C++ 中使用 _%lld_ 标识符读写 64 位整数。建议使用 _cout_ 流（也可使用 _%I64d_）。 \n\n考虑以下数组（见第二个样例）及其子数组 [2, 7]（子数组元素已着色）：\n\n"},{"iden":"input","content":"第一行包含两个整数 #cf_span[n] 和 #cf_span[t] (#cf_span[1 ≤ n, t ≤ 200000])，分别表示数组长度和查询次数。第二行包含 #cf_span[n] 个正整数 #cf_span[ai] (#cf_span[1 ≤ ai ≤ 106])，表示数组元素。接下来 #cf_span[t] 行，每行包含两个正整数 #cf_span[l], #cf_span[r] (#cf_span[1 ≤ l ≤ r ≤ n])，分别表示对应子数组的左右端点索引。"},{"iden":"output","content":"请输出 #cf_span[t] 行，第 #cf_span[i] 行应包含一个正整数，表示第 #cf_span[i] 个查询子数组的幂。请勿在 C++ 中使用 _%lld_ 标识符读写 64 位整数。建议使用 _cout_ 流（也可使用 _%I64d_）。"},{"iden":"examples","content":"输入3 21 2 11 21 3输出36输入8 31 1 2 2 1 3 1 12 71 62 7输出202020"},{"iden":"note","content":"考虑以下数组（见第二个样例）及其子数组 [2, 7]（子数组元素已着色）： 则 #cf_span[K1 = 3]，#cf_span[K2 = 2]，#cf_span[K3 = 1]，因此幂等于 #cf_span[32·1 + 22·2 + 12·3 = 20]。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions:**\n\nLet $ a = [a_1, a_2, \\dots, a_n] $ be an array of positive integers.  \nFor a subarray $ a[l:r] = [a_l, a_{l+1}, \\dots, a_r] $, define for each positive integer $ s $:  \n- $ K_s = \\#\\{ i \\in [l, r] \\mid a_i = s \\} $, the frequency of $ s $ in the subarray.\n\nThe **power** of the subarray $ a[l:r] $ is defined as:  \n$$\n\\sum_{s=1}^{\\infty} K_s^2 \\cdot s\n$$  \n(Note: Only finitely many $ K_s > 0 $, so the sum is finite.)\n\n---\n\n**Given:**\n\n- $ n, t \\in \\mathbb{Z}^+ $, $ 1 \\leq n, t \\leq 200000 $\n- Array $ a \\in (\\mathbb{Z}^+)^n $, $ 1 \\leq a_i \\leq 10^6 $\n- $ t $ queries, each given by $ (l, r) $, $ 1 \\leq l \\leq r \\leq n $\n\n---\n\n**Objective:**\n\nFor each query $ (l, r) $, compute:  \n$$\n\\sum_{s \\in \\text{values in } a[l:r]} \\left( \\text{freq}_{a[l:r]}(s) \\right)^2 \\cdot s\n$$\n\n---\n\n**Output:**\n\n$ t $ integers, each being the power of the corresponding subarray.","simple_statement":null,"has_page_source":false}