There are T test cases, for each test case, you will be given n (1<=n<=400000) operations for a stack.

Two possible operations:

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 first line is T(1<=T<=5).

for each case, the first line is n(1<=n<=400000) , which is the number of operations, then follows n line contains either operation 1 or operation 2.

for each pop operation, print the (MAX - MIN) value in the remains stack, if the stack is empty, print 0;

1
6
push 387
pop
push 278
push 416
push 111
pop

0
138

0 is because the stack is empty after the first pop;

138 is calculated by 416 - 278 = 138