cho.shColor Palette
No attempts yetTime limit3sMemory limit1024 MBProblem
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.