G. Great Factors
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You have an array $$$a$$$ of $$$n$$$ positive integers. There are three types of operations performed on this array:

  1. Given a value $$$i$$$, remove a random prime factor from $$$a_i$$$. If $$$a_i$$$ has no prime factors, do nothing.
  2. Given two values $$$l$$$ and $$$r$$$, find the minimum possible sum of the prime factors of the numbers $$$a_l, a_{l+1}, \ldots, a_r$$$.
  3. Given three values $$$l$$$, $$$r$$$, and $$$x$$$, assign the value $$$x$$$ to $$$a_i$$$ for all $$$l \leq i \leq r$$$.

Given the array $$$a$$$ and a sequence of $$$q$$$ operations performed in order, determine the result of each type 2 operation.

Input

The first line contains an integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$), the size of the array $$$a$$$.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^4$$$), the elements of the array $$$a$$$.

The third line contains an integer $$$q$$$ ($$$1 \leq q \leq 10^5$$$), the number of operations.

The next $$$q$$$ lines describe the operations performed in order. Each operation is described by an integer $$$t$$$ ($$$1 \leq t \leq 3$$$) and the values corresponding to the operation.

  • If $$$t=1$$$, a value $$$i$$$ ($$$1 \leq i \leq n$$$) is given.
  • If $$$t=2$$$, two values $$$l$$$ and $$$r$$$ ($$$1 \leq l \leq r \leq n$$$) are given.
  • If $$$t=3$$$, three values $$$l$$$, $$$r$$$, and $$$x$$$ ($$$1 \leq l \leq r \leq n$$$, $$$1 \leq x \leq 10^4$$$) are given.
Output

For each type 2 operation, print an integer, the minimum possible sum of the prime factors of the numbers $$$a_l, a_{l+1}, \ldots, a_r$$$.

Examples
Input
4
10 9 2 4
8
1 4
2 1 4
1 1
2 1 3
3 2 3 12
2 2 4
1 4
2 4 4
Output
17
10
16
0
Input
8
9608 9630 489 5648 5240 8338 9028 5564
10
2 6 6
3 3 7 9838
3 6 7 7525
1 8
2 8 8
2 2 5
2 1 3
1 5
2 6 7
2 5 6
Output
392
17
14883
6248
120
62
Note

For the first case, the first 4 operations are performed as follows:

  • Remove a random prime factor from $$$a_4$$$; since $$$a_4 = 4 = 2 \times 2$$$, we get $$$a_4 = 2$$$.
  • The sum of the prime factors of 10, 9, 2, and 2 is $$$2 + 5$$$ $$$+$$$ $$$3 + 3$$$ $$$+$$$ $$$2$$$ $$$+$$$ $$$2$$$ $$$= 17$$$.
  • Remove a random prime factor from $$$a_1$$$; since $$$a_1 = 10 = 2 \times 5$$$, we can get $$$a_1 = 2$$$ or $$$a_1 = 5$$$.
  • There are two possible sums: $$$2$$$ $$$+$$$ $$$3 + 3$$$ $$$+$$$ $$$2$$$ $$$ = 10$$$ or $$$5$$$ $$$+$$$ $$$3 + 3$$$ $$$+$$$ $$$2$$$ $$$ = 13$$$; the minimum is 10.