트라이
처음에는 등록된 단어가 없다.
$Q$개의 쿼리를 순서대로 처리하라.
쿼리는 다음 두 종류 중 하나이다.
1 S: 단어 $S$를 등록한다.2 P: 지금까지 등록한 단어 중 문자열 $P$로 시작하는 단어의 개수를 출력한다.
같은 단어를 여러 번 등록할 수 있으며, 각각을 별개의 단어로 센다.
입력
첫 번째 줄에 쿼리의 개수 $Q$가 주어진다. $(1 \leq Q \leq 200\,000)$
두 번째 줄부터 $Q$개의 줄에 걸쳐 쿼리가 하나씩 주어진다.
각 문자열은 알파벳 소문자로만 이루어져 있다.
입력으로 주어지는 모든 문자열의 길이 합은 $1\,000\,000$ 이하이다.
출력
2 P 쿼리마다 지금까지 등록한 단어 중 문자열 $P$로 시작하는 단어의 개수를 한 줄에 하나씩 출력한다.
예제 입력 1
9 1 apple 1 app 2 app 1 apply 1 banana 2 a 2 apple 2 ban 2 cat
예제 출력 1
2 3 1 1 0
예제 입력 2
6 1 abc 1 abc 1 ab 2 abc 2 ab 2 a
예제 출력 2
2 3 3