## F. SUM and REPLACE

time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

## Description

Let 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:

1. REPLACE l r — for every replace a**i with D(a**i);
2. 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·105) — the number of elements in the array and the number of queries to process, respectively.

The second line contains n integers a1, a2, …, a**n (1 ≤ a**i ≤ 106) — 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 lir**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.

## Solution

### AC代码

41131343 2018-08-02 20:37:41 MoonChasing F - SUM and REPLACE GNU C++ Accepted 249 ms 54800 KB
41131149 2018-08-02 20:30:15 MoonChasing F - SUM and REPLACE GNU C++ Time limit exceeded on test 2 2000 ms 54800 KB
41130678 2018-08-02 20:10:48 MoonChasing F - SUM and REPLACE GNU C++ Time limit exceeded on test 2 2000 ms 54800 KB

❤采之欲遗谁，所思在远道。❤
0%