컴퓨터 해킹

마일즈와 피터는 평행 우주에서 알케맥스 연구소의 비밀 데이터가 담긴 컴퓨터를 훔쳤다. 지금 마일즈는 그 내용을 살펴보고 있다. 그는 터미널에서 <<SuperSecretData>> 디렉터리를 열었다. 이 디렉터리에서는 파일이 저절로 생겼다가 사라지는 경우가 있다. 모든 파일 이름은 소문자 라틴 문자로만 이루어진다.

어떤 시점에 마일즈는 그 순간 디렉터리에 있는 파일 하나의 이름을 입력하는 데 필요한 키 입력 횟수의 최솟값을 알고 싶어 한다. 처음에 터미널에는 빈 문자열이 입력되어 있다. 마일즈는 소문자 라틴 문자 키를 누를 수 있고, 누른 문자는 문자열 끝에 덧붙는다. 또 tab 키를 누를 수 있다. tab 키를 누르면 다음 문자를 한 가지로 정할 수 있는 동안 문자열 끝에 문자가 계속 덧붙는다. 즉 터미널에 문자열 $s$가 있고, 이름이 $s\overline{c}$로 시작하는 파일의 집합이 이름이 $s$로 시작하는 파일의 집합과 같은 문자 $c$가 존재하면, $c$가 $s$의 끝에 덧붙는다. 여기서 $s\overline{c}$는 $s$ 뒤에 $c$를 이은 것을 뜻한다.

예를 들어 디렉터리에 passwords와 paroli 파일이 있고 터미널이 비어 있을 때 tab 키를 누르면 터미널에 pa가 나타난다. tab 키를 한 번 더 눌러도 문자열은 바뀌지 않는다. 이어서 s를 누르면 pas가 된다. 그다음 tab 키를 누르면 passwords가 된다.

마일즈의 질문에 답하라.

첫 줄에 질의의 개수 $q$ ($1 \le q \le 100\,000$)가 주어진다. 이어지는 $q$개의 줄에는 질의가 하나씩 주어진다. 각 질의는 질의 종류를 나타내는 문자 하나로 시작한다.

문자가 +이면 디렉터리에 새 파일이 생긴다는 뜻이고, 같은 줄에 파일 이름 $s_i$ ($1 \le |s_i| \le 100\,000$)가 주어진다.

문자가 -이면 디렉터리에서 파일을 삭제한다는 뜻이고, 같은 줄에 파일 번호 $a_i$ ($1 \le a_i$)가 주어진다. 파일은 등장한 순서대로 1부터 번호가 매겨진다.

문자가 ?이면 마일즈가 파일 이름을 입력하는 데 필요한 버튼 수의 최솟값을 묻는다는 뜻이고, 같은 줄에 그가 묻는 파일의 번호 $a_i$ ($1 \le a_i$)가 주어진다. 파일은 등장한 순서대로 1부터 번호가 매겨진다.

모든 $s_i$의 길이의 합은 $10^6$을 넘지 않는다. 한 시점에 디렉터리에 같은 이름의 파일이 두 개 있는 경우는 없다. 각 파일은 최대 한 번만 삭제된다. 세 번째 종류의 질의가 주어질 때 해당 파일은 이미 추가되었고 아직 삭제되지 않았다. 두 번째와 세 번째 종류의 질의에 주어지는 파일 번호는 그 시점까지 추가된 파일 개수를 넘지 않는다.

세 번째 종류의 질의마다 답을 한 줄에 하나씩 출력한다.