我們稱一個字串是「得字串」若它僅由小寫英文字母 d 和 e 組成。

一個得字串「得」的程度為子序列為 de 的個數。

例如：\(dedede\) 得的程度為 \(6\)，\(eedde\) 則為 \(2\)。

對於一個字串 \(s\)，我們稱 \(s\) 的一個前綴 \(s_1s_2...s_k\) 為「最長單字元前綴」，若它滿足 \(s_1=s_2=\cdots=s_k\) 且 \(s_{k+1}\neq s_k\)。

特別的，若 \(s\) 僅由一種字元組成，則 \(s\) 自己本身即為自己的最長單字元前綴。

得字串有一個特性，從它被創造的那刻起，每秒就會「得化」一次。

當一個得字串得化時，它的最長單字元前綴會「置換」，即若最長單字元前綴由 d 組成，則這些字元會全變成 e，反之則全變 d。

例如 \(ddedeeddee\) 經過 \(3\) 秒的變化：\(ddedeeddee\rightarrow eeedeeddee\rightarrow ddddeeddee\rightarrow eeeeeeddee\)

給定一個長度為 \(n\) 的得字串 \(s\)，請求出它從被創造那刻開始，分別過 \(0\) 秒、\(1\) 秒、\(\cdots\)、\(q\) 秒後得的程度是多少。

Input

第一行輸入兩個正整數 \(n,q\)。

\(1\le n\le 2\cdot10^5,0\le q\le 2\cdot10^5\)

第二行輸入一個長度為 \(n\) 的得字串 \(s\)。

\(|s|=n\)

Output

輸出 \(q+1\) 行，第 \(i\) 行輸出一個整數，代表 \(s\) 從被創造那刻開始過 \(i-1\) 秒後得的程度。

Constraints

第 \(1\) 組測資, \(n\le 5000\) 且 \(q=0\)。\((9\text{%})\)

第 \(2\) 組測資, \(q=0\)。\((19\text{%})\)

第 \(3\) 組測資, \(n\le 5000\)。\((31\text{%})\)

第 \(4\) 組測資, 沒有其他限制。\((41\text{%})\)

Sample Input 1

6 5
dedede

Sample Output 1

6
3
7
1
5
0

Sample Input 2

10 3
ddedeeddee

Sample Output 2

18
8
20
4

Notes

你做🉐出來嗎？