問題文

以下のいずれかの条件を満たす文字列を正しい括弧列と定義します。

• 空文字列
• ある正しい括弧列 A が存在して、(, A, ) をこの順に連結した文字列
• ある空でない正しい括弧列 A, B が存在して、A, B をこの順に連結した文字列

そして、正しい括弧列から末尾の文字を取り除くことを何回か繰り返すことで得られる文字列を美しい括弧列と定義します。

例えば、(((() や ()()、空文字列などは美しい括弧列であり、))()、()) などは美しい括弧列ではありません。

文字列 S と整数 L が与えられます。k=1,2,\ldots ,|S|-L+1 について独立に、以下の問いに答えてください。

S の隣り合う 2 文字を入れ替えることを繰り返すことで、S の k 文字目から k+L-1 文字目までを取り出した部分文字列が美しい括弧列となるようにしたい。操作回数の最小値を求めよ。

制約

• 1 \leq |S| \leq 5 \times 10^5
• S は ( と ) のみからなる文字列
• 1 \leq L \leq |S|
• L は整数

入力例 1

))((
2

出力例 1

2
1
0

k=1 のとき、S を ))(( → )()( → ())( とすると、() は美しい文字列です。操作回数は 2 回です。

入力例 2

))())
4

出力例 2

-1
-1

入力例 3

))()(()
3

出力例 3

4
2
0
1
0