Kile is the head chef of a famous restaurant in Zagreb. He recently quit his job to pursue his dream of becoming a baker at Mr. Malnar's pastry shop, because Mr. Malnar's is simply the best. Plus, dessert has always been his favorite part of a meal.

On his first day at work, he was greeted in the kitchen by a table with $n$ plates, and on the $i$-th plate, there were $A_i$ exquisite pastries. Kile is ready for work, but he was unaware of one key problem: working with all these sweets makes him hungry every now and then.

Every minute, he will perform one of three actions:

• ISPECI x y – adds $y$ new pastries to the $x$-th plate.
• POJEDI x y – Kile is so hungry that he takes and eats $y$ pastries from the $x$-th plate.
• POSLUZI y – every plate that contains at least $y$ pastries is taken out of the kitchen and served to the guests.

The plates are not returned to the kitchen, and the indices of the plates remain unchanged. Kile is interested in how many plates were taken out of the kitchen in each individual POSLUZI operation. Help him answer his question during the next $q$ minutes.

Input

The first line contains the natural numbers $n$ ($1 \le n \le 10^5$) and $q$ ($1 \le q \le 10^5$) from the problem description.

The second line contains $n$ numbers, where the $i$-th number denotes $a_i$ ($0 \le a_i \le 10^9$).

The next $q$ lines contain the description of the events.

If the $i$-th event is ISPECI, the line contains the numbers $x$ ($1 \le x \le n$) and $y$ ($0 \le y \le 10^9$).

If the $i$-th event is POJEDI, the line contains the numbers $x$ ($1 \le x \le n$) and $y$ ($0 \le y \le 10^9$). We guarantee that Kile will successfully perform all POJEDI events, i.e., the $x$-th plate will always contain at least $y$ pastries.

If the $i$-th event is POSLUZI, the line contains the number $y$ ($0 \le y \le 10^9$).

Output

For each POSLUZI query, you need to print how many plates were taken out.

Examples

Input 1

6 7
2 5 0 3 7 1
POSLUZI 6
ISPECI 3 4
POJEDI 2 2
ISPECI 1 3
POSLUZI 4
POSLUZI 3
ISPECI 6 4

Output 1

1
2
2

Input 2

4 6
1 2 6 2
ISPECI 2 2
POSLUZI 3
POJEDI 1 1
POSLUZI 1
ISPECI 1 3
POSLUZI 4

Output 2

2
1
0