Playlists#518

Playlists

... Yəqin ki, burada hər an bəzi maraqlı əfsanə görünə bilər ...

Sizin ədəd playlistiniz var. Hər bir playlist mahnıların siyahısıdır. Hər bir mahnının öz reytinqi var. Başqa sözlə, playlist s_i mahnıların siyahısıdır \left[ s_{i,1}, s_{i,2}, \dots, s_{i,k_i} \right], burada k_i siyahının uzunluğudur.

Siz playlistləri müəyyən bir sırada dinləmək istəyirsiniz. Tutaq ki, siz playlistləri s_1, s_2, \dots, s_n sırasına görə dinləyirsiniz. Onda mahnılar aşağıdakı siyahı olacaq \left[ s_{1,1}, s_{1,2}, \dots, s_{1, k_1}, s_{2, 1}, s_{2,2}, \dots, s_{n, k_n} \right].

Gəlin deyək ki, mahnılar siyahısı \left[ a_1, a_2, \dots, a_k \right] yalnız o zaman "böyük"dir ki, a_i > \sum_{j < i} a_j bütün 1 \le i \le k üçün, yəni, hər bir mahnının reytinqi əvvəlki bütün mahnıların cəmdən daha böyükdür.

Zəhmət olmasa, bütün playlistlərin sıralamaları arasında ən uzun "böyük" prefiksi tapın.

Input

İlk sətir tək bir tam ədəd (1 \le n \le 10^3) — playlistlərin sayı.

Sonrakı sətir playlistləri müəyyən edir.

-ci sətir tək bir tam ədəd k_i (1 \le k_i \le 10^6) — playlist -dəki mahnıların sayı.

(2i + 1)-ci sətir k_i tam ədədini s_{i, 1}, s_{i, 2}, \dots, s_{i, k_i} (0 \le s_{i, j} \le 10^9, s_{i,j} = 2^t bəzi üçün) — playlistdəki mahnıların reytinqlərini ehtiva edir.

Zəmanət verilir ki, \sum_{i=1}^{n} k_i \le 10^6.

Output

İlk sətirdə, ən uzun "böyük" prefiksin uzunluğunu tək bir tam ədəd olaraq çap edin.

İkinci sətirdə, belə bir nəticəni əldə edən tam ədədini çap edin — playlistlərin sırası.

Əgər bir neçə mümkün sıralama varsa, istənilənini çap edin.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Note

İlk nümunədə, (1, 2, 3) sırası ilə mahnılar [1, 4, 8, 32]-dir:

  • 1 > 0,,

  • 4 > 1,,

  • 8 > 1 + 4 = 5,,

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

Dörd mahnı da şərti ödəyir, beləliklə, böyük prefiksin uzunluğu -dür. Üç playlistin başqa heç bir sıralaması daha uzun böyük prefiks əldə etmir.

İkinci nümunədə, (2, 1, 4, 3) sırası ilə mahnılar [1, 2, 4, 8, 128, 256, 2]-dir:

  • 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.

Böyük prefiksin uzunluğu -dır

Scoring

  1. ( bal) n \le 3;

  2. ( bal) n \le 8;

  3. ( bal) k_i = 1;

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

  5. ( bal) əlavə məhdudiyyət yoxdur.