D. Deaga Loves Sequences
time limit per test
6.5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Davi Holanda, usually known by his nickname, Deaga, has been fiddling around with arithmetic progressions, as it's something very important to know for the entrance exam of the Institute of Meaningful Equations, otherwise known as IME. He discovered the existence of third-order arithmetic progressions, which are arithmetic progressions that, given the first four elements, follow the construction rule: $$$a_{i + 3} - 3a_{i + 2} + 3a_{i + 1} - a_i = k$$$, where $$$k$$$ is some non-zero constant. The constant varies depending on the sequence.

In order to furthermore learn about this type of arithmetic sequence, he began playing around with making operations with it. He got an array $$$v$$$, of length $$$n$$$, and given the first four elements and two indices $$$i$$$ and $$$j$$$, $$$(i \lt j)$$$, he'd add the elements of the sequence onto the array. Of course he'd add them in order, with the first element being added to index $$$i$$$, and the $$$(j - i)^{th}$$$ element being added to index $$$j$$$. However, he'd perform these operations given some restrictions:

  • The constant $$$k$$$ of the given sequence is divisible by $$$6$$$.
  • The following is true: $$$(a_2 - a_0 - \frac{4k}{3}) \equiv 0 \mod 2$$$.

Deaga does this many times and ends up getting bored doing all the calculations, and asks for your help to speed things up! Based on the initially empty array, he performs $$$q$$$ queries, in which one will add a certain sequence to a certain range of the array, and another one which will ask the sum of elements of a certain range.

Such graphic depicts what a third-order arithmetic progression looks like
Input

The first line of the input contains two integers, $$$n$$$ and $$$q$$$, $$$(4 \leq n \leq 2 \times 10^5)$$$, $$$(1 \leq q \leq 2 \times 10^5)$$$ — the size of the empty array and the amount of queries.

The next $$$q$$$ lines will contain information about the $$$i^{th}$$$ query done by Deaga. Each line will start with an integer $$$t_i$$$, $$$(1 \leq t_i \leq 2)$$$ — the type of query.

  • For $$$t_i = 1$$$, 6 integers, $$$l$$$, $$$r$$$, $$$a_0$$$, $$$a_1$$$, $$$a_2$$$, $$$a_3$$$, $$$(1 \leq l \lt r \leq n), (r - l \geq 3)$$$, $$$(1 \leq a_0, a_1, a_2, a_3 \leq 10^6)$$$ — the range of the update on the array and the first four elements of the sequence. It is guaranteed that this is a third-order arithmetic progression and that it follows the restrictions above.
  • For $$$t_i = 2$$$, 2 integers, $$$l$$$ and $$$r$$$, $$$(1 \leq l \leq r \leq n)$$$ — the range that Deaga wants to know the sum of. It is guaranteed that there's at least one query of this type.
Output

For every query in which $$$t_i = 2$$$, print out the sum of the elements in the range $$$[l, r]$$$. Since the sum can be very large, print out the sum modulo Deaga's favorite prime number: 1000696969.

Examples
Input
7 8
1 1 7 1 2 11 34
2 1 1
2 2 2
2 3 3
2 4 4
2 5 5
2 6 6
2 7 7
Output
1
2
11
34
77
146
247
Input
15 8
1 1 10 2 545 2224 5177
2 1 5
2 6 10
2 1 10
1 8 15 61 19 3 1
2 1 10
2 11 15
2 14 15
Output
17490
172265
189755
189838
1000696814
1000696821