자연수로 이루어진 길이 N인 수열이 있다.

Q개의 질의가 들어온다. 들어오는 질의의 종류는 다음과 같다.

• 0 i j k --- 수열에서 i번째 원소와 j번째 원소 사이에 있는 수들 중 k번째로 작은 수는 무엇인지 출력한다.
• 1 i k --- 수열에서 i번째 원소의 값을 k로 바꾼다.

입력

• 첫 줄에 수열의 길이와 질의의 개수를 나타내는 자연수 N, Q가 주어진다. (1 ≤ N ≤ 50,000, 1 ≤ Q ≤ 10,000)
• 둘째 줄에 수열의 정보를 나타내는 N개의 자연수가 주어진다. (수열의 원소 ≤ 10^9)
• 셋째 줄부터 Q개의 줄에 위 형식대로 질의가 주어진다. (1 ≤ i, j ≤ N , 1 ≤ k ≤ 10^9)

출력

입출력 예

입력

9 5
6 9 9 7 10 4 3 4 9
1 8 7
0 4 8 2
1 5 10
1 7 2
0 1 9 5

출력

4
7

출처: tamaki