{"raw_statement":[{"iden":"statement","content":"Let _D_(_x_) be the number of positive divisors of a positive integer _x_. For example, _D_(2) = 2 (2 is divisible by 1 and 2), _D_(6) = 4 (6 is divisible by 1, 2, 3 and 6).\n\nYou are given an array _a_ of _n_ integers. You have to process two types of queries:\n\n1.  _REPLACE_ _l_ _r_ — for every replace _a__i_ with _D_(_a__i_);\n2.  _SUM_ _l_ _r_ — calculate .\n\nPrint the answer for each _SUM_ query."},{"iden":"input","content":"The first line contains two integers _n_ and _m_ (1 ≤ _n_, _m_ ≤ 3·105) — the number of elements in the array and the number of queries to process, respectively.\n\nThe second line contains _n_ integers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 106) — the elements of the array.\n\nThen _m_ lines follow, each containing 3 integers _t__i_, _l__i_, _r__i_ denoting _i_\\-th query. If _t__i_ = 1, then _i_\\-th query is _REPLACE_ _l__i_ _r__i_, otherwise it's _SUM_ _l__i_ _r__i_ (1 ≤ _t__i_ ≤ 2, 1 ≤ _l__i_ ≤ _r__i_ ≤ _n_).\n\nThere is at least one _SUM_ query."},{"iden":"output","content":"For each _SUM_ query print the answer to it."},{"iden":"example","content":"Input\n\n7 6\n6 4 1 10 3 2 4\n2 1 7\n2 4 5\n1 3 5\n2 4 4\n1 5 7\n2 1 7\n\nOutput\n\n30\n13\n4\n22"}],"translated_statement":[{"iden":"statement","content":"设 #cf_span[D(x)] 为正整数 #cf_span[x] 的正因数个数。例如，#cf_span[D(2) = 2]（#cf_span[2] 可被 #cf_span[1] 和 #cf_span[2] 整除），#cf_span[D(6) = 4]（#cf_span[6] 可被 #cf_span[1]、#cf_span[2]、#cf_span[3] 和 #cf_span[6] 整除）。\n\n给定一个包含 #cf_span[n] 个整数的数组 #cf_span[a]。你需要处理两种类型的查询：\n\n对每个 _SUM_ 查询输出答案。\n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n, m ≤ 3·105]）——数组元素个数和待处理的查询数。\n\n第二行包含 #cf_span[n] 个整数 #cf_span[a1]、#cf_span[a2]、...、#cf_span[an]（#cf_span[1 ≤ ai ≤ 106]）——数组元素。\n\n接下来 #cf_span[m] 行，每行包含三个整数 #cf_span[ti]、#cf_span[li]、#cf_span[ri]，表示第 #cf_span[i] 个查询。若 #cf_span[ti = 1]，则该查询为 _REPLACE_ #cf_span[li] #cf_span[ri]；否则为 _SUM_ #cf_span[li] #cf_span[ri]（#cf_span[1 ≤ ti ≤ 2]，#cf_span[1 ≤ li ≤ ri ≤ n]）。\n\n至少存在一个 _SUM_ 查询。\n\n对每个 _SUM_ 查询输出答案。\n\n"},{"iden":"input","content":"第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n, m ≤ 3·105]）——数组元素个数和待处理的查询数。第二行包含 #cf_span[n] 个整数 #cf_span[a1]、#cf_span[a2]、...、#cf_span[an]（#cf_span[1 ≤ ai ≤ 106]）——数组元素。接下来 #cf_span[m] 行，每行包含三个整数 #cf_span[ti]、#cf_span[li]、#cf_span[ri]，表示第 #cf_span[i] 个查询。若 #cf_span[ti = 1]，则该查询为 _REPLACE_ #cf_span[li] #cf_span[ri]；否则为 _SUM_ #cf_span[li] #cf_span[ri]（#cf_span[1 ≤ ti ≤ 2]，#cf_span[1 ≤ li ≤ ri ≤ n]）。至少存在一个 _SUM_ 查询。"},{"iden":"output","content":"对每个 _SUM_ 查询输出答案。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ D(x) $ denote the number of positive divisors of a positive integer $ x $.  \nLet $ a = (a_1, a_2, \\dots, a_n) $ be an array of positive integers with $ n \\geq 1 $.  \nLet $ m $ be the number of queries.\n\n**Constraints**  \n1. $ 1 \\leq n, m \\leq 3 \\cdot 10^5 $  \n2. $ 1 \\leq a_i \\leq 10^6 $ for all $ i \\in \\{1, \\dots, n\\} $  \n3. Each query is of type $ t_i \\in \\{1, 2\\} $ with indices $ l_i, r_i $ such that $ 1 \\leq l_i \\leq r_i \\leq n $:  \n   - If $ t_i = 1 $: update $ a_j \\leftarrow D(a_j) $ for all $ j \\in \\{l_i, \\dots, r_i\\} $  \n   - If $ t_i = 2 $: compute $ \\sum_{j=l_i}^{r_i} a_j $\n\n**Objective**  \nFor each query with $ t_i = 2 $, output $ \\sum_{j=l_i}^{r_i} a_j $.","simple_statement":null,"has_page_source":false}