TESSER - Finding the Tesserect

Dr. Bruce Banner had estimated a coarse location of Tesseract through gamma radiation emission tracing experiment. It was estimated that Tesseract was hidden somewhere within the Alps mountains. Captain America was given the assignment to look for the Tesseract and bring it back to S.H.I.E.L.D. While roaming through the mountains of Alps, Captain America looked at the height of hills and clicked a panoramic photograph of mountains. This gives an idea of the heights of mountains. Meanwhile Banner was able to determine a continuous pattern of mountains behind which the Tesseract lies and transmitted a message containing the pattern.

The message is a string consisting of characters 'G', 'L' and 'E' where G means greater, L means less and E means equal. But this estimation is likely to go wrong due to not considering environmental disturbances that may have arisen in the medium during the experiment.

Pattern estimate is correct only if one can find a set of consecutive heights out of the given N heights satisfying the message pattern (if G is first character of the message string then second height should be greater than the first height of the selected set and so on) Captain America seeks your help to find out whether the estimation is correct or wrong so that Captain America could proceed his tasks.

Input

The first line of the input contains an integer T denoting the number of test cases. Each test case consists of 3 lines. The first line of each test case contains a single integer N denoting the number of hills. Second line of each test case consists of N integers (a_1, a_2 ... a_n), the heights of hills. Third line contains the message pattern.

  • 1T105
  • 2N105
  • 1a_i109
  • 1Length of Message PatternN-1

Output

For each test case print 'YES' if the pattern estimation is correct. Else print 'NO'.

Example

Input:
1
5
1 2 3 4 1
GGL

Output:
YES

 

Explanation

Answer is "YES", because 2 3 4 1 satisfies GGL pattern, i.e. 3 is greater than 2, 4 is greater than 3, 1 is less than 4.


Added by:BLANKRK
Date:2013-11-14
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Code Weavers 2013

hide comments
2024-06-27 00:43:29
Z string also got AC
2021-06-20 09:56:38
I used string and got Ac there is no problem in using array of char or string but do not declare any array in loop otherwise you will get tle
2021-01-03 19:05:20
AC in 1 Go
2020-12-28 07:59:42
use array of char otherwise it will give you tle
2020-06-19 01:43:54
KMP really rocks...!!!
2020-04-19 20:15:52
AC IN 1 GO.
TIME:-0.04
2018-01-17 10:21:12
if you are getting TLE with strings in c++, pick c++ 14 (6.3) as your language.
2017-06-28 11:37:44
KMP rocks ;)
2017-06-16 19:16:01
working with string causes TLE whereas array of char works perfectly
2017-02-10 09:28:23
Easy one AC in 1 go ☺️☺️
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.