Soviet Restaurant Scheduling

There are initially \(N\) people queuing at a Soviet restaurant, numbered from 1 to \(N\). The restaurant offers only one dish — the signature fried egg. There is no chef, so each customer must cook his own food. Due to limited equipment, at any given time at most one person can be cooking and at most one person can be eating.

Each person \(i\) needs \(a_i\) time to cook and \(b_i\) time to eat. Every customer must finish cooking before he starts eating. However, the orders in which they cook and eat can be arranged differently. In other words, the cooking sequence and the eating sequence (which must respect the individual precedence: for each person, cooking comes before eating) may be different.

Define the total dining time as the time elapsed from when the first person begins cooking until the last person finishes eating. The goal is to minimize this makespan.

This problem is the classical two‐machine flow shop scheduling problem which can be solved optimally by Johnson's rule. According to Johnson's rule, partition the jobs (customers) into two sets:

• S₁ = { \(i\) such that \(a_i \le b_i\) } (sort these in increasing order of \(a_i\) )
• S₂ = { \(i\) such that \(a_i > b_i\) } (sort these in decreasing order of \(b_i\) )

The optimal processing order is the concatenation \(S₁ \Vert S₂\) (i.e. the same sequence is used for both cooking and eating). The makespan can be computed by simulating the schedule as follows:

[ \begin{aligned} T_{A} &= 0, \quad T_{B} = 0, \ \text{for each job } i \text{ in the order:}
\quad T_{A} &+= a_i, \ \quad T_{B} &= \max(T_{A}, T_{B}) + b_i, \ \end{aligned} ]

The final value \(T_{B}\) is the minimum total dining time.

In addition to the initial set of customers, there are \(M\) events processed sequentially. Each event is one of the following types:

• DOLAZI a b: A new customer arrives with cooking time \(a\) and eating time \(b\). If this is the \(i\)th new arrival then his label is \(N+i\).
• ODLAZI x: The customer with label \(x\) leaves the queue.
• POREDAK: The customers want to know the optimal strategy. In response, you must output the optimal cooking/eating order (i.e. the Johnson sequence).

For events of type DOLAZI and ODLAZI, after processing the event you should output a single number — the minimum total dining time (i.e. \(T_B\) as computed above). For an event of type POREDAK, output two lines: the first line is the cooking order (a space‐separated list of customer labels) and the second line is the eating order (which is identical to the cooking order in an optimal Johnson schedule).

inputFormat

The first line contains two integers \(N\) and \(M\) — the initial number of customers and the number of events, respectively.

The next \(N\) lines each contain two integers \(a_i\) and \(b_i\) representing the cooking and eating times of the \(i\)th customer.

Each of the next \(M\) lines represents an event in one of the following formats:

• DOLAZI a b
• ODLAZI x
• POREDAK

It is guaranteed that for every ODLAZI event the customer with label \(x\) is present in the queue.

outputFormat

For each event, output as follows:

• If the event is DOLAZI or ODLAZI, output a single integer — the minimum total dining time after the event.
• If the event is POREDAK, output two lines:
  • The first line is a space‐separated list of the customer labels indicating the optimal cooking order.
  • The second line is the optimal eating order (which is identical to the cooking order in the Johnson schedule).

sample

2 3
3 5
4 1
POREDAK
DOLAZI 2 2
ODLAZI 1

1 2
1 2
11
7

</p>