B. Beats
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Nirva is one of Unballoon's newest talents. As everyone knows, one of the main pieces of advice we hear at the beginning of a competitive programming career is to focus on improving reasoning skills and leave learning more advanced topics, such as suffix automaton, flow, FFT, etc., for later. As everyone also knows, this advice is almost always completely ignored. Because of that, Nirva decided to learn "Segment Tree Beats". The author of this data structure himself has the following to say about it:

"In China, all of the 15 candidates for the Chinese National Team are asked to write a simple research report about algorithms in informatics Olympiad, and the score will be counted in the final selection. There are many interesting ideas and algorithms in these reports. And I find that some of them are quite new for competitors in CF although they are well known in China [...].

This blog is about my report which is written about two years ago. [...] the name "Segment tree beats" is given by C_SUNSHINE which is from a famous Japanese anime Angel Beats."

As expected, Nirva easily understood how Segment Tree Beats works and made her own implementation. To test whether it is correct, she thought it would be interesting to compare her implementation with yours.

You are given $$$n$$$ non-negative integers $$$a_1, \dots, a_n$$$. Your program must process $$$q$$$ operations of three types:

  1. $$$\operatorname{chmod}(l,r,x)$$$ — For all indices $$$i$$$ such that $$$l \le i \le r$$$, replace the value of $$$a_i$$$ with $$$a_i \mathbin{\%} x$$$.
  2. $$$\operatorname{chmax}(l,r,x)$$$ — For all indices $$$i$$$ such that $$$l \le i \le r$$$, replace the value of $$$a_i$$$ with $$$\max(a_i, x)$$$.
  3. $$$\operatorname{sum}(l,r)$$$ — Print the sum of the elements $$$a_i$$$ such that $$$l \le i \le r$$$, that is, $$$a_l + a_{l+1} + \dots + a_r$$$.
Input

The first line contains two integers $$$n$$$ and $$$q$$$ $$$(1 \le n, q \le 1000)$$$. The second line contains $$$n$$$ integers $$$a_1, \dots, a_n$$$ $$$(0 \le a_i \le 10^6)$$$.

Each of the next $$$q$$$ lines describes an operation in one of the following formats:

  • $$$1 \; l \; r \; x$$$ — representing the operation $$$\operatorname{chmod}(l,r,x);$$$
  • $$$2 \; l \; r \; x$$$ — representing the operation $$$\operatorname{chmax}(l,r,x);$$$
  • $$$3 \; l \; r$$$ — representing the operation $$$\operatorname{sum}(l,r).$$$

It is guaranteed that, in each operation, $$$1 \leq l \leq r \leq n$$$ and $$$1 \leq x \leq 10^6$$$.

Output

For each operation of type $$$3$$$ ($$$\operatorname{sum}$$$), print a single integer representing the result of that operation.

Example
Input
6 5
1 2 3 4 5 6
3 1 5
1 2 4 3
3 1 5
2 1 4 2
3 2 3
Output
15
9
4