Tag Groups of Measured Triplets

A bright plastic lemon‐colored submarine is investigating the ocean depths and measuring the concentration of plastic yocto particles in the water. Each measurement is a positive integer (thanks to a clever choice of units).

The measurement system is new, barely tested, and prone to errors. Management suspects it is full of flaws. In order to discover and fix these bugs, they have decided to analyze all measured triplets in the measurement sequence.

A triplet is a sequence of three integers taken from the measurement sequence (not necessarily consecutive, but in the same order as in the original sequence). For any triplet \((x,y,z)\), its signature is defined as \[ (\operatorname{sgn}(y-x),\; \operatorname{sgn}(z-y),\; \operatorname{sgn}(z-x)), \] where the function \(\operatorname{sgn}(x)\) is given by \[ \operatorname{sgn}(x)=\begin{cases} -1,& x0, \end{cases} \] and note that since the measurements are positive integers, differences may be 0 if measurements are equal.

The tag group of a triplet is defined as the lexicographically minimal triple of positive integers that has the same signature. The ordering between two triplets \((x_1,y_1,z_1)\) and \((x_2,y_2,z_2)\) is defined as follows: \((x_1,y_1,z_1) < (x_2,y_2,z_2)\) if and only if the first nonzero value in the triple \((x_1-x_2,\; y_1-y_2,\; z_1-z_2)\) is negative.

For the purpose of this problem the following minimal tag groups (for each possible signature) are pre‐determined:

• Signature \((0,0,0)\) → Tag group: \((1,1,1)\).
• Signature \((0,1,1)\) → Tag group: \((1,1,2)\).
• Signature \((0,-1,-1)\) → Tag group: \((2,2,1)\).
• Signature \((1,0,1)\) → Tag group: \((1,2,2)\).
• Signature \((1,1,1)\) → Tag group: \((1,2,3)\).
• Signature \((1,-1,0)\) → Tag group: \((1,2,1)\).
• Signature \((1,-1,-1)\) → Tag group: \((2,3,1)\).
• Signature \((-1,0,-1)\) → Tag group: \((2,1,1)\).
• Signature \((-1,1,0)\) → Tag group: \((2,1,2)\).
• Signature \((-1,-1,-1)\) → Tag group: \((3,2,1)\).

Your task is to take a measurement sequence as input, consider all triplets (subsequences of length 3 in the original order), obtain their signatures, map each signature to its corresponding tag group, and output the sorted set of unique tag groups (sorted in lexicographic order).

inputFormat

The first line contains an integer \(n\) indicating the number of measurements. The second line contains \(n\) positive integers separated by spaces.

outputFormat

Output the unique tag groups, one per line. For each tag group, output three positive integers separated by a space. The tag groups should be listed in lexicographically increasing order.

sample

3
1 1 1

1 1 1