题目描述

一个圆形游戏板上有 $N$ 个弹簧，按顺时针方向编号为 $1,2,\ldots,N$。每个弹簧的类型为 1 或 2：

• 站在类型 1 的弹簧上，机器人可沿指定方向跳到相邻的下一个弹簧；
• 站在类型 2 的弹簧上，机器人可沿指定方向跳过一个弹簧，到达距离为两格的弹簧。

游戏中有两个机器人，初始放在两个不同的弹簧上。每次你只能发出以下两种全局指令之一：

• 两个机器人同时顺时针跳跃；
• 两个机器人同时逆时针跳跃。

两个机器人必须同时移动，且方向相同；各自跳跃的距离由它当前所站弹簧的类型决定。

当两个机器人站在不同类型的弹簧上时，游戏结束。

给定 $Q$ 组两个机器人的初始位置。对每组询问，求结束游戏所需的最少指令数；若无论如何都无法结束，输出 $-1$。

输入格式

第一行包含两个整数 $N,Q$。

第二行包含 $N$ 个整数，第 $i$ 个整数为弹簧 $i$ 的类型，取值为 1 或 2。

接下来 $Q$ 行，每行包含两个不同的整数 $p_1,p_2$，表示两个机器人的初始位置。

数据范围：

输出格式

对每组询问输出一行：

• 若初始时两个机器人所在弹簧类型已经不同，输出 $0$；
• 否则输出使它们站到不同类型弹簧上的最少指令数；
• 若无法做到，输出 $-1$。

样例

输入

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

输出

0
-1
1