枪王贾巧

Tags:

Description

作为金陵十二钗中出场次数最少的贾巧姐，其实平时是在偷偷练枪。

今天，贾巧姐的枪法已经达到了百发百中的境界，但是你不相信，于是你想见识一下贾巧姐的枪技。

我们把贾巧姐表演枪技抽象成这样一个问题，在一个一维坐标下，贾巧姐会在某些位置射击目标，并且我们用$'<'$表示贾巧姐能在此位置向左射击，用$'>'$表示贾巧姐能在此位置向右射击，用$'@'$表示目标。每个坐标要么表示贾巧姐能够射击目标的方向，要么表示一个目标，并且有时需要进行更换调整。

表演可能有多个回合，每回合贾巧姐在一段范围内射击该范围内的目标，并且每回合在该范围的每个位置最多只射击一次，目标被击中后会倒下(新回合会刷新)。贾巧姐的枪技保证她是百发百中的。如果已经没有能射击的目标了，贾巧姐不会继续开枪。

因此，你需要完成这样一个过程：总共有$q$次操作，每次操作先输入3个值$x、a、b(x∈\{0,1\})$。

如果$x = 0$，则$a$为整数($1≤a≤N$)、$b$为一个字符($b∈\{'<', '>', '@'\}$)，表示将$a$位置处设置为b。

如果$x = 1$，则$a、b$都为整数($1≤a≤b≤N$)，你需要输出一个值$num$，表示$a$到$b$区间内最多能射倒几个目标（只考虑该区间内能够射击的位置和该区间的目标，题目保证至少有一个$x=1$的操作）。

Input

第一行一个正整数$N$($1≤N≤100000$)，表示一排总共有$N$个位置。

第二行$N$个字符$c$($c∈\{'<', '>', '@'\}$)，表示一开始每个位置的模拟情况。

第三行一个正整数$q$($1≤q≤100000$)，表示操作个数。

随后$q$行，每行三个值$x$ $a$ $b$，表示上述操作。

Output

对于每个$x =  1$的操作，输出一个$num$，表示该区间最多能射倒几个目标。每输出一个数后输出一个换行。

Samples

Hint

在第一个样例中，初始时刻状态为“>@@@<”。

第一个操作，贾巧姐先站在最左边向右开枪打倒一个目标，再站在最右边向左开枪打倒一个目标，最多能打倒2个目标。

第二个操作，区间1~2内，贾巧姐站在最左边向右开枪打倒一个目标，最多能打倒1个目标。

第三个操作，状态变为“>@<@<”。

第四个操作，状态变为“<@<@<”。

第五个操作，区间1~2内，贾巧姐能站在最左边，但只能向左开枪，左边没有目标，因此她不会开枪，最多能打倒0个目标。

第六个操作，区间1~3内，贾巧姐站在下标为3的位置向左开枪，最多能打倒1个目标。

Author