There are knights labeled to standing in a row. The -th knight has power .
The knights are competing in a jousting tournament. To do so, each knight will hold a sword pointing either to the left or to the right. The -th knight will point their sword to the left if and to the right if where is a binary string of length .
A joust is defined as the following process:
Initially all knights are alive.
Let be the list of knights still alive arranged in increasing order of label and be the size of .
For each from to . If the -th knight has an adjacent knight with bigger power pointing their sword at the -th knight's direction, then mark the knight as Formally the -th knight will be marked as dead if one of the following condition is true.
and and
and and
Return to step 2 if there is at least one knight in marked as dead.
Now you are given queries, each query are of the form:
Given integer (), change to .
After each query, find the number of knights alive after a joust is performed.
Do note that knights do not stay dead after a joust.
输入格式
The first line contains two space-separated integers and () -- the size of and the number of queries.
The second line contains space-separated integers ().
The third line contains a binary string of length .
Then lines follow. Each of the lines contains a single integer () denoting a query to change to .
输出格式
Output integers in order on lines, where is the number of knights alive after performing a joust after the -th query.
样例
样例输入 1
5 3
2 1 3 4 3
11011
1
3
4
样例输出 1
2
4
2
样例输入 2
10 5
10 1 2 3 8 9 4 5 7 6
0111100110
10
5
6
5
1
样例输出 2
5
5
3
6
1
数据范围与提示
Note
In the first sample input, after the first query, becomes 01011.
Initially, the (labels of) the knights alive are . After one iteration, the knights remaining are . After the second iteration, the knights remaining are . After the third iteration, no new knight dies, so 2 knights remain after a joust.
After the second query, becomes 01111.
After one iteration, the knights remaining are . After the second iteration, no new knight dies, so 4 knights remain after a joust.
Scoring
Subtask 1 (6 points):
Subtask 2 (9 points): for
Subtask 3 (17 points): if and the answer for each query is guaranteed to be at most .
