时空限制

1S/512M

题目描述

有 $n$ 个同学，第 $i$ 个同学的名字为 $S_i$。

老师进行了 $m$ 次点名，第 $i$ 次点名他会点到所有名字首字母或者末尾字母为 $c_i$ 的同学。

请你算出每个同学被点到的次数。

格式

输入格式

第一行包含两个整数 $n$ 和 $m$，分别表示同学的数量和老师点名的次数。

接下来 $n$ 行每行一个字符串 $S_i$，分别表示每个同学的名字。数据保证 $S_i$ 仅由小写英文字母组成，且 $1\leq |S_i|\leq 10$。

接下来 $m$ 行每行包含一个整数 $f_i$ 和一个小写英文字母 $c_i$，如果 $f_i=1$ 表示第 $i$ 次点名点到所有名字首字母为 $c_i$ 的同学，如果 $f_i=2$ 表示第 $i$ 次点名点到所有名字末尾字母为 $c_i$ 的同学。

输出格式

输出 $n$ 个整数，第 $i$ 个整数表示第 $i$ 个同学被点到的次数。

样例

样例输入 #1

4 5
alice
kobe
anna
anne
1 a
2 e
1 e
1 k
1 a

样例输出 #1

3 2 2 3

样例解释 #1

第 $1$ 次点名点到所有名字首字母为 a 的同学：alice、anna、anne；

第 $2$ 次点名点到所有名字末尾字母为 e 的同学：alice、kobe、anne；

第 $3$ 次点名点到没点到任何人；

第 $4$ 次点名点到所有名字首字母为 k 的同学：kobe；

第 $5$ 次点名点到所有名字首字母为 a 的同学：alice、anna、anne。

alice 被点到 $3$ 次，kobe 被点到 $2$ 次，anna 被点到 $2$ 次，anne 被点到 $3$ 次。

数据规模

对于 $50\%$ 的数据，$n,m\leq 1000$。

对于 $100\%$ 的数据，$1\leq n,m\leq 10^5$，$f_i\in \{1,2\}$。数据保证 $S_i$ 仅由小写英文字母组成，且 $1\leq |S_i|\leq 10$。