← 返回题目列表

AtCoder · nadafes2022_day2_m

M. 交换括号

中文机器翻译题面 查看原题

配点 : 800 点

問題文

满足以下任一条件的字符串。正确的括号顺序。

  • 空文字列
  • 一些正确的括号序列 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 是一个整数

入力

输入是按以下格式从标准输入给出的。

S
L

出力

|S|-L+1 行。

i\,(1 \leq i \leq |S|-L+1) 行中,k=i 时打印答案。但是,如果这是不可能的 输出 -1 。


入力例 1

))((
2

出力例 1

2
1
0

k=1 时,S 在 ))(( → )()( → ())( 必须满足() 是一个漂亮的字符串。运算次数为 2 次。


入力例 2

))())
4

出力例 2

-1
-1

入力例 3

))()(()
3

出力例 3

4
2
0
1
0