Simulate a Simplified Werewolf Game Night

This problem simulates one night in a simplified version of the Werewolf game with special roles: Werewolf, Civilian, Hunter, and Witch. At the start of the game, there are n (n ≥ 2) players numbered from 1 to n, all initially alive. Each player has one of the following roles:

• Werewolf: During the night, a werewolf may choose one other player (cannot target themselves) to kill. Note that a werewolf can even kill another werewolf.
• Civilian: A civilian does nothing at night.
• Hunter: A hunter does nothing if alive. However, if a hunter is killed (and not saved), they must execute a revenge kill by selecting one other player (cannot target themselves). If the hunter is later saved, his revenge kill still counts when he is subsequently killed.
• Witch: The witch has two potions – a healing potion and a poison. During the night, she can choose one of the following actions (but cannot use both in the same night):
  • Use the healing potion to save any one player who has already been killed during this night (this may be herself).
  • Use the poison to kill any one other player (cannot target herself).
  Note that a witch can act even if she has been killed, but if she is killed she is only allowed to use the healing potion on herself.

The night actions are provided in chronological order. Each action is given on a separate line with one of the following formats:

• 0 id1 id2: The werewolf with number id1 chooses to kill player id2.
• 1 id1 id2: The witch with number id1 chooses to use the poison on player id2.
• 2 id1 id2: The witch with number id1 chooses to use the healing potion on player id2.
• 3 id1 id2: The hunter with number id1 (who must be dead at the time of executing his revenge) chooses to kill player id2.

Important rules and validity checks:

• If any player number (either actor or target) is not in the range 1 to n, the input is invalid.
• For actions 0, 1, and 3, the target player must be alive at the moment the action is processed. For a healing potion (2), the target must already be dead.
• A player may not use a skill that does not belong to his/her role. The role of a player is implied by the type of action they take: 0 for werewolf, 1 or 2 for witch, and 3 for hunter.
• Each werewolf, witch, or hunter may only use their corresponding skill once in a night. (In particular, a witch cannot use both potions in the same night.)
• The actor in action 3 (hunter revenge) must be dead at the moment of the action.
• It is illegal for any action to target the actor themselves.
• If the actions are given in an order that violates the temporal logic (for example, using a healing potion on a player who is still alive), the entire night is considered to have an invalid input.

If any illegal condition is encountered, all actions for that night are discarded and the output should be Wrong.

After processing all valid actions sequentially, if no errors occurred, the final state is determined. If no player dies, output Safe. Otherwise, output the number of players who died followed by their player numbers in strictly increasing order (each separated by a space). For example, if players 1, 3, 5 died, output:

3 1 3 5

inputFormat

The input begins with two integers n and k (k ≥ 0) on the first line, where n is the total number of players and k is the number of actions performed during the night. The following k lines each describe one action in the formats described above.

For example:

4 3
0 1 2
3 2 3
1 4 1

outputFormat

If any error is detected in the sequence of actions, output Wrong (without quotes). Otherwise, if no player is dead at the end, output Safe. If there are dead players, output a line beginning with the number of dead players followed by their player numbers in strictly increasing order, separated by a single space.

For the sample input above, the correct output is:

3 1 2 3

sample

4 3
0 1 2
3 2 3
1 4 1

3 1 2 3