אתם מעיינים באוסף מקוון של $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.