This page is still under construction.

Parts of this page are still being built. What you see may change.

Wolf

Time limit2sMemory limit512 MB

Summary
Given your n-card pile and the opponent's remaining 51... wait 52-n cards, decide whether reordering both piles can make you win the next turn.
Level

Hard8 of 10

Topics
Greedy, Sorting, Implementation, Brute force
Solved
No attempts yet

Problem

Wolf is a two player card game that grew out of War and Svälta räv. The two piles together form one standard deck. A deck has 52 cards, and each card is a distinct pairing of one of 4 suits with one of 13 ranks. The suits are clubs C, diamonds D, hearts H and spades S, and the ranks run from 1 to 13. An ace is written as 1, a jack as 11, a queen as 12 and a king as 13, and a smaller number means a lower rank.

A turn runs like this. Both players take the top card of their own pile at the same time and show it. If the two cards have different suits, each player takes another card and shows it, and this repeats until the two shown cards have the same suit. When the suits match, the player whose card has the higher rank takes every card shown so far and the turn ends. The turn also ends when a player has to take a card and their pile is empty. That player loses the game. If both piles are empty at the same moment, the game is a draw.

Your opponent is away from the table, so you may reorder both piles however you like. You cannot move a card from one pile to the other, because your opponent knows which cards their pile holds. Decide whether some ordering of the two piles wins the next turn for you. You win the turn by taking the shown cards after a matching suit, or by having a card left when the opponent's pile runs out.

Input

The first line contains the number of cards nn in your pile (0≤n≤520 \le n \le 52).

Each of the next nn lines contains one card: a rank from 1 to 13 and one of the letters C, D, H, S, separated by a space. The nn cards are distinct, and the opponent holds the remaining 52−n52 - n cards of the deck.

Output

Print possible on the first line if some reordering of the two piles wins the next turn for you, and impossible if none does. Print either word in lowercase.

Examples3

  1. Example 1

    Input
    28
    1 C
    2 C
    3 C
    4 C
    5 C
    6 C
    7 C
    1 D
    2 D
    3 D
    4 D
    5 D
    6 D
    7 D
    1 H
    2 H
    3 H
    4 H
    5 H
    6 H
    7 H
    1 S
    2 S
    3 S
    4 S
    5 S
    6 S
    7 S
    
    Expected output
    possible
    
  2. Example 2

    Input
    0
    
    Expected output
    impossible
    
  3. Example 3

    Input
    1
    13 S
    
    Expected output
    possible