This is the hard version of the problem. The difference between the two versions is the definition of deterministic max-heap, time limit, and constraints on (n) and (t). You can make hacks only if both versions of the problem are solved. Consider a perfect binary tree with size (2^n - 1), with nodes numbered from (1) to (2^n-1) and rooted at (1). For each vertex (v) ((1 \le v \le 2^{n - 1} - 1)), vertex (2v) is its left child and vertex (2v + 1) is its right child. Each node (v) also has a value (a_v) assigned to it. Define the operation (\mathrm{pop}) as follows: initialize variable (v) as (1); repeat the following process until vertex (v) is a leaf (i.e. until (2^{n - 1} \le v \le 2^n - 1)); among the children of (v), choose the one with the larger value on it and denote such vertex as (x); if the values on them are equal (i.e. (a_{2v} = a_{2v + 1})), you can choose any of them; assign (a_x) to (a_v) (i.e. (a_v := a_x)); assign (x) to (v) (i.e. (v := x)); among the children of (v), choose the one with the larger value on it and denote such vertex as (x); if the values on them are equal (i.e. (a_{2v} = a_{2v + 1})), you can choose any of them; assign (a_x) to (a_v) (i.e. (a_v := a_x)); assign (x) to (v) (i.e. (v := x)); assign (-1) to (a_v) (i.e. (a_v := -1)). Then we say the (\mathrm{pop}) operation is deterministic if there is a unique way to do such operation. In other words, (a_{2v} \neq a_{2v + 1}) would hold whenever choosing between them. A binary tree is called a max-heap if for every vertex (v) ((1 \le v \le 2^{n - 1} - 1)), both (a_v \ge a_{2v}) and (a_v \ge a_{2v + 1}) hold. A max-heap is deterministic if the (\mathrm{pop}) operation is deterministic to the heap when we do it for the first and the second time . Initially, (a_v := 0) for every vertex (v) ($$$1