题目简述：给定$m \leq 10^9+9$，维护以下操作
1. "1 l r x"：将序列$a[l], a[l+1], \dots, a[r]$都乘上$x$。
2. "2 p x"：将$a[p]$除以$x$，保证可整除。
3. "3 l r"：求$(a[l]+a[l+1]+\dots+a[r]) \bmod m$。
解：code
除了操作2以外，都显然可以用线段树维护。
主要遇到的问题是$m$不一定是质数，不妨设$m = p_1^{m_1} p_2^{m_2} \dots p_k^{m_k}$，其中$k = O(\log m)$。由于$m \leq 10^9+9$，则$k \leq 9$。
我们将所有数字$x$都分解成$(k+1)$个部分$x = x_0 p_1^{x_1} p_2^{x_2} \dots p_k^{x_k}$，其中$\gcd(x_0,m) = 1$。
对于操作2，设$a = a_0 p_1^{a_1} p_2^{a_2} \dots p_k^{a_k}$，把$a$除以$x$可以看做是两个操作：
2.1. 将$a_0$乘以$x_0^{-1} \bmod m$。而求$x_0^{-1} \bmod m$需要Euclid辗转相除法。
2.2. 将$a_1, \dots, a_k$依次减去$x_1, \dots, x_k$。
因此，我们只需要维护$a_0, a_1, \dots, a_k$即可，时间复杂度为$O((q+n) \log n \log m)$。