Problem: Chimera II

Want to try solving this problem? You can submit your code online if you log in or register.

Chimera II

Input File: chimin.txt
Output File: chimout.txt
Time Limit: 1 second
Memory Limit: 1 GB

You've just graduated from high school and are ready to start your very own mad science lab. To prove your genius to the world you plan to breed a lion-goat hybrid.

All animals in existence are fundamentally described by their DNA sequence, which is a string of N upper case letters. You've managed to obtain the DNA sequences of a lion and of a goat. To bring your new creature to life, you must produce a specific DNA sequence, called the hybrid sequence.

New DNA sequences can be produced by splicing. This involves picking two DNA sequences from your lab (call these sequences S and T) and an integer x (0 < x < N), called the splicing point. Your state-of-the-art DNA photocopier will then produce a new DNA sequence which consists of the first x characters of S, followed by the last N-x characters of T. This new sequence is then stored in your lab and can be used for future splicing.

For example, say you pick the DNA sequences GOLEM and MOOSE, and take x=2. The splicing will take GO from the start of GOLEM and OSE from the end of MOOSE, and combine these to get the new DNA sequence GOOSE.

$\includegraphics[width=3cm]{Splicing}$

There's been a wave of blackouts recently, so to conserve power you want to minimise use of the DNA photocopier. Determine if it is possible to create the hybrid sequence, and if so the minimum number of splices required.

Input

The first line of input contains the integer N, the length of DNA sequences.
The next two lines each contain a string of length N, the two DNA sequences you already have in your laboratory.
The fourth line contains a string of length N, the required hybrid sequence.

Each string in the input consists only of upper case letters.

It is guaranteed that all three strings in the input will be different.

Output

If it is impossible to produce the hybrid sequence, your program should output PLAN FOILED. Otherwise, your problem should output two lines. On the first line you should output SUCCESS, and on the second line you should output a single integer: the minimum number of times you must splice to produce the required sequence.

Sample Input 1

5
MOOSE
GOLEM
GOOSE

Sample Output 1

SUCCESS
1

Sample Input 2

3
CAT
DOG
COW

Sample Output 2

PLAN FOILED

Sample Input 3

7
ABCDEFG
HIJKLMN
HBJDEMN

Sample Output 3

SUCCESS
4

Explanation

The first sample case corresponds to the splicing example given earlier. As explained above, you can combine the start of GOLEM and the end of MOOSE to make GOOSE in a single splice.

In the second sample case, there is no sequence of splicings that can produce the sequence COW starting with the sequences CAT and DOG.

For the third sample case, one example of an optimal sequence of splices is as follows:

Splice ABCDEFG and HIJKLMN with x=5 to form ABCDEMN.
Splice HIJKLMN and ABCDEFG with x=1 to form HBCDEFG.
Splice HBCDEFG and HIJKLMN with x=2 to form HBJKLMN.
Splice HBJKLMN and ABCDEMN with x=3 to form HBJDEMN.

Subtasks & Constraints

For all cases, 2 ≤ N ≤ 300,000.

For Subtask 1 (5 marks), N = 2.
For Subtask 2 (17 marks), you only need to determine whether it is possible to produce the hybrid sequence. Only the first line you output will be judged. In the case of SUCCESS a second line of output is not required, but if present it will not influence your score in this subtask.
For Subtask 3 (18 marks), all the letters in the first input string will be A, and all the letters in the second input string will be B.
For Subtask 4 (21 marks), if it is possible to produce the hybrid sequence then it will be possible to do so with at most 2 splices.
For Subtask 5 (24 marks), N ≤ 1000.
For Subtask 6 (15 marks), no further constraints apply.