Training Site
Sideways banner 8b44c02b768aa359c4d0a2bce3b247c6d7ab888f8b26852e9bfc3659c8c25612

Hopscotch

Input: Standard Input (stdin)
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.

Input

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.

Output

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).

Subtasks

  • 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

    plausible
    
  • Sample Input 2

    10
    E
    N
    N
    E
    E
    N
    S
    S
    E
    N
    

    Sample Output 2

    impossible