#P11735. [集训队互测 2015] 胡策的数列

[集训队互测 2015] 胡策的数列

题目描述

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

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

然而胡策已经看穿了一切:对于任意一个正数 tt,满足 a0=ta_0 = t 的数列 aa 是唯一的!但是,他想拿这个问题考一考拜胡策为师的你。

具体来说,胡策会给你一个长度为 nn 的表格,一开始每个格子都写着 00。有时他会让你将 a0=ta_0 = t 时的数列 aa 从第 pp 项到第 p+rlp + r - l 项的值分别写入表格中第 ll 到第 rr 格(覆盖原有的值),有时他会询问表格中某一段连续的格子中的数的和。

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

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

输入格式

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

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

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

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

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

输出格式

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

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

3 3
1 1 3 2 3
1 2 2 4 5
2 1 3
867840008
1000000000 3
1 1 12450 6666666 23333333
1 6666 99999 2333 44444
2 1 1000000000
431287288

提示

数据范围

  • 对于 20% 的数据,n,m1000n,m \leq 1000
  • 对于 50% 的数据,n,m30000n,m \leq 30000
  • 对于 100% 的数据,1n1091 \leq n \leq 10^91m1051 \leq m \leq 10^51t1091 \leq t \leq 10^91p1091 \leq p \leq 10^9