Description

In a tower defense mini-game, there are many defense lines. Each defense line is defended by a row of $n$ independent defense units $[1 : n]$.

During the game, enemies keep attacking the defense line. Each attack specifies defense units $[l : r]$ and applies an attack with attack power $a$. The first defense line has armor. After the armor takes an attack, the corresponding defense unit suffers damage equal to the attack power. However, once the total damage absorbed by the armor reaches a certain limit, it breaks, and from then on the damage the defense unit takes is doubled. The first defense line is currently strong, and the player is focusing on building the later lines. To monitor the game progress and the status of the first defense line, the player occasionally moves the mouse over a defense unit in the first defense line to view the damage it has taken.

Input Format

The first line contains two integers $n$ and $q$, denoting the number of defense units and the total number of attacks and queries.

The second line contains $n$ numbers, denoting the armor capacity $p_i$ of each defense unit.

Then follow $q$ lines, each in one of the following forms:

A l r a means applying an attack with attack power $a$ to defense units $l, l+1, \cdots, r$;

Q x means querying the current damage taken by defense unit $x$, with initial damage being $0$.

Output Format

One line containing one integer: the sum of all query results modulo ${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

Hint

【Sample Explanation】

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

【Constraints】

For 30% of the testdata, $q \le 10^3$.

For 100% of the testdata, $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$.

Translated by ChatGPT 5