Bezorath大陆抵抗地灾军团入侵的战争进入了僵持的阶段，世世代代生活在Bezorath这片大陆的精灵们开始寻找远古时代诸神遗留的神器，试图借助神器的神秘力量帮助她们战胜地灾军团。
在付出了惨痛的代价后，精灵们从步步凶险的远古战场取回了一件保存尚完好的神杖。但在经历过那场所有史书都视为禁忌的“诸神黄昏之战”后，神杖上镶嵌的奥术宝石已经残缺，神力也几乎消耗殆尽。精灵高层在至高会议中决定以举国之力收集残存至今的奥术宝石，并重金悬赏天下能工巧匠修复这件神杖。
你作为神术一脉第五百零一位传人，接受了这个艰巨而神圣的使命。神杖上从左到右镶嵌了n颗奥术宝石，奥术宝石一共有10种，用数字0123456789表示。有些位置的宝石已经残缺，用.表示，你需要用完好的奥术宝石填补每一处残缺的部分（每种奥术宝石个数不限，且不能够更换未残缺的宝石）。古老的魔法书上记载了m种咒语，其中是一个非空数字串，是这种组合能够激发的神力。
神杖的初始神力值，每当神杖中出现了连续一段宝石与相等时，神力值就会乘以。但神杖如果包含了太多咒语就不再纯净导致神力降低：设c为神杖包含的咒语个数（若咒语类别相同但出现位置不同视为多次），神杖最终的神力值为。（若c=0则神杖最终神力值为1。）
你需要使修复好的神杖的最终的神力值最大，输出任何一个解即可。

第一行两个正整数n,m，表示宝石数和咒语数。
第二行为一个长度为n的字符串T，表示初始的神杖。
接下来m行每行一个非空数字串和一个正整数，表示每种咒语。

输出最终神杖上从左到右镶嵌的宝石，多解时任意输出一个即可。

4 3
....
1 2
2 2
3 1

2019

法杖最终神力值为 2。

5 4
..0..
0 2
00 2
01 4
10 3

11012

法杖最终神力值为。

18 6
...2.1.0.1..1.0..1
011 6
111 4
010 12
121 7
101 5
10 3

121211203112120121

设，即所有咒语的串长之和。
对于的数据，满足。