2819 - Homework with Fibonacci 2819 - Homework with Fibonacci 2819 - Homework with Fibonacci

Statistics Sub: 1043 | AC: 318 | AC%: 30,49 | Score: 2,41
Created by I Copa UCLV de Programación - Yairon Cid Ruiz
Added by mario (2014-04-03)
Limits
Total Time: 30000 MS |Memory: 62 MB | Output: 64 MB | Size: 29 KB
Enabled languages
Available in

Description

Rodrigo Díaz de Vivar (1043 - July 10, 1099), known as Cid Campeador (“The lord-master of military arts”), was a Castillian nobleman, military leader, ferocious warrior, and diplomat that fought against the Moors. El Cid’s legendary martial abilities have fueled his reputation as an outstanding battlefield commander and one of the greatest heroes in Spain’s history.
El Cid before become a great warrior, he was a lover of mathematics and puzzles in his childhood. But once, he stuck with the following problem:
You are given a sequence of integers a1, a2, ..., an. Your task is to perform over the sequence m consecutive operations of the following type:

1 - For given numbers li and ri you've got to calculate: , where f(0) = f(1) = 1 and f(i) = f(i-1) + f(i-2) : i ≥ 2.
2 - For a group of three numbers li, ri, di you should increase value ax by di for all x (li ≤ x ≤ ri).
Rodrigo Díaz de Vivar (1043 - July 10, 1099), known as Cid Campeador (“The lord-master of military arts”), was a Castillian nobleman, military leader, ferocious warrior, and diplomat that fought against the Moors. El Cid’s legendary martial abilities have fueled his reputation as an outstanding battlefield commander and one of the greatest heroes in Spain’s history.
El Cid before become a great warrior, he was a lover of mathematics and puzzles in his childhood. But once, he stuck with the following problem:
You are given a sequence of integers a1, a2, ..., an. Your task is to perform over the sequence m consecutive operations of the following type:

1 - For given numbers li and ri you've got to calculate: , where f(0) = f(1) = 1 and f(i) = f(i-1) + f(i-2) : i ≥ 2.
2 - For a group of three numbers li, ri, di you should increase value ax by di for all x (li ≤ x ≤ ri).
Rodrigo Díaz de Vivar (1043 - July 10, 1099), known as Cid Campeador (“The lord-master of military arts”), was a Castillian nobleman, military leader, ferocious warrior, and diplomat that fought against the Moors. El Cid’s legendary martial abilities have fueled his reputation as an outstanding battlefield commander and one of the greatest heroes in Spain’s history.
El Cid before become a great warrior, he was a lover of mathematics and puzzles in his childhood. But once, he stuck with the following problem:
You are given a sequence of integers a1, a2, ..., an. Your task is to perform over the sequence m consecutive operations of the following type:

1 - For given numbers li and ri you've got to calculate: , where f(0) = f(1) = 1 and f(i) = f(i-1) + f(i-2) : i ≥ 2.
2 - For a group of three numbers li, ri, di you should increase value ax by di for all x (li ≤ x ≤ ri).

Input specification

The first line contains the number of test cases (at most 15). For each test case: The first line contains one integer n (1 ≤ n ≤ 10^5) - the number of integers in the sequence. The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 10^7), separated by spaces. The third line contains one integer m (1 ≤ m ≤ 10^5) - the number of operations. Then follow m lines that describe the operations. Each line starts with an integer ti (1 ≤ ti ≤ 2) indicating the operation type:
  • If ti = 1, then next follow two integers li and ri (1 ≤ li ≤ ri ≤ n), separated by spaces.
  • If ti = 2, then next follow three integers li, ri and di (1 ≤ li ≤ ri ≤ n, 0 ≤ di ≤ 100), separated by spaces.
The first line contains the number of test cases (at most 15). For each test case: The first line contains one integer n (1 ≤ n ≤ 10^5) - the number of integers in the sequence. The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 10^7), separated by spaces. The third line contains one integer m (1 ≤ m ≤ 10^5) - the number of operations. Then follow m lines that describe the operations. Each line starts with an integer ti (1 ≤ ti ≤ 2) indicating the operation type:
  • If ti = 1, then next follow two integers li and ri (1 ≤ li ≤ ri ≤ n), separated by spaces.
  • If ti = 2, then next follow three integers li, ri and di (1 ≤ li ≤ ri ≤ n, 0 ≤ di ≤ 100), separated by spaces.
The first line contains the number of test cases (at most 15). For each test case: The first line contains one integer n (1 ≤ n ≤ 10^5) - the number of integers in the sequence. The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 10^7), separated by spaces. The third line contains one integer m (1 ≤ m ≤ 10^5) - the number of operations. Then follow m lines that describe the operations. Each line starts with an integer ti (1 ≤ ti ≤ 2) indicating the operation type:
  • If ti = 1, then next follow two integers li and ri (1 ≤ li ≤ ri ≤ n), separated by spaces.
  • If ti = 2, then next follow three integers li, ri and di (1 ≤ li ≤ ri ≤ n, 0 ≤ di ≤ 100), separated by spaces.

Output specification

For each query where ti = 1, print the calculated sum modulo 1000000007 (10^9 + 7).
For each query where ti = 1, print the calculated sum modulo 1000000007 (10^9 + 7).
The first line contains the number of test cases (at most 15). For each test case: The first line contains one integer n (1 ≤ n ≤ 10^5) - the number of integers in the sequence. The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 10^7), separated by spaces. The third line contains one integer m (1 ≤ m ≤ 10^5) - the number of operations. Then follow m lines that describe the operations. Each line starts with an integer ti (1 ≤ ti ≤ 2) indicating the operation type:
  • If ti = 1, then next follow two integers li and ri (1 ≤ li ≤ ri ≤ n), separated by spaces.
  • If ti = 2, then next follow three integers li, ri and di (1 ≤ li ≤ ri ≤ n, 0 ≤ di ≤ 100), separated by spaces.

Sample input

1
5
3 1 2 5 6
3
1 1 3
2 2 4 2
1 2 5

Sample output

6
42

Hint(s)


,

,

,

Recommendation

We have carefully selected several similar problems: 3379 | 2156 | 3954 | 1811 | 2141 | 2378