#59. [SCOI 2015] 小凸解密码

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Sky390

题目描述

小凸得到了一个密码盘,密码盘被等分成 个扇形,每个扇形上有一个数字 ,和一个符号 +* 。密码盘解密的方法如下:

首先,选择一个位置开始,顺时针地将数字和符号分别记在数组 和数组 中。解密的方法如下:

  • 时:
  • +
  • *

操作完成后,可以得到一个长度为 的数组 ,然后以 为起点将 数组顺时针写成一个环,解密就完成了,称得到的环为答案环。

现在小凸得到了一份指令表,指令表上有 2 种操作。一种指令是修改操作,即改变原来密码盘上一个位置的数字和符号。另一种指令是询问操作,具体如下:

  • 首先从指令给出的位置开始完成解密,得到答案环。
  • 答案环上会有一些 连在一起,将这些连在一起的 称为零区间,找出其中距离 最远的那个零区间,输出这个距离(零区间和 的距离定义为:零区间内所有 距离中的最小值)。

输入格式

第一行包含两个整数 ,代表密码盘大小和指令个数。

接下来 行,每行包含一个整数和一个字符,按顺时针顺序给出了密码盘上的数组和符号。

接下来 行,依次给出指令。每行第一个整数代表指令类型:

  • 若第一个整数为 1,代表本行对应指令为修改操作,之后依次有两个整数 和一个字符 ,分别代表修改的位置,以及修改后该位置的数字和字符。
  • 若第一个整数为 2,代表本行对应指令位询问操作,之后有一个整数 ,代表本次操作中解密的开始位置。

密码盘上的位置标号为

数据保证合法,即数据中 +*

输出格式

对于每个询问操作 行,输出答案,若答案环上没有 ,输出 -1

样例

样例输入

5 8
0 *
0 *
0 *
0 *
0 *
2 0
1 0 1 +
1 2 1 +
2 3
1 1 1 +
1 3 1 +
1 4 1 +
2 4

样例输出

0
2
-1

数据范围与提示

样例解释:

对于第 个询问,答案环为 ,仅有 个零区间,且 在其中,所以距离是

对于第 个询问,答案环为 ,有 个零区间, 距离是 距离是 ,故答案为

对于第 个询问,答案环为 ,没有零区间,答案是 ?1

数据范围:

  • 对于 数据,
  • 对于 数据,
  • 对于 数据,