You are given an array $a = (a_1, a_2, \dots, a_n)$ of $n$ non-negative integers. Let $d(x)$ denote the number of positive divisors of $x$. For example, $d(6) = 4$, since the positive divisors of $6$ are $1, 2, 3$, and $6$. By convention, $d(0) = 0$.

You must process $q$ queries of the following three types:

• 1 l r x — For every $i$ such that $l \le i \le r$, replace $a_i$ with $(a_i \mathbin{\mathrm{OR}} x)$.
• 2 idx y — Replace $a_{\mathit{idx}}$ with $(a_{\mathit{idx}} \mathbin{\mathrm{AND}} y)$.
• 3 l r — Compute and output $\sum_{i=l}^{r} d(a_i)$.

Here, $\mathrm{OR}$ and $\mathrm{AND}$ denote the bitwise OR and bitwise AND operations, respectively.

Input

The first line contains two integers $n$ ($1 \le n \le 10^5$) and $q$ ($1 \le q \le 10^5$) — the length of the array and the number of queries.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^6$) — the initial elements of the array.

Each of the next $q$ lines describes a query and begins with an integer $\mathit{type} \in \{1, 2, 3\}$:

• If $\mathit{type} = 1$, three integers $l, r, x$ follow ($1 \le l \le r \le n$, $0 \le x \le 10^6$).
• If $\mathit{type} = 2$, two integers $\mathit{idx}, y$ follow ($1 \le \mathit{idx} \le n$, $0 \le y \le 10^6$).
• If $\mathit{type} = 3$, two integers $l, r$ follow ($1 \le l \le r \le n$).

It is guaranteed that there is at least one query of type $3$.

Output

For each query of type $3$, output a single integer on a new line --- the sum of $d(a_i)$ over $l \le i \le r$.

Example

stdin

5 4
4 5 6 7 8
3 1 5
1 1 3 2
2 4 3
3 1 5

stdout

15
16

Note

Initially, $a = [4, 5, 6, 7, 8]$, with divisor counts $d(4) = 3$, $d(5) = 2$, $d(6) = 4$, $d(7) = 2$, and $d(8) = 4$.

• Query 1 (3 1 5): The sum over $[1, 5]$ is $3 + 2 + 4 + 2 + 4 = 15$.
• Query 2 (1 1 3 2): $a_1 = 4 \mathbin{\mathrm{OR}} 2 = 6$, $a_2 = 5 \mathbin{\mathrm{OR}} 2 = 7$, $a_3 = 6 \mathbin{\mathrm{OR}} 2 = 6$. The array becomes $[6, 7, 6, 7, 8]$.
• Query 3 (2 4 3): $a_4 = 7 \mathbin{\mathrm{AND}} 3 = 3$. The array becomes $[6, 7, 6, 3, 8]$.
• Query 4 (3 1 5): The divisor counts are now $4, 2, 4, 2, 4$, so the sum is $4 + 2 + 4 + 2 + 4 = 16$.