有 $$$n$$$ 个城市位于一条直线上。城市编号从 $$$1$$$ 到 $$$n$$$。
门户用于在城市之间移动。门户有 $$$4$$$ 颜色:蓝色、绿色、红色和黄色。每个城市都有两种不同颜色的门户。如果城市 $$$i$$$ 具有相同颜色的传送门,您可以从城市 $$$i$$$ 移动到城市 $$$j$$$(例如,您可以在“蓝红色”城市和“蓝绿色”城市之间移动)。此动作需要花费 $$$|i-j|$$$ 硬币。
你的任务是回答 $$$q$$$ 独立查询:计算从城市 $$$x$$$ 移动到城市 $$$y$$$ 的最低成本。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1 \le n, q \le 2 \cdot 10^5$$$) - 分别是城市数量和查询数量。
第二行包含以下类型的 $$$n$$$ 字符串:BG、BR、BY、GR、GY 或 RY;其中第 $$$i$$$ 描述了位于第 $$$i$$$ 城市的门户;符号B表示城市中有一个蓝色的传送门,G——绿色,R——红色,Y——黄色。
接下来的 $$$q$$$ 行的第 $$$j$$$ 行包含两个整数 $$$x_j$$$ 和 $$$y_j$$$ ($$$1 \le x_j, y_j \le n$$$) - 第 $$$j$$$ 查询的描述。
输入的附加限制:
- 所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$;
- 所有测试用例的 $$$q$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个查询,打印一个整数 - 从城市 $$$x$$$ 移动到城市 $$$y$$$ 的最低成本(如果不可能,则打印 $$$-1$$$)。
示例
输入 #1
2 4 5 BR BR GY GR 1 2 3 1 4 4 1 4 4 2 2 1 BG RY 1 2
输出 #1
1 4 0 3 2 -1