یک برج هانوی از 3 میله و $n$ دیسک با اندازه‌های $1…n$ تشکیل شده است. یک حالت معتبر از هانوی عبارت‌است از قرار گرفتن دیسک‌ها روی میله‌های مختلف به‌طوری که هیچ دیسکی روی دیسکی کوچک‌تر از خودش قرار نگیرد. یک حرکت معتبر یعنی حرکت دادن بالاترین دیسک یک میله به یک میله‌ی دیگر بطوری که حالت اولیه و حالت تولید شده هر دو معتبر باشند.

$k$ حالت معتبر با شماره‌های $1…k$ داده شده است. می‌خواهیم ببینیم اگر بخواهیم حالت ۱ را با کم‌ترین حرکت به حالت $k$ تبدیل کنیم در حین تبدیل کدام‌یک از حالت‌های دیگر تولید می‌شوند. فرض کنید هر حرکت ۱ ثانیه طول می‌کشد. برنامه‌ی شما باید شماره‌ی حالت‌هایی که تولید می‌شوند را به ترتیب زمان تولید بنویسید.

در ورودی در خط اول اعداد $n$ و $k$ ‌($1 \leq n,k \leq 150$) آمده است. سپس در $k$ سطر در هر سطر $n$ عدد آمده است. اگر $x$، عدد $i$ام از سطر $j$ ام این اعداد باشد($1 \leq x \leq 3$ و $1 \leq i \leq n$ و $1 \leq j \leq k$) به این معنی است که در حالت $j$ دیسک شماره‌ی $i$ در میله‌ی $x$ام قرار دارد.

به ترتیب زمان تولید، شماره‌ی حالت‌هایی را که در حین تبدیل حالت ۱ به حالت $k$ تولید می‌شوند بنویسید.

• محدودیت زمان: ۵ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

• سوال بعد
• سوال قبل