[중등부] 2021 KOI 1차 2교시 실기 대비 모의고사 2회

정올국 외곽 지역에는 일방통행 시티라는 도시가 있다.

일방통행 시티라는 지명에 걸맞게, 이 지역은 모든 주도로가 일방통행이다. 구체적으로는, 1번 마을부터 n번 마을까지가 있는데, 각 i번째 마을은 i+1번째 마을로 향해 갈 수 있는 일방 통행 도로가 있고, 예외적으로 n번 마을만 1번 마을로 일방통행으로 연결 되어 있다. 쉽게 말해, 기본적으로 고리 모양의 도시이다. 

이 지역 사람들은 지나칠 정도로 여유로운 것을 좋아하는데, 그들의 하루 일과는 자기 마을에서 도로를 따라 갈 수 있는 가장 먼 곳으로 이동하면서 주변 경치를 즐기는 것이다.

일방통행 시티의 시장인 태구는 매달 다음 3가지 중 한 가지 개발사항을 추진한다.

• 1 x w : x번 마을에서 가장 먼 마을을 y라고 하자. y로부터 길이 w의 도로를 만들고, 그 끝에 새로운 마을을 짓는다.

• 2 x w : x번 마을에 길이 w의 도로를 만들고, 그 끝에 새로운 마을을 짓는다.

• 3 x : x번 마을에서 가장 먼 마을을 y라고 하자. y마을을 철거하고, y마을로 가는 도로도 철거한다. 단 이 정책으로 1번부터 n번 마을은 사라지지 않음을 보장한다.

태구 시장은 또한 각 마을로부터 가장 먼 마을간의 거리도 알고 싶었다. 그래서 다음과 같은 조사를 하기도 한다.

• ​4 x : x번 마을에서 가장 먼 마을을 y라고 하자. x와 y간의 거리를 알아본다.

태구의 오른팔인 당신은, 일방통행 시티를 시뮬레이트하는 프로그램을 만들기로 하였다. 각 4가지 사항에 대한 일방통행 시티 시뮬레이터를 프로그래밍하라.​ 

※만약 가장 먼 거리의 마을이 여러개라면, 가장 최근에 추가된 마을을 고려한다.