时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld
题目描述
大司马每天日程太多，需要一个高效的数据结构进行时间管理。经过研究，他认为这个问题可以被归结如下：
给定一个长度为n的序列，第i个元素为
，请支持如下两种操作：
)
，表示将
的值都与x取最大公约数，即对于
，将替换为)
，两个数的最大公约数是能够同时整除两个数的最大数。
)
，询问此时的和。
请注意，操作有时间顺序，2类操作输出的是进行询问时对应区间的和。
给定一个长度为n的序列，第i个元素为
请注意，操作有时间顺序，2类操作输出的是进行询问时对应区间的和。
输入描述:
每个测试点仅包含一组输入数据。
第一行两个整数，表示序列长度和操作个数。
第二行n个整数，第i个整数表示。
接下来m行，每行为题目描述提到的的两种格式之一，表示一次操作，操作按照时间顺序给出。
输出描述:
按照输入顺序，对于每个2类操作，输出一行一个整数表示对应的和。