SP33062 LCMP - LCM Pesticide

N个斯洛伐克农民在一条河边拥有相邻的田地，形成一条直线。每个田地都有害虫（可能没有）。 得益于巧妙的斯洛伐克科学，农民们可以为每种害虫分配一个素数。然后，可以为每个田地分配一个正数，代表正遭受该害虫的害虫-此数的素因数分解表明存在哪些害虫，每个质数的幂表示该害虫对田地的侵害程度。 然后，可以为每种农药分配一个正数，其设计应使其素因数分解表明其可以抑制的害虫，并且每个素数的幂代表它可以处理该害虫的强度。 为了帮助农民，斯洛伐克政府可以选择一种害虫，然后将专门针对该害虫设计的农药倒入河中，从而在所有田地中完全抑制该物种。但是，由于环境方面的考虑，他们一次只能使用一种农药-当政府改用针对另一种害虫设计的另一种农药时，以前被禁止的农药会全力返回所有领域。 最重要的是，农民工会可以要求自己在田间喷洒农药。由于这是使用飞机完成的，因此他们只能要求将农药喷洒在连续的田地上。 现在，对于每个请求，政府都想知道他们可以使用的最便宜的农药，以抑制所请求领域中所有田地上的所有害虫。

第一行包含两个整数N和Q，表示字段数和事件数。 第二行包含N个整数f1,...,fN 表示分配给字段的数字。它们将为正，且不大于10^5 随后出现Q行，按事件发生的顺序描述事件。 如果输入的第一行为1，则再输入一个P,表示斯洛伐克政府已开始将针对害虫编号P（素数）的农药泵入河中，并且不再针对以前的害虫泵农药（如果它们是这样做。P=1是个例外，这意味着根本没有农药被泵入河中。最初，政府不抽任何农药。) 如果输入的第一行为0，则再输入L，R，表示农民要求从L到R的连续区域（包括首尾）喷洒农药。

对于第一个输入为0的每个事件，输出最小数量的农药并模10^9+7，该农药可以处理从L到R的该段区域中的所有侵扰。 如果输入的第一个为1，则不用输出 # 输入输出样例 ### 输入 #1 10 12 4 2 3 5 6 47 10007 32768 59049 1 0 1 5 0 2 5 1 2 0 1 5 0 2 5 0 6 10 1 3 0 6 10 1 1 0 1 10 0 10 10 0 1 5 ### 输出 #1 60 30 15 15 772456932 411740567 342852967 1 60