아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

철도 공사

시간 제한2초메모리 제한512 MB

요약
원형 이중 연결 리스트에서 역을 삽입하고 삭제하면서, 각 공사마다 인접한 역의 고유 번호를 출력한다.
난이도

보통10점 중 4점

유형
연결 리스트, 해시맵
정답자
아직 제출이 없습니다

문제


[그림] 2호선 노선도

연세대학교가 위치한 신촌역이 속한 2호선은 그림과 같이 NN개의 역이 원형으로 연결되어 있다. 각 역은 고유 번호가 할당돼 있으며 역들의 고유 번호는 서로 다르다. 그리고 특정 역의 다음 역은 시계 방향으로 인접한 역을 의미하고, 이전 역은 반시계 방향으로 인접한 역을 의미한다.

2호선은 지하철 노선들 중 유일한 흑자 노선이다. 때문에 2호선 공사 자금이 넉넉하기에 MM번의 공사를 거치려고 한다. 각 공사는 다음 4가지 중 하나를 시행한다.

  • 고유 번호 ii를 가진 역의 다음 역의 고유 번호를 출력하고, 그 사이에 고유 번호 jj인 역을 설립한다.
  • 고유 번호 ii를 가진 역의 이전 역의 고유 번호를 출력하고, 그 사이에 고유 번호 jj인 역을 설립한다.
  • 고유 번호 ii를 가진 역의 다음 역을 폐쇄하고 그 역의 고유 번호를 출력한다.
  • 고유 번호 ii를 가진 역의 이전 역을 폐쇄하고 그 역의 고유 번호를 출력한다.

이 때, 이미 설립한 역은 다시 설립하지 않으며 폐쇄한 역은 다시 설립될 수 있다. 그리고 폐쇄 작업은 현재 설립된 역이 22개 이상일 때만 들어온다.

2호선을 공사하는 프로그램을 만들어보자.

입력

첫 번째 줄에 공사를 시작하기 이전에 있는 역의 개수를 나타내는 양의 정수 NN과 공사 횟수를 나타내는 양의 정수 MM이 주어진다. (1≤N≤500,0001 \le N \le 500\\,000, 1≤M≤1,500,0001 \le M \le 1\\,500\\,000)

두 번째 줄에는 공사를 시작하기 이전에 있는 역의 고유 번호를 시계 방향 순서대로 주어진다. 같은 고유 번호를 가진 역은 주어지지 않는다.

이후 MM개의 줄에 걸쳐서 공사에 대한 정보를 다음과 같이 주어진다.

  • BN ii jj : 고유 번호 ii를 가진 역의 다음 역의 고유 번호를 출력하고, 그 사이에 고유 번호 jj인 역을 설립한다.
  • BP ii jj : 고유 번호 ii를 가진 역의 이전 역의 고유 번호를 출력하고, 그 사이에 고유 번호 jj인 역을 설립한다.
  • CN ii : 고유 번호 ii를 가진 역의 다음 역을 폐쇄하고 그 역의 고유 번호를 출력한다.
  • CP ii : 고유 번호 ii를 가진 역의 이전 역을 폐쇄하고 그 역의 고유 번호를 출력한다.

입력으로 들어오는 모든 역의 고유 번호는 11 이상 1,000,0001\\,000\\,000 이하의 양의 정수다. 폐쇄 작업은 현재 설립된 역이 22개 이상일 때만 들어오며, 이미 설립된 역은 또 설립될 수 없지만 폐쇄된 역은 다시 설립될 수 있다.

출력

각 공사에 대한 출력 값을 MM개의 줄에 걸쳐서 출력한다.

예제1

  1. 예제 1

    입력
    4 4
2 7 3 5
BN 5 11
BP 3 6
CP 2
CN 7
    예상 출력
    2
7
11
6