Hide

Problem C
Pýramídasala

Languages en is
/problems/pyramidasala/file/statement/en/img-0001.jpg
Image from flickr.com

The company Pyramids Inc. sells hundreds of pyramids each year. Their business model is different from what is commonly known in companies. Pýramídas, the owner, hired employees to sell for the company. His employees then hired their own employees, which in turn hired their own employess, and so forth. Therefore, each employee has a single supervisor (except for Pýramídas) but can have multiple subordinates. If an employee has a subordinate, then they will always have at least two subordinates. In other words, employees will never have exactly one subordinate. Be aware that subordinates are ordered by the date of their hiring. The first subordinate to be hired comes first, then the second and so forth.

Pýramídas is the owner of all the pyramids to begin with and then he sells them to his employees. Those employees then sell them to their employees. This continues until the pyramids are in the possession of employees with no subordinates. The pyramids are then sold to pyramid enthusiast which are not employed by the company. Employees then must send $10\% $ of their profits to their supervisor.

Recently, there have been some complaints regarding the legitimacy of the operation. You have been hired to investigate. The first step of the investigation is to understand the heirarchy of the company. Sadly, none of the employees are willing to provide any information to you about who their supervisor is, nor who their subordinates are.

You have access to an employee manifest which lists the employee ID of each employee. You have also discovered three sequences of employee IDs which, supposedly, describe the heirarchy of the company. Your friend, Bjarki, is an expert on decryption and has deciphered the three different methods used to create the sequences.

  1. First, the employee writes their own employee ID and then orders their subordinates to mimic this action. The subordinates will then in turn order their own subordinates.

  2. First, the employee orders their first subordinate to mimic this action. Then, the employee writes their own employee ID. Following that, the second subordinate mimics this action. The employee then writes their employee ID again. Next up is the third subordinate. Each time, the employee writes their own employee ID between the actions of their subordinates, until the last one is done. If the employee has no subordinates, then they simply write their own employee ID once.

  3. First, the employee orders their subordinates to mimic this action and then writes their own employee ID. The subordinates will then in turn order their own subordinates.

Using these three sequences, can you determine the heirarchy of the company? Can you determine who works for who and in what order subordinates were hired for each employee?

Input

Input is four lines. The first line consists of two integers $1 \leq N \leq 10^5$, the total number of employees, and $M$, the number of employee IDs in sequence $2$. The second line consists of $N$ integers, sequence $1$. The third line consists of $M$ integers, sequence $2$. The fourth line consists of $N$ integers, sequence $3$.

Employee IDs are always integers between $1$ to $N$, but they are not assigned in any particular order.

Output

Output $N$ lines. Line $i$ should consist of the employee IDs of all subordinates of employee with ID $i$. The subordinates must be output in the correct order. You may assume that a single solution exists.

Scoring

Group

Points

Constraints

1

15

$1 \leq N \leq 100$, employees have at most $2$ subordinates each and sequence $2$ is increasing.

2

15

$1 \leq N \leq 100$ and employees have at most $2$ subordinates.

3

15

$1 \leq N \leq 100$

4

20

Employees have at most $2$ subordinates and sequence $2$ is increasing.

5

20

Employees have at most $2$ subordinates.

6

15

No further constraints.

Explanation of samples

The first sample is in group $1$ and the heirarchy of the company can be seen below.

\includegraphics[width=0.5\textwidth ]{sample1}
Figure 1: Example 1

The second sample is in group $2$ and the heirarchy of the company can be seen below.

\includegraphics[width=0.5\textwidth ]{sample2}
Figure 2: Example 2

The third sample is in group $3$ and the heirarchy of the company can be seen below.

\includegraphics[width=0.5\textwidth ]{sample3}
Figure 3: Example 3
Sample Input 1 Sample Output 1
5 5
2 1 4 3 5
1 2 3 4 5
1 3 5 4 2
1:
2: 1 4
3:
4: 3 5
5:
Sample Input 2 Sample Output 2
7 7
5 7 3 1 2 4 6
3 7 2 1 4 5 6
3 2 4 1 7 6 5
1: 2 4
2:
3:
4:
5: 7 6
6:
7: 3 1
Sample Input 3 Sample Output 3
12 15
6 8 5 7 1 12 3 11 10 4 9 2
5 8 7 6 12 1 3 6 10 11 4 11 9 11 2
5 7 8 12 3 1 10 4 9 2 11 6
1: 12 3
2:
3:
4:
5:
6: 8 1 11
7:
8: 5 7
9:
10:
11: 10 4 9 2
12:

Please log in to submit a solution to this problem

Log in