+ محدودیت زمان: ۲.۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- باباشله‌پز قصد دارد قصر یشم را به آش‌فروشی تبدیل کند! از آنجا که قصر یشم حدود هزار پله دارد او می‌خواهد تا جای ممکن بار کمتری را بر دوش پسرش پو بیندازد. بنابرین تصمیم به فشرده‌سازی آش‌های خود می‌گیرید. هر آش از تعدادی رشته تشکیل شده‌است و هر رشته نیز دنباله‌ای از حروف کوچک انگلیسی است. حال رشته $B$ را می‌توان به انتهای رشته $A$ وصل کرد اگر حرف آخر $A$ برابر با حرف اول $B$ باشد. توجه کنید طول رشته حاصل از اضافه کردن $B$ به $A$ **یکی کمتر** از طول مجموعه آن‌ها قبل از اتصال است. مثلاً می‌توانیم ‍`amazing` را به `quera` اضافه کنیم تا `queramazing` به‌دست آید.  طول هر رشته برابر تعداد حروف آن و طول هر آش برابر مجموع طول رشته‌های آن است. پو از شما کمک می‌خواهد. # ورودی در سطر اول $t$ یا تعداد آش‌ها می‌آید. سپس در خطوط بعد اطلاعات $t$ آش داده می‌شود. $$ 1 \le t \le 100 \, 000$$ در سطر اول آش $i$ام $r_i$ یا تعداد رشته‌های آش $i$ام می‌آید. $$ 1 \le |s_{i,j}| \le 1000 \, 000$$ سپس در سطر $j$ام از $r_i$ سطر بعد $s_{i,j}$ رشته $j$ام آش $i$ام می‌آید. $$ \sum_{i, j} |s_{i,j}| \le 1000 \, 000 $$ # خروجی در $t$ خط کمینه اندازه هر آش پس از فشرده‌سازی را به ترتیب خروجی دهید. # مثال ## ورودی نمونه ۱ ``` 3 2 shifoo oogvey 4 quera math quantum amazing 3 abc cba a ``` ## خروجی نمونه ۱ ``` 11 21 5 ``` در آش اول می‌توان `oogvey` را به انتها `shifoo` اضافه کرد تا به `shifooogvey` با طول ۱۱ رسید. راه دیگری برای اتصال آن‌ها نیست و اگر دو رشته از هم جدا باشند هم مجموع طولشان ۱۲ است. در آش سوم می‌توان ابتدا `abc` را به انتهای `a` اضافه کرد تا `abc` بدست آید و سپس `cba` را به انتها `abc` اضافه کرد تا `abcba` به طول ۵ بدست آید. می‌توان نشان داد آشی با طول کمتر نمی‌توان ساخت.

حل سؤال در بانک سؤالات