Sequence Formation Using Patterns

You are given several patterns consisting of sequences of integers and a target sequence. Your task is to determine whether the target sequence can be completely formed by concatenating one or more of the given patterns in order.

More formally, you are given an integer \( M \) representing the number of available patterns, followed by \( M \) patterns. Each pattern is a sequence of integers. Finally, a target sequence is provided. You need to check if the target sequence can be segmented into contiguous sub-sequences such that each sub-sequence exactly matches one of the provided patterns.

If the target sequence can be segmented entirely into patterns, output Possible; otherwise, output Impossible.

Note: Each pattern should match a contiguous block in the target sequence. Patterns can appear in any order and may be used at most once per occurrence in the segmentation process.

inputFormat

The input is given via standard input and has the following format:

M
pattern1
pattern2
... (M patterns in total)
target_sequence

Here, M is an integer denoting the number of patterns. Each pattern and the target sequence are provided as space-separated integers on their own lines.

outputFormat

Output a single line to standard output containing either Possible or Impossible (without quotes), depending on whether the target sequence can be fully segmented into the given patterns.

3
1 2 3
4 5 6
7 8
1 2 3 4 5 6 7 8

Possible