هذه مسألة ذات تشغيلين. سيُشغَّل حلّك مرتين في كل اختبار.

تدرس Алеся وБорис التشفير في درس المعلوماتية. وقد قرّرا ابتكار طريقتهما الخاصة لتشفير الرسائل.

تختار Алеся عددًا قدره $k$ من الأعداد الصحيحة المختلفة من $1$ إلى $n$، وتسمّي المجموعة الناتجة $T$. تريد Алеся إرسال المجموعة $T$ إلى Борис كرسالة مشفّرة. ولهذا، ستبني Алеся انطلاقًا من المجموعة $T$ مجموعة أخرى $R$، تتكوّن أيضًا من أعداد صحيحة من $1$ إلى $n$، وترسلها إلى Борис.

لا يريد الاثنان أن يتغيّر حجم الرسالة بعد التشفير، ولذلك يجب أن تحتوي $R$ أيضًا على $k$ أعداد بالضبط. كما يعتقدان أنه إذا احتوت $T$ و$R$ على عنصر مشترك واحد على الأقل، فلن يكون تشفيرهما آمنًا بما يكفي. لذلك يجب ألا يوجد عدد ينتمي إلى كلٍّ من $T$ و$R$، أي يجب ألا تتقاطع المجموعتان $T$ و$R$. من المضمون أن $k \le n/2$، ولذلك يمكن دائمًا بناء مجموعة واحدة على الأقل $R$ انطلاقًا من المجموعة $T$.

عندما يتلقّى Борис الرسالة المشفّرة $R$، يجب أن يفكّ تشفيرها ويحصل على الرسالة الأصلية $T$.

ساعد Алеся وБорис على ابتكار خوارزميتي التشفير وفكّ التشفير وتنفيذهما. في التشغيل الأول سيؤدّي برنامجك دور Алеся، وفي التشغيل الثاني سيؤدّي دور Борис.

الإدخال

يحتوي السطر الأول من الإدخال على عدد واحد $a$ يساوي $1$ أو $2$، وهو رقم تشغيل برنامجك.

يحتوي السطر الثاني على عدد واحد $m$، وهو عدد الرسائل ($1 \le m \le 300\,000$) التي يجب على برنامجك تشفيرها (في التشغيل الأول) أو فكّ تشفيرها (في التشغيل الثاني).

تحتوي الأسطر التالية وعددها $2m$ على أوصاف $m$ رسائل، بواقع سطرين لكل رسالة.

يحتوي السطر الأول من وصف الرسالة على عددين صحيحين $n_i$ و$k_i$ ($2 \le n_i \le 10^9$، $1 \le k_i \le 300\,000$، $k_i \le \frac{n_i}{2}$). ويحتوي السطر الثاني على $k_i$ أعداد صحيحة مختلفة من $1$ إلى $n_i$، مرتّبة ترتيبًا تصاعديًا.

من المضمون أن مجموع جميع قيم $k_i$ في الاختبار الواحد لا يتجاوز $300\,000$.

إذا كان $a = 1$، فإن الأعداد المعطاة تمثّل الرسالة الأصلية. وإذا كان $a = 2$، فإن الأعداد المعطاة هي نتيجة تشغيل برنامجك لتشفير رسالة ما أثناء التشغيل الأول لبرنامجك.

الإخراج

يجب أن يطبع البرنامج $m$ أسطر؛ يجب أن يحتوي السطر $i$ على $k_i$ أعداد صحيحة مختلفة من $1$ إلى $n_i$، مرتّبة ترتيبًا تصاعديًا.

في التشغيل الأول، يجب على البرنامج أن يطبع، لكل رسالة أصلية $T_i$، المجموعة $R_i$ التي يجب ألا تتقاطع مع $T_i$.

في التشغيل الثاني، يجب على البرنامج أن يستعيد الرسالة الأصلية $T_i$ لكل رسالة مشفّرة $R_i$.

أمثلة

التشغيل الأول

الإدخال 1

1
2
2 1
1
5 2
1 4

الإخراج 1

2
2 3

التشغيل الثاني

الإدخال 2

2
2
5 2
2 3
2 1
2

الإخراج 2

1 4
1

ملاحظة

لاحظ أن المثال يعرض خيارات محدّدة للإخراج في التشغيل الأول وللإدخال في التشغيل الثاني. إذا طبع برنامجك مجموعة أخرى $R$، فسيكون الإدخال في التشغيل الثاني مختلفًا أيضًا.

كذلك، في التشغيل الثاني، لا تُقدَّم الرسائل المشفّرة إلى برنامج المشارك بالضرورة بالترتيب نفسه الذي وردت به في التشغيل الأول.

المهام الفرعية

لتحديد القيود الإضافية على الإدخال، نرمز إلى تسلسل الأعداد التي تحدّد المجموعة $T_i$ بالرموز $t_1, t_2, \ldots, t_{k_i}$. وهي مرتّبة ترتيبًا تصاعديًا.

نرمز إلى مجموع قيم $n_i$ في الاختبار الواحد بالرمز $N$.

نرمز إلى مجموع قيم $k_i$ في الاختبار الواحد بالرمز $K$.