시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 8 | 0 | 0 | 0.000% |
One big company is developing a computer game named "Combostone", that should blast the market. The rules of the game are quite complicated, so implementation of the server engine, which should adhere to the rules, was outsourced. You are asked to implement such server engine.
The players of the game are able to summon creatures to the arena, and then they can improve these creatures. Every creature has two parameters --- an integer value of its attack $a$ and an integer value of its remaining health points $h$. Let us denote parameters of a creature as $(a, h)$. There are no creatures in the arena at the beginning of the game.
Players are able to use the following spells:
The server engine that you should implement must be able to process all the events, and for every summoned creature it must determine the number of the turn when this creature dies, or find out that it is still alive at the end of the game.
Also, the engine should correctly process the cases when the player tries to interact with the dead creatures: if the spell Blessed Champion, Divine Spirit or Attack! is applied to the dead creature, nothing should happen. If the spell Molten Reflection is applied to the dead creature, a new creature with the same parameters is summoned, but it is assumed to be killed at the turn of its creation.
The first line of input contains an integer $n$ --- the number of turns in the game ($1 \le n \le 250\,000$).
The next $n$ lines contain turn descriptions in the following format:
It is guaranteed that any creatures mentioned in the queries have already been summoned at the time of the query, but they can be already dead.
The first line of output must contain one integer $k$ --- the number of creatures summoned in the game.
The next line must contain $k$ integers $t_1, t_2, \ldots, t_k$. If the creature with id $i$ is alive at the end of the game, $t_i$ should be equal to $-1$, otherwise $t_i$ should be equal to the number of the turn, when this creature was killed.
16 1 2 1 3 1 1 5 1 2 3 1 1 3 3 3 3 4 1 5 1 3 3 3 5 1 3 5 4 3 5 4 3 4 1
5 13 5 14 -1 16
The table below shows how the parameters of the creatures changed in the sample test.
turn | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|
0 | - | - | - | - | - |
1 | (1, 1) | - | - | - | - |
2 | (2, 1) | - | - | - | - |
3 | (2, 2) | - | - | - | - |
4 | (2, 2) | (1, 1) | - | - | - |
5 | (2, 1) | dead | - | - | - |
6 | (2, 2) | dead | - | - | - |
7 | (2, 2) | dead | (1, 1) | - | - |
8 | (2, 2) | dead | (1, 2) | - | - |
9 | (2, 2) | dead | (1, 4) | - | - |
10 | (2, 2) | dead | (1, 4) | (2, 2) | - |
11 | (2, 1) | dead | (1, 2) | (2, 2) | - |
12 | (2, 1) | dead | (1, 4) | (2, 2) | - |
13 | dead | dead | (1, 2) | (2, 2) | - |
14 | dead | dead | dead | (2, 1) | - |
15 | dead | dead | dead | (2, 1) | - |
16 | dead | dead | dead | (2, 1) | dead |