색상 팔레트

문제

그래픽 소프트웨어를 만드는 회사에서 새 그래픽 프로그램을 개발하고 있다. 이 프로그램의 모듈 중 하나는 색상 팔레트를 관리한다. 프로그램이 시작되면 팔레트는 비어 있다. 사용자는 팔레트에 새로운 색을 추가하거나, 주어진 색과 팔레트에 있는 색 중 가장 비슷한 색이 무엇인지 물어볼 수 있다.

색은 $K$비트 정수($0$부터 $2^K-1$까지의 값)로 표현하며, 두 색의 유사도는 두 색의 비트 표현에서 값이 일치하는 비트의 개수로 정의한다. 예를 들어 $K = 5$일 때 색 00110과 10101의 유사도는 $2$인데, 왼쪽에서 두 번째와 세 번째 비트만 서로 값이 같기 때문이다.

프로그램은 다음 연산들로 이루어진 색상 팔레트 관리 모듈처럼 동작하며, 각 연산이 호출되는 순서대로 로그를 출력한다.

연산	설명
`init(int k, int n)`	$k$비트 색을 사용하도록 팔레트를 초기화한다. 프로그램 시작 시 한 번 호출되며, 그 뒤에 `add`와 `find` 호출이 모두 합쳐 $n$번 이어진다.
`add(int c)`	색 $c$를 팔레트에 추가한다.
`find(int c)`	색 $c$에 대해 팔레트에서 가장 잘 맞는 색을 찾는다. 팔레트의 색 중 $c$와의 유사도가 가장 큰 색을 반환한다. 유사도가 가장 큰 색이 여러 개이면 그중 값이 가장 작은 색을 반환한다. 이 연산은 팔레트에 색이 최소 한 개 있을 때만 호출된다.
`done()`	작업 종료. 프로그램 끝에서 한 번 호출된다.

입력

입력의 첫 줄에는 색을 표현하는 데 사용하는 비트 수 $K$ ($1 \le K \le 20$)와 연산의 개수 $N$ ($1 \le N \le 10^6$)이 주어진다. 이어지는 $N$개의 줄에는 각각 두 정수 $T_i$와 $C_i$ ($0 \le C_i < 2^K$)가 주어진다. $T_i = 1$은 색 $C_i$를 팔레트에 추가함을, $T_i = 2$는 색 $C_i$에 대해 팔레트에서 가장 잘 맞는 색을 찾음을 뜻한다.

출력

모듈이 처리한 연산들의 로그를 출력한다. 먼저 init(K, N)을 출력한다. 그다음 각 연산을 주어진 순서대로 처리하며 다음을 출력한다.

색 $C$를 추가하는 연산이면 add(C)를 출력한다.
색 $C$를 찾는 연산이면 find(C) = R를 출력한다. 여기서 $R$은 팔레트의 색 중 $C$와의 유사도(일치하는 비트 수)가 가장 큰 색이다. 그런 색이 여러 개이면 $R$은 그중 값이 가장 작은 색이다.

마지막으로 done()을 출력한다. find 연산은 팔레트에 색이 최소 한 개 있을 때만 주어진다.