Evan somehow found an array, , consisting of integers in the range on the ground. Looking at it, he came up with a problem. However, he has no clue how to solve it. After asking all his friends, no one knew how to solve it, so he comes to you, asking for help.

Evan gives you the following function:

where denotes the factorial operation. In other words, the function returns if is divisible by , and otherwise.

Evan will give you queries:

`1 l r`

Print the maximum value of for all elements in the subarray .`2 l r v`

Add to all elements in the subarray .

#### Input Specification

The first line will contain integers, .

The second line will contain integers, , the initial array.

The next lines will each contain a valid query as defined above.

It is guaranteed that at any point in time, all elements of the array will be in the range .

#### Output Specification

For every type query, output the maximum value of for all elements in the subarray on its own line.

#### Constraints

##### Subtask 1 [10%]

##### Subtask 2 [30%]

##### Subtask 3 [60%]

No additional constraints.

#### Sample Input

```
9 9 2
2 3 5 6 8 10 7 11 16
1 1 5
2 1 5 1
1 1 5
1 4 5
1 6 8
1 9 9
2 6 9 -3
1 6 8
1 9 9
```

#### Sample Output

```
5
7
7
11
-1
7
13
```

## Comments