256-to-16 Grayscale Image Compression

An image is composed of many pixels. In a 256-level grayscale image, a pixel is represented by one byte with a value between \(0\) (black) and \(255\) (white), where the values in between represent different shades of gray. In this problem, you are required to compress a 256-level grayscale image into a 16-level grayscale image. In the compressed image each pixel’s value will be in the range \(0-15\) (or, equivalently, \(0-F\) in hexadecimal).

The compression is performed as follows:

1. Count the frequency of each grayscale value in the input image.
2. Select the top 16 grayscale values with the highest frequency. If several values have the same frequency, choose those with smaller grayscale values first.
3. Assign a new 16-level code to each selected grayscale value. The most frequent value is assigned the code \(0\), the second most frequent is assigned \(1\), and so on, until the 16th value is assigned \(F\) (in hexadecimal notation).
4. For any pixel whose grayscale value is not among these selected 16, map it to the closest (in terms of absolute difference of grayscale values) among the 16 chosen candidates. If there is a tie, choose the candidate having the smaller new code.

Your program should read an image represented as a sequence of pixel values, perform the compression, and output the new 16-level grayscale codes for each pixel (using hexadecimal digits \(0-9\) and \(A-F\)).

inputFormat

The first line contains an integer \(N\) representing the number of pixels in the image. The second line contains \(N\) space-separated integers, each in the range [0, 255], representing the grayscale values of the pixels.

outputFormat

Output a single line containing \(N\) space-separated hexadecimal digits (uppercase) representing the compressed pixel values. Each digit will be one of \(0-9\) or \(A-F\).

sample

5
0 255 128 128 100

1 3 0 0 2