Tidepool Lanterns
Along a straight tidepool path there are shells, numbered from to . Shell has an opening height and a color .
For a tide level , shell is open if . The open shells form several open groups. An open group is a maximal contiguous segment of positions such that every shell in that segment is open, and:
- either or shell is closed;
- either or shell is closed.
An open group is mixed if at least one shell in it has color A and at least one shell in it has color B.
You are given tide levels. For each level, report the number of mixed open groups.
Input
The first line contains two integers and (), the number of shells and the number of tide levels.
Output
Print lines. The -th line must contain one integer: the number of mixed open groups at tide level .
Samples
Sample 1
Input
7 4 3 1 4 1 5 9 2 ABAABBA 0 1 3 10
Output
0 0 1 1
At level , no shell is open. At level , positions and are open, but each is alone. At level , positions and form one mixed group, while positions and are single-color groups. At level , all shells are in one mixed group.