Replication - Part 2

Limits: 2 sec., 512 MiB

To increase their lifespan, viruses use corevaluation. The process by which a virus adds an arbitrary gene to its genotype. Your task is to emulate the behavior of the virus genotype in the absence of the ability to predict the added gene.

Input

The first line of input contains an integer N, P - the number of requests and first element in the tree. Then N queries follow, where the addition operation is:

’\(+ A_i\)’, where \(A_i\) is the length of the i-th added gene.

’-’ - delete operation.

Also guaranteed that at any given time the genetic tree will not be empty.

Output

After each operation, a line of the form "C T" is displayed, where C is the number of substitution operations during the operation, T is the new top item in the hierarchy

Constraints

\(1 \le \mathbf{N} \le 10^7\), \(1 \le \mathbf{P} \le 10^9\), \(1 \le \mathbf{A_i} \le 10^9\)

Samples