أنت تتصفح مجموعة على الإنترنت من $n$ عناصر مرقمة من $1$ إلى $n$ ومرتبة على دائرة. العنصر الواقع يمين كل عنصر $i$ هو العنصر $i+1$، والعنصر الواقع يمين العنصر $n$ هو العنصر $1$. وبالمثل، العنصر الواقع يسار كل عنصر $i$ هو العنصر $i-1$، والعنصر الواقع يسار العنصر $1$ هو العنصر $n$.

للعناصر $m$ معلمات مرقمة من $1$ إلى $m$. قيمة المعلمة $j$ للعنصر $i$ هي عدد صحيح $a_{i,j}$.

أثناء التصفح، يوجد في كل لحظة مؤشر يشير إلى عنصر ما، يُسمى العنصر الحالي.

كذلك يمكنك إدارة مجموعة من شروط التصفية. كل شرط هو زوج $(j,v)$ يعني أن المعلمة رقم $j$ للعنصر يجب أن تساوي $v$. يحقق العنصر الحالي دائمًا جميع الشروط في المجموعة.

لتصفح المجموعة، يمكنك إجراء عمليات. يجب أن تكون كل عملية من أحد الأنواع الأربعة التالية:

• النقر على «يمين». ينتقل المؤشر إلى أقرب عنصر يمين العنصر الحالي يحقق جميع شروط التصفية. وعلى وجه الخصوص، إذا كان العنصر الحالي هو العنصر الوحيد الذي يحققها، فلا يتحرك المؤشر.

• النقر على «يسار». وبالمثل، ينتقل المؤشر إلى أقرب عنصر يسار العنصر الحالي يحقق جميع شروط التصفية، ويبقى في مكانه إذا كان العنصر الحالي هو العنصر الوحيد الذي يحققها.

• إضافة شرط تصفية جديد $(j,v)$ لعددين صحيحين $j$ و$v$. إذا حقق العنصر الحالي هذا الشرط، فلا يتحرك المؤشر. وإلا، ينتقل إلى أقرب عنصر يمين العنصر الحالي يحقق جميع شروط التصفية، بما فيها الشرط الجديد. إذا لم يوجد عنصر كهذا، فالعملية غير مسموحة ولا يمكن إجراؤها.

• إزالة أي شرط تصفية $(j,v)$ من المجموعة. لا يتحرك المؤشر.

لكل زوج مرتب من العناصر $(i,j)$، أجب عن السؤال التالي:

• إذا بدأت التصفح والمؤشر يشير إلى العنصر $i$ ولا توجد شروط تصفية في المجموعة، فما أقل عدد من العمليات تحتاجه لنقل المؤشر إلى العنصر $j$؟ يمكن أن تكون مجموعة شروط التصفية كيفما كانت في النهاية.

الإدخال

يحتوي السطر الأول على عددين صحيحين $n$ و$m$ يمثلان عدد عناصر المجموعة وعدد معلمات كل عنصر ($2\le n\le500$; $1\le m\le5$).

يحتوي السطر رقم $i$ من الأسطر الـ$n$ التالية على $m$ أعداد صحيحة $a_{i,1},a_{i,2},\ldots,a_{i,m}$ تمثل قيم معلمات العنصر $i$ ($1\le a_{i,j}\le n$).

الإخراج

اطبع $n$ أسطر يحتوي كل منها على $n$ أعداد صحيحة.

يجب أن يساوي العدد الصحيح رقم $j$ في السطر رقم $i$ أقل عدد من العمليات اللازمة لنقل المؤشر من العنصر $i$ إلى العنصر $j$، بدءًا بمجموعة فارغة من شروط التصفية.

أمثلة

الإدخال 1

9 3
5 3 7
5 3 4
5 3 7
5 3 2
5 3 4
5 3 7
2 3 7
5 3 7
2 3 7

الإخراج 1

0 1 2 1 2 3 1 2 1
1 0 1 1 2 2 1 3 2
2 1 0 1 1 2 1 3 2
3 2 1 0 1 1 1 3 2
3 2 2 1 0 1 1 3 2
3 1 2 1 1 0 1 2 2
2 1 3 1 2 1 0 1 2
2 1 3 1 2 2 1 0 1
1 1 3 1 2 3 2 1 0

ملاحظة

في الاختبار المثال، إحدى أسرع الطرق الممكنة للانتقال من العنصر 2 إلى العنصر 5 هي:

• أضف شرط تصفية جديدًا $(3,4)$. بما أن قيمة المعلمة 3 للعنصر 2 تساوي 4 بالفعل، يبقى المؤشر عند العنصر 2.

• انقر على «يمين». ينتقل المؤشر إلى أقرب عنصر يمين العنصر 2 يحقق الشرط الفعال الوحيد $(3,4)$. هذا هو العنصر 5. (النقر على «يسار» بدلًا من ذلك ينجح أيضًا.)

إحدى أسرع الطرق الممكنة للانتقال من العنصر 8 إلى العنصر 3 هي:

• أضف شرط تصفية جديدًا $(3,4)$. بما أن العنصر 8 لا يحقق هذا الشرط، ينتقل المؤشر إلى أقرب عنصر يمين العنصر 8 تكون قيمة معلمته 3 مساوية لـ4. هذا هو العنصر 2.

• أزل شرط التصفية $(3,4)$. يبقى المؤشر عند العنصر 2.

• انقر على «يمين». بما أنه لا توجد شروط تصفية في المجموعة، ينتقل المؤشر إلى العنصر 3.