Bingo

Interview

Time limit1sMemory limit1024 MB

Summary

Given bingo boards and a drawn sequence, list the players who have a full row, column, or diagonal marked after m draws, in input order.

Level: Easy2 of 10
Topics: Array, Hash map, Simulation
Solved: No attempts yet

Problem

To play Bingo, you need a game master and a drum with $90$ balls, each containing a number from $1$ to $90$ , such that every number appears on exactly one ball. Before the game starts, the game master gives each of the $n$ players a $5 \times 5$ board. Each field of a board contains an integer between $1$ and $90$ , and all integers on a board are distinct. Each player gets a unique board. After the boards are handed out, the game begins. The game master draws a ball with number $x_i$ , announces it, and sets the ball aside. Each player marks that number on their board if it appears there. A player who marks all $5$ numbers of a row, column, main diagonal, or antidiagonal shouts Bingo! and wins, which ends the game. In this version, the game master draws $m$ balls before anyone may shout Bingo!, even if a player already has a full line. When the $m$ -th ball is drawn, all players shout Bingo! at the same time. Find every player who has all the numbers marked in at least one row, column, or diagonal after the $m$ draws.

Input

The first line contains the integer $n$ ( $1 \le n \le 50$ ), the number of players. Then $n$ groups of six lines follow. The first line of each group is the player name, a string of at most $20$ lowercase English letters. No two players have the same name. The next five lines each contain five integers between $1$ and $90$ , describing the board. All integers on a board are distinct. The next line contains the integer $m$ ( $1 \le m \le 90$ ), the number of balls drawn. The next line contains $m$ integers between $1$ and $90$ , the drawn numbers in order. Each number is drawn at most once.

Output

On the first line, print $k$ , the number of players who have Bingo! after $m$ draws. Then print the names of those $k$ players, one per line, in the same order as they appear in the input.

Examples3

Example 1

Input

3
babylasagna
10 11 12 13 14
15 16 17 18 19
20 21 22 23 24
25 26 27 28 29
30 31 32 33 34
nataliebalmix
10 20 30 40 50
11 21 31 41 51
12 22 32 42 52
13 23 33 43 53
14 24 34 44 54
lettri
89 88 87 86 10
85 84 83 11 82
81 80 12 79 78
77 13 76 75 74
14 73 72 71 70
6
10 11 12 13 14 15

Expected output

3
babylasagna
nataliebalmix
lettri

Example 2

Input

1
honi
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25
4
1 2 49 50

Expected output

Example 3

Input

4
rim
15 23 14 26 34
12 11 13 16 17
90 67 45 24 18
85 82 77 66 22
62 71 32 35 7
tim
61 89 25 63 12
29 30 31 32 33
11 17 42 24 18
88 82 77 66 22
44 71 54 35 7
dagi
15 23 14 26 34
12 11 13 16 17
90 67 45 24 18
85 82 77 66 22
62 71 36 35 7
dim
15 23 14 26 34
12 11 13 16 17
90 67 45 24 18
85 82 77 66 22
42 51 32 33 7
7
15 11 66 7 42 30 61

Expected output

1
tim