This is the hard version of the problem. The difference between the versions is that in this version, the time limit and the constraints on (n) and (q) are higher. You can hack only if you solved all versions of this problem. Gellyfish has an array consisting of (n) sets. Initially, all the sets are empty. Now Gellyfish will do (q) operations. Each operation contains one modification operation and one query operation, for the (i)-th ((1 \leq i \leq q)) operation: First, there will be a modification operation, which is one of the following: Insert operation: You are given an integer (r). For the (1)-th to (r)-th sets, insert element (i). Note that the element inserted here is (i), the index of the operation, not the index of the set. Reverse operation: You are given an integer (r). Reverse the (1)-th to (r)-th sets. Delete operation: You are given an integer (x). Delete element (x) from all sets that contain (x). Followed by a query operation: Query operation: You are given an integer (p). Output the smallest element in the (p)-th set (If the (p)-th set is empty, the answer is considered to be (0)). Now, Flower needs to provide the answer for each query operation. Please help her! Additional constraint on the problem : Gellyfish will only give the next operation after Flower has answered the previous query operation. That is, you need to solve this problem online . Please refer to the input format for more details. The first line contains two integers (n) and (q) ((1 \leq n, q \leq 3 \cdot 10^5)) — the number of the sets and the number of operations. As you need to respond to the operations online, the operations will be encoded. The (i)-th line of the following (q) lines contains three integers (a), (b), and (c) ((1 \leq a \leq 3), (1 \leq c \leq n)) — describing the (i)-th operation in an encoded form. Here, (a) represents th