There are T test cases, for each test case, there are n (1<=n<=400000) operations for a stack. And there are only two operations in this problem.

The following operations are:

1. push x

2. pop

For operation 1 you are asked to push x(1<=x<=100000000) in to the stack.

For operation 2 you are asked to pop out the top element of the stack and print the maximum number of the stack - minimum number in the stack.

The ﬁrst line is an integer T(1<=T<=5).
For each case, the ﬁrst line is n(1<=n<=400000) , which is the number of operations, then the following are n lines containing either operation 1 or operation 2.

It is not guaranteed that whether the stack is empty. If the stack is empty and you are asked to pop the element, you can just ignore the operation, but still need to print the corresponding answer.

For each pop operation, print the (MAX - MIN) value in the remaining stack. If the stack is empty, print 0.

For each test case, print each answer in a line.

Hint: 0 is because the stack is empty after the ﬁrst pop.

138 is calculated by 416 - 278 = 138.