This is the hard version of the problem. The only difference between the two versions is the set of allowed values for the initial array and for (x) in operations of type (1). In this version, these values can be any integers in (-10^9, 10^9). You can make hacks only if both versions of the problem are solved. Before her final sortie, Chtholly asks Willem three questions. The second is this: what will remain if the sky truly reaches its end? Willem cannot answer her directly. Instead, he opens a chronicle containing (n) records, numbered from (1) to (n). Each record holds an integer: a positive value represents hope, while a negative value represents despair. The initial contents of the chronicle form an array (a_1,a_2,\ldots,a_n), called version (0). Chtholly then performs (q) operations. For each (1\le i\le q), the (i)-th operation creates a new version (i) from version (i-1). Each operation has one of the following four types: (1 l r x): set (a_k\gets x) for every (l\le k\le r). (2 l r): set (a_k\gets -a_k) for every (l\le k\le r). (3 l r): set (a_k\gets\max(a_k,0)) for every (l\le k\le r). (4 p): consider the value at position (p) in every previous version (0,1,\ldots, i-1). Let these values be (b_0,b_1,\ldots,b_{i-1}). Find the maximum sum over all non-empty subarrays(^{\text{∗}}) of this sequence. If the operation is of type (1), (2), or (3), the specified modification is applied to version (i-1) to obtain version (i). An operation of type (4) does not modify the array, so version (i) is identical to version (i-1). The operations are encoded and must be processed in order. Their decoding depends on (\mathrm{lastans}), which is updated after every operation of type (4). Help Willem answer every operation of type (4). (^{\text{∗}})An array (c) is a subarray