我，真是個笨蛋

題目敘述

「原來我已經是個殭屍了。」Sayaka Miki搞懂了這一切後受到了嚴重的打擊，Kyubey只是表示每個知道事實的都會這樣，不如就不說了。已經不是人類的Sayaka Miki要如何面對自己的青梅竹馬Kyosuke Kamijo呢？隔天到了學校，更令人打擊的是剛恢復身體的Kyosuke Kamijo到學校沒多就被另一位女同學表白成功，自己的夢想是實現了，但也讓自己失去所有的事物，心灰意冷的Sayaka Miki想要把自己投注在戰鬥中，這是她活在這世界上僅存的意義了。

為了要能最大化發揮自己的能力，Sayaka Miki統計了一下，發現魔女們的分布恰好落在一條直線上，我們可以用$a_0,a_1,a_2,\cdots ,a_{n-1}$來表示這$n$隻魔女的能力，而魔女的能力會有共伴效應而彼此消長，我們量化魔女的能力到整數上，最初時每位魔女的能力都是$0$，Sayaka Miki發現每隔一段時間，一些相連的魔女的能力會同步的增加減少。而Sayaka Miki有兩種攻擊方法可以攻擊一個範圍$a_l\cdots a_r$內的魔女們，第一種是單刀直入的衝過去，會讓Sayaka Miki損失$a_l+a_{l+1}+\cdots a_r$的魔法能量，第二的是她的大絕，瘋狂亂砍，會因為魔女的數量而急遽的增加魔法消耗量！其大小等於範圍內任兩魔女能力乘積之和，如果只有一隻的話那就不需要消耗任何能量，因為大絕會直接失敗。不過不管承受什麼傷害，魔女能力不會因而改變。

在Sayaka Miki瘋狂的殺戮中，Homura Akemi與Kyoko Sakura正默默的看的這一切，「這樣放任下去行嗎？大量消耗自己的能力，卻沒有任何的補充」Kyoko Sakura好奇的問，卻得到一句冷酷的回答「她會毀滅自己。」如果能計算出Sayaka Miki使用的魔力是否能有一線轉機？這困難的任務就交由你來解決了！

輸入說明

只有單筆測資，測資的第一行有兩個整數$N,Q$表示有$N$隻魔女，能力依序為$a_0,a_1\cdots a_{n-1}$，而依序有$Q$次紀錄，每次紀錄占一行，格式分別如下：

$0~a~b$ 表示$Sayaka Miki$對編號$a,a+1,\cdots b-1,b$的魔女單刀直入衝過去。
$1~a~b$ 表示$Sayaka Miki$對編號$a,a+1,\cdots b-1,b$的魔女使用了瘋狂亂砍。
$2~a~b~c$ 表示此時編號$a,a+1,\cdots b-1,b$的魔女能力同步增加了$c$，已知$|c|\leq 10000$。

保證$0< N,Q\leq 100000$。

輸出說明

對於每一次$Sayaka Miki$使用技能，輸出一行，為其消耗的魔法能量是多少。由於數字很大，請把答案取其除以$1000000009$的餘數，使數值落在$0\sim 1000000009-1$的範圍中。

範例輸入

範例輸出

提示

這個國家把成長期的女性稱為「少女」，那麼終將成為魔女的妳們，就該稱為「魔法少女」吧？
$2\times 500000005=1+1000000009$

Judge Setting

run-time limit: 1000 ms
memory limit: 6553600 byte
測資數量: 0