점수 내기

아멜과 니나는 알파벳 소문자와 숫자 $\mathbf{0}$-$\mathbf{9}$로 만든 문자열을 가지고 점수 내기를 한다. 아멜은 가장 높은 점수를 얻을 수 있는 문자열을 만들고, 니나는 가장 낮은 점수를 얻을 수 있는 문자열을 만든다. 두 사람이 만드는 문자열의 길이는 1 이상이어야 한다.

문자열 $A$의 점수는 다음 두 값을 더한 것이다.

• prefix list에 있는 문자열 중 $A$의 prefix(접두사)인 것들의 점수 합
• suffix list에 있는 문자열 중 $A$의 suffix(접미사)인 것들의 점수 합

어느 list에 조건을 만족하는 문자열이 없으면 그 list의 값은 $0$점으로 계산한다. 두 list는 모두 빈 상태에서 시작한다.

내기 도중 prefix list와 suffix list가 계속 바뀌므로, 아멜과 니나는 매 순간 어떤 문자열을 만들어야 유리한지 헷갈린다.

아멜과 니나를 도와 아래 쿼리를 처리하자.

• < str X: prefix list에 점수 $X$를 가진 문자열 str을 추가한다. str이 이미 있으면 점수를 $X$로 바꾼다.
• > str X: suffix list에 점수 $X$를 가진 문자열 str을 추가한다. str이 이미 있으면 점수를 $X$로 바꾼다.
• +: 아멜이 얻을 수 있는 최대 점수를 출력한다.
• -: 니나가 얻을 수 있는 최소 점수를 출력한다.

첫째 줄에 쿼리의 개수 $Q$가 주어진다. ($1\le Q \le 300\,000$)

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

• $-10^9 \le X \le 10^9$, $X$는 정수이다.
• 입력에 등장하는 모든 문자열은 길이가 1 이상이며 알파벳 소문자로만 이루어져 있다. 숫자 $\mathbf{0}$부터 $\mathbf{9}$까지는 포함되지 않는다.
• 입력에 등장하는 문자열의 길이 합은 $1\,000\,000$을 넘지 않는다.
• + 또는 - 쿼리가 적어도 하나 있다.

+와 - 쿼리마다 결과를 한 줄에 하나씩 출력한다.

아래 출력의 점수를 얻는 문자열의 예시는 차례대로 abc, 111, abcd, ab123, abc이다.