A60054.机器人Ⅱ

本题是机器Ⅰ的加强，题面完全一样，仅数据范围不一样

一条环形纸带被均分成 $n$ 个格子，每个格子被涂上了黑白两种颜色之一。从格子 $1$ 开始顺时针数，依次为格子 $1$，格子 $2$，……，格子 $n$。格子 $i$ 的颜色为 $c_i$；有 $m$ 个程序，第 $j$ 个程序可以被描述为 $(p_j,l_j,r_j)$ ，意义如下：

• 把两个机器人 $Lobot$、$Robot$ 放置到格子 $p_j$ 上。同时我们记目前的颜色 $color_t$ 为 $c_{p_j}$ , 目前时间 $t = 0$ 。
• 若机器人 $Lobot$ 位于格子 $l_j$ 上，并且机器人 $Robot$ 位于 $r_j$ 上，程序结束。否则进行一次移动。 移动规则如下:
  • 目前时间 $t$ 增加 $1$ 。
  • 若目前颜色 $color_t$ 为黑色 ，$Lobot$ 机器人逆时针移动一次 ,$Lobot$ 到达位置 $q$ 。
  • 若目前颜色 $color_t$ 为白色 ，$Robot$ 机器人顺时针移动一次 ,$Robot$ 到达位置 $q$ 。
  • 目前的颜色 $color_t$ 更改为 $c_q$ 。

对于第一次移动，我们认为上一次移动的机器人移动到了颜色为 $color_{p_j}$ 的格子上。

对于所有的 $m$ 个程序，判断它会在运行多少秒后停止，或断言它不会停止。

对于每组测试数据，第一行为两个正整数 $n , m$。

第二行为一个长度为 $n$ 的字符串 $c$，第 $i$ 个字符表示 $c_i$，其中若 $c_i=\texttt{1}$ 表示格子 $i$ 是白色的，若 $c_i=\texttt{0}$ 表示格子 $i$ 是黑色的。

接下来 $m$ 行，每行用三个整数 $p_j,l_j,r_j$ 表示一个程序。

对于每组测试数据，输出 $m$ 行，对于第 $i$ 行：

• 若第 $i$ 个程序会停止，输出一个整数表示它运行的秒数 $t_i$。
• 若第 $i$ 个程序不会停止，输出 -1。

数据范围

• $1 \le n \le 10^6$
• $1\le m \le 5 \times 10^5$
• $c_i \in \{1 ,0 \}$
• $1 \le p_j ,l_j ,r_j \le n$