Atharva is currently in an interview. He has memorized a list of statements that he is prepared to say during the interview. The interviewer is marking him by points. He starts the interview with one point. Every statement he says affects his points in some way – as a function of his current points. Find a way to maximize the amount of points he gets in the interview.
The statements change his points in one of three ways (as a function of p-number of points):
1.+c
where the new number of points is \(p + c\)
2.^c
where the new number of points is
3.*c
where the new number of points is
Input Specification
The first line contains , the number of statements that Atharva has prepared.
The next lines contain a statement in the form stated above, describing how the statement affects the points.
\(1 \le S \le 10^5\)
\(0 \le c \le 10^9\) (whole number)
Output Specification
On the first line, output the number of statements he should say.
On the second line, output a number of indices (0-indexed), representing the order Atharva should say the statements so that he can maximize his points.
If there are multiple ways to do this, pick the way with the least number of statements and the least lexicographical order.
Sample Input 1
3
+0
^1
*1
Sample Output 1
0
Sample Input 2
3
^2
+5
*3
Sample Output 2
3
1 2 0
Explanation for Sample Outputs
For the first sample, no matter what Atharva says, his points stay at .
For the second sample Atharva can achieve a maximum score of \(2^{3 \times (1+5)} = 262144\).
Comments