Problem I
Polkagris
The board of Chalmers Coding Club have departed from Gothenburg on tågluff to Hamburg, Zürich, Venice and beyond, but the first stop is Gränna! Gränna is famous for its polkagrisar, which are similar to candy canes but are available in many different colors and flavors. The colors of the sticks are typically twisted together, but in order for this problem to make sense you have to imagine they are sequences of single-colored segments.
On their way there, the board has spent a great deal of time deciding the flavors for their desired polkagris, which can be represented as a string of $T$ letters A-Z. But upon arrival to the polkagris shop, all their sticks are sold out except for a few belonging to one same batch, that, unfortunately, does not match the desired configuration.
A little distraught, but not that much since the trip will be very fun regardless, the board leaves to continue their journey without polkagrisar. That night, Gustav, who in recent times has become impressively culinarily minded, realizes that maybe they could have reheated the polkagris while folding one of its ends over and onto the main body, kneading it into a single stick again. Any difference in length or width of the respective segments being merged does not matter since the sugary mass is highly deformable, but only identical flavors are allowed to be merged to avoid a bland mess. For example, the polkagris CBABCDCB can be folded over the D into CBABBCCD, then again over the A, requiring just a little bit of stretching, into ABBBCCCD which satisfies anyone with a craving for ABCD.
Maybe this process, if performed iteratively, could have turned the store’s polkagris into the one that they actually wanted?
Input
The first line of the input contains the two integers $N$ and $T$ $(1 \leq T \leq N \leq 10^7)$, the lengths of the store’s available and the board’s desired polkagrisstång.
The second line contains the store’s available polkagrisstång.
The third line contains the board’s desired polkagrisstång.
No two adjacent characters will be identical.
Output
If the available polkagrisstång can be worked into the desired one, print “possible”. Otherwise, print “impossible”.
Scoring
Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.
|
Group |
Points |
Constraints |
|
$1$ |
$27$ |
$N \leq 100$ |
|
$2$ |
$31$ |
$N \leq 10^4$ |
|
$3$ |
$42$ |
No additional constraints. |
Explanation of sample 1
The string ABCBC can be folded at its midpoint to produce something that after kneading looks like AABBC, but the board does not mind unevenly long or thick segments and so considers this an acceptable ABC polkagris.
Explanation of sample 2
The polkagris ABC is of course the same as CBA, just turn it the other way!
Explanation of sample 3
The leftmost flavor of ABABABCA can be repeatedly folded over to reach ABCA. However, since there is no way to fold away the rightmost A, creating the polkagris ABC is unfortunately not possible.
| Sample Input 1 | Sample Output 1 |
|---|---|
5 3 ABCBA ABC |
possible |
| Sample Input 2 | Sample Output 2 |
|---|---|
3 3 ABC CBA |
possible |
| Sample Input 3 | Sample Output 3 |
|---|---|
8 3 ABABABCA ABC |
impossible |
| Sample Input 4 | Sample Output 4 |
|---|---|
8 4 ABABABCA ABCA |
possible |
| Sample Input 5 | Sample Output 5 |
|---|---|
12 3 BABACABACABA BAC |
possible |
| Sample Input 6 | Sample Output 6 |
|---|---|
12 3 BABACABACABA CAB |
possible |
