대기줄 복원
시간 제한1초메모리 제한128 MB
각 사람이 줄의 어느 자리에 들어섰다는 기록으로 해산 직전 각자의 최종 위치를 구합니다.
- 난이도
보통10점 중 5점
- 유형
- 세그먼트 트리
- 정답자
- 아직 제출이 없습니다
문제
건설 노동자 아드리안은 오늘 할 일이 많지 않아, 가게 앞 대기줄을 연구하는 자료를 모으고 있다.
아드리안은 근처 가게 앞 대기줄을 지켜보며, 차례로 도착하는 사람이 줄의 어느 위치에 섰는지를 기록한다. 하루가 시작될 때 줄에는 아무도 없었다. 새로 온 사람이 반드시 줄 맨 뒤에 서는 것은 아니다. 누군가와 미리 약속했거나, 돈을 주었거나, 무언가를 건넸거나, 다른 방법을 써서 줄의 어느 위치든 끼어들 수 있다. 한 번 줄에 선 사람은 정오까지 줄을 떠나지 않았고, 정오가 되자 오늘 가게가 열지 않는다는 사실이 밝혀져 모두 흩어졌다.
아드리안은 자신의 기록만으로, 사람들이 흩어지기 직전의 줄 배치를 복원할 수 있는지 궁금하다.
입력
첫 줄에 테스트 세트의 수 ()가 주어진다. 이어서 각 테스트 세트가 차례로 주어진다.
각 세트의 첫 줄에는 아침부터 정오까지 줄에 선 사람의 수를 나타내는 자연수 ()이 주어진다. 둘째 줄에는 개의 정수 (, )이 주어진다.
가 이면 번째 사람은 줄의 맨 앞에 섰다는 뜻이다. 그렇지 않으면 번째 사람은, 자신이 도착한 순간에 줄의 앞에서부터 세어 번째였던 사람의 바로 뒤에 섰다는 뜻이다.
출력
각 세트마다 한 줄에 개의 정수를 공백 하나로 구분하여 출력한다. 번째 정수는 번째로 줄에 들어온 사람의 최종 위치여야 한다. 줄의 맨 앞에 선 사람의 위치는 , 그 뒤는 와 같이 매긴다.