Pizza Marathon

Tired of the hard work underground, the Ninja Turtles decided to take a vacation. How better to spend free time when you are green and carry a shell on your back? A week-long pizza marathon, of course!

The turtles have the menu of their favorite pizzeria. Each pizza has a name and a price. The size of a pizza equals the length of its name. Some pizzas the turtles have already tried. To order, they pick a pizza they liked and order all pizzas similar to it with size at least $k$. Pizza $i$ is similar to pizza $j$ if $s_i$ is a prefix of $s_j$.

The turtles cannot travel around the city themselves, so they asked April to report changes at the pizzeria, in particular changes in prices.

During the week, Donatello wrote down pizza orders and price changes in his notebook. At the end of the week he tried to total all orders, found there were too many, and asked you to help.

The first line contains two integers $n$ and $m$ ($1 \le n \le 10^6$, $1 \le m \le 10^6$), the number of pizzas on the menu and the number of notes in the notebook. The next $n$ lines describe the menu: the $i$-th line contains the name $s_i$ and the initial price $c_i$ ($0 < c_i \le 10^9$) of the $i$-th pizza, separated by a space. Names consist only of lowercase Latin letters. The total length of all names does not exceed $10^6$. All names are distinct.

The next $m$ lines contain Donatello's notes in one of the following formats:

• "? i k": the turtles ordered pizzas similar to the $i$-th pizza with size at least $k$ ($1 \le i \le n$, $1 \le k \le 10^6$).
• "! i j": April reported that the price of the $i$-th pizza increased by $j$ ($1 \le i \le n$, $|j| \le 10^9$).

For each order, print its total cost on a separate line.