Ballot Analysis Report Generator

Election committee of Flatland is preparing for presidential elections. To minimize human factor in ballot counting they decided to develop an automated Ballot Analyzing Device (\(BAD\)).

There are \(n\) candidates running for president. The ballot contains one square field for each candidate. The voter must mark exactly one of the fields. If no field is marked or there are two or more marked fields, the ballot is invalid. Each voter puts his/her ballot to a special scanner in \(BAD\). The scanner analyzes marks on the ballot and creates a special voting string of \(n\) characters: 'X' for a marked field and '.' for an unmarked one.

Your task is to develop a report generator for \(BAD\).

Given voting strings for all ballots, your program must print the voting report. Candidates in the report must be arranged in order of decreasing number of votes. If two candidates have the same number of votes, they must retain the same order as in the ballot. For each candidate, calculate his/her result in percent (if the candidate received \(p\) votes, the result in percent is \(100p/m\)). The last line of the report must indicate the percentage of the invalid ballots.

inputFormat

The first line of input contains two integers (n) and (m), representing the number of candidates and the number of ballots respectively. Each of the following (m) lines contains a string of (n) characters, each being either 'X' or '.', indicating the marks on the ballot.

outputFormat

Print (n+1) lines. The first (n) lines should correspond to the candidates arranged in order of decreasing vote counts. Each line must contain the candidate number (starting from 1) followed by a space and the vote percentage formatted to two decimal places with a '%' symbol. The last line should display the invalid ballots percentage in the same format, prefixed by the word "invalid".

sample

3 5
X..
.X.
..X
XX.
.XX

1 20.00%
2 20.00%
3 20.00%
invalid 40.00%