Printing Design Phrases

You are given a set of available letters and a list of design phrases. Each design phrase consists of letters that must be printed. For each phrase, you must check if there are enough available letters to print it. When printing a phrase, the letters used are deducted from the available pool.

The task is to determine whether it is possible to print all design phrases in the given order using the available letters.

Formally, let \(S\) be the string of available letters, and let \(P_1, P_2, \ldots, P_n\) be the design phrases. For each phrase \(P_i\), check if for every character \(c\) in \(P_i\), the number of occurrences of \(c\) in \(S\) is at least as many as in \(P_i\). If so, subtract these counts and continue; otherwise, output Impossible. If all phrases can be printed, output Possible.

inputFormat

The input is given via standard input in the following format:

<available_letters>
<n>
<phrase_1>
<phrase_2>
... 
<phrase_n>

Where:

• <available_letters> is a string of lowercase letters.
• <n> is an integer representing the number of design phrases.
• <phrase_i> is the i-th design phrase (a string of letters).

outputFormat

Output a single line to standard output containing either Possible if all design phrases can be printed, or Impossible otherwise.

aabbcc
2
abc
bca

Possible