قوائم التشغيل#518

قوائم التشغيل

ثانيتان
512 ميغابايت
Hard

... ربما تظهر أسطورة رائعة هنا في أي وقت قريب ...

لديك قوائم تشغيل. كل قائمة تشغيل هي قائمة من الأغاني. كل أغنية لها تقييمها. بعبارة أخرى، قائمة التشغيل 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، أي، كل أغنية لها تقييم أكبر من جميع الأغاني السابقة مجتمعة.

يرجى العثور على أطول "بادئة رائعة" بين جميع ترتيبات قوائم التشغيل.

Input

السطر الأول يحتوي على عدد صحيح واحد (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.

Output

في السطر الأول، اطبع عدد صحيح واحد — طول أطول "بادئة رائعة".

في السطر الثاني، اطبع عدد صحيح — ترتيب قوائم التشغيل الذي يحقق هذه النتيجة.

إذا كان هناك عدة ترتيبات ممكنة، اطبع أي منها.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Note

في المثال الأول، مع الترتيب (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.

البادئة الرائعة لها طول 

Scoring

  1. ( نقاط) n \le 3;

  2. ( نقاط) n \le 8;

  3. ( نقاط) k_i = 1;

  4. ( نقاط) s_{i,j} < 32;

  5. ( نقاط) لا قيود إضافية.