27524번 - 점수 내기

문제

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

어떤 문자열 $A$의 점수는,

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

을 더한 값이다. 각 list에 조건을 만족하는 문자열이 없다면 0ドル$점으로 간주하여 계산한다. 또한 내기는 각 list가 비어있는 상태로 시작한다.

내기의 재미를 위해 prefix list와 suffix list가 계속 바뀌기 때문에, 아멜과 니나는 매 순간 어떤 문자열을 만들어야 가장 유리할지 헷갈리기 시작했다.

아멜과 니나를 도와 아래와 같은 쿼리를 수행해주자.

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

list의 모든 문자열은 항상 알파벳 소문자로만 구성되어 있지만, 아멜과 니나는 알파벳 소문자뿐만 아니라 숫자도 사용할 수 있음에 유의하자.

입력

첫째 줄에 쿼리의 개수 $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이다.