G. Double Elimination
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

One of the greatest e-sport events, The Invitational TOAD-3 Championship, will feature $$$16$$$ best teams in the world. In order to prolong the fascinating event and acquire more money from advertising a double-elimination tournament scheme will be used.

First, all teams are ordered by their rating and the $$$i$$$-th team in the sorted list plays versus the team at position $$$(17-i)$$$. The winner of each of these matches goes to the winners' bracket, the loser goes to the losers' bracket.

Participants of the winners' bracket continue to play a single-elimination tournament, except that the losers of each round "drop down" into the losers' bracket.

Each round of the loser's bracket is conducted in two stages; a minor stage followed by a major stage. Both contain the same number of matches which is the same again as the number of matches in the corresponding round of the winners' bracket. If the minor stage of a looser's bracket round contains $$$2^k$$$ matches, there will be $$$2^k$$$ winners. Meanwhile, the $$$2^k$$$ matches in the corresponding round of the winners' bracket will produce $$$2^k$$$ losers. These $$$2^{k+1}$$$ teams will then form pairs for $$$2^k$$$ matches of the corresponding major stage of the looser's bracket. At this stage of the round, looser of the winners' bracket round can play only against winners of the minor stage of the looser's bracket.

In both brackets, before each round opponents are chosen at random to form pairs. Same apply to the process of forming pairs of type "loser from winners' bracket versus winner of the minor stage from the losers' bracket" at the major stages of the losers' bracket rounds.

All players who are eliminated from the same stage are considered to share the same position in the resulting ranking.

Below is the scheme of how the double-elimination tournament for 16 teams is held.

  • The first round is played; winners of the first round form the winners' bracket, losers of the first round form the losers' bracket.
  • The eight losers of the first round form pairs of the first minor stage of the losers' bracket, we denote this stage as $$$L_8a$$$. The four losers are eliminated (their participation in the tournament is over, they share places from $$$13$$$ to $$$16$$$), while the four winners proceed to the major stage of this round, we denote it as $$$L_8b$$$.
  • The eight winners of the first round form pairs for the first round of the winners' bracket, we denote this as $$$W_8$$$. The four winners proceed to the stage $$$W_4$$$, four losers proceed to stage $$$L_8b$$$.
  • During stage $$$L_8b$$$, each losing team from $$$W_8$$$ plays against the winning team from $$$L_8a$$$, the four losers are eliminated (they end up at places $$$9-12$$$), while the winners proceed to the stage $$$L_4a$$$.
  • The four winners of $$$L_8b$$$ go to stage $$$L_4a$$$. The losers are eliminated (they end up at places $$$7-8$$$), while two winners proceed to stage $$$L_4b$$$.
  • The four winners of $$$W_8$$$ form pairs for the second round of the winners' bracket (named $$$W_4$$$), the two winners proceed to stage $$$W_2$$$, the two losers proceed to stage $$$L_4b$$$.
  • In stage $$$L_4b$$$, each losing team from $$$W_4$$$ plays against some winner $$$L_4a$$$, the two losers are eliminated (they end up at places $$$5-6$$$), while the winners proceed to stage $$$L_2a$$$.
  • In stage $$$L_2a$$$ the two winners of $$$L_4b$$$ play one match against each other, the loser finishes the tournament at the $$$4$$$-th place, the winner proceeds to stage $$$L_2b$$$ (also know as loser's bracket final).
  • In stage $$$W_2$$$ one match is played. The winner proceeds directly to the grand final, the loser proceeds to stage $$$L_2b$$$.
  • In stage $$$L_2b$$$ one match is played, the winner proceeds to the grand final, the loser finishes the tournament at the third place.
  • The winner of the match in grand final is declared a champion, the loser finishes the tournament second.

You are given the list of teams with the results of all matches played by this team during the tournament in chronological order. Determine the final place for each team.

Input

The input contains $$$16$$$ lines.

Each line consists of two strings — the team name $$$t$$$ made up of lowercase English letters ($$$1 \le |t| \le 50$$$) and the string $$$G$$$ with the outcomes of all games this team has played. String $$$G$$$ consists of digits 1 and 0 only. If the $$$i$$$-th character of this string equals 1 it means that this team won its $$$i$$$-th match on the tournament. If the $$$i$$$-th character of this string equals to 0, it means that this team lost its $$$i$$$-th match on the tournament.

You may assume that all team names are distinct and that the distribution of wins and losses correspond to some correctly held double-elimination tournament for those teams.

Output

Print 16 lines. Each line should contain the notation for place: one integer if the place is not shared, and two integers separated by single '-' — the highest and the lowest if the place is shared, followed by the team name.

Teams shall be listed by their places in increasing order. If several teams share a place, sort those teams by the name lexicographically. See sample output for further clarification.

Example
Input
escmraeett 11100
neigulsievse 010
noet 1010
nduymianegt 00
psimraiett 10111111
ustprriov 1100
yccnrieuwq 010
go 1010
agmiicnigv 10110
ctosaasetb 00
sugtacmiivnngi 11010
hpaenlte 00
lggsdp 11110
taincf 010
ainlclea 010
asmtaeert 00
Output
1 psimraiett
2 lggsdp
3 escmraeett
4 sugtacmiivnngi
5-6 agmiicnigv
5-6 ustprriov
7-8 go
7-8 noet
9-12 ainlclea
9-12 neigulsievse
9-12 taincf
9-12 yccnrieuwq
13-16 asmtaeert
13-16 ctosaasetb
13-16 hpaenlte
13-16 nduymianegt