Background

Translated from COCI 2023/2024 Contest #4 T1 “Bingo”.

Problem Description

It is time to play Bingo.

To play Bingo, you need a game host and a drum containing 90 balls. The balls in the drum are numbered from $1$ to $90$, and each number is written on exactly one ball.

Before the game starts, the host gives each of the $n$ players a $5 \times 5$ board. Each cell contains an integer from $1$ to $90$. All numbers on a single board are distinct, and all players’ boards are different from each other.

After all players receive their boards, the game begins.

The host starts drawing balls from the drum. After drawing the ball numbered $x_i$, the host announces the number to all players and puts the ball aside. All players check their boards, and if the drawn number appears on their board, they cross it out.

When a player has crossed out all 5 numbers in a row, a column, the main diagonal, or the anti-diagonal, that player will shout Bingo!. At that moment, the game ends and that player wins.

To make the game more interesting, the host decides to add an extra rule. Before anyone is allowed to shout Bingo!, the host will first draw $m$ balls. (Even if a player has already crossed out 5 in a line, they must wait until $m$ balls have been drawn before they can shout Bingo!.)

However, at the instant the host draws the $m$-th ball, a commotion breaks out. All players shout Bingo!.

The host does not know whom to believe. To resolve this situation, he asks you for help. Compute how many players can shout Bingo! after $m$ balls have been drawn.

Input Format

The first line contains an integer $n$ ($1 \le n \le 50$), the number of players.

Then follow $n \times 6$ lines:

• The first line contains a string of length at most $20$, consisting only of lowercase English letters, the player’s name. No two players have the same name.
• The next $5$ lines each contain $5$ integers in the range $1$ to $90$, describing the player’s board. All numbers on each board are distinct.

The next line contains an integer $m$ ($1 \le m \le 90$), the number of balls the host will draw.

The next line contains $m$ integers in the range $1$ to $90$, the numbers of the balls drawn from the drum. Each number appears at most once.

Output Format

On the first line output an integer $k$, the number of players who can shout Bingo!.

Then output $k$ lines with their names, in the same order as in the 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

3
babylasagna
nataliebalmix
lettri

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

0

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

1
tim

Hint

Sample Explanation 1

babylasagna achieves Bingo! on the first row.

nataliebalmix achieves Bingo! on the first column.

lettri achieves Bingo! on the anti-diagonal from bottom-left to top-right.

Sample Explanation 2

Only 4 balls were drawn, so nobody can cross out 5 numbers.

Subtasks

Translated by ChatGPT 5