Christmas is slowly approaching, and Bajtazar has decided to buy a new decoration to adorn his home. This year, he wants to go for minimalism and purchase a chain where the lamps are one of two colors: green or red. He went to a nearby lighting store and asked the shopkeeper to show him two-colored chains.

Unfortunately, years spent working in various Bajtocki positions have made Bajtazar have his own opinion on every (even the most trivial) topic, and he does not hesitate to express it (even when no one is listening). In terms of fashion and aesthetics, he has set views, which is particularly burdensome for all the shopkeepers who have happened to serve Bajtazar and listen to his complaining about how the presented goods do not quite please him.

And so it happened this time: Bajtazar stared at the chain presented to him for a long time, after which he stated that "in principle, it is quite all right, but the general aesthetics are ruined by the fact that there is no four-lamp fragment in the chain where the lamps would have the colors red-green-green-red." Since the shopkeeper did not have another chain, he decided to change the color of one of the lamps so that the aforementioned fragment would appear in the chain.

Bajtazar nodded with satisfaction, but after a moment he said that now he is still missing a fragment with the colors green-red-green-green-red. The shopkeeper replaced another lamp, to which Bajtazar stated that it is all beautiful, but another important fragment, due to the color scheme, is still missing.

Although Bajtazar is very patient in explaining why the chain is still not perfect, he fears that the shopkeeper's actions in changing the colors of the lamps are quite chaotic and will not necessarily lead them to the goal quickly. As a rationalization, he asked you to write a program that will help him quickly find the missing fragments that ruin his sense of aesthetics. To start with, write a program for him that will find the length of the shortest fragment that does not appear in a given chain.

Input

The first line of input contains two integers $n$ and $m$ ($1 \le n \le 100\,000$, $0 \le m \le 10\,000$) separated by a single space, representing the number of lamps in the chain and the number of color changes made by the shopkeeper. The second line contains a word consisting of $n$ characters $0$ and $1$ representing the colors of the consecutive lamps in the chain.

The next $m$ lines contain descriptions of color changes: the $i$-th of these lines contains a single integer $a_i$ ($1 \le a_i \le n$) indicating that the shopkeeper changed the color of the $a_i$-th lamp of the chain.

Output

You should output exactly $m + 1$ lines: the $i$-th of them should contain a single integer representing the length of the shortest word consisting of characters $0$ and $1$ that does not appear as a substring in the word encoding the lamp colors of the chain after $i - 1$ shopkeeper changes.

Examples

Input 1

6 2
001010
6
2

Output 1

2
3
2

Note

Explanation of the example: In the word 001010, the shortest missing substring is 11 of length 2. After changing the sixth character, we get 001011, in which all substrings of length 1 and 2 appear, but, for example, the substring 110 of length 3 does not appear. After changing the second character, we get 011011, in which the substring 00 does not appear.

Subtasks