在 OI 界，有一个无人不知无人不晓，OI 水平前无古人后无来者的胡策，江湖人称一眼秒题胡大爷！

今天胡策正在研究一个远古传下来的数列：$a_0, a_1, a_2, \dots$，数列的第 $k$ 项为 $a_k$。这个数列有特别的性质，对于 $i > 1$ 有：$25 a_i + 20 a_{i - 1} = 12 a_{i - 2}$。因为流传的时间太过久远，$a_0$ 和 $a_1$ 的值都已经看不清了，但是在最后还记载着，这个数列有一个特别的性质：对于任意的 $i \geq 0$，都有 $a_i \geq 0$。

然而胡策已经看穿了一切：对于任意一个正数 $t$，满足 $a_0 = t$ 的数列 $a$ 是唯一的！但是，他想拿这个问题考一考拜胡策为师的你。

具体来说，胡策会给你一个长度为 $n$ 的表格，一开始每个格子都写着 $0$。有时他会让你将 $a_0 = t$ 时的数列 $a$ 从第 $p$ 项到第 $p + r - l$ 项的值分别写入表格中第 $l$ 到第 $r$ 格（覆盖原有的值），有时他会询问表格中某一段连续的格子中的数的和。

当然，作为胡策的弟子，你必须在胡策提出一个询问的时候马上作出回应。

因为这是一个远古的问题，胡策只给了你一台远古的计算机，它只有 $64\texttt{MB}$的内存。

输入格式

第一行两个正整数 $n,m$。分别表示表格的长度和操作个数。

接下来 $m$ 行，每行描述一个操作。每行的第一个整数 $\mathrm{type}$ 描述了操作的类型，$\mathrm{type} = 1$ 表示是修改操作，$\mathrm{type} = 2$ 表示是询问操作。

如果是修改操作，接下来有四个整数 $l,r,t,p$，意义如上所述。

如果是询问操作，接下来有两个整数 $l,r$，意义如上所述。

由于胡策需要确定你是在线回答他的问题，输入中的 $l, r$ 是加密了的。于是你需要把输入中的 $l, r$ 分别异或 $\mathrm{lastans}$ 来得到实际的 $l, r$。$\mathrm{lastans}$ 表示上一次询问操作的答案，初始为 $0$。保证实际的 $l, r$ 满足 $1 \leq l \leq r \leq n$。

输出格式

对每个询问操作输出一行，表示询问的答案。

答案一定能写成 $\frac{v}{u}$ 的形式，其中 $v, u$ 是互质的整数，且 $u > 0$。为了避免分数，你只用输出一个介于 $0$ 到 $10^9 + 8$ 之间的整数 $x$ 满足 $ux \equiv v \pmod{10^9 + 9}$ 来表示答案。显然在本题中，这样的 $x$ 是唯一的。

样例一

input

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

output

867840008

explanation

答案是 $\frac{592}{3125}$，对应的 $x$ 为 $867840008$。

样例二

input

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

output

431287288

样例三

见样例数据下载。

限制与约定

对于 20% 的数据，$n,m \leq 1000$。

对于 50% 的数据，$n,m \leq 30000$。

对于 100% 的数据，$1 \leq n \leq 10^9$，$1 \leq m \leq 10^5$，$1 \leq t \leq 10^9$，$1 \leq p \leq 10^9$。

时间限制：$1\texttt{s}$

空间限制：$64\texttt{MB}$

来源

中国国家集训队互测2015 - By 张天扬

下载

样例数据下载