균형 잡힌 트리 자르기

아나 반 리어 교수는 균형 잡힌 이진 탐색 트리에 관한 강의를 준비하고 있다. 이 트리는 다음 두 가지 성질을 가진 이진 트리다.

• 균형 트리: 모든 노드에서 왼쪽 서브트리의 높이와 오른쪽 서브트리의 높이 차이가 1 이하이다. 예를 들어 그림 B.1에서 7번 노드의 왼쪽 서브트리 높이는 2, 오른쪽 서브트리 높이는 1이다. 왼쪽(또는 오른쪽) 자식이 없으면 그 서브트리의 높이는 0으로 본다.
• 탐색 트리: 각 노드는 값을 가진다. 노드의 값은 왼쪽 서브트리의 모든 값보다 크고, 오른쪽 서브트리의 모든 값보다 작다. 예를 들어 그림 B.1에서 7번 노드의 왼쪽 서브트리에는 4, 5, 6이 있으며, 모두 7보다 작다.

아나는 동료에게서 이런 트리의 그림을 받았다. 이 트리는 값이 1부터 $n$까지인 $n$개의 노드로 이루어져 있다. 슬라이드에 넣기에는 너무 커서 트리를 줄이려고 한다. 노드 몇 개를 지워서 남은 노드가 정확히 $k$개가 되게 할 것이다. 노드를 지울 때는 그 노드의 서브트리도 함께 지운다. 결과 트리도 여전히 균형 잡힌 이진 탐색 트리여야 한다.

교육 목적상 아나는 최종 트리의 값이 작기를 바란다. 남은 $k$개 값의 목록이 사전순으로 가장 작아지기를 원한다. 예를 들어 값이 2, 5, 9인 트리가 2, 6, 7인 트리보다 낫다.

아나는 더 중요한 일로 매우 바쁘다. 그래서 어느 노드를 지울지 정하는 일은 조교인 당신이 맡는다.

그림 B.1: 샘플 입력 2와 그 해의 그림.

입력은 다음과 같이 주어진다.

• 첫 줄에 정수 $n$과 $k$가 주어진다 ($2 \le n \le 5 \times 10^5$, $1 \le k \le n - 1$). $n$은 트리의 노드 수이고, $k$는 남길 노드 수이다.
• 이어서 $n$개의 줄이 주어진다. $i$번째 줄에는 값이 $i$인 노드의 부모를 나타내는 정수 $p_i$ ($1 \le p_i \le n$ 또는 $p_i = -1$)가 있다. 값이 $i$인 노드가 루트이면 $p_i = -1$이다.

주어진 트리는 균형 잡힌 이진 탐색 트리임이 보장된다.

길이가 $n$인 이진 문자열을 한 줄로 출력한다. $i$번째 문자는 값이 $i$인 노드를 남기면 '1', 지우면 '0'이다.