一个合法的括号序列是这样定义的：

1. 空串是合法的。
2. 如果字符串S是合法的，则（S）也是合法的。
3. 如果字符串A和B是合法的，则AB也是合法的。

现在给你一个由N个结点组成的树，结点由1—N标号，每个结点代表一个括号：‘（’或者‘）’。请编写程序对这棵树实现以下几个操作：

1. Replace a b c：修改，将结点a到结点b路径上所有结点的括号改为c。
2. Invert a b：取反，对于结点a到结点b路径上所有结点的括号，即‘（’改为‘）’，‘）’改为‘（’。
3. Query a b：询问，对于结点a到结点b路径上所有结点的括号形成的括号字符串（注意：这里的路径是有方向的，a到b与b到a不同，见样例），至少要改变多少位才能变成合法的括号序列。

第一行是一个整数N，表示结点的个数。

第二行是一个长度为N的字符串，第i位字符表示i号结点代表的括号。

接下来N-1行，每行两个整数，设为x，y。表示在树中有一条连接x结点和y结点的边。

接下来一行是一个整数M，表示需要实现的操作数。

接下来M行，表示需要依次执行的M个操作，格式如问题描述，操作名与数字之间均用空格隔开。

输出数据包含T行，T是M个操作中Query操作的次数。

Query操作的结果依次对应输出文件的一行，该行只有一个整数，表示执行Query操作的结果。若无解，则输出-1。

测试点1—6，N，M≤3000。

测试点4—13，树中任意结点的度数不超过2。

测试点13—15，数据保证没有Invert和Replace操作。

对于100%的数据，1≤N，M≤100000，保证读入的数据合法，即形成一棵树。