## Problem

### Description

In mathematical terms, the sequence of is defined by the recurrence relation .
loves Fibonacci numbers very much. Today gives you an array consisting of integers: . Moreover, there are queries, each query has one of the two types:

1. Format of the query “ ”. In reply to the query, you need to add to each element , where .
2. Format of the query “ ”. In reply to the query you should output the value of modulo .

Help reply to all the queries.

### Input

The first line of the input contains two integers and . The second line contains n integers — initial array .
Then, lines follow. A single line describes a single query in the format given in the statement. It is guaranteed that for each query inequality holds.

### Output

For each query of the second type, print the value of the sum on a single line.

Input

Output

### Note

After the first query, .
For the second query, .
After the third query, .
For the fourth query, .

## Translation

1. 中的每个数对应加上从的斐波那契数，即使加上
2. 询问的值