我永远喜欢珂朵莉~

题目背景

http://sukasuka-anime.com/ 戒不掉的珂毒 出不动的分块 ![](https://cdn.luogu.org/upload/pic/11191.png) ![](https://cdn.luogu.org/upload/pic/11192.png) ![](https://cdn.luogu.org/upload/pic/11193.png) 哦对了有没有想买BD的珂学家啊?支持一下墨鱼吧~ 或者有没有人想来手办众筹啊?

题目描述

给珂朵莉一个长为n的非负数序列a,支持以下两个操作: 1 l r x : 把区间[l,r]中所有x的倍数/x 2 l r : 查询区间[l,r]的和 珂朵莉很可爱,所以你要帮珂朵莉写这个题

输入输出格式

输入格式


第一行两个数表示n,m 第二行n个非负整数表示ai 之后m行每行一个操作 1 l r x : 把区间[l,r]中所有x的倍数/x 2 l r : 查询区间[l,r]的和

输出格式


对于每次询问,输出一行一个数表示答案

输入输出样例

输入样例 #1

5 3
1 2 3 4 5
2 1 5
1 1 5 2
2 1 5

输出样例 #1

15
12

说明

1 <= n , m <= 100000 0 <= ai <= 500000 1 <= x <= 500000