상사

이미지 출처: coursesidekick.com

대기업에서는 누가 무엇을 책임지는지 파악하는 데 상당히 많은 노력이 드는 경우가 흔하다. 이를 좀 더 쉽게 관리하기 위해, 자기 자신의 상사인 CEO을 제외한 모든 사람에게 상사를 지정하는 것이 일반적이다. 이 방식은 잘 작동하지만, 사람들이 직장을 그만두기 시작하고 다른 사람들이 회사에 새로 입사하므로 이 모든 계획을 그에 맞게 갱신해야 한다.

이 문제를 해결하려면 이 모든 정보를 관리하며, 주어진 어떤 사람에 대해서도 그 사람의 상사가 누구인지 알려 줄 수 있는 프로그램이 필요하다.

직원이 퇴사하면 그 직원의 상사가 그 직원의 모든 부하 직원을 넘겨받는다. 즉, $x$이 $y$의 상사이고, $y$이 $z$의 상사이며, $y$이 퇴사하면 이후에는 $x$이 $z$의 상사가 된다. 직원이 회사에 입사하면 상사가 지정된다. 회사의 CEO은 절대로 퇴사하거나 교체되지 않는다. 그 사람이 없으면 회사가 하룻밤 사이에 파산할 것이기 때문이다(적어도 본인의 말에 따르면 그렇다).

채점

그룹 | 점수 | 제약 조건

1 | 10 | $n, q \leq 10$.

2 | 15 | $n, q \leq 1\,000$.

3 | 20 | + 또는 - 쿼리가 없다.

4 | 20 | - 쿼리가 없다.

5 | 35 | 추가 제약 조건이 없다.

입력의 첫째 줄에는 처음의 직원 수와 이어질 쿼리 수를 나타내는 두 정수 $n, q$이 주어진다. 항상 $1 \leq n, q \leq 200\,000$을 만족한다. 직원에게는 $1, 2, \dots, n$의 번호가 매겨지며, 여기서 $1$은 CEO이다. 다음 줄에는 $n$개의 정수 $y_1, y_2, \dots, y_n$가 주어진다. 여기서 $y_i$은 직원 번호 $i$의 상사인 직원의 번호를 나타내므로, $1 \leq y_i \leq n$이다.

다음 $q$개 줄에는 각각 하나의 쿼리가 주어진다. 각 줄은 +, - 또는 ?로 시작한다. 모든 경우에 같은 줄에서 정수 $x$이 뒤따른다.

줄이 +로 시작하면 상사가 $x$인 새 직원이 입사한다는 뜻이다. 새 직원의 번호는 사용 가능한 번호 중 가장 작은 번호이다. 처음에 이 번호는 $n + 1$이지만, 어떤 직원이 퇴사하면 그 번호를 사용할 수 있게 된다. 따라서 $2, 8$와 $11$이 퇴사하면 사용 가능한 가장 작은 번호는 $2$이다. 하지만 아무도 퇴사하지 않았고 $n + 1$이 방금 사용되었다면, 다음으로 사용 가능한 번호는 $n + 2$이며 이후에도 같은 방식으로 정해진다.

줄이 -로 시작하면 직원 번호 $x$이 방금 퇴사했다는 뜻이다.

마지막으로 줄이 ?로 시작하면 직원 $x$의 상사 번호를 출력해야 한다. 여기서 $x$은 항상 현재 회사에서 근무 중인 직원의 번호이다. CEO을 제외하면 직접적으로든 간접적으로든 자기 자신의 상사인 사람은 절대로 없다.

?로 시작하는 각 쿼리마다 해당 상사의 번호를 한 줄에 하나씩 출력한다.