A counter starts at \(x\). Apply a sequence of commands: + v adds \(v\), - v subtracts \(v\), and * v multiplies by \(v\).

Input

The first line contains integers \(x\) and \(q\). Each of the next \(q\) lines contains an operator and an integer \(v\).

The input satisfies:

• \(0 <= q <= 10^4\)
• \(|x|,|v| <= 10^9\)

Output

Print the counter value after every command, one value per line. If \(q=0\), print an empty output.

Example

Input

19 4
- -4
+ -3
+ 1
* -3

Output

23
20
21
-63