+ محدودیت زمان: ۳ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- عمو اسکروچ پس از خانه تکانی برای پذیرایی از خود و جبران انرژی از دست‌رفته تصمیم به تدارک غذایی لذیذ برای شب سال نو گرفت. برای همین کتاب آشپزی خود را باز کرد. اما پس از دیدن مواد اولیه‌ی غذاها گیج شد زیرا هیچ‌کدام از آن‌ها را نمی‌شناخت. در نتیجه شروع به جست‌وجوی ‌آن‌ها در اینترنت کرد. نام کل مواد اولیه موجود در کتاب به صورت $n$ رشته‌ی $s_{1}\,,\,s_{2}\,,\,...\,,\,s_{n}\ $ است. عمو اسکروچ برای پخت غذای لذیذ خود، در $q$ مرحله مجموعه‌ی مواد اولیه‌ی انتخابی خود را به صورت زیر تغییر می‌دهد (**در ابتدا لیست مواد اولیه‌ی انتخابی خالی است**): + عدد $i$ ($1 \le i \le n$) را انتخاب می‌کند اگر $s_i$ در مجموعه‌اش بود آن را حذف و در غیر این صورت آن را اضافه می‌کند.  دکمه‌های روی کیبورد عمو اسکروچ شامل حروف کوچک انگلیسی و کلیدهای $Backspace$ و $Enter$ است. برای فشردن هر دکمه به غیر از دکمه‌ی $Enter$، یک واحد انرژی مصرف می‌شود (فشردن دکمه‌ی $Enter$ به دلیل لذت‌بخش بودن، انرژی‌ای لازم ندارد). روند جست‌وجو به این صورت است که عمو اسکروچ ترتیبی دلخواه از مواد اولیه مجموعه‌اش انتخاب کرده و هر کدام را دقیقاً یک بار جست‌وجو می‌کند، برای جست‌وجوی یک رشته باید ابتدا آن رشته را بنویسد و سپس کلید $Enter$ را فشار دهد (برای جزئیات بیشتر توضیح مثال را مشاهده کنید). از آنجا که عمو اسکروچ انرژی زیادی ندارد، از شما می‌خواهد که به او بگویید پس از هر مرحله تغییر، به ازای تمام حالات تایپ کردن مواد اولیه‌ی لیست دلخواه خود، کمترین میزان انرژی‌ای که صرف می‌کند چقدر است. # ورودی در خط اول دو عدد $n$ و $q$ آمده که نشان دهنده‌ی تعداد مواد اولیه و تعداد تغییرات است. سپس در خط $i$ اًم از $n$ خط بعدی رشته‌ی $s_i$ از حروف کوچک انگلیسی آمده است. در خط $i$ اًم از $q$ خط بعدی نیز عدد $x_i$ آمده که عدد انتخاب شده توسط عمو اسکروچ را نشان می‌دهد. $$1 \le n \le 100\ 000$$ $$1 \le q \le 200\ 000$$ $$1 \le x_i \le n$$ **تضمین می‌شود جمع طول رشته‌ها از $100\ 000$ کمتر است همچنین رشته‌های ورودی متمایزند.** # خروجی در خروجی $q$ خط چاپ کنید، به طوری که در خط $i$ اًم، پاسخ مسئله بعد از تغییر $i$ اًم باشد. # مثال ## ورودی نمونه ۱ ``` 3 5 aab ab abc 1 2 3 2 3 ``` ## خروجی نمونه ۱ ``` 3 5 7 7 3 ``` تغییر اول: مجموعه به ${aab}$ تبدیل می‌شود که برای جست‌وجوی آن به ترتیب کلیدهای زیر را فشار می‌دهیم (توجه کنید که کلید $Enter$ انرژی‌ای کم نمی‌کند): $a, a, b, Enter$ تغییر دوم: مجموعه به ${aab,ab}$ تبدیل می‌شود که برای جست‌وجوی آن به ترتیب کلیدهای زیر را فشار می‌دهیم: $a, b, Enter, Backspace, a, b, Enter$ تغییر سوم: مجموعه به ${aab,ab,abc}$ تبدیل می‌شود که برای جست‌وجوی آن به ترتیب کلیدهای زیر را فشار می‌دهیم: $a, a, b, Enter, Backspace, Backspace, b, Enter, c, Enter$ تغییر چهارم: مجموعه به ${aab,abc}$ تبدیل می‌شود که برای جست‌وجوی آن به ترتیب کلیدهای زیر را فشار می‌دهیم: $a, a, b, Enter, Backspace, Backspace, b, c, Enter$ ## ورودی نمونه ۲ ``` 4 7 aca abb baa bab 4 3 1 2 2 4 1 ``` ## خروجی نمونه ۲ ``` 3 5 11 15 11 9 3 ```

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