Termite Nest Proximity

In a forest, there are trees that may have termite nests. Initially, there are \(N\) termite nests, with at most one nest per tree. As new termite nests may be discovered later, the system supports dynamic additions.

When planning to build a cabin on a tree located at position \(x\), small H wants to know the distances to the closest \(P\) termite nests. The distance between two trees at positions \(x\) and \(t\) is given by:

$$ \text{distance} = |x - t| $$

You are given the initial positions of termite nests and a series of operations. There are two types of operations:

• Query Operation: Represented by a line starting with Q followed by two numbers \(x\) and \(P\). For this operation, output the distances from \(x\) to its \(P\) closest termite nests in increasing order.
• Add Operation: Represented by a line starting with A followed by a number \(x\). This operation adds a new termite nest at position \(x\). It is guaranteed that there is no termite nest already at \(x\).

The input begins with two integers \(N\) and \(Q\), where \(N\) is the number of initial termite nests and \(Q\) is the number of operations. The next line contains \(N\) integers representing the positions of the termite nests. Then follow \(Q\) lines each representing an operation as described above.

inputFormat

The first line contains two integers \(N\) and \(Q\) separated by a space.

The second line contains \(N\) integers representing the positions of the initial termite nests. The positions are not necessarily in sorted order.

Each of the next \(Q\) lines represents an operation:

• Q x P -- A query operation. \(x\) is the position where the cabin is planned, and \(P\) is the number of nearest termite nests to report. It is guaranteed that at least one termite nest exists when a query is made.
• A x -- An add operation. \(x\) is the position where a new termite nest is added. It is guaranteed that there is no termite nest at \(x\).

outputFormat

For each query operation, output a single line containing the distances of the \(P\) closest termite nests (based on the absolute difference \(|x-t|\)) in non-decreasing order, separated by a single space.

sample

5 4
1 5 10 15 20
Q 8 3
A 12
Q 8 3
Q 15 2

2 3 7
2 3 4
0 3

</p>