Optimal Battlefield Temperature

A contest is about to begin. Each warrior has two attributes: temperature and energy. There are two factions:

• Ice warriors: Their skills inflict freezing damage that lowers the temperature. Hence, an Ice warrior can only participate if the battlefield temperature is not lower than his own temperature.
• Fire warriors: Their skills burn by raising the temperature. A Fire warrior may participate only if the battlefield temperature is not higher than his own temperature.

Once a battlefield temperature T is chosen, the eligible warriors from each faction line up:

• Ice warriors: All warriors with temperature ≤ T are selected and sorted in increasing order of their own temperature. When temperatures are equal, the warrior with higher energy is placed earlier.
• Fire warriors: All warriors with temperature ≥ T are selected and sorted in decreasing order of their own temperature. When temperatures are equal, the warrior with higher energy comes first.

The battle is conducted sequentially. The first warrior in the Ice queue battles the first in the Fire queue. In each duel, both warriors expend the same amount of energy, equal to the lesser of the two current energies. The warrior whose energy depletes (i.e. becomes 0) is eliminated, while the other (with leftover energy) continues to fight the next opponent. If both warriors exhaust their energy simultaneously, both are eliminated and the next pair (the next available warriors) will fight. The duels continue until one faction has no warriors left. It can be shown that the total energy consumption in the battle equals 2\min(S_{ice}, S_{fire}), where S_ice is the sum of energies of the participating Ice warriors and S_fire is the sum of energies of the participating Fire warriors.

Your task is to determine the optimal battlefield temperature. That is, among all temperatures that allow at least one warrior from each faction to participate, choose the temperature that maximizes the total energy consumption (i.e. 2\min(S_{ice}, S_{fire})). If there are multiple temperatures yielding the same maximum consumption, choose the highest such temperature.

---

The contest is currently in the registration phase – no warrior has registered yet. You will receive a sequence of events. Each event is either:

• 1 faction temperature energy (a registration event), where faction is either Ice or Fire, or
• 2 id (a withdrawal event) – which withdraws the registration corresponding to the id of the sign‐up event (the first registration has id 1, the second 2, etc.).

After each event, output the current optimal battlefield temperature and the corresponding total energy consumption (i.e. temperature total_consumption). If under the current registration there is no valid matchup (i.e. if one faction has no eligible warriors for any battlefield temperature), simply output Peace.

Note on computation: For a given temperature T, the participating warriors are defined as follows:

• Ice warriors: All with warrior_temperature ≤ T (contribute to S_ice).
• Fire warriors: All with warrior_temperature ≥ T (contribute to S_fire).

The total consumption is then:

\[ Total = 2 \cdot \min\Big(\sum_{\text{Ice, }t \le T} energy, \; \sum_{\text{Fire, }t \ge T} energy\Big). \]

You only need to consider battlefield temperatures T in the interval \([T_{min}, T_{max}]\), where \(T_{min}\) is the minimum temperature among all Ice warriors, and \(T_{max}\) is the maximum temperature among all Fire warriors. Since the functions \(S_{ice}(T)\) and \(S_{fire}(T)\) are step functions (changing only at warriors’ temperature values), it is sufficient to consider candidate temperatures equal to the warriors’ temperatures that lie in \([T_{min}, T_{max}]\).

inputFormat

The first line contains an integer Q (the number of events). The next Q lines each contain an event, which is formatted as follows:

• Registration: 1 faction temperature energy. faction is either Ice or Fire.
• Withdrawal: 2 id, where id is the sign-up event number to be withdrawn.

After each event, you must immediately output the answer for the current registration state.

outputFormat

After each event, output one line. If a valid contest can be held (i.e. there is at least one eligible warrior from each faction), print the optimal battlefield temperature and the total energy consumed (separated by a space). Otherwise, print Peace.

sample

3
1 Ice 10 100
1 Fire 20 200
2 1

Peace
20 200
Peace

</p>