URI Online Judge | 1941

Palindrome

By Vinícius Fernandes dos Santos, Centro Federal de Educação Tecnológica de Minas Gerais BR Brazil

Timelimit: 1

A palindrome is a string such that its reversal is equal to the original string. In other words, it is a string that, when read backwards, is equal to the original string. For example BANANAB is a palindrome, while BANANAS not. In this problem we are interested in an issue a little more interesting.

Given a string S, we want to find a subsequence that is a palindrome. A subsequence is a string that can be obtained from the removal of zero or more characters of the original string. For example ANNA is a subsequence of BANANAS.

It will also be given a set of S positions is called special positions. Its task is to find the size of the substring that is a palindrome and contains the largest number of possible special positions. If more than a subsequence maximizing the number of special positions, you must print the size of the largest.

Input

The input consists of two lines. The first line contains a string of capital letters S with at least 1 and a maximum of 2000 characters. The second line contains an integer N (0 ≤ N|S|), indicating the number of special positions we are interested in include the palindrome, followed by N distinct numbers from 1 to |S|, even containing the positions special S.

Output

Your program must print a single integer representing the size of the largest palindrome possible, as defined above.

Input Samples Output Samples

BANANAS

0

5

BANANAS

1 7

1

ACDAAACX

3 2 3 8

3

MARATONA

4 3 1 5 2

3