Color Palette

Time limit3sMemory limit1024 MB

Summary

Maintain a set of K-bit colors under insertions and, for each query color, return the stored color with the maximum number of matching bit positions, breaking ties by smallest value.

Level: Medium7 of 10
Topics: Trie, Bit manipulation, Greedy, Brute force
Solved: No attempts yet

Problem

A company that makes graphics software is developing a new graphics program. One of its modules manages a color palette. When the program starts, the palette is empty. The user can add new colors to the palette, or ask which of the palette's colors is most similar to a given color.

Colors are represented as $K$ -bit integers (values from $0$ to $2^K-1$ ), and the similarity of two colors is the number of bit positions where their binary representations agree. For example, when $K = 5$ , the similarity of colors 00110 and 10101 is $2$ , because only the second and third bits from the left have the same value.

The program behaves like a palette-management module built from the following operations, and it prints a log in the order the operations are called.

Operation	Description
`init(int k, int n)`	Initialize the palette to use $k$ -bit colors. Called once at the start, followed by a total of $n$ `add` and `find` calls.
`add(int c)`	Add color $c$ to the palette.
`find(int c)`	Find the best match for color $c$ in the palette. Returns the palette color whose similarity to $c$ is largest. If several colors are equally most similar, return the smallest such color value. This operation is called only when the palette already holds at least one color.
`done()`	End of work. Called once at the very end.

Input

The first line of the input contains the number of bits $K$ ( $1 \le K \le 20$ ) used to represent colors and the number of operations $N$ ( $1 \le N \le 10^6$ ). Each of the following $N$ lines contains two integers $T_i$ and $C_i$ ( $0 \le C_i < 2^K$ ). $T_i = 1$ means "add color $C_i$ to the palette", and $T_i = 2$ means "find the best match for color $C_i$ in the palette".

Output

Print the log of the operations the module processed. First print init(K, N). Then process each operation in the given order and print the following.

For an operation that adds color $C$ , print add(C).
For an operation that looks up color $C$ , print find(C) = R, where $R$ is the palette color whose similarity to $C$ (the number of matching bits) is largest. If several colors are equally similar, $R$ is the smallest such color value.

Finally print done(). A find operation is given only when the palette already contains at least one color.

Examples2

Example 1

Input

Expected output

init(2, 3)
add(1)
find(0) = 1
find(1) = 1
done()

Example 2

Input

Expected output

init(3, 5)
add(0)
add(7)
find(1) = 0
add(1)
find(1) = 1
done()