Description

A match is about to begin.

Each warrior has two attributes: temperature and energy. There are two factions of warriors. Ice warriors’ skills cool the surroundings and deal freezing damage, so the arena temperature must be no lower than the warrior’s own temperature for them to participate. Fire warriors’ skills heat the surroundings and deal burning damage, so the arena temperature must be no higher than the warrior’s own temperature for them to participate.

Once the arena temperature is fixed, the warriors who can participate on each side form a queue. Ice warriors are sorted by their own temperature from low to high, and fire warriors are sorted by their own temperature from high to low. If temperatures are equal, the warrior with higher energy goes first. First, the first warriors of both sides fight. They consume the same amount of energy; the warrior with less energy will run out of energy and leave the match, while the warrior with remaining energy continues to fight the next warrior on the other side (if both run out of energy, then the next warriors on both sides fight). This repeats until one side’s queue becomes empty, and the match ends.

You need to find the best arena temperature: the maximum temperature value among those that make the total energy consumed by both sides as large as possible.

Now, the match is still in the registration stage, and currently no warriors have registered. Next, you will continuously receive registration messages and withdrawal messages. A registration message contains the faction and the two attributes of the registering warrior, and a withdrawal message contains the index of the registration message to withdraw. Every time the registration status changes (i.e., you receive one message), you must immediately report the current best arena temperature, and the sum of the total energy consumed by both sides at that temperature. If under the current situation the match cannot be held at any temperature (i.e., one side has no warrior that can participate), output Peace.

Input Format

The first line contains an integer $Q$, the number of messages.

The next $Q$ lines are either 1 t x y $(t \in \{0, 1\}$, and $x$ and $y$ are both positive integers$)$ or 2 k ($k$ is a positive integer):

1 t x y denotes a registration message. If $t = 0$, the registering warrior is an ice warrior; if $t = 1$, the registering warrior is a fire warrior. $x$ is the warrior’s own temperature, and $y$ is the warrior’s energy.

2 k denotes a withdrawal message, withdrawing the $k$-th message. The withdrawn message is guaranteed to be a registration message. A withdrawn message will not be withdrawn again.

Output Format

Output $Q$ lines. Each line contains two positive integers separated by one space, representing the current best temperature and the sum of the total energy consumed by both sides at that temperature.

8
1 1 103 150
1 0 100 100
1 1 102 150
1 0 103 300
2 1
1 1 101 100
1 1 104 350
1 0 100 400

Peace
103 200
103 200
103 300
102 200
102 200
104 700
102 1000

Hint

Sample 1 Explanation

For convenience, assume that if the $k$-th message is a registration message, then the corresponding warrior is warrior $k$. In the sample, warriors $1,2,3,4,6,7,8$ exist. Since the 5-th message is a withdrawal message, there is no warrior $5$.

The outputs are explained one by one below:

1. Only fire warriors exist: warrior $1$. The match cannot be held, output Peace.
2. Temperatures $100 \sim 103$ can all achieve the maximum consumed energy $200$: warrior $1$ vs warrior $2$ consumes energy $200$, so the best temperature is $103$.
3. Temperatures $100 \sim 103$ can all achieve the maximum consumed energy $200$: warrior $1$ vs warrior $2$ consumes energy $200$, so the best temperature is $103$.
4. Temperature $103$ can achieve the maximum consumed energy $300$: first, warrior $1$ vs warrior $2$ consumes energy $200$; then, warrior $1$ vs warrior $4$ consumes energy $100$, so the best temperature is $103$.
5. From now on, warrior $1$ no longer exists. Temperatures $100 \sim 102$ can achieve the maximum consumed energy $200$: warrior $2$ vs warrior $3$ consumes energy $200$, so the best temperature is $102$.

Sample 2

See the additional files icefire2.in and icefire2.ans.

Constraints

$10\%$ of the data: $Q \leq 100$, $x \leq 10^3$.

Another $20\%$ of the data: $Q \leq 10^4$, $x \leq 5000$, there are no withdrawal messages, and the input $x$ is non-decreasing in order.

$60\%$ of the data (including the above $20\%$, same below): $Q \leq 2 \times 10^5$, $x \leq 2 \times 10^5$.

$90\%$ of the data: $Q \leq 2 \times 10^6$, $x \leq 2 \times 10^6$.

$100\%$ of the data: $1 \leq Q \leq 2 \times 10^6$, $1 \leq x \leq 2 \times 10^9$, the sum of all $y$ does not exceed $2 \times 10^9$, and it is guaranteed that there do not exist two warriors with exactly the same $t, x, y$.

Translated by ChatGPT 5