넥슨 사진관

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

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

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

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

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

• $a$번 의자에 앉은 캐릭터를 $b$로 바꾼다. (바뀐 캐릭터는 그 의자에 계속 앉아 있는다.)
• $a$번 의자부터 $b$번 의자까지 앉은 캐릭터들의 사진을 찍을 때, 가운데에 서는 캐릭터가 누구인지 알려준다. (양 끝 의자도 포함한다.)

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

입력 형식

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

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

다음 $Q$개의 줄에는 세 정수 $t$, $a$, $b$가 공백으로 구분되어 주어진다. ($1 \le t \le 2$) 이는 다음을 의미한다.

• $t = 1$: $a$번 의자에 앉은 캐릭터를 $b$로 바꾼다. ($1 \le a \le N$; $1 \le b \le 10^9$)
• $t = 2$: $a$번 의자부터 $b$번 의자까지 앉은 캐릭터들의 사진을 찍을 때, 가운데에 서는 캐릭터가 누구인지 알려준다. ($1 \le a \le b \le N$; 단, $b - a + 1$은 홀수)

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

출력 형식

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

예제

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

3
6

채점 방식

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

해설