Background

Special for beginners, ^_^

Description

一个合法的括号序列是这样定义的： 空串是合法的。 2.如果字符串S是合法的，则(S)也是合法的。 3.如果字符串A和B是合法的，则AB也是合法的。 现在给你一个长度为N的由‘(和‘)'组成的字符串，位置标号从1到N。对这个字符串有下列四种操作： Replace a bc：将[a，b]之间的所有括号改成c。例如：假设原来的字符串为：))0)0)(，那么执行操作Replace 2 7(后原来的字符串变为：)(((((0(. 2.Swap a b： 将[a，b]之间的字符串翻转。例如：假设原来的字符串为：))()0)(，那么执行操作Swap 3 5后原来的字符串变为：))))(0)(。 3.Invert a b： 将[a，b]之间的‘(’变成‘)’，‘)’变成‘(’。例如：假设原来的字符串为：))()0)(，那么执行操作 Invert 4 8后原来的字符串变为：))((0(((.4.Query a b： 询问[a，b]之间的字符串至少要改变多少位才能变成合法的括号序列。改变某位是指将该位的‘(’变成‘)’或‘)’变成‘(’。注意执行操作Query并不改变当前的括号序列。例如：假设原来的字符串为：))0)0)(，那么执行操作 Query 3(的结果为2，因为要将位置5的‘)’变成‘(’并将位置6的‘(’变成‘)’。

Format

Input

从文件input.txt中读入数据，输入文件的第一行是用空格隔开的两个正整数N和M，分别表示字符串的长度和将执行的操作个数。第二行是长度为N的初始字符串S。接下来的M行是将依次执行的M个操作，其中操作名与操作数之间以及相邻操作数之间均用空格隔开。30%的数据满足N，M≤3000。100%的数据满足N，M≤100000。

Output

输出文件 output. txt包含T行，其中T是输入的将执行的M个操作中 Query 操作出现的次数。Query操作的每次出现依次对应输出文件中的一行，该行只有一个非负整数，表示执行对应 Query 操作的结果，即：所指字符串至少要改变多少位才能变成合法的括号序列。输入数据保证问题有解。

Samples

4 5
Replace  )
uerr12
Swap 2 3
Invert 3 4
luerrI4

1
2

Limitation

样例解释：输入中有2个Query操作，所以输出有2行。执行第一个Query操作时的括号序列为))((，因改变第1位可使[1，2]之间的字符串变成合法的括号序列，故输出的第一行为1。执行第二个Query操作时的括号序列为)(0，因要改变第1位和第2位才能使[1，4]之间的字符串变成合法的括号序列，故输出的第二行为2。