Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

C. Tree Generator™

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputOwl Pacino has always been into trees — unweighted rooted trees in particular. He loves determining the diameter of every tree he sees — that is, the maximum length of any simple path in the tree.

Owl Pacino's owl friends decided to present him the Tree Generator™ — a powerful machine creating rooted trees from their descriptions. An $$$n$$$-vertex rooted tree can be described by a bracket sequence of length $$$2(n - 1)$$$ in the following way: find any walk starting and finishing in the root that traverses each edge exactly twice — once down the tree, and later up the tree. Then follow the path and write down "(" (an opening parenthesis) if an edge is followed down the tree, and ")" (a closing parenthesis) otherwise.

The following figure shows sample rooted trees and their descriptions:

Owl wrote down the description of an $$$n$$$-vertex rooted tree. Then, he rewrote the description $$$q$$$ times. However, each time he wrote a new description, he picked two different characters in the description he wrote the last time, swapped them and wrote down the resulting string. He always made sure that each written string was the description of a rooted tree.

Pacino then used Tree Generator™ for each description he wrote down. What is the diameter of each constructed tree?

Input

The first line of the input contains two integers $$$n, q$$$ ($$$3 \le n \le 100\,000$$$, $$$1 \le q \le 100\,000$$$) — the number of vertices in the tree and the number of changes to the tree description. The following line contains a description of the initial tree — a string of length $$$2(n-1)$$$ consisting of opening and closing parentheses.

Each of the following $$$q$$$ lines describes a single change to the description and contains two space-separated integers $$$a_i, b_i$$$ ($$$2 \leq a_i, b_i \leq 2n-3$$$) which identify the indices of two brackets to be swapped. You can assume that the description will change after each query, and that after each change a tree can be constructed from the description.

Output

Output $$$q + 1$$$ integers — the diameter of each constructed tree, in the order their descriptions have been written down.

Examples

Input

5 5 (((()))) 4 5 3 4 5 6 3 6 2 5

Output

4 3 3 2 4 4

Input

6 4 (((())())) 6 7 5 4 6 4 7 4

Output

4 4 4 5 3

Note

The following figure shows each constructed tree and its description in the first example test:

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Nov/15/2019 16:55:39 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|