PLCS

Time limit1sMemory limit16 MB

Summary

Find the longest common subsequence of A and B that contains X, excludes Y, and has prime length, or report -1.

Level: Medium7 of 10
Topics: Dynamic programming, String, Number theory
Solved: No attempts yet

Problem

The PLCS (Prime Longest Common Subsequence) problem gives two sequences and asks for the longest common subsequence of both whose length is prime.

Given strings $A$ and $B$ , a character $X$ that must be included in the PLCS, and a character $Y$ that must not be included in the PLCS, print the length of the longest common subsequence of $A$ and $B$ that contains $X$ , does not contain $Y$ , and has prime length. If no such subsequence exists, print -1.

The strings $A$ and $B$ and the characters $X$ and $Y$ consist of lowercase English letters. Each of $A$ and $B$ contains exactly one $X$ .

Input

The first line contains the string $A$ .

The second line contains the string $B$ . $(1 \le |A|, |B| \le 50,000)$

The third line contains the character $X$ .

The fourth line contains the character $Y$ . $(X \neq Y)$

Output

On the first line, print the length of the longest common subsequence of $A$ and $B$ that contains $X$ , does not contain $Y$ , and has prime length. If no such subsequence exists, print -1.

Examples3

Example 1
Input
```
aabbcbad
ababacda
c
b
```
Expected output
```
3
```
Example 2
Input
```
aabaaa
cccbcc
b
c
```
Expected output
```
-1
```
Example 3
Input
```
aabaaa
bca
b
x
```
Expected output
```
2
```