题目背景

http://sukasuka-anime.com/

戒不掉的珂毒

出不动的分块

哦对了有没有想买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]的和

输出格式

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

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

15
12

提示

1 <= n , m <= 100000

0 <= ai <= 500000

1 <= x <= 500000