Sequence Operations and Maximum Query

You are given an initial sequence of n integers, all initialized to 0. Then you will perform q operations on the sequence. After each operation, you are to output the maximum value in the sequence.

The operations are in one of the following formats:

• 1 x: Append the integer x to the end of the sequence.
• 2: Remove the last element from the sequence (if it exists).
• 3 k: Multiply every element of the sequence by k. That is, for each element a_i, update it as \(a_i = a_i \times k\).
• 4: Square every element in the sequence. That is, for each element a_i, update it as \(a_i = a_i^2\).

For example, if the initial length is 3 and the operations are as follows:

1 5
1 2
1 8
3 2
4
2
2
4

The sequence evolves as follows (starting with three 0's):

Initial: [0, 0, 0]
After "1 5": [0, 0, 0, 5]   -> max = 5
After "1 2": [0, 0, 0, 5, 2] -> max = 5
After "1 8": [0, 0, 0, 5, 2, 8] -> max = 8
After "3 2": [0, 0, 0, 10, 4, 16] -> max = 16
After "4": [0, 0, 0, 100, 16, 256] -> max = 256
After "2": [0, 0, 0, 100, 16] -> max = 100
After "2": [0, 0, 0, 100] -> max = 100
After "4": [0, 0, 0, 10000] -> max = 10000

Output the maximum value after each operation in the order the operations were applied.

inputFormat

The input is given in the following format from stdin:

 n q
 op_1
 op_2
 ...
 op_q

Where n and q are integers representing the initial length of the sequence and the number of operations, respectively. Each of the next q lines contains an operation, which can be one of the following forms: "1 x", "2", "3 k", or "4".

outputFormat

Print the resulting maximum value in the sequence after each operation to stdout. Each output value should be printed on its own line.

## sample

3 8
1 5
1 2
1 8
3 2
4
2
2
4

5
5
8
16
256
100
100
10000

</p>