Salaries in big tech are becoming increasingly competitive, so top FAANG company Famazon is rolling out a new payment structure.

Famazon's corporate hierarchy can be modeled as a complete binary tree with ~n~ employees, numbered from ~1~ to ~n~. Employee ~1~ is the CEO. For every employee ~i~ ~(1 \le i \leq n)~, their direct subordinates (if they exist) are employees ~2i~ and ~2i+1~, provided these indices do not exceed ~n~.

Initially, all employees have a salary of ~0~ dollars. Whenever an employee receives a raise, their salary increases by some amount. Each employee directly under them receives a raise of one dollar less, their subordinates receive one dollar less than that, and so on. It is guaranteed that this number remains above ~0~ for all employees.

Throughout the year, ~m~ events will occur at Famazon:

• Raise: A specified employee receives a raise, along with all employees under them as described above.
• Audit: The salary of a specified employee is audited and must be reported.

Help Famazon manage their company!

Input

The first line contains two integers ~n~ and ~m~ (~1 \le n \le 131072~, ~1 \leq m \leq 10^5~), the number of employees at Famazon, and the number of queries. It is guaranteed that ~n = 2^k - 1~ for some positive integer ~k~. The employees are numbered from ~1~ to ~n~ and form a complete binary tree, where:

• Employee ~1~ is the root.
• For every employee ~i~, their left child (if it exists) is ~2i~ and their right child is ~2i + 1~.
• Employees with index greater than ~n~ do not exist.

The next ~m~ lines will be in one of two forms:

• PAYRISE A X, indicating that employee ~A~ should get a raise of ~X~ dollars, the employees under them by one less, and so on. If ~n = 2^k -1~, ~k \leq X \leq 10^9~.
• AUDIT A, indicating that you should output the pay of employee ~A~.

Output

Output the correct salaries for every AUDIT query.

Example

Input 1

7 6
PAYRISE 2 5
PAYRISE 1 2
AUDIT 2
AUDIT 1
PAYRISE 6 10
AUDIT 6

Output 1

6
2
10