Mia is learning data structures, this semester. Knowing this, her boyfriend, John, gives her a difficult problem, which is about designing a new data structure.
In this problem, you are going to design a data structure which stores a sequence of elements and supports the following operations (ndenotes the total number of elements currently stored in the data structure):
Insertcelements, all of which arex, at positionp.
e.g. The original sequence is [1, 1, 2, 3]. After inserting: 1 2 3 4 (inserting 3 elements valued 4 at position 2), the sequence becomes [1,4, 4, 4, 1, 2, 3]. Now, if you insert: 1 8 1 5 (append 5 to the last modified sequence, since 8 is the position after the last element), the sequence becomes [1, 4, 4, 4, 1, 2, 3,5].
Modify the values of the longest consecutive elements, all of which have the same values as that of the element positioned a t p, to x.
e.g. The original sequence is [1, 1, 1, 2, 2, 2, 2, 3, 2, 2]. After modifying: 2 5 6, the sequence becomes [1, 1, 1, 6, 6, 6, 6, 3, 2, 2]. The original element positioned at 5 is 2, and the longest consecutive elements with the same value as 2 would be 2's positioned at 4 to 7.
Modify the length of the longest consecutive elements, all of which have the same values as that of the element positioned a t p, to c.
e.g. The original sequence is [1, 1, 1, 2, 2, 2, 2, 2, 3, 2, 2]. After modifying: 3 5 3, the sequence becomes [1, 1, 1, 2, 2, 2, 3, 2, 2].
e.g. The original sequence is [1, 1, 1, 2, 2, 2, 2, 2, 3, 2, 2]. After modifying: 3 11 4, the sequence becomes [1, 1, 1, 2, 2, 2, 2, 2, 3, 2, 2, 2, 2].
e.g. The original sequence is [1, 1, 1, 2, 2, 2, 2, 2, 3, 2, 2]. After modifying: 3 1 0, the sequence becomes [2, 2, 2, 2, 2, 3, 2, 2].
Modify the value of the element positioned a t p to x.
e.g. The original sequence is [1, 1, 1, 1]. After modifying: 4 3 2, the sequence becomes [1, 1, 2, 1].
Remove the element positioned a t p.
e.g. The original sequence is [1, 1, 1, 1]. After removing: 5 2, the sequence becomes [1, 1, 1].
Query the value of the element positioned a t p.
e.g. The sequence is [1, 1, 2, 3]. Query: 6 2 and you will get 1.
The first line is an integer T (1 ≤ T ≤ 10), indicates that there are T-group data.
For each test case, the first line contains one integerm(1 ≤ m ≤ 300,000), which represents the number of operations.
Each of the followingmlines contains an operation described above.
It is guaranteed thatnwill never exceed 1,000,000 after any operation.
For each test case, output the results (one at a line) for all the Single Element Queries (Operation 6).
**You are guaranteed that all the positions are valid. If you're getting runtime error (RE), please go over your solution.**