Gravel

All submissions for this problem are available.

Bob has n heap(s) of gravel (initially there are exactly c piece(s) in each). He wants to do m operation(s) with that heaps, each maybe:

• adding pieces of gravel onto the heaps from u to v, exactly k pieces for each,
• or querying "how many pieces of gravel are there in the heap p now?".

Request

Help Bob do operations of the second type.

Input

• The first line contains the integers n,m,c, respectively.
• m following lines, each forms:
  • S u v k to describe an operation of the first type.
  • Q p to describe an operation of the second type.

(Each integer on a same line, or between the characters S, Q and the integers is separated by at least one space character)

Output

For each operation of the second type, output (on a single line) an integer answering to the respective query (follows the respective Input order).

Example

Input:

7 5 0
Q 7
S 1 7 1
Q 3
S 1 3 1
Q 3

Output:

0
1
2

Limitations

• 0<n≤10⁶
• 0<m≤250 000
• 0<u≤v≤n
• 0≤c,k≤10⁹
• 0<p≤n

---

Date:	2010-05-05
Time limit:	2s
Source limit:	50000B
Languages:	All except: SCALA HASK ERL CAML CLPS PRLG WSPC BF ICK JS