... Być może wkrótce pojawi się tutaj jakaś fajna legenda ...
Masz playlist. Każda playlista to lista piosenek. Każda piosenka ma swoją ocenę. Innymi słowy, playlista s_i to lista piosenek \left[ s_{i,1}, s_{i,2}, \dots, s_{i,k_i} \right], gdzie k_i to długość listy.
Chcesz słuchać playlist w pewnej kolejności. Załóż, że słuchasz playlist w kolejności s_1, s_2, \dots, s_n. Wtedy piosenki będą listą \left[ s_{1,1}, s_{1,2}, \dots, s_{1, k_1}, s_{2, 1}, s_{2,2}, \dots, s_{n, k_n} \right].
Mówimy, że lista piosenek \left[ a_1, a_2, \dots, a_k \right] jest świetna, jeśli a_i > \sum_{j < i} a_j dla wszystkich 1 \le i \le k, tzn. każda piosenka ma wyższą ocenę niż wszystkie poprzednie piosenki razem wzięte.
Twoim zadaniem jest znaleźć najdłuższy możliwy świetny prefiks wśród wszystkich uporządkowań playlist.
Pierwsza linia zawiera jedną liczbę całkowitą (1 \le n \le 10^3) — liczba playlist.
Następne linie definiują playlisty.
Linia zawiera jedną liczbę całkowitą k_i (1 \le k_i \le 10^6) — liczbę piosenek w playliście .
Linia (2i + 1) zawiera k_i liczb całkowitych s_{i, 1}, s_{i, 2}, \dots, s_{i, k_i} (0 \le s_{i, j} \le 10^9, s_{i,j} = 2^t dla pewnego ) — oceny piosenek w playliście.
Gwarantuje się, że \sum_{i=1}^{n} k_i \le 10^6.
W pierwszej linii wypisz jedną liczbę całkowitą — długość najdłuższego świetnego prefiksu.
W drugiej linii wypisz liczb całkowitych — kolejność playlist, która osiąga taki wynik.
Jeśli istnieje kilka możliwych kolejności, wypisz dowolną.
Przykład 1
Przykład 2
W pierwszym przykładzie, przy kolejności (1, 2, 3) piosenki to [1, 4, 8, 32]:
1 > 0,,
4 > 1,,
8 > 1 + 4 = 5,,
32 > 1 + 4 + 8 = 13,.
Wszystkie cztery piosenki spełniają warunek, więc świetny prefiks ma długość . Żadne inne uporządkowanie trzech playlist nie osiąga dłuższego świetnego prefiksu.
W drugim przykładzie, przy kolejności (2, 1, 4, 3) piosenki to [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.
Świetny prefiks ma długość .
( punktów) n \le 3;
( punktów) n \le 8;
( punktów) k_i = 1;
( punktów) s_{i,j} < 32;
( punktów) brak dodatkowych ograniczeń.