Source: Super League of Chinese College Students Algorithm Design 2022, Contest 2 by HDU.

Problem Description

Some contestants said on the Internet that they love Multi-University Training, did the rest of them have no keyboards?

You must be the one whose keyboard is badly broken. When you press a key, it triggers a random number of times.

Given a character $ch$ and an integer $k$, it means you press an alphanumeric key $ch$ only once, but it triggers $k$ times, and $k$ character $ch$ will be added to the end of the buffer.

Given a character - and an integer $k$, it means you press the backspace key, it triggers $k$ times, delete $k$ characters from the end (If the number of characters is less than $k$, the buffer will be cleared).

Given the operations in chronological order, could you input your target text? Which means whether there is a time, your target text is a substring of your buffer characters? Answer yes or no. (In formal language theory and computer science, a substring is a contiguous sequence of characters within a string.)

Input

First line has one integer $T$, indicating there are $T$ test cases. In each case:

First line has two integers $n, m$, $n$ indicates the length of your target text, $m$ indicates the number of times you press the key.

Second line has a string of length $n$, which contains only lowercase letters.

For next $m$ lines, each line has a character $ch$ and an integer $k$, their meanings are described above.

$1 \leq n, m \leq 2 \times 10^5, 0 \leq k \leq 10^9, \sum {(n+m)} \leq 2\times 10^6$.

Output

In each case, print yes or no, without quote.

Sample

3
6 6
iloveu
i 1
l 1
o 1
v 1
e 1
u 0
6 10
imfive
u 10
- 20
i 1
m 1
f 1
i 1
v 5
- 4
e 2
- 2
4 4
abab
a 2
b 2
- 3
b 1

no
yes
no