Training Site
Sideways banner

Shadow's Battle

Input: Standard Input (stdin)
Output: Standard Output (stdout)
Memory limit: 64 megabytes
Time limit: 1.0 seconds

After scouring the misty mountains high and low, your band of weary travellers has fallen straight into a trap! You find yourselves single file in a dark tunnel. Suddenly a magical light shines upon you, revealing the evil sorceress Shadow in your midst. You must overcome her to escape!

Shadow strikes first, and then your group has a chance to strike back. You take it in turns to attack until either Shadow dies or everyone in your group has been killed. Shadow's power is a powerful light beam that does damage to anyone it touches. However, if one of your band is 'sheltered' by another one of your band, they will not be hit.

Your task is to determine who is alive at the end of the battle.

All players start with 10 health points, and Shadow starts with 60 health points.


There are 5 people in your band, in the positions 1, 2, 3, 7 and 8. Shadow is in position 4.

P P P S _ _ P P
1 2 3 4 5 6 7 8

This is a graphical representation of your band of players (P), Shadow (S) and any empty spaces (_). The numbers along the bottom represent the position number.

The amount of damage that the group does as an attack is the sum of all individual attacks. So if the individual players' attacks are 13, 6, 4, 9, and 5, then the group attack is 37. Shadow's attack in this example is 10.

Shadow takes the first turn. Her cast reaches only the players in positions 3 and 7, as the rest of the group is shielded. Both of them are reduced to 0 health, and die.

P P _ S _ _ _ P
1 2 3 4 5 6 7 8

Now it is the group's turn. The remaining 3 players have 13 + 6 + 5 = 24 damage. Shadow's health is now at 36 points.

When Shadow casts again, she kills the players in positions 2 and 8.

P _ _ S _ _ _ _
1 2 3 4 5 6 7 8

The last remaining player then casts with a damage of 13. Shadow's health decreases to 23.

Shadow casts again, and kills the last remaining player. The battle is done.


The first line contains a single integer, N, representing the number of players (1 \le N \le 100).

The next N lines each contain two space-separated integers. The first, p_i is the position of player i (1 \le p_i \le 200). The second, a_i is the amount of damage that player i can cast (1 \le a_i \le 100). Players are input in ascending order of position.

Note that all positions are distinct, including Shadow and the players; no position will hold more than one person.

The last line contains two space-separated integers. The first, p_S is Shadow's position (1 \le p_S \le 200), and the second, a_S is Shadow's attack damage (1 \le a_S \le 100).


If Shadow wins, print Shadow wins!

If the players win, print We win! Players alive: followed by a space separated list of integers of the positions of the players that are still alive, in ascending order.

  • Sample Input 1

    1 13
    2 6
    3 9
    7 4
    8 5
    4 10

    Sample Output 1

    Shadow wins!
  • Sample Input 2

    1 6
    2 4
    3 5
    4 3
    6 2
    7 6
    5 4

    Sample Output 2

    We win! Players alive: 1 2 3 7