«شرکت تولیدی دبّه‌ی آقای موز و دوستان» معروف به «شتدآمود» یکی از خوش‌نام‌ترین کارخانه‌های دبّه‌سازی است که همه ساله روز قبل از امتحانات عملی، از دبّه‌های جدیدش رونمایی می‌کند.

آقای موز اخیرا تصمیم گرفته کارخانه‌ی جدیدی در زمینه‌ی تولید رشته‌ها احداث کند. او می‌خواهد تا پیش از پایان امتحانات عملی رشته‌هایی بسازد و به دانش‌پژوهان هدیه دهد.

منظور از رشته، دنباله‌ای متشکّل از حروف کوچک انگلیسی است.

در ابتدا آقای موز باید به مغازه‌ی رشته‌فروشی برود و تعدادی رشته بخرد؛ سپس این رشته‌ها را به کارگرانش بدهد. کارگران کارخانه‌ی رشته‌سازی، می‌توانند پسوندی از هر رشته را حذف کنند و سپس رشته‌های باقی‌مانده را با ترتیب دلخواه پشت سر هم قرار دهند. در نهایت رشته‌ی حاصل را داخل کوره‌ی رشته‌پزی می‌گذارند تا این قطعات به یکدیگر متّصل شوند. دقّت کنید پسوندهایی که حذف می‌شوند می‌توانند تهی هم باشند، یعنی هیچ قسمتی از رشته حذف نشود.

مثلا اگر آقای موز دو رشته‌ی tanin، یک رشته‌ی qosxyz و یک رشته‌ی ehtemal به کارگرانش بدهد، آن‌ها می‌توانند با حذف پسوندی از هر رشته، چهار رشته‌ی qos، tan، tani و eh را بسازند و با پشت سر هم قرار دادن آن‌ها رشته‌ی qostantanieh را تولید کنند.

در مغازه‌ی رشته فروشی $n$ نوع رشته و از هر نوع رشته به تعداد نامحدود وجود دارد. این رشته‌ها را با $t_1, t_2, ....., t_n$ نمایش می‌دهیم. هزینه‌ی خرید هر یک از این رشته‌ها هم $1$ ریال است.

هم‌چنین در دوره‌ی تابستانه(پاییزه؟) $m$ دانش‌پژوه وجود دارند؛ آقای موز رشته‌ی بزرگی(به طول $L$) به نام $S$ دارد و به ازای $m$ زیررشته از $S$ که با $[l_i, r_i)$ مشخّص می‌شوند($1 \le i \le m$)، می‌خواهد رشته‌ای برابر با آن زیررشته تولید کند و به دانش‌پژوه $i$ام هدیه دهد. دقّت کنید حروف هر رشته به طول $L$ از چپ به راست با اعداد $0$ تا $L - 1$ شماره‌گذاری می‌شوند و زیررشته‌ی $[l, r)$ نشان‌دهنده‌ی زیررشته‌ای است که از کنار هم قرار دادن حروف $l$ تا $r - 1$ آن رشته(به ترتیب) ایجاد می‌شود.

به آقای موز بگویید که کم‌ترین هزینه‌ی مورد نیاز برای تامین هدیه‌ی هر دانش‌پژوه چند ریال است.

در خط اول ورودی دو عدد $n$ و $m$ آمده است که به ترتیب تعداد رشته‌های داخل رشته‌فروشی و تعداد دانش‌پژوهان دوره‌ی تابستانه است.

در خط $i$ام از $n$ خط بعد، رشته‌ی $t_i$ آمده است. این رشته‌ها، رشته‌های موجود در مغازه‌ی رشته‌فروشی هستند.

پس از آن نیز رشته‌ی $S$ آمده است.

در خط $i$ام از $m$ خط بعد نیز دو عدد $l_i$ و $r_i$ آمده است که نشان‌دهنده‌ی بازه‌ی مربوط به هر دانش‌پژوه است.

خروجی می‌بایست متشکّل از $m$ خط باشد. در $i$امین خط، کم‌ترین هزینه‌ای که برای تولید رشته‌ی مربوط به دانش‌پژوه $i$ام نیاز است را چاپ کنید. هم‌چنین اگر این کار ممکن نیست، $-1$ چاپ کنید.

• زیرمسئله اول (۲۵ نمره): $L \le 500$
• زیرمسئله دوم (۲۵ نمره): $m \le 10$
• زیرمسئله سوم (۵۰ نمره): بدون محدودیت اضافی

• محدودیت زمان: ۴ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت
• $1 \le L, m \le 300\ 000$
• $1 \le n \le 10\ 000$
• $0 \le l_i < r_i \le L$
• مجموع طول $t_i$ ها نیز حداکثر $500\ 000$ است.

• سوال بعد