Problem
کازوما با سه همراه سفر می کند: آکوا، مگومین و تاریکی. اما هزینه سفر پرداخت نمی شود، بنابراین تیم ما باید وظایف محول شده توسط انجمن ماجراجو را انجام دهد.
کازوما قبلاً n کار را برای تکمیل انتخاب کرده است. با این حال، هر زمان که یک تیم با نیروی کامل کاری را انجام می دهد، اتفاقات غیرقابل پیش بینی و پوچ رخ می دهد. به همین دلیل کازوما تصمیم گرفت که برای هر یک از وظایف، دقیقاً دو همراه داشته باشد.
نسبت هر یک از همراهان به کازوما با یک عدد صحیح مشخص می شود. در ابتدا، نگرش هر یک از آنها خنثی و برابر با 0 است. در روند تکمیل کار، نگرش دخترانی که او این وظیفه را بر عهده می گیرد نسبت به او در جهت مثبت یا منفی تغییر می کند (یا ممکن است اصلاً تغییر نکند) .
برای هر یک از وظایف، کازوما می داند که چگونه نگرش هر دختر نسبت به او پس از اتمام کار تغییر می کند. او می خواهد در تکالیف همراهی کند تا پس از انجام همه آنها، نگرش همه دختران نسبت به او برابر شود. اگر می توان از راه های مختلف به این امر دست یافت، البته لازم است که این رابطه تا حد امکان خوب باشد.
به کازوما کمک کنید تا بفهمد برابرترین رفتاری که می تواند با همه دختران داشته باشد چیست.
ورودی:
خط اول شامل یک عدد صحیح مثبت n (1 ≤ n ≤ 25) — تعداد کارهایی که باید تکمیل شوند.
n خط بعدی حاوی توضیحات — خط i-ام شامل سه عدد a
i، m
i، d
i — اگر قهرمان آنها را با خود همراه کند تا کار i-ام را انجام دهد، به ترتیب نگرش آکوا، مگومین یا تاریکی نسبت به کازوما تغییر می کند.
همه اعداد در ورودی اعداد صحیح هستند و در مقدار مطلق از 10
7 تجاوز نمی کنند.
خروجی:
اگر راه حلی وجود ندارد، "غیر ممکن" را در خط اول چاپ کنید.
در غیر این صورت رابطه ای که همه دخترها با کازوما خواهند داشت را چاپ کنید و در عین حال حداکثر ممکن را چاپ کنید.
مثال:
<بدن>
| ورودی |
خروجی |
3
1 0 0
0 1 0
0 0 1
| 1 |
7
0 8 9
5 9 -2
6-8-7
9 4 5
-4 -9 9
-4 5 2
-6 8 -7
| 5 |
2
1 0 0
1 1 0
| غیر ممکن |