33158번 - 자동 완성

경인이는 파일 검색 프로그램의 자동 완성 기능을 개발하고 있다. 당연하게도 경인이는 당신에게 구현을 맡겼다!

$N$개의 파일은 이름을 나타내는 서로 다른 문자열 $S_i$와 중요도를 나타내는 정수 $W_i$로 표현된다. 이제 다음과 같은 $Q$개의 사용자 입력을 순서대로 처리해야 한다.

• $T$ $D$: 문자열 $T$로 자동 완성할 수 있는 파일 중 가장 중요도가 높은 것을 찾고 그 중요도에 정수 $D$를 더한다. 즉, $T$를 접두사로 갖는 $S_i$ 중 $W_i$가 가장 높은 $i$를 출력하고 그 $W_i$에 $D$를 더한다. 만약 그러한 파일이 여러 개라면 $i$가 가장 작은 파일을 선택한다. 조건을 만족하는 파일이 없다면 -1을 출력하고 아무것도 하지 않는다.

경인이를 도와 자동 완성 기능을 구현해 보자.

첫 번째 줄에 파일의 개수 $N$과 사용자 입력의 개수 $Q$가 공백으로 구분되어 주어진다. $(1 \le N, Q \le 200\,000)$

두 번째 줄부터 $N$개의 줄에 걸쳐 $i$번째 줄에 파일 $i$의 이름인 문자열 $S_i$와 중요도인 정수 $W_i$가 공백으로 구분되어 주어진다. $\left(1 \le \sum_{i=1}^N|S_i| \le 200\,000; |W_i| \le 10^8 \right)$

다음 줄부터 $Q$개의 줄에 걸쳐 사용자 입력인 문자열 $T$와 정수 $D$가 공백으로 구분되어 주어진다. $\left(1 \le \sum_{j=1}^Q|T_j| \le 200\,000; |D_j| \le 10^8\right)$

주어지는 모든 문자열은 알파벳 대소문자로만 구성된다. 대소문자가 다른 알파벳은 다른 글자이다.

각 사용자 입력의 결과를 $Q$개의 줄에 걸쳐 출력한다.