문제
Bessie는 Elsie의 다가오는 어휘 퀴즈를 도와주고자 합니다. 시험에 출제될 단어들은 M개의 서로 다른 단어들로 구성된 단어 은행에서 가져오게 되며, 이 단어 은행 내의 어떤 단어도 다른 단어의 접두사(prefix)가 되지 않습니다.
단어 은행이 비어 있지 않은 동안, Bessie는 단어 은행에서 단어 하나를 선택하여 제거한 후, 그 단어를 왼쪽에서 오른쪽으로 한 글자씩 읽어 Elsie에게 전달합니다. Elsie의 임무는 단어를 유일하게 식별할 수 있게 되는 순간 Bessie에게 알려주는 것이며, 그 즉시 Bessie는 읽기를 멈춥니다.
Bessie는 단어 은행에 있는 단어들을 w₁, w₂, …, w_M의 순서로 읽기로 이미 결정해 두었습니다. 만약 Elsie가 가능한 한 빨리 답한다면, Bessie는 각 단어에 대해 몇 글자를 읽게 될까요?
단어들은 압축된 형식으로 주어집니다. 먼저 N+1개의 서로 다른 단어들을 정의한 후, 단어 은행은 다른 단어의 접두사가 아닌 단어들로 구성됩니다. 단어들은 다음과 같이 정의됩니다:
처음에 0번째 단어는 빈 문자열입니다.
그 후, 1 ≤ i ≤ N에 대해 i번째 단어는 pᵢ번째 단어에 한 글자를 덧붙인 것으로 정의됩니다 (0 ≤ pᵢ < i). 모든 N+1개의 단어들이 서로 다르도록 글자들이 선택됩니다.
입력
첫 번째 줄에 N가 주어지며, 여기서 N+1은 압축 형식으로 주어진 단어의 개수입니다.
다음 줄에는 p₁, p₂, …, p_N이 공백으로 구분되어 주어지며, pᵢ는 i번째 단어가 pᵢ번째 단어에 한 글자를 덧붙여 만들어졌음을 나타냅니다.
단어 은행에 포함될 단어의 개수 M는, 다른 단어의 접두사가 아닌 단어들의 개수입니다.
그 다음 M개의 줄에는 w₁, w₂, …, w_M이 주어지며, 이는 단어 은행에서 wᵢ번째 단어가 i번째로 읽힐 것임을 의미합니다. 주어지는 w₁, …, w_M는 단어 은행에 있는 단어들의 순열임이 보장됩니다.
출력
각 테스트 케이스에 대해, M개의 줄을 출력합니다. i번째 줄에는 Bessie가 i번째 단어를 읽을 때 읽는 문자 수를 출력합니다.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 20점 | 단어의 길이가 20을 넘지 않음 |
| #2 | 30점 | 모든 단어들의 길이 합이 10⁷을 넘지 않음 |
| #3 | 50점 | 추가 제약 없음 |
예제1
5
0 1 2 3 4
5
0
총 6개의 단어(0번부터 5번까지)가 압축 형식으로 주어집니다. 이 중 단어 은행에는 다른 단어의 접두사가 아닌 단어들만 포함되는데, 여기서는 5번 단어만이 해당되므로 단어 은행에는 단 하나의 단어가 있습니다. 단어 은행에 단 하나의 단어만 남으면 Elsie는 어떤 글자도 들을 필요가 없으므로, Bessie는 0글자를 읽습니다.
예제2
4
0 0 1 1
4
3
2
2
1
0
압축 형식으로 주어진 단어들 중 단어 은행은 단어 2, 3, 4로 구성됩니다.
단어 4의 경우, 단어 3과 첫 글자가 동일하므로 Elsie가 단어 4를 유일하게 식별하려면 최소 2글자가 필요합니다.
단어 3의 경우, 단어 4는 이미 읽힌 상태이므로 Elsie는 1글자만 들어도 단어를 식별할 수 있습니다.
마지막으로, 단어 은행에 단 하나의 단어가 남으면 Elsie는 0글자만 듣고도 식별할 수 있습니다.
예제3
4
0 0 1 1
2
3
4
1
2
0
단어 은행은 단어 2, 3, 4로 구성되며, 읽히는 순서가 예제 3과 같이 주어집니다.
첫 번째 읽는 단어(단어 2)는 1글자를 들었을 때 식별이 가능하고,
두 번째 읽는 단어(단어 3)는 2글자가 필요하며,
마지막 단어는 단어 은행에 유일하게 남으므로 0글자를 읽습니다.