A competition is about to begin.

Each warrior has two attributes: temperature and energy. There are two factions of warriors: Ice-type warriors, whose skills cause cooling and freezing damage to the surroundings, requiring the arena temperature to be no lower than their own temperature to participate; and Fire-type warriors, whose skills cause heating and burning damage to the surroundings, requiring the arena temperature to be no higher than their own temperature to participate.

When the arena temperature is fixed, the eligible warriors from both sides are arranged into queues. Ice-type warriors are sorted by their own temperature in ascending order, and Fire-type warriors are sorted by their own temperature in descending order. If temperatures are equal, the warrior with more energy is placed in front. First, the first warrior from each side engages in combat. Both warriors consume the same amount of energy; the warrior with less energy is exhausted and leaves the competition, while the warrior with remaining energy continues to fight the next warrior from the opposing side (if both are exhausted, the next warriors from both sides engage). This process repeats until one side's queue is empty, at which point the competition ends.

You need to find the optimal arena temperature: the highest temperature that maximizes the total energy consumed by both the Ice and Fire factions.

The competition is currently in the registration phase, and no warriors have registered yet. You will continuously receive registration information and withdrawal information. Registration information includes the faction and the two attributes of the warrior, while withdrawal information includes the index of the registration information to be withdrawn. Whenever the registration status changes (i.e., upon receiving an update), you must immediately report the optimal arena temperature under the current situation and the total energy consumed by both sides at that temperature. If no competition can be held under the current situation (i.e., one side has no eligible warriors), output Peace.

Input

The first line contains a number $Q$, representing the number of updates.

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

$1\ t\ x\ y$ represents a registration entry, where $t = 0$ indicates an Ice-type warrior and $t = 1$ indicates a Fire-type warrior. $x$ represents the warrior's temperature, and $y$ represents the warrior's energy.

$2\ k$ represents a withdrawal entry, withdrawing the $k$-th registration entry. The withdrawn entry is guaranteed to be a registration entry, and an already withdrawn entry will not be withdrawn again.

Output

Output $Q$ lines, each containing two space-separated positive integers representing the optimal temperature and the total energy consumed by both Ice and Fire factions at that temperature under the current situation.

Examples

Input 1

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

Output 1

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

Note 1

For convenience, let us define that if the $k$-th entry is a registration, it corresponds to warrior $k$. The example contains warriors $1, 2, 3, 4, 6, 7, 8$. Since the 5th entry is a withdrawal, there is no warrior $5$.

Explanation of each output:

1. Only Fire-type warriors: warrior $1$, no competition possible, output Peace.
2. Temperatures $100\sim 103$ all result in the maximum energy consumption of $200$: warrior $1$ fights warrior $2$ consuming $200$ energy. The optimal temperature is $103$.
3. Temperatures $100\sim 103$ all result in the maximum energy consumption of $200$: warrior $1$ fights warrior $2$ consuming $200$ energy. The optimal temperature is $103$.
4. Temperature $103$ results in the maximum energy consumption of $300$: first, warrior $1$ fights warrior $2$ consuming $200$ energy; then, warrior $1$ fights warrior $4$ consuming $100$ energy. The optimal temperature is $103$.
5. From now on, warrior $1$ no longer exists. Temperatures $100\sim 102$ result in the maximum energy consumption of $200$: warrior $2$ fights warrior $3$ consuming $200$ energy. The optimal temperature is $102$.
6. Temperatures $100\sim 102$ result in the maximum energy consumption of $200$: warrior $2$ fights warrior $3$ consuming $200$ energy. The optimal temperature is $102$.
7. Temperatures $100\sim 104$ result in the maximum energy consumption of $700$: first, warrior $2$ fights warrior $7$ consuming $200$ energy; then, warrior $4$ fights warrior $7$ consuming $500$ energy. The optimal temperature is $104$.
8. Temperatures $100\sim 102$ result in the maximum energy consumption of $1000$: first, warrior $7$ fights warrior $8$ consuming $700$ energy; then, warrior $1$ fights warrior $8$ consuming $100$ energy; then, warrior $1$ fights warrior $2$ consuming $200$ energy. The optimal temperature is $102$.

Subtasks

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

Another $20\%$ of the data: $Q \le 10^4, x\le 5000$, no withdrawal entries, and input $x$ is non-decreasing.

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

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

$100\%$ of the data: $Q\le 2\times 10^6, x\le 2\times 10^9$, the sum of all $y$ does not exceed $2\times 10^9$, and it is guaranteed that no two warriors have identical $t, x, y$.