Replication - Part 1

Limits: 2 sec., 512 MiB

Replication - the process of creating two daughter DNA molecules based on the parent DNA molecule. DNA replication is performed by a various of complex operations, consisting of 15-20 different protein-enzymes. In order to replicate, viruses are constantly dividing their DNA - thereby shrinking it. For viruses, replication of the longest gene is the optimal division.

Also, each virus has a genetic tree.

A genetic tree is a binary tree that satisfies the property: if gene B is a descendant node of gene A, then the length of gene A is more or equal length of gene B. When the gene is removed from a tree, the virus replaces it with the most recent gene in the hierarchy and performs the replacement operation. Substitution is the process of exchange in the tree of a short gene with a longer one, provided that the shorter gene is higher in the hierarchy. If the shorter gene is higher in the hierarchy, it is exchanged with the direct (neighboring) in the hierarchy, the longer gene. Replacement operations occur independently until the entire hierarchy satisfies the property of the genetic tree. When the gene is goind to be inserted, it is added as the last one in the hierarchy, and the replacement operation also occurs.

Your task is to emulate the behavior of the virus genotype. There are two requests for the addition of a gene and the removal of the top of the genetic tree. After each request, print a new vertex and the number of replacement operations performed during the operation.

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.

Guaranteed that each added gene will be shorter in length than the previous \(A_i > A_j\) for all \(j > i\) as well as \(P > A_i\). It is also guaranteed that at any given time the genetic tree will not be empty, and all the elements of the tree are unique.

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^5\), \(1 \le \mathbf{P} \le 10^9\), \(1 \le \mathbf{A_i} \le 10^9\)

Samples