The Safe Secret

A nineteenth century duke built a room for his valuables and chose the code of its safe in an unusual way. He was so afraid of being robbed that he told nobody the code. He only wrote down how to obtain it, on a sheet of paper meant for his heir after his death. The paper read:

1. Look at the inner side of the dukedom ring, which is now yours.
2. Starting at the number closest to the ruby, copy the numbers and the symbols in clockwise order, leaving out the last symbol. That is the first sequence. Start at the next number and do the same, and you get the second sequence. Repeat until you have started at every number once.
3. For each sequence, do the following.
   1. Replace every ? by +, - or *. Do that in all possible ways to get several arithmetic expressions.
   2. Evaluate each expression. The sums, the differences and the products may be performed in any order. Do that in all possible orders to get several values.
   3. Take the minimum and the maximum of those values.
   4. Write the digits of the minimum and append to them the digits of the maximum. Do not write the sign. That is the code of the sequence.
4. Concatenate the codes in the order the sequences were obtained. That string of digits is the safe secret.

The ring carries $k$ numbers and $k$ symbols engraved in a circle, in the order $n_1$, $s_1$, $n_2$, $s_2$, ..., $n_k$, $s_k$. The number closest to the ruby is $n_1$. The $r$-th sequence reads $2k-1$ elements clockwise starting at $n_r$, so it holds $k$ numbers and the $k-1$ symbols between them, and the last symbol is left out.

The symbol choices and the evaluation order are decided separately for each sequence, and each ? may take a different symbol. The operators keep their positions, and only the order of evaluation changes. For instance 1 - 5 + 0 * -2 - -3 gives 11 when it is evaluated as ((((1 - 5) + 0) * -2) - -3), and it gives -4 when it is evaluated as (1 - (5 + (0 * (-2 - -3)))).

If the minimum of a sequence is -4 and the maximum is 11, the code of that sequence is 411, because the sign of a negative value is dropped and only its digits are written.

Given the numbers and the symbols engraved on the ring, find the safe secret.

The first line has one positive integer $k$, the number of (number, symbol) pairs that form the ring.

The second line has $2k$ elements $n_1$, $s_1$, $n_2$, $s_2$, ..., $n_k$, $s_k$, separated by single spaces. Each $n_i$ is a number and each $s_i$ is +, -, * or ?.

Print the safe secret on a single line.

• $2 \le k \le 200$
• $-9 \le n_i \le 9$
• Every value produced by the process above fits in a signed 64 bit integer.