Description

有些选手在网上说他们喜欢多校联合训练，难道其他人都没有键盘吗？

你的键盘一定是坏得很彻底的那个。当你按下一个键时，它会随机触发若干次。

给定一个字符 $ch$ 和一个整数 $k$，表示你只按了一次字母或数字键 $ch$，但它触发了 $k$ 次，于是 $k$ 个字符 $ch$ 会被添加到缓冲区的末尾。

给定字符 - 和一个整数 $k$，表示你按下了退格键，它触发了 $k$ 次，从缓冲区末尾删除 $k$ 个字符（如果缓冲区中的字符数不足 $k$ 个，则缓冲区被清空）。

给定按时间顺序排列的操作序列，你能否输入你的目标文本？也就是说，是否存在某个时刻，你的目标文本是缓冲区中字符串的一个子串？回答 yes 或 no。（在形式语言理论和计算机科学中，子串是指字符串中一段连续的字符序列。）

Format

Input

第一行包含一个整数 $T$，表示测试数据的组数。对于每组测试数据：

第一行包含两个整数 $n, m$，其中 $n$ 表示目标文本的长度，$m$ 表示你按键的次数。

第二行包含一个长度为 $n$ 的字符串，仅由小写字母组成。

接下来 $m$ 行，每行包含一个字符 $ch$ 和一个整数 $k$，含义如上所述。

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

Output

对于每组测试数据，输出一行 yes 或 no（不含引号）。

Samples

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

Source

2022 中国大学生算法设计超级联赛（2），杭州电子科技大学出题。