Playlists#518

Playlists

... Peut-être qu'une légende cool apparaîtra ici très bientôt ...

Vous avez playlists. Chaque playlist est une liste de chansons. Chaque chanson a sa note. En d'autres termes, la playlist s_i est une liste de chansons \left[ s_{i,1}, s_{i,2}, \dots, s_{i,k_i} \right], où k_i est la longueur de la liste.

Vous voulez écouter les playlists dans un certain ordre. Supposons que vous écoutez les playlists dans l'ordre de s_1, s_2, \dots, s_n. Alors les chansons seront une liste \left[ s_{1,1}, s_{1,2}, \dots, s_{1, k_1}, s_{2, 1}, s_{2,2}, \dots, s_{n, k_n} \right].

Disons qu'une liste de chansons \left[ a_1, a_2, \dots, a_k \right] est "géniale" si et seulement si a_i > \sum_{j < i} a_j pour tout 1 \le i \le k, c'est-à-dire, chaque chanson a une note plus élevée que toutes les chansons précédentes combinées.

Veuillez trouver le plus long préfixe "génial" parmi tous les ordres de playlists.

Input

La première ligne contient un entier (1 \le n \le 10^3) — le nombre de playlists.

Les lignes suivantes définissent les playlists.

La -ème ligne contient un entier k_i (1 \le k_i \le 10^6) — le nombre de chansons dans la playlist .

La ligne (2i + 1) contient k_i entiers s_{i, 1}, s_{i, 2}, \dots, s_{i, k_i} (0 \le s_{i, j} \le 10^9, s_{i,j} = 2^t pour un certain ) — les notes des chansons dans la playlist.

Il est garanti que \sum_{i=1}^{n} k_i \le 10^6.

Output

Dans la première ligne, imprimez un entier — la longueur du plus long préfixe "génial".

Dans la deuxième ligne, imprimez entiers — l'ordre des playlists qui atteint ce résultat.

S'il y a plusieurs ordres possibles, imprimez-en un.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Note

Dans le premier exemple, avec l'ordre (1, 2, 3), les chansons sont [1, 4, 8, 32] :

  • 1 > 0,,

  • 4 > 1,,

  • 8 > 1 + 4 = 5,,

  • 32 > 1 + 4 + 8 = 13,.

Les quatre chansons satisfont la condition, donc le préfixe génial a une longueur de . Aucun autre ordre des trois playlists n'atteint un préfixe génial plus long.

Dans le deuxième exemple, avec l'ordre (2, 1, 4, 3), les chansons sont [1, 2, 4, 8, 128, 256, 2] :

  • 1 > 0,

  • 2 > 1,

  • 4 > 1 + 2 = 3,

  • 8 > 1 + 2 + 4 = 7,

  • 128 > 1 + 2 + 4 + 8 = 15,

  • 256 > 1 + 2 + 4 + 8 + 128 = 143,

  • 2 \not> 1 + 2 + 4 + 8 + 128 + 256 = 399.

Le préfixe génial a une longueur de 

Scoring

  1. ( points) n \le 3;

  2. ( points) n \le 8;

  3. ( points) k_i = 1;

  4. ( points) s_{i,j} < 32;

  5. ( points) aucune restriction supplémentaire.