题目描述

在一个塔防小游戏中，有很多防线。每条防线由一排 $n$ 个独立的防御体 $[1 : n]$ 进行防御。

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

输入格式

第一行，两个整数 $n$ 和 $q$，分别表示防御体个数以及攻击和查询的总数。

第二行，$n$ 个数，表示每个防御体护甲的承受能力 $p_i$ 。

接下来 $q$ 行，每行可能具有如下形式：

A l r a 表示对防御体 $l,l+1,\cdots,r$ 进行攻击力为 $a$ 的攻击；

Q x 表示查询防御体 $x$ 目前所受到的伤害，初始时伤害为 $0$ 。

输出格式

一行，一个整数，表示所有查询结果之和对 ${10}^9+9$ 取模的余数。

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

16

提示

【样例解释】

3/0 1/0 4/0 1/0 2/0

[A 1 3 2]

1/2 2 2/2 1/0 2/0

[Q 2] ! 2

[A 1 4 1]

3 4 1/3 1 2/0

[Q 1] -> 3

[A 1 4 1]

5 6 4 3 2/0

[Q 2] -> 6

[Q 1] -> 5

【数据范围】

$30 \%$ 的数据， $q \le 10^3$。

$100 \%$ 的数据，$1 \le n \le 10^5$，$1 \le q \le 10^5$，$0 \le p_i \le 10^6$，$0 \le a \le 10^4$。