After trying so many start-up business ideas, you feel too drained to continue to entrepreneur life. Instead, you join a nondescript consultancy, where you help banks drain the funds of their customers to dump into crypto.

The bank you are consulting with has ~n~ customers, numbered from ~1~ to ~n~, each with some initial balance. The bank wants to complete ~m~ operations, with one of two types:

• DRAIN L R X: For each customer between numbers ~L~ and ~R~ (inclusive), drain their accounts so they have no more than X dollars. If a customer already has X or less dollars, nothing happens to them.
• AUDIT L R: For each customer between numbers numbers ~L~ and ~R~ (inclusive), add up their balances and output them.

Help the bank complete all requested operations.

Input

The first line contains two integers ~n~ and ~m~ ~(1 \leq n, m \leq 10^5)~, indicating that the bank has ~n~ customers, and wants to do ~m~ operations.

The second line contains ~n~ integers ~b_1, \dots, b_n~ (~0 \leq b_i \leq 10^9~), representing the initial balances of each of the customers ~1~ through ~n~.

The next ~m~ lines are in one of two forms:

• DRAIN L R X: Indicating that you need to do the DRAIN operation for customers between ~L~ and ~R~ (~1 \leq L, R \leq n~) for value ~X~ (~1 \leq X \leq 10^9~).
• AUDIT L R: Indicating that you need to do the AUDIT operation for customers between ~L~ and ~R~ (~1 \leq L, R \leq n~) and output the answer.

Output

Your outputs will come from all AUDIT operations. There will always be at least one.

Example

Input 1

5 5
6 7 3 4 7
AUDIT 1 3
DRAIN 1 5 5
AUDIT 2 2
DRAIN 3 5 1
AUDIT 1 5

Output 1

16
5
13

The first, third and five queries are AUDITS, with outputs of 16, 5 and 13 respectively.

Input 2

3 7
10 10 10
AUDIT 1 3
DRAIN 2 2 10
AUDIT 1 3
DRAIN 2 2 5
AUDIT 1 3
DRAIN 3 3 1
AUDIT 1 3

Output 2

30
30
25
16

Input 3

5 7
5 4 5 4 5
AUDIT 1 3
DRAIN 1 4 4
AUDIT 1 3
AUDIT 2 4
AUDIT 3 5
DRAIN 1 5 1
AUDIT 1 5

Output 3

14
12
12
13
5