# Wow! Such Sequence!

Time Limit: 10000/5000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

## Description

Recently, Doge got a funny birthday present from his new friend, Protein Tiger from St. Beeze College. No, not cactuses. It's a mysterious blackbox.

After some research, Doge found that the box is maintaining a sequence an of n numbers internally, initially all numbers are zero, and there are THREE "operations":

1.Add d to the k-th number of the sequence.
2.Query the sum of ai where l ≤ i ≤ r.
3.Change ai to the nearest Fibonacci number, where l ≤ i ≤ r.
4.Play sound "Chee-rio!", a bit useless.

Let F0 = 1,F1 = 1,Fibonacci number Fn is defined as Fn = Fn - 1 + Fn - 2 for n ≥ 2.

Nearest Fibonacci number of number x means the smallest Fn where |Fn - x| is also smallest.

Doge doesn't believe the machine could respond each request in less than 10ms. Help Doge figure out the reason.

## Input

Input contains several test cases, please process till EOF.
For each test case, there will be one line containing two integers n, m.
Next m lines, each line indicates a query:

2 l r - "query sum"
3 l r - "change to nearest Fibonacci"

1 ≤ n ≤ 100000, 1 ≤ m ≤ 100000, |d| < 231, all queries will be valid.

## Output

For each Type 2 ("query sum") operation, output one line containing an integer represent the answer of this query.

## Sample Input

1 1
2 1 1
5 4
1 1 7
1 3 17
3 2 4
2 1 5

## Sample Output

0
22

## Source

2014 Multi-University Training Contest 3