Избирательная комиссия Флатландии готовится к президентским выборам. Чтобы свести к минимуму человеческий фактор при подсчете голосов, они решили разработать автоматическое устройство для анализа бюллетеней (УАБ).

На пост президента баллотируются n кандидатов. Бюллетень содержит одно квадратное поле для каждого кандидата. Избиратель должен отметить ровно одно из полей. Если поле не помечено или имеется два или более отмеченных поля, бюллетень недействителен. Каждый избиратель ставит свой бюллетень на специальный сканер в УАБ. Сканер анализирует отметки в бюллетене и создает специальную строку голосования из n символов: 'X' для отмеченного поля и '.' для немаркированного. Теперь строки голосования должны быть проанализированы, чтобы получить отчет. Ваша задача - разработать генератор отчетов для УАБ.

С учетом строк голосования для всех бюллетеней Ваша программа должна распечатать отчет о голосовании. Кандидаты в протоколе должны быть расположены в порядке убывания количества голосов. Если два кандидата имеют одинаковое количество голосов, они должны иметь тот же порядок, что и в бюллетене для голосования. Для каждого кандидата рассчитайте его / ее результат в процентах (если кандидат получил p голосов, результат в процентах составляет 100p/m). В последней строке отчета должен быть указан процент недействительных бюллетеней.

Входные данные

Первая строка содержит два целых числа n и m (2 ≤ n ≤ 10, 1 ≤ m ≤ 1000) - количество кандидатов и количество бюллетеней. Следующие n строк содержат фамилии кандидатов. Каждое имя представляет собой строку не более 100 английских букв. Нет ни одного кандидата с именем "Invalid".

Затем следуют m строк, каждая из которых содержит одну строку голосования.

Выходные данные

Выведите n + 1 строк. Сначала выведите результаты для кандидатов в процентах. Для каждого кандидата выведите его / ее фамилию, затем пробел, а затем его / ее результат в процентах и знак процента '%'. В последней строке должен быть указан процент недействительных бюллетеней: слово "Invalid", за которым следуют пробел, процент недействительных бюллетеней и знак процента.

Округлите все числа до двух цифр после десятичной точки. Если число находится точно посередине двух представимых чисел, выведите большее (например, выведите "12.35" для 12.345).