Everything Map

모든 문자열에 값을 매핑하면서도 탐색을 충분히 빠르게 할 수 있을까?

모든 문자열을 정수에 대응하는 맵 $M$과 빈 문자열 $S$를 가지고 있다. 처음에 $M$은 모든 문자열을 $0$에 대응하고 있다.

다음 $5$종류의 쿼리를 수행하는 프로그램을 작성하라.

• 1 $c$: $S$ 뒤에 문자 $c$를 추가한다. $c$는 알파벳 소문자만 주어진다.
• 2: $S$의 맨 뒤에서 $1$개의 문자를 지운다. $S$가 빈 문자열인 경우 아무 일도 하지 않는다.
• 3 $x$: $M[S]$에 $x$를 더한다. $(-10\,000 \le x \le 10\,000)$
• 4: $M[S]$를 출력한다.
• 5: $S$ 뒤에 $S$를 추가한다.

첫째 줄에 쿼리의 수 $Q$가 주어진다. $(1 \le Q \le 2 \times 10^{5})$

둘째 줄부터 $Q$개의 줄에 걸쳐 쿼리가 한 줄에 하나씩 주어진다.

4번 쿼리는 하나 이상 주어진다.

$4$번 쿼리가 주어질 때마다 $M[S]$를 출력하라.