... Можливо, незабаром тут з'явиться якась крута легенда ...
У вас є плейлістів. Кожен плейліст — це список пісень. Кожна пісня має свій рейтинг. Іншими словами, плейлист s_i — це список пісень \left[ s_{i,1}, s_{i,2}, \dots, s_{i,k_i} \right], де k_i — це довжина списку.
Ви хочете слухати плейлісти в певному порядку. Припустимо, ви слухаєте плейлісти в порядку s_1, s_2, \dots, s_n. Тоді пісні будуть у списку \left[ s_{1,1}, s_{1,2}, \dots, s_{1, k_1}, s_{2, 1}, s_{2,2}, \dots, s_{n, k_n} \right].
Скажемо, що список пісень \left[ a_1, a_2, \dots, a_k \right] є «чудовим», якщо і тільки якщо a_i > \sum_{j < i} a_j для всіх 1 \le i \le k, тобто кожна пісня має більший рейтинг, ніж усі попередні пісні в сумі.
Будь ласка, знайдіть найдовший «чудовий» префікс серед усіх порядків плейлістів.
Перший рядок містить єдине ціле число (1 \le n \le 10^3) — кількість плейлістів.
Наступні рядків визначають плейлісти.
-ий рядок містить єдине ціле число k_i (1 \le k_i \le 10^6) — кількість пісень у плейлісті .
(2i + 1)-ий рядок містить k_i цілих чисел s_{i, 1}, s_{i, 2}, \dots, s_{i, k_i} (0 \le s_{i, j} \le 10^9, s_{i,j} = 2^t для деякого ) — рейтинги пісень у плейлісті.
Гарантується, що \sum_{i=1}^{n} k_i \le 10^6.
У першому рядку виведіть єдине ціле число — довжину найдовшого «чудового» префікса.
У другому рядку виведіть цілих чисел — порядок плейлістів, який досягає такого результату.
Якщо є кілька можливих порядків, виведіть будь-який.
Приклад 1
Приклад 2
У першому прикладі, з порядком (1, 2, 3) пісні є [1, 4, 8, 32]:
1 > 0,,
4 > 1,,
8 > 1 + 4 = 5,,
32 > 1 + 4 + 8 = 13,.
Усі чотири пісні задовольняють умову, тому чудовий префікс має довжину . Жоден інший порядок трьох плейлістів не досягає довшого чудового префікса.
У другому прикладі, з порядком (2, 1, 4, 3) пісні є [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.
Чудовий префікс має довжину
( балів) n \le 3;
( балів) n \le 8;
( балів) k_i = 1;
( балів) s_{i,j} < 32;
( балів) без додаткових обмежень.