추천 영상
시간 제한1초메모리 제한128 MB
K개 영상의 추천 그래프에서 각 학생이 시작 영상에서 M-1번 이동한 뒤 도달하는 영상을 함수형 그래프 점프로 구하는 문제입니다.
문제
프로그래밍 수업을 듣던 N명의 학생이 남은 M분 동안 몰래 온라인 동영상을 보려고 한다.
동영상은 1번부터 K번까지 번호가 붙어 있다. 어떤 동영상을 보고 있으면, 화면에는 그 동영상의 추천 동영상 목록이 함께 보이며 그중 가장 위에 있는 동영상 하나만 고려한다.
각 학생은 처음에 주어진 동영상 하나를 보기 시작한다. 모든 동영상은 정확히 1분 동안 본다. 한 동영상을 1분 동안 본 뒤에는, 방금 본 동영상의 가장 위 추천 동영상을 다음 1분 동안 본다.
각 학생이 처음 보는 동영상 번호와 각 동영상의 가장 위 추천 동영상 번호가 주어질 때, M번째 분에 각 학생이 보고 있는 동영상 번호를 출력하라.
입력
첫째 줄에 N, K, M이 주어진다. 1 <= N, K <= 100,000, 1 <= M <= 1,000,000,000이다. N은 학생의 수, K는 동영상의 수, M은 남은 수업 시간(분)이다.
둘째 줄에는 각 학생이 처음 보는 동영상 번호 N개가 주어진다. 각 번호는 1 이상 K 이하이다.
셋째 줄에는 각 동영상의 가장 위 추천 동영상 번호 K개가 주어진다. i번째 수는 i번 동영상의 가장 위 추천 동영상 번호이며, 각 번호는 1 이상 K 이하이다.
출력
첫째 줄에 각 학생이 M번째 분에 보고 있는 동영상 번호를 입력 순서대로 공백으로 구분해 출력한다.