胡策的数列

时间限制:20s      空间限制:64MB

题目描述

在OI界,有一个无人不知无人不晓,OI水平前无古人后无来者的胡策,江湖人称一眼秒题胡大爷!
今天胡策正在研究一个远古传下来的数列:a[0]=... , a[1]=... ,对i>1,有 25a[i]+20a[i-1]=12a[i-2]。因为流传的时间太过久远,a[0]和a[1]的值都已经看不清了,但是在最后还记载着,这个数列有一个特别的性质:对于任意的i>=0,都有a[i]>=0。
然而胡大爷已经看穿了一切:对于任意一个正数a[0],这个数列都是唯一的!但是,他想拿这个问题考一考拜胡大爷为师的你。
具体来说,胡大爷会给你一个长度为n的表格,一开始每个格子都写着0。有时他会让你将a[0]=t 时数列从第p项开始的一段写入表格中第 l 到第 r 格(覆盖原有的值),有时他会询问表格中某一段连续的格子中的数的和。
当然,作为胡大爷的弟子,你必须在胡大爷提出一个询问的时候马上作出回应。
因为这是一个远古的问题,胡大爷只给了你一台远古的计算机,它只有64MB的内存。


输入格式

第一行两个整数n,m。分别表示表格的长度和操作个数。
接下来m行,每行描述一个操作。每行的第一个整数type描述了操作的类型,type=1表示是修改操作,type=2表示是询问操作。
如果是修改操作,接下来有四个整数l,r,t,p,意义如上所述。
如果是询问操作,接下来有两个整数l,r,意义如上所述。
为了体现在线,实际的l,r为输入的l,r对lastans取异或后的答案。lastans表示上一次询问操作的答案,初始为0。


输出格式

对每个询问操作输出一行,表示询问的答案。
为了避免实数,输出对10^9+9取模。


样例输入

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

样例输出

867840008

提示

对于100%的数据,1<=n<=10^9,1<=m<=10^5,1<=t<=10^9,1<=p<=10^9,1<=l<=r<=n。


题目来源

2015年集训队互测