Bob is going trick-or-treating in an extremely rich neighborhood composed of houses arranged in a row. His friends have given him a list of integers which denotes the amount of candy that the th house gives them.

However, because he is a seasoned trick-or-treater, Bob can get much more candy than that. Bob defines a list which denotes the factor of candy that the th house will give him. Initially, for all (where is the factorial of ).

In his route, Bob will start at a house where, using his charm, he will obtain candies. In addition, he will continue right until a house , where at each subsequent house he will boast about the amount of candy that he has already collected, causing his candy count to increase by a factor of . Note that if Bob goes from houses to , his total amount of candy at the end will be .

Bob would like you, his trusted friend, to help him do a few calculations before he starts his route. He will ask you to handle queries, of the following types:

`1 i v`

The th house has increased its candy supply, meaning that its value of is increased by a factor of .`2 l r`

Bob considers taking the route from houses to . In order to share the candies with his friends, he would like to know the number of different ways that he can evenly split the number of candies that he collects. Formally, he would like to find the number of positive divisors of , modulo .

Please help Bob answer these queries so he can have a successful Halloween!

#### Input Specification

The first line of input will contain two space-separated integers, and .

The next line of input will contain space-separated integers, .

The next lines of input will each contain one query as per the description above .

#### Output Specification

For each query of type , output the answer on a separate line.

#### Subtasks

##### Subtask 1 [10%]

For each query of type , it is guaranteed that the number of candies will be less than or equal to .

##### Subtask 2 [20%]

##### Subtask 3 [70%]

No further constraints.

#### Sample Input 1

```
3 2
1 2 3
1 2 2
2 1 3
```

#### Sample Output 1

`8`

#### Explanation for Sample Output 1

Intially, Bob's list is . After the first operation, it is . For the second operation, the amount of candies is . Since there are ways to evenly distribute candies ( can be divided by , , , , , , , and ), the answer is .

#### Sample Input 2

```
5 5
1 5 5 2 4
2 2 4
1 5 2
1 1 1
1 2 3
2 1 5
```

#### Sample Output 2

```
72
195
```

## Comments