{"raw_statement":[{"iden":"statement","content":"给定一个长为 $n$ 的序列 $a$，有 $m$ 次操作。\n\n每次有两种操作：\n\n``1 l r x``：对于区间 $[l,r]$ 内所有 $i$，将 $a_i$ 变成 $\\gcd(a_i,x)$。\n\n``2 l r``：查询区间 $[l,r]$ 的和，答案对 $2^{32}$ 取模后输出。"},{"iden":"input","content":"第一行两个数 $n,m$。\n\n第二行 $n$ 个数表示 $a_i$。\n\n之后 $m$ 行，每行三个或四个数，表示一次操作。"},{"iden":"output","content":"对每个 $2$ 操作，输出一行一个数表示这次查询的答案。"},{"iden":"note","content":"Idea：nzhtl1477，Solution：nhtl1477，Code：ccz181078，Data：ccz181078\n\n对于 $20\\%$ 的数据，满足 $1 \\le n,m,a_i,x \\le 10^3$。\n\n对于 $50\\%$ 的数据，满足  $1 \\le n,m \\le 10^5$，且 $a$ 中的元素与每次操作的 $x$ 均随机生成。\n\n对于另外 $20\\%$ 的数据，满足所有的查询均在修改后发生。\n\n对于 $100\\%$ 的数据，满足 $1\\le n\\le 2\\cdot 10^5,1\\le m\\le 5 \\cdot 10^5$，所有数值为 $[1,10^{18}]$ 内的整数。"}],"translated_statement":null,"sample_group":[["10 10\n4 1 5 10 1 3 8 2 8 2 \n2 1 7\n2 1 10\n1 7 10 4\n1 5 8 10\n2 1 8\n1 3 5 2\n1 3 4 3\n2 5 8\n2 3 7\n2 6 10","32\n44\n26\n6\n6\n11"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}