Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

brute force

data structures

dsu

number theory

*2000

No tag edit access

The problem statement has recently been changed. View the changes.

×
F. SUM and REPLACE

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputLet *D*(*x*) be the number of positive divisors of a positive integer *x*. For example, *D*(2) = 2 (2 is divisible by 1 and 2), *D*(6) = 4 (6 is divisible by 1, 2, 3 and 6).

You are given an array *a* of *n* integers. You have to process two types of queries:

- REPLACE
*l**r*— for every replace*a*_{i}with*D*(*a*_{i}); - SUM
*l**r*— calculate .

Print the answer for each SUM query.

Input

The first line contains two integers *n* and *m* (1 ≤ *n*, *m* ≤ 3·10^{5}) — the number of elements in the array and the number of queries to process, respectively.

The second line contains *n* integers *a*_{1}, *a*_{2}, ..., *a*_{n} (1 ≤ *a*_{i} ≤ 10^{6}) — the elements of the array.

Then *m* lines follow, each containing 3 integers *t*_{i}, *l*_{i}, *r*_{i} denoting *i*-th query. If *t*_{i} = 1, then *i*-th query is REPLACE *l*_{i} *r*_{i}, otherwise it's SUM *l*_{i} *r*_{i} (1 ≤ *t*_{i} ≤ 2, 1 ≤ *l*_{i} ≤ *r*_{i} ≤ *n*).

There is at least one SUM query.

Output

For each SUM query print the answer to it.

Example

Input

7 6

6 4 1 10 3 2 4

2 1 7

2 4 5

1 3 5

2 4 4

1 5 7

2 1 7

Output

30

13

4

22

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/04/2023 07:30:53 (k1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|