In front of a Soviet restaurant, there are $N$ people waiting for the restaurant to open. The people are labeled with natural numbers from $1$ to $N$ in the order they gathered in front of the restaurant. The menu offers only one option, the so-called "house specialty," fried eggs. There is no cook in the restaurant, so the guests must prepare their own meals. Additionally, there is only one frying pan in the restaurant, so at any given time, at most one guest can prepare food. Furthermore, there is only one fork and only one knife, so at any given time, at most one guest can eat. Fortunately, there are infinitely many plates in the restaurant, so a guest who finishes preparing food can transfer the finished meal to a plate and wait for the fork and knife to become available.

For each guest, it is known how much time they need to prepare their food and how much time they need to eat it. Your task is to determine the minimum time required for all $N$ guests to finish eating if they decide to prepare and eat their food in an optimal order.

However, that is not all. Before the restaurant opened, $K$ key events occurred of the following types:

• DOLAZI a b – A new guest has arrived who can prepare food in $a$ minutes and eat it in $b$ minutes. The newly arrived guest is labeled with the smallest natural number that has not been assigned to any of the previous guests.
• ODLAZI x – The guest who was the $x$-th to arrive in front of the restaurant has left.
• POREDAK – The guests are impatient and want to know the optimal order of preparing and eating food so that everyone finishes eating in the shortest possible time.

Before the first event, you need to print the minimum time required for all $N$ guests to finish eating. For each event of type DOLAZI or ODLAZI, you need to print the minimum time required for the set of guests currently in front of the restaurant to finish eating. Finally, after each event of type POREDAK, you need to print the order in which it is optimal to prepare and eat food so that the set of people currently in front of the restaurant finishes eating in the shortest possible time.

Input

The first line contains the natural numbers $N$ and $K$ from the problem description.

In the $i$-th of the next $N$ lines, there are two natural numbers $a_i$ and $b_i$ ($1 \le a_i, b_i \le 10^9$) which indicate that the guest labeled $i$ can prepare food in $a_i$ minutes and eat it in $b_i$ minutes.

The next $K$ lines each contain one key event in the format described in the problem text. You may assume that the events are mutually consistent. That is, a guest who has not yet arrived will never leave. Also, there will be at least one guest in front of the restaurant at all times, and the speed of preparing and eating food for newly arrived guests will obey the aforementioned constraints.

Output

In the first line, you need to print the minimum time required for the initial $N$ guests to finish eating.

If the $i$-th event is of type DOLAZI or ODLAZI, then in the $(i+1)$-th line, you need to print the minimum time required for the set of guests who are in front of the restaurant after the $i$-th event to finish eating.

If the $i$-th event is of type POREDAK, then in the $(i+1)$-th line, you need to print $2x$ numbers, where $x$ denotes the number of guests currently in front of the restaurant. The first $x$ numbers should contain the labels of the guests in the order they will prepare their food, while the last $x$ numbers should contain the labels of the guests in the order they will eat their food.

Subtasks

Examples

Input 1

2 1
1 3
2 3
POREDAK

Output 1

7
1 2 1 2

Input 2

1 4
4 3
DOLAZI 3 8
DOLAZI 5 2
ODLAZI 1
ODLAZI 3

Output 2

7
14
16
13
11

Note

Explanation of the first example:

The guest labeled 1 starts preparing their meal and finishes in the first minute. Then that same person starts eating, and the guest labeled 2 starts preparing their meal. In the third minute, the guest labeled 2 finishes preparing their meal, but the guest labeled 1 has not yet finished eating, so the second guest must wait until the fourth minute. Finally, in the fourth minute, the guest labeled 2 starts their meal, which they finish in the seventh minute.