Output: Standard Output (stdout)
Memory limit: 32 megabytes
Time limit: 5.0 seconds
While it commonly refers to the popular children's jumping game, Hopscotch is also the name of the most adorable rabbit (in the world). Hopscotch is a simple creature, and spends his entire existence in one of three states: sleeping, exploring, and nibbling.
- When Hopscotch is sleeping, he can either keep sleeping or wake up and begin exploring.
- When Hopscotch is exploring, he will inevitably find something he considers to be edible, and begin nibbling.
- When Hopscotch is nibbling, he will either return to exploring or spontaneously begin sleeping.
We have been trying to document Hopscotch's day. We've recorded a log of N states that we've observed Hopscotch in. Unfortunately, Hopscotch is very fast and we're worried that we might have missed recording a state. Given our log of the N recorded states, please tell us whether they describe a plausible sequence (the state transitions follow the rules described above) or whether the sequence described is impossible. The sequence may begin in any state.
The first line will contain a single non-negative integer N, describing the number of states that have been recorded in the log.
The following N lines each contain a single character representing the recorded state. 'S' represents sleeping, 'E' represents exploring, and 'N' represents nibbling.
If the sequence described is plausible, output a single line containing the text
plausible (without quotes).
If the sequence described is impossible, output a single line containing the text
impossible (without quotes).
- Subtask 1 (20%): N \leq 1,000, the sequence only contains entries of sleeping.
- Subtask 2 (30%): N \leq 1,000, the sequence contains no entries of sleeping.
- Subtask 3 (50%): N \leq 1,000,000, no further restrictions apply.
Sample Input 1
10 S S S E N S S S E N
Sample Output 1
Sample Input 2
10 E N N E E N S S E N
Sample Output 2