피자 마라톤

지하에서 하는 고된 일에 지친 닌자 거북이들은 휴가를 가기로 했다. 초록색이고 등에 껍질을 진 그들이 자유 시간을 보내기에 일주일짜리 피자 마라톤만큼 좋은 방법이 있을까?

거북이들은 단골 피자집의 메뉴를 가지고 있다. 메뉴에는 피자마다 이름과 가격이 적혀 있다. 피자의 크기는 이름의 길이와 같다. 거북이들은 이미 먹어 본 피자가 있다. 주문할 때는 마음에 든 피자 하나를 고르고, 그와 비슷하면서 크기가 $k$ 이상인 피자를 모두 주문한다. 피자 $i$가 피자 $j$와 비슷하다는 것은 $s_i$가 $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$).

각 주문마다 주문 금액을 한 줄에 하나씩 출력한다.