/ WHOJ / 题库 /

欢送的村民

欢送的村民

描述

周幽王去审查地方治安,走的时候,有nn位村民“自发”地欢送他。村民以1m/s1m/s的速度从前方与他相遇或从后方追他。现在已知每位村民的行走方向L/RL/R(可以把它认为是一条直线,周幽王在一个点,村民往左走或往右走)和在这个直线上的坐标(均为偶数)。问任意两个村民相遇的最早时间。

格式

输入格式

第一行为正整数tt,表示数据组数;每组数据中,第一行为正整数nn,表示村民个数,第二行nn个字符RRLL表示每个村民的行走方向,第三行为nn个非负整数aia_i,表示每个村民的初始坐标,坐标保证为偶数且任意两个村民的初始位置均不相同。

输出格式

对于每组数据,输出任意两个村民相遇的最早时间,如果不会发生相遇,输出1-1

样例1

输入样例1

1
4
RLRL
2 4 6 10

输出样例1

限制

对于100100%的数据,t5n105,ai109t≤5,n≤10^5,a_i≤10^9

来源

地址:vijosvijos,芜湖OIOI团队
作者:黑暗路西法0808
模拟赛T4T4