Jasiu likes to play hopscotch with his friends. They decided to improve the rules of the game a little. Initially, $N$ square fields are drawn on the sidewalk, arranged one after another. The fields are numbered from 1 upwards, starting from the left. Some fields contain single pebbles. Each player chooses a starting field and an integer $K > 1$. Then, starting from the chosen field, they jump by $K$ fields until they jump beyond field number $N$. The player's score is equal to the number of fields with pebbles that they landed on during the jumps. It is now Jasiu's turn, and he really wants to get as many points as possible. Knowing the positions of the pebbles, calculate the maximum score he can achieve.

Input

The first line of standard input contains an integer $N$ ($1 \le N \le 10^6$), representing the number of fields. The second line contains a string of length $N$ consisting of the characters . and/or #. If the $i$-th character in the line is #, there is a pebble on field number $i$; otherwise, the field is empty.

Output

The first and only line of standard output should contain a single integer representing the maximum score Jasiu can achieve.

Examples

Input 1

8
#..#...#

Output 1

2

Input 2

6
####..

Output 2

2

Input 3

9
#.#..#..#

Output 3

3

The middle school students from 2014 are now professionals competing in the Algorithmic Engagements, and one can expect that they are interested in significantly more difficult problems. In our version of the problem, the arrangement of pebbles is not fixed once and for all – we start with an empty sidewalk with $n$ fields, and the children add and remove pebbles while playing. After each such change on the sidewalk, Jasiu would like to know what the maximum game score he can achieve is.

Note: You can also find a discussion of this problem on the internet, which we link here for your convenience: https://www.youtube.com/live/jxYu1MGGjBc. However, we do not guarantee that the information contained therein is in any way useful for solving our version of the problem.

Input

The first line of input contains two integers $n$ and $q$ ($1 \le n \le 10\,000\,000$, $1 \le q \le 1\,000\,000$), representing the number of fields on the sidewalk and the number of events to consider.

The next $q$ lines contain descriptions of the events; the $i$-th of them contains an integer $a_i$ ($1 \le a_i \le n$), meaning that the $i$-th event is adding a pebble to field $a_i$ (if there was no pebble there) or removing a pebble from field $a_i$ (if there was one).

Output

You should output exactly $q$ lines; the $i$-th line should contain a single integer representing the maximum score Jasiu can achieve immediately after the $i$-th event.

Examples

Input 1

9 10
1
4
8
2
3
8
6
9
2
4

Output 1

1
2
2
3
3
2
3
3
3
3

Note

Explanation of the example: After the first three events, we have the first (left) situation from the original problem (up to an additional ninth field, which remains empty and thus does not affect the score). After the next three events, we get the second (middle) situation, and finally – the third (right) one.