피라미드 판매

이미지 출처: 플리커닷컴

피라미드 유한회사는 매년 수백 개의 피라미드를 판매한다. 이 회사의 사업 모델은 일반적으로 알려진 기업의 사업 모델과 다르다. 회사 소유주인 Pýramídas는 회사를 위해 판매하는 직원들을 고용했다. Pýramídas의 직원들은 자신의 직원들을 고용하고, 그 직원들은 다시 자신의 직원들을 고용하는 식으로 계속 이어진다. 따라서 직원마다 상사가 한 명 있지만(Pýramídas는 제외), 부하 직원은 여러 명일 수 있다. 어떤 직원에게 부하 직원이 있다면, 그 직원에게는 항상 적어도 두 명의 부하 직원이 있다. 다시 말해, 직원에게 부하 직원이 정확히 한 명인 경우는 절대 없다. 부하 직원들은 고용된 시점에 따라 순서가 정해진다는 점에 유의한다. 가장 먼저 고용된 부하 직원이 맨 앞에 오고, 그다음에 고용된 직원이 뒤따르는 식이다.

처음에는 Pýramídas가 모든 피라미드를 소유하며 이를 자신의 직원들에게 되판다. 그 직원들은 다시 자신의 직원들에게 피라미드를 되팔고, 이 과정은 피라미드가 자신의 밑에 직원이 없는 사람들의 손에 들어갈 때까지 계속된다. 그 직원들은 회사 직원은 아니지만 피라미드에 관심이 있는 사람들에게 피라미드를 판매한다. 그런 다음 직원들은 수익의 $10\%$을 자신의 상사에게 넘겨야 한다.

최근 이 사업의 합법성에 관한 민원이 제기되었다. 당신은 이를 조사하기 위해 고용되었다. 조사의 첫 단계는 회사의 구조를 파악하는 것이다. 안타깝게도 어느 직원도 누가 누구를 위해 일하는지 또는 누가 누구의 상사인지에 관한 정보를 제공하려 하지 않는다.

당신에게는 각 직원의 직원 번호가 적힌 직원 명부가 있다. 또한 회사의 구조를 나타낸다는 세 개의 직원 번호 수열도 입수했다. 암호화 전문가인 친구 Bjarki는 이 세 수열을 만들 때 다음과 같은 서로 다른 세 가지 방법이 사용되었다는 사실을 알아냈다.

• 먼저 직원이 자신의 번호를 적고, 부하 직원들에게 자신의 행동을 따르라고 지시한다. 부하 직원들도 자신의 부하 직원들에게 같은 지시를 내린다.

• 먼저 자신의 첫 번째 부하 직원에게 자신의 행동을 따르라고 지시한다. 다음으로 자신의 번호를 적는다. 그런 다음 두 번째 부하 직원에게 자신의 행동을 따르라고 지시한다. 다시 자신의 번호를 적는다. 그다음에는 세 번째 부하 직원의 차례이다. 마지막 부하 직원이 끝낼 때까지 부하 직원들의 행동 사이마다 항상 자신의 번호를 적는다. 부하 직원이 없는 직원은 자신의 번호를 한 번 적는다.

• 먼저 직원이 부하 직원들에게 자신의 행동을 따르라고 지시한 다음 자신의 번호를 적는다. 부하 직원들도 자신의 부하 직원들에게 같은 지시를 내린다.

이 세 수열을 바탕으로 회사의 구조를 알아낼 수 있는가? 누가 누구를 위해 일하며, 부하 직원들은 어떤 순서로 고용되었는가?

배점

그룹 | 점수 | 제한

1 | 15 | $1 \leq N \leq 100$, 직원마다 부하 직원이 최대 2명이며 수열 2가 오름차순이다

2 | 15 | $1 \leq N \leq 100$이고 직원마다 부하 직원이 최대 2명이다

3 | 15 | $1 \leq N \leq 100$

4 | 20 | 직원마다 부하 직원이 최대 2명이며 수열 2가 오름차순이다

5 | 20 | 직원마다 부하 직원이 최대 2명이다

6 | 15 | 추가 제한 없음

입력은 네 줄로 주어진다. 입력의 첫째 줄에는 직원 수 $1 \leq N \leq 10^{5}$과 수열 2에 포함된 수의 개수 $M$이라는 두 정수가 주어진다. 둘째 줄에는 수열 1을 이루는 $N$개의 정수가 주어진다. 셋째 줄에는 수열 2를 이루는 $M$개의 정수가 주어진다. 넷째 줄에는 수열 3을 이루는 $N$개의 정수가 주어진다.

직원 번호는 항상 $1$ 이상 $N$ 이하의 정수지만, 특정한 방식으로 배정되지는 않는다.

$N$개의 줄을 출력한다. $i$번째 줄에는 번호가 $i$인 직원의 모든 부하 직원 번호를 아래 예제와 같은 형식으로 출력한다.

항상 정확히 하나의 해가 존재한다고 가정해도 된다.

첫 번째 예제는 그룹 1에 해당하며, 회사의 구조는 아래 그림과 같다.

[h!]

예제 1

두 번째 예제는 그룹 2에 해당하며, 회사의 구조는 아래 그림과 같다.

[h!]

예제 2

세 번째 예제는 그룹 3에 해당하며, 회사의 구조는 아래 그림과 같다.

[h!]

예제 3