Пицца-марафон

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

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

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

В первой строке входного файла записано два целых числа $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$ строках находятся записи из блокнота Донателло в следующем формате:

• "? i k" --- черепашки заказали пиццы, похожие на $i$-ю и размером не меньше $k$ $(1 \le i \le n, 1 \le k \le 10^6)$.
• "! i j" --- Эйприл принесла сообщение, что стоимость $i$-й пиццы увеличилась на $j$ $(1 \le i \le n, |j| \le 10^9)$.

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