\documentclass[12pt]{article}
\input{structure.tex}
\renewcommand{\bottomtitlespace}{2cm}

\begin{document}

\renewcommand{\tl}{$2$ сек.}
\renewcommand{\ml}{$1024$ MB}

\problem{Задача T4. РЕЧНИК}
\addauthor{Автор: Александър Гатев}{2026}{02}{01}
\renewcommand{\header}{
	ЗИМНИ СЪСТЕЗАНИЯ ПО ИНФОРМАТИКА\\
	``Д-р Младен Манев"\\
	Габрово, 31 януари 2026 г.\\
	Група T (отборен формат)
}

\begin{wrapfigure}{r}{0.28\textwidth}
	\begin{adjustbox}{width=0.28\textwidth}
		\includegraphics{job_image}
	\end{adjustbox}
\end{wrapfigure}

Анди е безработен студент от първи курс, който се е решил твърдо да си намери стаж за лятото. За да е конкурентно способен на пазара, той използва AI applier, с който да изпрати CV-то си на горилион компании, докато не получи някоя оферта. Оставяйки резюмето му да обикаля света, Анди се захваща с изрешаването на LeetCode задачи, за да научи всеки алгоритъм, който може да му се падне на интервю. Както знаем, такъв процес изисква доста енергия, а ястията в столовата му не са най-евтините (но все пак единствения му шанс за незамразена храна). За да припечели малко, Анди реши да предложи една от скорошните си задачи на зимните състезания, а тя е както следва:

Даден е речник съставен от $N$ думи $W_1,\ W_2,\ ...\ W_N$, състоящи се по някаква причина само от главните латински букви \texttt{$\{$A,C,G,U$\}$}. Освен това има и $Q$ въпроса за речника от следния вид:
\newline
\begin{itemize}
    \item По дадени два низа $P_i$ и $S_i$ се търси броят на думите, за които първите $|P|$ букви съвпадат с $P$, а последните $|S|$ букви с $S\ $ (тук с $|A|$ бележим дължината на низа $A$).
\end{itemize}

Напишете програма \textbf{\texttt{dictionary}}, която да отговаря на тези въпроси.

\subsection{Вход}
От първия ред на стандартния вход се въвеждат естествените числа $N$ и $Q$ -- броят думи и броят заявки. На следващите $N$ реда се въвежда $N$-те думи $W_1, W_2, ... W_N$. От последните $Q$ реда се въвеждат двойки низове $P_i$, $S_i$, описващи поредния въпрос.

\subsection{Изход}
На $Q$ отделни реда изведете по едно цяло число -- търсения брой думи.

\subsection{Ограничения}
\vspace{0.1em}
\begin{itemize}
	\item $1 \leq N, Q \leq 10^5$
	\item $1 \leq |W_i|, |P_i|, |S_i| \leq 10^5$
	\item $ |W_1| + |W_2| + \dots + |W_N| \leq Sum$
    \item $ |P_1| + |P_2| + \dots + |P_Q| \leq Sum$
    \item $ |S_1| + |S_2| + \dots + |S_Q| \leq Sum$
    \item Тук $Sum = 2\times 10^6$
	\item Всички низове са съставени само от буквите \texttt{$\{$A,C,G,U$\}$}.
\end{itemize}

\subsection{Подзадачи}
\begin{table}[H]
	\begin{tblr}{|Q[c,m]|Q[c,m]|Q[c,m]|Q[c,m]|Q[c,m]|}
		\hline
		\textbf{Подзадача} & \textbf{Точки} & \textbf{Необходими подзадачи} & $N,Q$ & \textbf{Други ограничения} \\
		\hline
		$1$ & $10$ & $-$ & $\leq 100$ & $|W_i|, |P_i|, |S_i| \leq 100$ \\ 
		\hline
		$2$ & $25$ & $1$ & $\leq 5000$ & $-$ \\ 
        \hline	
        $3$ & $25$ & $1$ & $\leq 10^5$ & $Sum = 10^5$ \\
        \hline
        $4$ & $40$ & $1-3$ & $\leq 10^5$ & $-$ \\ 
        \hline	
	\end{tblr}
	\caption*{Точките за дадена подзадача се получават само ако се преминат успешно всички тестове, предвидени за нея.}
\end{table}
\FloatBarrier

\subsection{Примери}
\begin{table}[H]
	\begin{tblr}{|l|l|X[j]|}
    
    		\hline
    		\textbf{Вход} & \textbf{Изход} & \textbf{Обяснение на примера} \\
    		\hline
    		\texttt{\makecell[lt]{2 3 \\AUGC \\AGC \\G C \\AU C \\A C}}
    		& 
    		\texttt{\makecell[lt]{0 \\1 \\2}}
    		& 
            {Първа заявка - $\{\}$.\\
            Втора заявка - \{\texttt{AUGC}\}.\\
            Трета заявка - \{\texttt{AUGC}, \texttt{AGC}\}.} \\
    		\hline
            \texttt{\makecell[lt]{3 3 \\AA \\AA \\ AGA \\AA AA \\AG GA \\AG GA}}
       		& 
       		\texttt{\makecell[lt]{2 \\1 \\1}}
       		& 
       		{ } \\
       		\hline
            \texttt{\makecell[lt]{8 7 \\GCGCUACCCCAACACAAGGCAAGAUAUA \\G \\GGAC \\GCGG \\U \\GCGCUACCCCAACACAAGGCAAGAUGGUC \\GCCG \\GCGCUGA \\GCGCUACCC A \\GCGCUACCCC AC \\GCG C \\GCGC A \\G G \\G C \\G GGA}}
       		& 
       		\texttt{\makecell[lt]{1 \\0 \\1 \\2 \\3 \\2 \\0}}
       		& 
       		{ } \\
       		\hline

	\end{tblr}
\end{table}
\FloatBarrier
	
\end{document}