Flatland 选举委员会正在筹备总统选举。为了最大限度地减少计票过程中的人为因素，他们决定开发一种自动选票分析设备（Ballot Analyzing Device，简称 BAD）。

共有 $n$ 名候选人参选总统。选票上为每位候选人设有一个方格。选民必须且只能在其中一个方格内打钩。如果没有任何方格被标记，或者有两个及以上的方格被标记，则该选票无效。每位选民将选票放入 BAD 的专用扫描仪中。扫描仪会分析选票上的标记，并生成一个包含 $n$ 个字符的特殊投票字符串：用 'X' 表示已标记的方格，用 '.' 表示未标记的方格。现在需要对这些投票字符串进行分析以生成报告。你的任务是为 BAD 开发一个报告生成器。

给定所有选票的投票字符串，你的程序必须打印投票报告。报告中的候选人必须按得票数从多到少排列。如果两名候选人的得票数相同，则他们必须保持在选票上的原始顺序。对于每位候选人，计算其得票百分比（如果候选人获得了 $p$ 张选票，则百分比结果为 $100p/m$）。报告的最后一行必须标明无效选票的百分比。

输入格式

第一行包含两个整数 $n$ 和 $m$ —— 候选人数和选票数（$2 \le n \le 10$；$1 \le m \le 1000$）。接下来的 $n$ 行包含候选人的姓氏。每个名字是一个长度不超过 100 个英文字母的字符串。没有候选人被命名为 “Invalid”。

随后有 $m$ 行，每一行包含一个投票字符串。

输出格式

打印 $n+1$ 行。首先打印候选人的百分比结果。对于每位候选人，打印其姓氏，后跟一个空格，然后是其百分比结果和一个百分号 '%'。最后一行必须标明无效选票的百分比：单词 “Invalid”，后跟一个空格，无效选票的百分比和一个百分号。

将所有数字四舍五入到小数点后恰好两位。如果数字恰好处于两个可表示数字的中间，则输出较大的一个（例如，对于 12.345，输出 “12.35”）。

样例

输入 1

4 7
Loudy
Apples
Dogman
Miller
.X..
X...
....
..X.
..XX
..X.
..X.

输出 1

Dogman 42.86%
Loudy 14.29%
Apples 14.29%
Miller 0.00%
Invalid 28.57%