Description

假设这里有一个队列，我们可以对其进行下述操作：

PUSH X：意味着将一个整数$X（-2^{31}\lt X\lt 2^{31}）$加入到队尾。

POP：从队头删除一个数，如果队列为空则不进行操作。

MINUS：将队列中所有的数字变成其相反数。

MAX：输出队列中所有数字的最大值，如果队列为空则不进行输出。

Format

Input

第一行包括一个整数$T（T\le 10）$，表示接下来有$T$组测试数据。对于每一组测试数据，第一行包括一个数$N（N\le 2000000）$，表示操作次数，接下来的$N$行给出具体操作。

Output

对于每一组数据，在新的一行输出MAX返回的数。每组测试数据之间输出一个空行。

Samples

1
6
PUSH -2
MINUS
PUSH -1
MAX
POP
MAX

2
-1

Hint

数据结构题。队列的操作。