The Rocky Horror Picture Show P16636

Statement

thehtml

If you’re staying at Dr. Frank N. Furter’s place, you’d better watch your step! The moment the music kicks in, just look at the squares on the floor, join the other guests, follow the dance moves, and…let’s do the Time Warp again!

But hey, there are so many ways you can literally get warped and be sent back to Transsexual Transylvania:

If you hit any of the room walls (then you get warped!).
If you bump into another guest mid-air as you try to swap your positions (then you both get warped before you can land on your target square!).
If you land your step in the same square as other guests (then you all get warped!)

Given how all guests are at the start of the dance, can you tell how many of you would remain on the dance floor if the music went on forever?

Input

Input begins with the number of cases n ≥ 0. For every case, we have the dimensions W and H of the room, followed by the number of people P, followed by P triplets x_i, y_i, b_i with the position of the dancer and the direction he or she is facing. Follow the number of steps ‍S in the dance, followed by S characters s_i ∈ {‵F′, ‵R′, ‵B′, ‵L′} denoting a step forward, right, backward, or left, respectively.

Assume that W and H are between 1 and 10⁶, 1 ≤ P ≤ 10⁴, 1 ≤ x_i ≤ W, 1 ≤ y_i ≤ H, b_i ∈ {‵N′, ‵E′, ‵S′, ‵W′}, 1 ≤ S ≤ 10⁴, and that no two dancers will start at the same position.

Output

For each case, print the number of people that will be dancing indefinitely without ever being warped.

Public test cases

Input

2
6 5
3  2 2 E  2 4 N  5 3 W
4  R F L B
6 5
3  2 3 E  2 4 N  4 3 W
4  R F L B

Output

3
1

Information

Author: Edgar Gonzàlez
Language: English
Official solutions: C++
User solutions: C++