\begin{problem}{Пицца-марафон}{pizza.in}{pizza.out}{5 секунды}{512 мегабайт}

%Автор задачи: Алексей Цыпленков
%Автор условия: Алексей Цыпленков

Устав от тяжелых трудовых будней подземных супергероев, черепашки-ниндзя решили взять отпуск.
А как лучше всего можно провести свободное время, если вы зеленого цвета и носите на спине панцирь?
Конечно устроив недельный пицца-марафон!

У черепашек есть меню их любимой пиццерии. В нем записано название каждой пиццы и ее стоимость.
При этом, что интересно, размер пиццы совпадает с длиной ее названия. Поскольку некоторые пиццы 
черепашки уже пробовали, то заказы они делают следующим образом: выбирают пиццу, которая им понравилась
и заказывают все, похожие на нее, размером не меньше некоторого числа $k$. Считается, что пицца $i$ похожа на
пиццу $j$, если ее название $s_i$ является префиксом названия $j$-й пиццы $s_j$. Так как сами черепашки не могут
свободно передвигаться по городу, они попросили Эйприл сообщать им об изменениях в работе пиццерии,
в частности, об изменении цен на пиццы. 

В течение всей недели Донателло, которому было поручено следить за количеством потраченных на пиццу
денег, делал в своем блокноте записи о заказах пиццы и изменениях цен. Когда же в конце недели он решил
посчитать стоимость всех заказов, он обнаружил, что их оказалось невероятно много, поэтому он попросил вас 
помочь с этой задачей.

\InputFile
В первой строке входного файла записано два целых числа $n$ и $m$ $(1 \le n \le 10^6, 1 \le m \le 10^6)$
~--- число пицц в меню и число заметок в блокноте. В следующих $n$ строк содержится описание меню пиццерии:
в $i$-й строке через пробел записаны название $i$-й пиццы $s_i$ и ее начальная стоимость $c_i$ $(0 < c_i \le 10^9)$.
Названия пицц состоят только их малых латинских букв. Гарантируется, что суммарная длина всех строк не превышает $10^6$.
Гарантируется, что все названия пицц различны.

В следующих $m$ строках находятся записи из блокнота Донателло в следующем формате: 
\begin{itemize}
\item \texttt{"? i k"}~--- черепашки заказали пиццы, похожие на $i$-ю и размером не меньше $k$ $(1 \le i \le n, 1 \le k \le 10^6)$.
\item \texttt{"! i j"}~--- Эйприл принесла сообщение, что стоимость $i$-й пиццы увеличилась на $j$ $(1 \le i \le n, |j| \le 10^9)$.
\end{itemize}

\OutputFile
Для заказа каждой пиццы в отдельной строке выведите её стоимость.	

\Examples
\begin{example}
\exmp{
2 4
margarita 20
marga 10
? 1 5
? 1 6
? 2 5
? 2 6
}{
30
20
10
0
}%
\exmp{
2 2
supreme 20
supremesuper 30
! 2 20
? 2 2
}{
70
}%
\end{example}

\Note
Решения, работающие в случае, когда $m \le 100$ и сумма длин всех строк не превышает $10^5$, будут оцениваться в $30$ баллов.

Решения, работающие в случае, когда $m \le 10000$ и максимальная длина строк не превышает $10^4$, будут оцениваться в $60$ баллов.

\end{problem}