In the OI community, there is a legendary figure known to all, whose competitive programming skills are unparalleled: Hu Ce, also known as "Master Hu, the One-Second Problem Solver!"

Today, Hu Ce is studying an ancient sequence: $a_0, a_1, a_2, \dots$, where the $k$-th term is $a_k$. This sequence has a special property: for $i > 1$, $25 a_i + 20 a_{i - 1} = 12 a_{i - 2}$. Because the sequence is so ancient, the values of $a_0$ and $a_1$ are no longer legible. However, it is recorded that the sequence has a special property: for any $i \geq 0$, $a_i \geq 0$.

Hu Ce has seen through it all: for any positive number $t$, the sequence $a$ satisfying $a_0 = t$ is unique! However, he wants to test you, his student.

Specifically, Hu Ce gives you a table of length $n$, initially filled with $0$ in every cell. Sometimes he will ask you to write the values of the sequence $a$ (where $a_0 = t$) from the $p$-th term to the $(p + r - l)$-th term into the $l$-th to $r$-th cells of the table (overwriting existing values). Other times, he will ask for the sum of the numbers in a continuous segment of the table.

As a student of Hu Ce, you must respond immediately whenever he poses a query.

Because this is an ancient problem, Hu Ce has provided you with an ancient computer that has only $64\texttt{MB}$ of memory.

Input

The first line contains two positive integers $n$ and $m$, representing the length of the table and the number of operations, respectively.

The next $m$ lines each describe an operation. The first integer $\mathrm{type}$ in each line describes the type of operation: $\mathrm{type} = 1$ denotes an update operation, and $\mathrm{type} = 2$ denotes a query operation.

If it is an update operation, it is followed by four integers $l, r, t, p$, with meanings as described above.

If it is a query operation, it is followed by two integers $l, r$, with meanings as described above.

Since Hu Ce needs to ensure you are answering his questions online, the $l$ and $r$ in the input are encrypted. You must XOR the $l$ and $r$ from the input with $\mathrm{lastans}$ to obtain the actual $l$ and $r$. $\mathrm{lastans}$ is the answer to the previous query operation, initially $0$. It is guaranteed that the actual $l$ and $r$ satisfy $1 \leq l \leq r \leq n$.

Output

For each query operation, output a single line representing the answer to the query.

The answer can always be written in the form $\frac{v}{u}$, where $v$ and $u$ are coprime integers and $u > 0$. To avoid fractions, you only need to output an integer $x$ between $0$ and $10^9 + 8$ such that $ux \equiv v \pmod{10^9 + 9}$. Clearly, such an $x$ is unique in this problem.

Examples

Input 1

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

Output 1

867840008

Note 1

The answer is $\frac{592}{3125}$, and the corresponding $x$ is $867840008$.

Input 2

1000000000 3
1 1 12450 6666666 23333333
1 6666 99999 2333 44444
2 1 1000000000

Output 2

431287288

Constraints

For 20% of the data, $n, m \leq 1000$.

For 50% of the data, $n, m \leq 30000$.

For 100% of the data, $1 \leq n \leq 10^9$, $1 \leq m \leq 10^5$, $1 \leq t \leq 10^9$, $1 \leq p \leq 10^9$.