题目描述

在一个塔防小游戏中，有很多防线。 每条防线由一排n个独立的防御体[1 : n]进行防御。
游戏过程中，会不断有敌人对防线进行攻击，每次攻击会指定防御体[l : r]进行攻击力为a的攻击。 第一防线具有护甲，护甲承受攻击后，对应的防御体所受到的伤害为攻击力，但护甲承受的伤害总量到达一定程度后就会破碎，此时防御体所受的伤害加倍。 目前第一防线的力量充足，玩家致力于对后面的防线的建设，不过为确认游戏进度和第一防线的情况，玩家会不时地将鼠标移动到第一防线的某个防御体上，以查看其所受到的伤害。

输入格式：

第一行，两个整数n; q，分别表示防御体个数以及攻击和查询的总数。
第二行， n个数，表示每个防御体护甲的承受能力pi。
接下来 q 行，每行可能具有如下形式
A l r a 表示对防御体$l,l+1,\"cdots,r$进行攻击力为a的攻击
Q x 表示查询防御体x目前所受到的伤害，初始时伤害为0

输出格式：

一行，一个整数，表示所有查询结果之和对1,000,000,009的余数

输入样例#1：

5 7
3 1 4 1 2
A 1 3 2
Q 2
A 1 4 1
Q 1
A 1 4 1
Q 2
Q 1

输出样例#1：

16