在一个环形游戏板上有 $N$ 个弹簧。弹簧有两种类型：红色弹簧和蓝色弹簧。当机器人落在红色弹簧上时，它可以向左或向右跳跃一个弹簧。当机器人落在蓝色弹簧上时，它可以向左或向右跳跃两个弹簧。

两个机器人分别在弹簧 1 和 6 上，且给出了逆时针跳跃指令的情况。

你将使用两个机器人进行游戏。在游戏开始时，你将两个机器人放置在游戏板上不同的弹簧上。然后你可以发出一个方向指令——顺时针或逆时针。两个机器人将同时向你指定的方向跳跃。当机器人落在不同颜色的弹簧上时，游戏结束。

给你 $Q$ 次询问。每次询问包含两个机器人的起始弹簧位置。对于每次询问，求结束游戏所需的最少指令数。

输入格式

第一行包含两个整数 $N$ 和 $Q$ ($3 \le N \le 100\,000$，$1 \le Q \le 100\,000$)。

第二行包含 $N$ 个整数，第 $i$ 个整数表示弹簧 $i$ 的类型。红色弹簧用 1 表示，蓝色弹簧用 2 表示。

接下来的 $Q$ 行，每行包含两个整数 $p_1$ 和 $p_2$，表示两个机器人开始游戏时的位置 ($1 \le p_1, p_2 \le N$，$p_1 \neq p_2$)。

输出格式

输出 $Q$ 行。在第 $i$ 行中，输出一个整数，表示第 $i$ 次询问中使两个机器人落在不同颜色弹簧上所需的最少指令数。如果无法使机器人落在不同颜色的弹簧上，则输出 -1。

样例

输入样例 1

8 3
1 2 2 2 1 2 1 2
1 2
1 5
3 6

输出样例 1

0
-1
1