Bingo P36031

Statement

Un cartón de bingo contiene 15 números del 1 al 99, ordenados en 3 filas de 5 números cada una, sin que el mismo número aparezca más de una vez. Los jugadores van tachando los números de su cartón a medida que estos salen del bombo. Se premia al primer jugador que tacha todos los números de una de las tres líneas de su cartón (“ ‘!Han cantado línea!’’) y al primero que tacha el cartón entero (“ ‘!Han cantado bingo!’’). Si varios jugadores cantan línea o bingo a la vez el premio se reparte equitativamente.

En este problema se te da el orden en el que saldrán las 99 bolas del bombo, y se te pida que descubras cuáles de los cartones en juego te interesaría haber comprado, asumiendo que el precio del cartón es de 10 euros y que los premios por cantar línea y bingo son 17 y 28 euros respectivamente. En concreto, deberás resolver varias situaciones parecidas: el orden de salida de las bolas será siempre el mismo, pero en cada situación sólo habrá en juego un cierto subconjunto de los $k$ cartones distintos que tiene la compañía que organiza la partida.

Entrada

La entrada consiste en una línea con el número $k$ de cartones, con $1<k<100$ . A continuación, y separados por líneas en blanco, se dan los $k$ cartones, los 15 números de cada cartón separados por espacios y distribuidos en 3 líneas de 5.

Le sigue en una línea el número $q$ de situaciones distintas, con $1\le q\le 10000$ . Una situación viene definida por el subconjunto de tamaño $n$ de los $k$ cartones que entran en juego, y viene descrita por el número $n$ ( $1\le n \le k$ ) y los índices $i_1, \ldots, i_n$ , entre $1$ y $k$ , de los $n$ cartones distintos que participan en la situación, todos ellos ocupando la misma línea y separados por espacios. Finalmente, separado por una línea en blanco, se dan los 99 números del bombo en el orden en que salen, separados por espacios y cambiando de línea cada 10 números.

Se te pide que resuelvas 5 entradas como las descritas en menos de 1 segundo.

Salida

Escribe $q$ líneas, una por situación. Cada línea contiene la lista ordenada de aquellos cartones que han entrado en juego en la situación y que convendría haber comprado, o sea, aquellos que recibirán un premio superior a 10 euros. Debes escribir estos índices en orden creciente y separados por espacios. Deja una línea en blanco en caso de no haber ningún cartón rentable.

Public test cases

Input

5

1 2 3 4 97
5 6 7 8 98
9 10 11 12 99

1 2 3 4 97
15 6 7 8 98
9 10 11 12 99

1 2 3 4 97
25 6 7 8 98
9 10 11 12 99

1 2 3 4 97
35 6 7 8 98
9 10 11 12 99

1 2 3 4 97
45 6 7 8 98
9 10 11 12 99

5
1 1
2 1 2
5 1 2 3 4 5
3 1 2 3
4 1 2 3 4

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 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
81 82 83 84 85 86 87 88 89 90
91 92 93 94 95 96 97 98 99

Output

Input

5

3 18 35 61 68
4 24 41 64 75
12 30 49 66 82

24 35 60 82 93
29 39 65 86 97
34 48 66 87 99

7 31 38 68 83
12 33 46 75 87
23 34 57 79 97

11 19 45 51 74
15 23 49 55 94
16 42 50 66 99

2 17 28 46 66
7 19 37 49 83
16 23 39 64 96

7
1 3
2 5 4
3 3 1 2
2 4 3
4 3 5 4 1
5 1 2 3 4 5
4 1 4 2 3

6 48 97 8 19 66 49 42 95 11
93 51 79 40 7 47 80 26 37 44
86 89 25 72 17 31 15 58 76 57
46 5 61 62 1 4 23 30 55 2
9 90 64 56 12 91 24 45 21 39
99 75 83 32 29 78 59 16 22 13
94 84 77 27 33 85 81 53 69 60
28 68 67 73 87 70 35 10 43 52
63 36 65 38 3 14 50 92 34 96
18 20 71 74 54 41 88 98 82

Output

Information

Author: Omer Giménez
Language: Spanish
Other languages: English
Official solutions: C++
User solutions: C++