codeforces#P1371F. Raging Thunder

    ID: 31263 远端评测题 3000ms 512MiB 尝试: 0 已通过: 0 难度: 10 上传者: 标签>data structuresdivide and conquerimplementation*2800

Raging Thunder

Description

You are a warrior fighting against the machine god Thor.

Thor challenge you to solve the following problem:

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

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

If the symbol "<" is on the conveyor ii, then:

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

If the symbol ">" is on the conveyor ii, then:

  • If i=ni=n, the ball falls into the hole nn.
  • If the symbol ">" is on the conveyor i+1i+1, the ball moves to the conveyor i+1i+1.
  • If the symbol "<" is on the conveyor i+1i+1, the ball falls into the hole ii.

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

  • First, for all conveyors l,l+1,...,rl,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,...,rl,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.

The first line contains two integers nn, qq (1n5×105,1q1051 \le n \le 5 \times 10^5 , 1 \le q \le 10^5).

The second line contains a string ss of length nn. It consists of characters "<" and ">".

Next qq lines contain the descriptions of the queries, ii-th of them contains two integers ll, rr (1lrn)(1 \le l \le r \le n), describing the ii-th query.

Print qq lines, in the ii-th of them print the answer to the ii-th query.

Input

The first line contains two integers nn, qq (1n5×105,1q1051 \le n \le 5 \times 10^5 , 1 \le q \le 10^5).

The second line contains a string ss of length nn. It consists of characters "<" and ">".

Next qq lines contain the descriptions of the queries, ii-th of them contains two integers ll, rr (1lrn)(1 \le l \le r \le n), describing the ii-th query.

Output

Print qq lines, in the ii-th of them print the answer to the ii-th query.

Samples

输入数据 1

5 6
&gt;&lt;&gt;&gt;&lt;
2 4
3 5
1 5
1 3
2 4
1 5

输出数据 1

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}\{2,3,4\}. All three balls fall into the hole 22. So the answer is 33.
  • In the second query, the conveyors change to ">>>>>". After that, put a ball on each conveyor {3,4,5}\{3,4,5\}. All three balls fall into the hole 55. So the answer is 33.
  • In the third query, the conveyors change to "<<<<<". After that, put a ball on each conveyor {1,2,3,4,5}\{1,2,3,4,5\}. All five balls fall into the hole 00. So the answer is 55.
  • In the fourth query, the conveyors change to ">>><<". After that, put a ball on each conveyor {1,2,3}\{1,2,3\}. All three balls fall into the hole 33. So the answer is 33.
  • In the fifth query, the conveyors change to "><<><". After that, put a ball on each conveyor {2,3,4}\{2,3,4\}. Two balls fall into the hole 11, and one ball falls into the hole 44. So, the answer is 22.
  • In the sixth query, the conveyors change to "<>><>". After that, put a ball on each conveyor {1,2,3,4,5}\{1,2,3,4,5\}. Three balls fall into the hole 33, one ball falls into the hole 00 and one ball falls into the hole 55. So, the answer is 33.