J. XOR String
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a string $$$S$$$ , consisting of $$$n$$$ lowercase English letters $$$S_0,S_1,S_2,...,S_{n-1}$$$.

Each character in the string $$$S_i$$$ has a value $$$V_i$$$.

Define $$$U=\{x|x\in \mathbb Z,0\leq x\leq n-1\}$$$.

A string $$$t(|t|\leq n)$$$ is said to be qualified if there exists a non-empty set $$$P$$$ which meets the following requirements:

  • $$$P\subseteq U$$$
  • $$$\forall p\in P,\forall i\in[0,|t|-1],t_i=S_{(p+i)\mod n}$$$
  • $$$\forall p\in \complement_UP,\exists i\in[0,|t|-1],t_i\neq S_{(p+i)\mod n}$$$
  • $$$\bigoplus_{p \in P} V_p =0$$$, which means the XOR sum of $$$V_p$$$ equals to $$$0$$$, for all elements $$$p$$$ in $$$P$$$.

Please calculate the length of the longest qualified string $$$t$$$.

Input

The first line contains a string $$$S$$$ of length $$$n~(1\leq n\leq 10^5)$$$, consisting of lowercase English letters. The second line contains $$$n$$$ integers, $$$V_0,V_1,V_2,...,V_{n-1}~(0\leq V_i \lt 2^{10})$$$.

Output

Output an integer, the length of the longest qualified string $$$t$$$. If there is no qualified string, output $$$0$$$.

Example
Input
aaabab
1 1 2 3 2 4
Output
3