题目描述

Ran 最近沉迷在花道之中，甚至都忘了明天就是她和 Moka 的婚礼。今天 Moka 带来了 \(n\) 朵花，每朵花是红色或者青色，其中第 \(i\) 朵花的美丽值为 \(a_i\)。Moka 和 Ran 希望你将这些花分成两部分用作明天她们婚礼上的捧花，报酬是一朵花。

你需要在 \(n\) 朵花中拿走一朵，同时你可以选择任意朵青色的花将它们染成红色（可以不选），然后将剩余的 \(n-1\) 朵花按红色、青色分成两个部分（每个部分都可以为空），最小化两个部分花朵极差的最大值。

花朵极差的定义为：所有花朵中最大的美丽值减去所有花朵中最小的美丽值；若没有花朵，则花朵极差为 \(0\)。

简单易懂（？）题面：先选择一个整数 \(i\)，使得 \(s_i: = 'N'\)，再选择任意个整数 \(i(s_i = 'G')\)，使得 \(s_i: = 'R'\)，定义 \(f(c) = max_{s_i = c}\ a_i - min_{s_i = c}\ a_i\)，最小化 \(max(f('R'), f('G'))\)。

输入格式

第一行输入一个正整数 \(T(1 \le T \le 2 \times 10^5)\)，表示数据组数。

对于每一组数据：

第一行输入一个正整数 \(n(1 \le n \le 10^5)\)，表示花朵数量。

第二行输入 \(n\) 个正整数 \(a_i(1 \le a_i \le 10^9)\)，表示每朵花的美丽值。

第三行输入一个长度为 \(n\)，只由大写字母组成的字符串 \(s\)， \(s_i = 'R', s_i = 'G'\) 分别表示第 \(i\) 朵花颜色为红色、青色。

数据保证 \(\sum n \le 5.1 \times 10^5\)。

输出格式

对于每组数据输出一个整数表示答案。

样例输入

1
6
1 1 4 5 1 4
RGRGRG

样例输出

1

提示

拿走第3朵花，将第2朵花染成红色。

第1、2、5朵花为红色，美丽值分别为{1, 1, 1}；

第4、6朵花为青色，美丽值分别为{5, 4}；

因此最后的答案为1。