You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 3.0 seconds
Memory limit: 512.0 MB

# Problem
You are a warrior fighting against the machine god Thor.

Thor challenge you to solve the following problem:

There are $$$n$$$ conveyors arranged in a line numbered with integers from $$$1$$$ to $$$n$$$ from left to right. Each conveyor has a symbol "<" or ">". The initial state of the conveyor $$$i$$$ is equal to the $$$i$$$-th character of the string $$$s$$$. There are $$$n+1$$$ holes numbered with integers from $$$0$$$ to $$$n$$$. The hole $$$0$$$ is on the left side of the conveyor $$$1$$$, and for all $$$i \geq 1$$$ the hole $$$i$$$ is on the right side of the conveyor $$$i$$$.

When a ball is on the conveyor $$$i$$$, the ball moves by the next rules:

If the symbol "<" is on the conveyor $$$i$$$, then:

- If $$$i=1$$$, the ball falls into the hole $$$0$$$.
- If the symbol "<" is on the conveyor $$$i-1$$$, the ball moves to the conveyor $$$i-1$$$.
- If the symbol ">" is on the conveyor $$$i-1$$$, the ball falls into the hole $$$i-1$$$.

If the symbol ">" is on the conveyor $$$i$$$, then:

- If $$$i=n$$$, the ball falls into the hole $$$n$$$.
- If the symbol ">" is on the conveyor $$$i+1$$$, the ball moves to the conveyor $$$i+1$$$.
- If the symbol "<" is on the conveyor $$$i+1$$$, the ball falls into the hole $$$i$$$.

You should answer next $$$q$$$ queries, each query is defined by the pair of integers $$$l, r$$$ ($$$1 \leq l \leq r \leq n$$$):

- First, for all conveyors $$$l,l+1,...,r$$$, the symbol "<" changes to ">" and vice versa. These changes remain for the next queries.
- After that, put one ball on each conveyor $$$l,l+1,...,r$$$. Then, each ball falls into some hole. Find the maximum number of balls in one hole. After the query all balls disappear and don't considered in the next queries.

## Input Format
The first line contains two integers $$$n$$$, $$$q$$$ ($$$1 \le n \le 5 \times 10^5 , 1 \le q \le 10^5$$$).

The second line contains a string $$$s$$$ of length $$$n$$$. It consists of characters "<" and ">".

Next $$$q$$$ lines contain the descriptions of the queries, $$$i$$$-th of them contains two integers $$$l$$$, $$$r$$$ $$$(1 \le l \le r \le n)$$$, describing the $$$i$$$-th query.

## Output Format
Print $$$q$$$ lines, in the $$$i$$$-th of them print the answer to the $$$i$$$-th query.

## Examples
```input
5 6
><>><
2 4
3 5
1 5
1 3
2 4
1 5
```
```output
3
3
5
3
2
3
```

## Note
- In the first query, the conveyors change to ">><<<". After that, put a ball on each conveyor $$$\{2,3,4\}$$$. All three balls fall into the hole $$$2$$$. So the answer is $$$3$$$.
- In the second query, the conveyors change to ">>>>>". After that, put a ball on each conveyor $$$\{3,4,5\}$$$. All three balls fall into the hole $$$5$$$. So the answer is $$$3$$$.
- In the third query, the conveyors change to "<<<<<". After that, put a ball on each conveyor $$$\{1,2,3,4,5\}$$$. All five balls fall into the hole $$$0$$$. So the answer is $$$5$$$.
- In the fourth query, the conveyors change to ">>><<". After that, put a ball on each conveyor $$$\{1,2,3\}$$$. All three balls fall into the hole $$$3$$$. So the answer is $$$3$$$.
- In the fifth query, the conveyors change to "><<><". After that, put a ball on each conveyor $$$\{2,3,4\}$$$. Two balls fall into the hole $$$1$$$, and one ball falls into the hole $$$4$$$. So, the answer is $$$2$$$.
- In the sixth query, the conveyors change to "<>><>". After that, put a ball on each conveyor $$$\{1,2,3,4,5\}$$$. Three balls fall into the hole $$$3$$$, one ball falls into the hole $$$0$$$ and one ball falls into the hole $$$5$$$. So, the answer is $$$3$$$.

Now solve the problem and return the code.