| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 5 초 | 1024 MB | 14 | 4 | 2 | 16.667% |
Устав от тяжелых трудовых будней подземных супергероев, черепашки-ниндзя решили взять отпуск. А как лучше всего можно провести свободное время, если вы зеленого цвета и носите на спине панцирь? Конечно устроив недельный пицца-марафон!
У черепашек есть меню их любимой пиццерии. В нем записано название каждой пиццы и ее стоимость. При этом, что интересно, размер пиццы совпадает с длиной ее названия. Поскольку некоторые пиццы черепашки уже пробовали, то заказы они делают следующим образом: выбирают пиццу, которая им понравилась и заказывают все, похожие на нее, размером не меньше некоторого числа $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)$.Для заказа каждой пиццы в отдельной строке выведите её стоимость.
2 4 margarita 20 marga 10 ? 1 5 ? 1 6 ? 2 5 ? 2 6
30 20 10 0
2 2 supreme 20 supremesuper 30 ! 2 20 ? 2 2
70