在 OI 界,有一个无人不知无人不晓,OI 水平前无古人后无来者的胡策,江湖人称一眼秒题胡大爷!
今天胡策正在研究一个远古传下来的数列:a0,a1,a2,…,数列的第 k 项为 ak。这个数列有特别的性质,对于 i>1 有:25ai+20ai−1=12ai−2。因为流传的时间太过久远,a0 和 a1 的值都已经看不清了,但是在最后还记载着,这个数列有一个特别的性质:对于任意的 i≥0,都有 ai≥0。
然而胡策已经看穿了一切:对于任意一个正数 t,满足 a0=t 的数列 a 是唯一的!但是,他想拿这个问题考一考拜胡策为师的你。
具体来说,胡策会给你一个长度为 n 的表格,一开始每个格子都写着 0。有时他会让你将 a0=t 时的数列 a 从第 p 项到第 p+r−l 项的值分别写入表格中第 l 到第 r 格(覆盖原有的值),有时他会询问表格中某一段连续的格子中的数的和。
当然,作为胡策的弟子,你必须在胡策提出一个询问的时候马上作出回应。
因为这是一个远古的问题,胡策只给了你一台远古的计算机,它只有 64MB的内存。
输入格式
第一行两个正整数 n,m。分别表示表格的长度和操作个数。
接下来 m 行,每行描述一个操作。每行的第一个整数 type 描述了操作的类型,type=1 表示是修改操作,type=2 表示是询问操作。
如果是修改操作,接下来有四个整数 l,r,t,p,意义如上所述。
如果是询问操作,接下来有两个整数 l,r,意义如上所述。
由于胡策需要确定你是在线回答他的问题,输入中的 l,r 是加密了的。于是你需要把输入中的 l,r 分别异或 lastans 来得到实际的 l,r。lastans 表示上一次询问操作的答案,初始为 0。保证实际的 l,r 满足 1≤l≤r≤n。
输出格式
对每个询问操作输出一行,表示询问的答案。
答案一定能写成 vu 的形式,其中 v,u 是互质的整数,且 u>0。为了避免分数,你只用输出一个介于 0 到 109+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 张天扬