Tima חזר ממסעו ל-Xorland והביא איתו מערך של $n$ מספרים שלמים. Xorland היא מדינה קטנה הידועה במאכלים שלה, במוזיקה שלה ובמשחקים על מערכים. מאפיין מיוחד של המשחקים ב-Xorland הוא שאין מנצח: החברות תמיד מנצחת! אחד המשחקים האלה הוא ״Xor-Mat״.

כללי ״Xor-Mat״ פשוטים. לפני תחילת המשחק, שני השחקנים בוחרים מערך $a$ ומספר שלם $k$. לאחר מכן השחקן הראשון צובע כל מספר במערך באחד מ-$k$ צבעים. נסמן ב-$c_i$ את צבעו של המספר ה-$i$ במערך, כאשר הצבעים ממוספרים מ-$1$ עד $k$. לאחר מכן השחקן השני בוחר זוג אינדקסים $(i,j)$ כך ש-$i\ne j$ ו-$c_i=c_j$.

מטרתו של השחקן הראשון היא למקסם את $a_i\oplus a_j$, ואילו השחקן השני מנסה למזער את $a_i\oplus a_j$. כאן $\oplus$ היא פעולת XOR על סיביות.

Mansur הזמין את Tima למשחק ״Xor-Mat״. הם משחקים על המערך של Tima. Mansur הוא השחקן הראשון ו-Tima הוא השני. הדפיסו את ערך הביטוי $a_i\oplus a_j$ כאשר שני השחקנים משחקים באופן מיטבי. מצאו גם צביעה מיטבית של המערך ש-Mansur עשוי לבחור.

קלט

השורה הראשונה מכילה מספר שלם אחד $t$ ($1\le t\le5\cdot10^4$), מספר מקרי הבדיקה.

לאחר מכן מופיעות $2\cdot t$ שורות בתבנית הבאה:

השורה הראשונה של כל מקרה בדיקה מכילה שני מספרים שלמים $n$ ($2\le n\le5\cdot10^4$) ו-$k$ ($1\le k\le\min(n-1,50)$).

השורה השנייה של כל מקרה בדיקה מכילה $n$ מספרים שלמים $a_1,a_2,\ldots,a_n$ ($1\le a_i\le10^9$), המערך של Tima.

מובטח שסכום ערכי $n$ בכל מקרי הבדיקה אינו עולה על $5\cdot10^4$.

פלט

לכל מקרה בדיקה בקלט הדפיסו שתי שורות:

• בשורה הראשונה הדפיסו את ערך הביטוי $a_i\oplus a_j$ כאשר שני השחקנים משחקים באופן מיטבי.
• בשורה השנייה הדפיסו $n$ מספרים שלמים $c_1,c_2,\ldots,c_n$ ($1\le c_i\le k$), כאשר $c_i$ הוא הצבע ש-Mansur בוחר למספר ה-$i$ במערך. אם קיימת יותר מדרך אחת לצבוע את המערך באופן מיטבי, אפשר להדפיס כל אחת מהן.

ניקוד

נסמן ב-$S$ את סכום ערכי $n$ בכל מקרי הבדיקה.

דוגמאות

קלט 1

2
3 1
1 2 3
3 2
1 2 3

פלט 1

1
1 1 1
3
1 1 2