+ محدودیت زمان: ۴ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت + روز ۲ دوره ۳۰ ---------- «شرکت تولیدی دبّه‌ی آقای موز و دوستان» معروف به «شتدآمود» یکی از خوش‌نام‌ترین کارخانه‌های دبّه‌سازی است که همه ساله روز قبل از امتحانات عملی، از دبّه‌های جدیدش رونمایی می‌کند. آقای موز اخیرا تصمیم گرفته کارخانه‌ی جدیدی در زمینه‌ی تولید رشته‌ها احداث کند. او می‌خواهد تا پیش از پایان امتحانات عملی رشته‌هایی بسازد و به دانش‌پژوهان هدیه دهد. منظور از رشته، دنباله‌ای متشکّل از حروف کوچک انگلیسی است. در ابتدا آقای موز باید به مغازه‌ی رشته‌فروشی برود و تعدادی رشته بخرد؛ سپس این رشته‌ها را به کارگرانش بدهد. کارگران کارخانه‌ی رشته‌سازی، می‌توانند پسوندی از هر رشته را حذف کنند و سپس رشته‌های باقی‌مانده را با ترتیب دلخواه پشت سر هم قرار دهند. در نهایت رشته‌ی حاصل را داخل کوره‌ی رشته‌پزی می‌گذارند تا این قطعات به یکدیگر متّصل شوند. دقّت کنید پسوندهایی که حذف می‌شوند می‌توانند تهی هم باشند، یعنی هیچ قسمتی از رشته حذف نشود. مثلا اگر آقای موز دو رشته‌ی tanin، یک رشته‌ی qosxyz و یک رشته‌ی ehtemal به کارگرانش بدهد، آن‌ها می‌توانند با حذف پسوندی از هر رشته، چهار رشته‌ی qos، tan، tani و eh را بسازند و با پشت سر هم قرار دادن آن‌ها رشته‌ی qostantanieh را تولید کنند. در مغازه‌ی رشته فروشی $n$ نوع رشته و از هر نوع رشته به تعداد نامحدود وجود دارد. این رشته‌ها را با $t_1, t_2, \cdots, 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$ آمده است که نشان‌دهنده‌ی بازه‌ی مربوط به هر دانش‌پژوه است. $$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$ است. # خروجی خروجی می‌بایست متشکّل از $m$ خط باشد. در $i$امین خط، کم‌ترین هزینه‌ای که برای تولید رشته‌ی مربوط به دانش‌پژوه $i$ام نیاز است را چاپ کنید. هم‌چنین اگر این کار ممکن نیست، $-1$ چاپ کنید. # زیرمسئله‌ها | زیرمسئله | نمره | محدودیت |:------------------:|:----------:|:------------------:| | ۱ | ۲۵ | $L \le 500$ | | ۲ | ۲۵ | $m \le 10$ | | ۳ | ۵۰ | بدون محدودیت اضافی | # مثال ## ورودی نمونه ۱ ``` 3 13 ab ac aef abaaceaef 0 1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0 9 1 2 6 9 5 9 4 9 ``` ## خروجی نمونه ۱ ``` 1 1 2 3 3 -1 -1 -1 -1 -1 1 -1 -1 ```