넥슨 사진관

NYPC 2019 · 예선

넥슨 사진관에서는 넥슨의 다양한 캐릭터들의 사진을 찍으려고 한다. 캐릭터들은 11번부터 NN번까지 번호가 붙은 NN개의 의자에 앉아 있고, 이 캐릭터들 중 연속된 자리에 앉은 캐릭터 홀수 명을 골라서 좌우대칭이 되도록 일렬로 세워 사진을 찍으려 한다. (편의를 위해, 캐릭터들은 11 이상 10910^9 이하의 정수 하나로 표현된다.)

사진을 찍을 때 캐릭터들은 의자에서 일어나 사진을 찍는 곳으로 나와서 적당한 순서로 일렬로 서서 사진을 찍고 다시 원래 자리에 돌아간다. 또한 사진을 다양하게 찍기 위해서 앉아있는 캐릭터를 바꿀 수도 있다.

좌우 대칭으로 찍어야 사진이 멋지게 찍힌다고 믿고 있다. 이를 위해 넥슨 사진관은 자리 배치를 효율적으로 하고 싶어하고 사진을 찍을 때 가운데 서는 캐릭터가 누구인지를 빨리 알아야 그 캐릭터를 중심으로 잘 맞춰서 줄을 설 수 있다.

예를 들어, 연속된 캐릭터 33, 33, 77, 55, 77, 55, 33의 사진을 찍어야 할 경우, 좌우 대칭으로 서는 방법은 37535733\,7\,5\,3\,5\,7\,3, 75333577\,5\,3\,3\,3\,5\,7, 57333755\,7\,3\,3\,3\,7\,5 등 여러가지 방법이 있으나 가운데에 서는 캐릭터는 항상 캐릭터 33이라는 것을 알 수 있다.

당신은 넥슨 사진관에서 캐릭터들을 배치하는 업무를 맡았다. 이 때 당신이 처리해야할 업무는 다음과 같다.

넥슨 사진관은 매우 바쁘기 때문에 당신은 이 일을 빠르게 처리 할 수 있어야 한다. 위의 업무들을 처리하며 이 중 가운데에 서는 캐릭터가 누구인지 계속 출력하는 프로그램을 작성하시오.

입력 형식

첫째 줄에 캐릭터와 의자의 수 NN과 업무의 수 QQ가 공백으로 구분되어 주어진다. (1N,Q1000001 \le N, Q \le 100\,000)

둘째 줄에 현재 의자에 앉아 있는 캐릭터의 번호 N개가 공백으로 구분되어 주어진다. 주어지는 수는 11 이상 10910^9이하이다.

다음 QQ개의 줄에는 세 정수 tt, aa, bb가 공백으로 구분되어 주어진다. (1t21 \le t \le 2) 이는 다음을 의미한다.

t=2t = 2인 업무를 할 때, aa번 의자 부터 bb번 의자까지의 캐릭터를 좌우 대칭으로 세울 수 있음이 보장된다. 또한, 이러한 업무가 11개 이상 있음이 보장된다.

출력 형식

t=2t = 2인 업무에 대해, aa번 의자 부터 bb번 의자까지 캐릭터를 좌우 대칭으로 세웠을 때, 가운데에 서는 캐릭터의 번호를 줄로 구분하여 출력한다.

예제

입력

7 3 3 3 7 5 7 5 3 2 1 7 1 4 6 2 3 5

출력

3 6

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞추어야 그 종류에 배정된 점수를 받을 수 있다.

종류 1: 17

N,Q1000N, Q \le 1\,000

종류 2: 57

t=2t = 2인 업무만 주어진다.

종류 3: 26

별다른 제약조건 없음.

해설