금고의 비밀번호

19세기의 어느 공작은 귀중품을 보관할 방을 만들고 금고의 비밀번호를 특이한 방법으로 정했다. 도둑맞는 것을 워낙 두려워한 나머지 비밀번호를 아무에게도 말하지 않았고, 비밀번호를 얻는 방법만 종이에 적어 두었다가 세상을 떠날 때 상속자에게 넘기게 했다. 종이에는 이렇게 적혀 있었다.

1. 이제 네 것이 된 공작 반지의 안쪽 면을 보아라.
2. 루비와 가장 가까운 수부터 시계 방향으로 수와 기호를 차례로 옮겨 적되, 마지막 기호는 빼라. 이것이 첫 번째 수열이다. 다음 수에서 시작해 같은 일을 하면 두 번째 수열이 나온다. 모든 수에서 한 번씩 시작할 때까지 되풀이하라.
3. 각 수열마다 다음을 하라.
   1. 모든 ?를 +, -, * 중 하나로 바꾼다. 가능한 모든 방법으로 바꿔 여러 개의 식을 만든다.
   2. 각 식을 계산한다. 덧셈, 뺄셈, 곱셈은 어떤 순서로 해도 된다. 가능한 모든 순서로 계산해 여러 개의 값을 얻는다.
   3. 그 값 중 최솟값과 최댓값을 고른다.
   4. 최솟값의 숫자를 적고 그 뒤에 최댓값의 숫자를 이어 적는다. 부호는 적지 않는다. 이것이 그 수열의 코드다.
4. 수열을 얻은 순서대로 코드를 모두 이어 붙인다. 이 숫자열이 금고의 비밀번호다.

반지에는 수 $k$개와 기호 $k$개가 $n_1$, $s_1$, $n_2$, $s_2$, ..., $n_k$, $s_k$ 순서로 원을 이루며 새겨져 있다. 루비와 가장 가까운 수가 $n_1$이다. $r$번째 수열은 $n_r$에서 시작해 시계 방향으로 원소 $2k-1$개를 읽은 것이고, 수 $k$개와 그 사이의 기호 $k-1$개로 이루어진다. 마지막 기호는 빠진다.

기호를 고르는 방법과 계산 순서는 수열마다 따로 정한다. ?마다 다른 기호를 골라도 된다. 연산자의 자리는 그대로이고 계산하는 순서만 달라진다. 예를 들어 1 - 5 + 0 * -2 - -3을 ((((1 - 5) + 0) * -2) - -3) 순서로 계산하면 11이고, (1 - (5 + (0 * (-2 - -3)))) 순서로 계산하면 -4다.

어떤 수열의 최솟값이 -4이고 최댓값이 11이면 그 수열의 코드는 411이다. 값이 음수여도 부호는 버리고 숫자만 적기 때문이다.

반지에 새겨진 수와 기호가 주어진다. 금고의 비밀번호를 구하라.

첫째 줄에 수와 기호로 이루어진 쌍의 개수 $k$가 주어진다.

둘째 줄에 원소 $2k$개 $n_1$, $s_1$, $n_2$, $s_2$, ..., $n_k$, $s_k$가 공백 한 칸으로 구분되어 주어진다. $n_i$는 수이고, $s_i$는 +, -, *, ? 중 하나다.

첫째 줄에 금고의 비밀번호를 출력한다.

• $2 \le k \le 200$
• $-9 \le n_i \le 9$
• 위 과정으로 나오는 모든 값은 부호 있는 64비트 정수 범위에 들어간다.