wwgs1145行超级屎山求调，悬赏n关

// the beginning of <bits/std++.h>

// C++ includes used for precompiling -*- C++ -*-

// Copyright (C) 2003-2014 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 3, or (at your option)
// any later version.

// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.

// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
// <http://www.gnu.org/licenses/>.

/** @file stdc++.h
 *  This is an implementation file for a precompiled header.
 */

// 17.4.1.2 Headers

// C
#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdalign>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif

// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif

// the end of <bits/std++.h>

//the begining of "OILib.h"

/*
	定义了部分简便的类型缩写
	包含一部分基础数据结构
*/

namespace OILib{

#if __cplusplus <= 199711L	
	#error too old compiler bruh
#endif

	typedef long long llong ;
	typedef long double exdouble;
	typedef unsigned int uint;
	typedef unsigned long long ullong;
	
	template<typename T>
	using Function=std::function<T>;
	
	template<typename Type,uint offset=0>
	class Array{
	private:
		uint size;
		Type *arr;
		inline void ReMalloc(const uint newSize){
			Type*p=new Type[newSize]();
			if(arr!=nullptr)delete[]arr;
			arr=p;
			size=newSize;
		}
		inline void ReMalloc(const uint newSize,const Type&val){
			ReMalloc(newSize);
			for(uint i=0;i<size;i++)arr[i]=val;
		}
	public:
		Array():size(0),arr(nullptr){}
		Array(const uint size):size(0),arr(nullptr)
			{ReMalloc(size);}
		Array(const uint size,const Type&val):size(0),arr(nullptr)
			{ReMalloc(size,val);}
		Array(const Array&obj):size(0),arr(nullptr)
		{
			if(this==&obj)return;
			ReMalloc(obj.size);
			for(uint i=0;i<size;i++)arr[i]=obj.arr[i];
		}
		Array(const std::initializer_list<Type>&li):size(0),arr(nullptr){
			ReMalloc(li.size());
			uint i=0;
			for(
				typename std::initializer_list<Type>::iterator it=li.begin();
				it!=li.end();
				it++,i++
			)arr[i]=(*it);
		}
		Array(const std::vector<Type>&v):size(0),arr(nullptr){
			ReMalloc(v.size());
			for(uint i=0;i<size;i++)arr[i]=v[i];
		}
		Array(const Type*newArr,const int newSize):size(0),arr(nullptr){
			ReMalloc(newSize);
			for(uint i=0;i<size;i++)arr[i]=newArr[i];
		}
		Array(const uint size,std::istream&stream):size(0),arr(nullptr){
			ReMalloc(size);
			stream>>(*this);
		}
//		Array(const uint size,Freader&reader):size(0),arr(nullptr){
//			ReMalloc(size);
//			for(uint i=0;i<size;i++)reader>>reader[i];
//		}
		
		Array&operator=(const Array&obj){
			if(this==&obj)return *this;
			ReMalloc(obj.size);
			for(uint i=0;i<size;i++)arr[i]=obj.arr[i];
			return *this;
		}
		
		~Array(){
			size=0;
			if(arr!=nullptr)delete[]arr;
			arr=nullptr;
		}
		bool operator==(const Array&obj)const{
			if(this==&obj)return true;
			if(size!=obj.size)return false;
			for(uint i=0;i<size;i++)
				if(!(arr[i]==obj[i]))
					return false;
			return true;
		}
		void ReSize(const uint newSize){
			Array newArr(newSize);
			for(uint i=0;i<std::min(newSize,size);i++)newArr[i]=arr[i];
			(*this)=newArr;
		}
		inline Type&operator[](const uint index){return arr[index-offset];}
		inline const Type&operator[](const uint index)const{return arr[index-offset];}
		inline uint GetSize()const{return size;}
		inline uint GetOffset()const{return offset;}
		
		friend class Iterator;
		class Iterator:public std::iterator<std::random_access_iterator_tag,Type>{
			friend class Array;
			Type *p;
		public:
			Iterator():p(nullptr){}
			Iterator(const Iterator&obj):p(obj.p){}
			~Iterator(){}
			
			Iterator&operator=(const Iterator&obj){p=obj.p;return *this;}
			Type&operator*()const{return *p;}
			
			Iterator&operator++(){p++;return *this;}
			Iterator&operator--(){p--;return *this;}
			Iterator operator++(int){Iterator it(*this);p++;return it;}
			Iterator operator--(int){Iterator it(*this);p--;return it;}
			Iterator&operator+=(const uint i){p+=i;return *this;}
			Iterator&operator-=(const uint i){p-=i;return *this;}
			Iterator operator+(const uint i)const{Iterator it(*this);it.p+=i;return it;}
			Iterator operator-(const uint i)const{Iterator it(*this);it.p-=i;return it;}
			uint operator-(const Iterator&obj)const{return (uint)(p>obj.p?p-obj.p:obj.p-p);}
			
			bool operator!=(const Iterator&obj)const{return p!=obj.p;}
			bool operator==(const Iterator&obj)const{return p==obj.p;}
			bool operator<(const Iterator&obj)const{return p<obj.p;}
			bool operator>(const Iterator&obj)const{return p>obj.p;}
			bool operator<=(const Iterator&obj)const{return p<=obj.p;}
			bool operator>=(const Iterator&obj)const{return p>=obj.p;}
		};
		friend class ConstIterator;
		class ConstIterator:public std::iterator<std::random_access_iterator_tag,Type>{
			friend class Array;
			Type *p;
		public:
			ConstIterator():p(nullptr){}
			ConstIterator(const Iterator&obj):p(obj.p){}
			~ConstIterator(){}
			
			ConstIterator&operator=(const Iterator&obj){p=obj.p;return *this;}
			const Type&operator*()const{return *p;}
			
			ConstIterator&operator++(){p++;return *this;}
			ConstIterator&operator--(){p--;return *this;}
			ConstIterator operator++(int){ConstIterator it(*this);p++;return it;}
			ConstIterator operator--(int){ConstIterator it(*this);p--;return it;}
			ConstIterator&operator+=(const uint i){p+=i;return *this;}
			ConstIterator&operator-=(const uint i){p-=i;return *this;}
			ConstIterator operator+(const uint i)const{ConstIterator it(*this);it.p+=i;return it;}
			ConstIterator operator-(const uint i)const{ConstIterator it(*this);it.p-=i;return it;}
			uint operator-(const ConstIterator&obj)const{return (uint)(p>obj.p?p-obj.p:obj.p-p);}
			
			bool operator!=(const ConstIterator&obj)const{return p!=obj.p;}
			bool operator==(const ConstIterator&obj)const{return p==obj.p;}
			bool operator<(const ConstIterator&obj)const{return p<obj.p;}
			bool operator>(const ConstIterator&obj)const{return p>obj.p;}
			bool operator<=(const ConstIterator&obj)const{return p<=obj.p;}
			bool operator>=(const ConstIterator&obj)const{return p>=obj.p;}
		};
		Iterator Begin(){Iterator it;it.p=&arr[0];return it;}
		Iterator End(){Iterator it;it.p=&arr[size-1]+1;return it;}
		inline Iterator begin(){return Begin();}
		inline Iterator end(){return End();}
		ConstIterator Begin()const{ConstIterator it;it.p=&arr[0];return it;}
		ConstIterator End()const{ConstIterator it;it.p=&arr[size-1]+1;return it;}
		inline ConstIterator begin()const{return Begin();}
		inline ConstIterator end()const{return End();}
		
		friend std::istream&operator>>(std::istream&stream,Array&arr){
			for(auto&val:arr)stream>>val;
			return stream;
		}
		friend std::ostream&operator<<(std::ostream&stream,const Array&arr){
			for(auto&val:arr)stream<<val<<' ';
			return stream;
		}
	};
	
	template<typename Type>
	class List{
	private:
		struct Node{
			Node():val(Type()),pre(nullptr),next(nullptr){}
			Node(const Type&val):val(val),pre(nullptr),next(nullptr){}
			~Node(){
				if(pre!=nullptr)pre->next=next;
				if(next!=nullptr)next->pre=pre;
				val=Type();
				pre=nullptr;next=nullptr;
			}
			Type val;
			Node *pre,*next;
		};
		uint length;
		Node *head,*tail;
		Node* InsertBack(Node*p,const Type&val){
			Node *newNode=new Node(val);
			if(p==nullptr){
				if(head==nullptr){
					head=tail=newNode;
				}else{
					newNode->next=head;
					head->pre=newNode;
					head=newNode;
				}
			}else{
				if(p==tail){
					p->next=newNode;
					newNode->pre=p;
					tail=newNode;
				}else{
					Node *pre=p,*next=p->next;
					pre->next=newNode;
					newNode->pre=pre;
					newNode->next=next;
					next->pre=newNode;
				}
			}
			length++;
			return newNode;
		}
		Node* InsertFront(Node *p,const Type&val){
			if(p==nullptr)return InsertBack(tail,val);
			return InsertBack(p->pre,val);
		}
		void Erase(Node*p){
			if(p==head&&p==tail)head=tail=nullptr;
			else if(p==head)head=p->next;
			else if(p==tail)tail=p->pre;
			length--;
			delete p;
		}
	public:
		List():length(0),head(nullptr),tail(nullptr){}
		List(const Array<Type>&arr):length(0),head(nullptr),tail(nullptr)
		{
			for(
				typename Array<Type>::ConstIterator it=arr.Begin();
				it!=arr.End();
				it++
			)InsertBack(tail,*it);
		}
		~List(){while(length)Erase(head);}
		friend class Iterator;
		class Iterator:public std::iterator<std::bidirectional_iterator_tag,Type>
		{
			friend class List;
			Node *p;
		public:
			Iterator():p(nullptr){}
			Iterator(const Iterator&obj):p(obj.p){}
			~Iterator(){}
			Iterator&operator=(const Iterator&obj){p=obj.p;return *this;}
			
			Type&operator*()const{return p->val;}
			
			Iterator&operator++(){p=p->next;return *this;}
			Iterator&operator--(){p=p->pre;return *this;}
			Iterator operator++(int){Iterator it(*this);p=p->next;return it;}
			Iterator operator--(int){Iterator it(*this);p=p->pre;return it;}
			
			bool operator!=(const Iterator&obj)const{return p!=obj.p;}
			bool operator==(const Iterator&obj)const{return p==obj.p;}
		};
		friend class ConstIterator;
		class ConstIterator:public std::iterator<std::bidirectional_iterator_tag,Type>
		{
			friend class List;
			Node *p;
		public:
			ConstIterator():p(nullptr){}
			ConstIterator(const ConstIterator&obj):p(obj.p){}
			~ConstIterator(){}
			ConstIterator&operator=(const ConstIterator&obj){p=obj.p;return *this;}
			
			const Type&operator*()const{return p->val;}
			
			ConstIterator&operator++(){p=p->next;return *this;}
			ConstIterator&operator--(){p=p->pre;return *this;}
			ConstIterator operator++(int){ConstIterator it(*this);p=p->next;return it;}
			ConstIterator operator--(int){ConstIterator it(*this);p=p->pre;return it;}
			
			bool operator!=(const ConstIterator&obj)const{return p!=obj.p;}
			bool operator==(const ConstIterator&obj)const{return p==obj.p;}
		};
	private:
		Iterator MakeIterator(Node*p){Iterator it;it.p=p;return it;}
		ConstIterator MakeIterator(Node*p)const{ConstIterator it;it.p=p;return it;}
	public:
		inline Iterator Begin(){return MakeIterator(head);}
		inline Iterator End(){return MakeIterator(nullptr);}
		inline Iterator begin(){return Begin();}
		inline Iterator end(){return End();}
		inline ConstIterator Begin()const{return MakeIterator(head);}
		inline ConstIterator End()const{return MakeIterator(nullptr);}
		inline ConstIterator begin()const{return Begin();}
		inline ConstIterator end()const{return End();}
		
		inline Iterator InsertFront(Iterator it,const Type&val){return MakeIterator(InsertFront(it.p,val));}
		inline Iterator InsertBack(Iterator it,const Type&val){return MakeIterator(InsertBack(it.p,val));}
		inline Iterator PushFront(const Type&val){return MakeIterator(InsertFront(head,val));}
		inline Iterator PushBack(const Type&val){return MakeIterator(InsertBack(tail,val));}
		inline void Erase(const Iterator&it){Erase(it.p);}
	};
	template<typename Val,uint offset=0>
	class Graph{
	private:
		Array<List<std::pair<uint,Val> >,offset>edge;
	public:
		Graph(){}
		Graph(const uint size):edge(Array<List<std::pair<uint,Val> >,offset>(size)){}
		void ReSize(const uint newSize){edge.ReSize(newSize);}
		
		void AddEdge(const uint u,const uint v){edge[u].PushBack(std::make_pair(v,Val()));}
		void AddEdge(const uint u,const uint v,const Val&val){edge[u].PushBack(std::make_pair(v,val));}
		List<std::pair<uint,Val> >&Edge(const uint u){return edge[u];}
		
		const List<std::pair<uint,Val> >&GetEdge(const uint u)const{return edge[u];}
	};
	template<uint offset>
	class Graph<void,offset>{
	private:
		Array<List<uint>,offset>edge;
	public:
		Graph(){}
		Graph(const uint size):edge(Array<List<uint>,0>(size)){}
		void ReSize(const uint newSize){edge.ReSize(newSize);}
		
		void AddEdge(const uint u,const uint v){edge[u].PushBack(v);}
		List<uint>&Edge(const uint u){return edge[u];}
		
		const List<uint>&GetEdge(const uint u)const{return edge[u];}
	};
	template<typename Type>
	class SparseTable{
	private:
		Function<Type(Type,Type)>Func;
		Array<Array<std::pair<Type,Type> > >f;
		void MakeTable(const Array<Type>&arr){
			f.ReSize(std::log2(arr.GetSize())+1);
			f[0].ReSize(arr.GetSize());
			for(uint i=0;i<arr.GetSize();i++)f[0][i]=std::make_pair(arr[i],i);
			for(uint j=1;(1u<<j)<=arr.GetSize();j++){
				f[j].ReSize(arr.GetSize()-(1<<j)+1);
				for(uint i=0;i<arr.GetSize()-(1<<j)+1;i++){
					if(Func(f[j-1][i].first,f[j-1][i+(1<<(j-1))].first)==f[j-1][i].first)
						f[j][i]=std::make_pair(f[j-1][i].first,f[j-1][i].second);
					else
						f[j][i]=std::make_pair(f[j-1][i+(1<<(j-1))].first,f[j-1][i+(1<<(j-1))].second);
				}
			}
		}
	public:
		SparseTable(){}
		SparseTable(const SparseTable&obj):Func(obj.Func),f(obj.f){}
		SparseTable(const Array<Type>&arr,const Function<Type(Type,Type)>&Func):Func(Func)
			{MakeTable(arr);}
		uint RMQ(const uint l,const uint r)const{
			uint len=log2(r-l+1);
			if(Func(f[len][l].first,f[len][r-(1<<len)+1].first)==f[len][l].first){
				return f[len][l].second;
			}else{
				return f[len][r-(1<<len)+1].second;
			}
		}
	};
	template<typename Type,uint offset=0>
	class Discretizationer{
	private:
		std::unordered_map<Type,uint>m;
		std::unordered_map<uint,Type>rm;
	public:
		Discretizationer(){}
		Discretizationer(const Array<Type>&arr){Discretization(arr);}
		
		void Discretization(Array<Type>arr){
			m.clear();rm.clear();
			sort(arr.Begin(),arr.End());
			for(const Type&val:arr)
				if(m.find(val)==m.end())
					rm[m[val]=m.size()-1u+offset]=val;
		}
		uint IndexMax()const{return m.size();}
		uint GetIndex(const Type&val)const{return *(m.find(val));}
		Type Object(const uint ind)const{return *(rm.find(ind));}
		const Type& GetObject(const uint ind)const{return *(rm.find(ind));}
	};
//	template<typename Type,typename Tag>
//	class Trie{
//	private:
//		struct Node{
//			Node(){}
//			Node(const Type&val):val(val){}
//			~Node(){
//				val=Type();
//				tag=Tag();
//				for(auto it=child.begin();it!=child.end();it++)
//					delete (*it).second;
//				child.clear();
//			}
//			Type val;
//			Tag tag;
//			std::unordered_map<Type,Node*>child;
//			
//			Node* Malloc(const Type&val){
//				if(child[val]==nullptr)child[val]=new Node(val);
//				return child[val];
//			}
//			Node* GetChild(const Type&val){return child[val];}
//			const Node* GetChild(const Type&val)const{return child[val];}
//		};
//		std::vector<Node*>perRoot;
//	public:
//		Trie(){perRoot.push_back(new Node());}
//		void Insert(const Array<Type>&arr,const Tag&tag,const uint ver=0){
//			Node *u=perRoot[ver];
//			for(auto it=arr.Begin();it!=arr.End();it++)
//				u=u->Malloc(*it);
//			u->tag+=tag;
//		}
//		uint PerInsert(const Array<Type>&arr,const Tag&tag,const uint ver=0){
//			Node *u=perRoot[ver];
//			for(auto it=arr.Begin();it!=arr.End();it++)
//				u=u->Malloc(*it);
//			u->tag+=tag;
//		}
//	};
	template<typename Type>
	class Range{
	public:
		Type l,r;
		Range(){}
		Range(const Type&l,const Type&r):l(l),r(r){}
	private:
		friend class Iterator;
		class IteratorBase:public std::iterator<std::bidirectional_iterator_tag,Type>
		{
		protected:
			friend class Range;
			Type now;
		public:
			IteratorBase(){}
			IteratorBase(const IteratorBase&obj):now(obj.now){}
			~IteratorBase(){}
			IteratorBase&operator=(const IteratorBase&obj){now=obj.now;return *this;}		
			IteratorBase&operator++(){now++;return *this;}
			IteratorBase&operator--(){now--;return *this;}
			IteratorBase operator++(int){IteratorBase it(*this);now++;return it;}
			IteratorBase operator--(int){IteratorBase it(*this);now--;return it;}
			
			bool operator!=(const IteratorBase&obj)const{return now!=obj.now;}
			bool operator==(const IteratorBase&obj)const{return now==obj.now;}
		};
	public:
		class Iterator:public IteratorBase{public:Type&operator*(){return this->now;}};
		class ConstIterator:public IteratorBase{public:const Type&operator*()const{return this->now;}};
	private:
		Iterator MakeIterator(const Type&val){Iterator it;it.now=val;return it;}
		ConstIterator MakeIterator(const Type&val)const{ConstIterator it;it.now=val;return it;}
	public:
		inline Iterator Begin(){return MakeIterator(l);}
		inline Iterator End(){Type temp=r;return MakeIterator(++temp);}
		inline Iterator begin(){return Begin();}
		inline Iterator end(){return End();}
		inline ConstIterator Begin()const{return MakeIterator(l);}
		inline ConstIterator End()const{Type temp=r;return MakeIterator(++temp);}
		inline ConstIterator begin()const{return Begin();}
		inline ConstIterator end()const{return End();}
	};
	template<typename Type>
	Range<Type>MakeRange(const Type&l,const Type&r){return Range<Type>(l,r);}
	template<typename Integer>
	Array<bool>GetBits(Integer val){
		constexpr uint length=sizeof(Integer)*8;
		std::bitset<length>bitSet(val);
		Array<bool>bits(length);
		for(uint i=0;i<length;i++)bits[i]=bitSet[length-1-i];
		return bits;
	}
}
namespace OILib{
	const int Max=100000;
	const int Mod=1e9;
}

//the end of "OILib.h"

using namespace std;
using namespace OILib;

template<typename Type>
class SegmentTree_OnlyReturnNode{
private:
	struct Node{
		Node():lc(nullptr),rc(nullptr){}
		Node(const llong l,const llong r):l(l),r(r),lc(nullptr),rc(nullptr),val(Type()){}
		~Node(){
			if(lc!=nullptr)delete lc;
			if(rc!=nullptr)delete rc;
		}
		llong l,r;
		Node *lc,*rc;
		Type val;
		inline llong GetMiddle(){return (l+r)/2;}
	}*root;
	Node* NewNode(const llong l,const llong r){return new Node(l,r);}
	Node* CopyNode(Node *p){
		Node *newP=new Node();
		(*newP)=(*p);
		return newP;
	}
	Node* CreateLeft(Node *p){
		if(p->lc==nullptr){
			llong l=p->l,r=p->r;
			p->lc=NewNode(l,(l+r)/2);
		}
		return p->lc;
	}
	Node* CreateRight(Node *p){
		if(p->rc==nullptr){
			llong l=p->l,r=p->r;
			p->rc=NewNode((l+r)/2+1,r);
		}
		return p->rc;
	}
	void Create(Node *p){
		CreateLeft(p);
		CreateRight(p);
	}
	std::vector<Type*>Query(Node *p,const llong pos){
		if(pos<(p->l)||(p->r)<pos)return std::vector<Type*>();
		std::vector<Type*>v;
		v.push_back(&(p->val));
		if(p->l==p->r)return v;
		if(pos<=p->GetMiddle()){
			auto v2=Query(CreateLeft(p),pos);
			v.insert(v.end(),v2.begin(),v2.end());
		}else{
			auto v2=Query(CreateRight(p),pos);
			v.insert(v.end(),v2.begin(),v2.end());
		}
		return v;
	}
	std::vector<Type*> Query(Node *p,const llong l,const llong r){
		if(r<(p->l)||(p->r)<l)return vector<Type*>();
		std::vector<Type*>v,v1,v2;
//cout<<p->l<<','<<p->r<<'\n';
		if(l<=(p->l)&&(p->r)<=r){
			v.push_back(&(p->val));
			return v;
		}
		v1=Query(p->lc,l,r);
		v2=Query(p->rc,l,r);
		v.insert(v.end(),v1.begin(),v1.end());
		v.insert(v.end(),v2.begin(),v2.end());
		return v;
	}
public:
	SegmentTree_OnlyReturnNode():root(nullptr){}
	SegmentTree_OnlyReturnNode(const int l,const int r):root(new Node(l,r)){}
	~SegmentTree_OnlyReturnNode(){if(root!=nullptr)delete root;}
	std::vector<Type*> Query(const llong pos){return Query(root,pos);}
	std::vector<Type*> Query(const llong l,const llong r){return Query(root,l,r);}
};
template<typename Type>
class AVLTree{
private:
	struct Node{
		Node():prt(nullptr),lc(nullptr),rc(nullptr),size(1),cnt(1),val(Type()){}
		Node(const Type&val):prt(nullptr),lc(nullptr),rc(nullptr),size(1),cnt(1),val(val){}
		Node *prt,*lc,*rc;
		uint size;
		uint cnt;
		Type val;
	}*root;
	void PushUp(Node *x){
		x->size=x->cnt;
		if(x->lc!=nullptr)x->size+=x->lc->size;
		if(x->rc!=nullptr)x->size+=x->rc->size;
	}
	void Zig(Node *x){
		Node *y=x->prt;
		if(y==nullptr)return;
		Node *prt=y->prt;
		Node *t1=x->lc,*t2=x->rc,*t3=y->rc;
		if(t1!=nullptr)t1->prt=x;
		if(t2!=nullptr)t2->prt=y;
		if(t3!=nullptr)t3->prt=y;
		x->lc=t1,x->rc=y,x->prt=prt;
		y->lc=t2,y->rc=t3,y->prt=x;
		if(prt!=nullptr){
			if(prt->lc==y)
				prt->lc=x;
			else
				prt->rc=x;
		}
		PushUp(x);PushUp(y);
		if(prt!=nullptr)PushUp(prt);
	}
	void Zag(Node *y){
		Node *x=y->prt;
		if(x==nullptr)return;
		Node *prt=x->prt;
		Node *t1=x->lc,*t2=y->lc,*t3=y->rc;
		if(t1!=nullptr)t1->prt=x;
		if(t2!=nullptr)t2->prt=x;
		if(t3!=nullptr)t3->prt=y;
		x->lc=t1,x->rc=t2,x->prt=y;
		y->lc=x,y->rc=t3,y->prt=prt;
		if(prt!=nullptr){
			if(prt->lc==x)
				prt->lc=y;
			else
				prt->rc=y;
		}
		PushUp(x);PushUp(y);
		if(prt!=nullptr)PushUp(prt);
	}
	void Rotate(Node *p){
		if(p->prt->lc==p)Zig(p);
		else Zag(p);
	}
	Node* Splay(Node *p){
		while(p->prt!=nullptr){
			if(p->prt->prt==nullptr){
				Rotate(p);
			}else{
				if(p->prt->lc==p){
					if(p->prt->prt->lc==p->prt){
						Rotate(p->prt);Rotate(p);
					}else{
						Rotate(p);Rotate(p);
					}
				}else{
					if(p->prt->prt->lc==p->prt){
						Rotate(p);Rotate(p);
					}else{
						Rotate(p->prt);Rotate(p);
					}
				}
			}
		}
		return p;
	}
	Node* Find(const Type&val){
		Node *now=root;
		while(now!=nullptr){
			if(val<now->val){
				now=now->lc;
			}else if(val==now->val){
				return root=Splay(now);
			}else{
				now=now->rc;
			}
		}
		return now;
	}
	Node* FindMax(Node*root){
		Node *now=root;
		while(now->rc!=nullptr)now=now->rc;
		return Splay(now);
	}
	Node* FindMin(Node*root){
		Node *now=root;
		while(now->lc!=nullptr)now=now->lc;
		return Splay(now);
	}
public:
	AVLTree():root(nullptr){}
	void Insert(const Type&val){
		if(root==nullptr){
			root=new Node(val);
			return;
		}
		Node *p=Find(val);
		if(p!=nullptr){
			p->cnt++;
			p->size++;
			return;
		}
		Node *now=root;
		while(true){
			if(val<=now->val){
				if(now->lc==nullptr)break;
				now=now->lc;
			}else{
				if(now->rc==nullptr)break;
				now=now->rc;
			}
		}
		if(val<now->val){
			now->lc=new Node(val);
			now->lc->prt=now;
			PushUp(now);
			root=Splay(now->lc);
		}else{
			now->rc=new Node(val);
			now->rc->prt=now;
			PushUp(now);
			root=Splay(now->rc);
		}
	}
	void Delete(const Type&val){
		Node *p=Find(val);
		root=Splay(p);
		p->cnt--;
		if(p->cnt>0)return;
		if(p->lc==nullptr&&p->rc==nullptr){
			root=nullptr;
		}else if(p->lc==nullptr){
			p->rc->prt=nullptr;
			root=p->rc;
		}else if(p->rc==nullptr){
			p->lc->prt=nullptr;
			root=p->lc;
		}else{
			p->lc->prt=nullptr;
			p->rc->prt=nullptr;
			Node *pl=FindMax(p->lc);
			pl->rc=p->rc;
			p->rc->prt=pl;
			root=pl;
			PushUp(pl);
		}
		delete p;
	}
	bool IsExist(const Type&val){
		if(Find(val)==nullptr)return false;
		return true;
	}
	uint CountRank(const Type&val){
		Node *now=root;
		uint ans=0;
		while(now!=nullptr){
			if(val<now->val){
				now=now->lc;
			}else if(val==now->val){
				root=Splay(now);
				if(now->lc==nullptr)return 1;
				else return now->lc->size+1;
			}else{
				if(now->lc==nullptr)ans+=now->cnt;
				else ans+=now->lc->size+now->cnt;
				now=now->rc;
			}
		}
		return ans+1;
	}
	Type FindKth(uint rank){
		Node *now=root;
		while(now!=nullptr){
			if(rank<=(now->lc==nullptr?0:now->lc->size)){
				now=now->lc;
			}else if(rank<=(now->lc==nullptr?0:now->lc->size)+now->cnt){
				root=Splay(now);
				return now->val;
			}else{
				rank-=(now->lc==nullptr?0:now->lc->size)+now->cnt;
				now=now->rc;
			}
		}
		return Type();
	}
	Type FindPre(const Type&val){
		Insert(val);
		Node *p=Find(val);
		if(p->lc==nullptr)return INT_MIN;
		p=p->lc;
		while(p->rc!=nullptr)p=p->rc;
		Delete(val);
		return p->val;
	}
	Type FindSuc(const Type&val){
		Insert(val);
		Node *p=Find(val);
		if(p->rc==nullptr)return INT_MAX;
		p=p->rc;
		while(p->lc!=nullptr)p=p->lc;
		Delete(val);
		return p->val;
	}
	Type FindMax(){
		Node *now=root;
		while(now->rc!=nullptr)now=now->rc;
		return now->val;
	}
	Type FindMin(){
		Node *now=root;
		while(now->lc!=nullptr)now=now->lc;
		return now->val;
	}
	uint GetSize(){return root->sum;}
};
bool CountIsExist(const vector<AVLTree<int>*>&v,const int k){
	for(auto pt:v)
		if((*pt).IsExist(k))
			return true;
	return false;
}
int CountRank(const vector<AVLTree<int>*>&v,const int k){
	int ans=0;
	for(auto pt:v)
		ans+=(*pt).CountRank(k)-1;
	
	return ans+1;
}
int CountMax(const vector<AVLTree<int>*>&v){
	int ans=INT_MIN;
	for(auto pt:v)
		ans=max(ans,(*pt).FindMax());
	return ans;
}
int CountMin(const vector<AVLTree<int>*>&v){
	int ans=INT_MAX;
	for(auto pt:v)
		ans=min(ans,(*pt).FindMin());
	return ans;
}
int CountKth(const vector<AVLTree<int>*>&v,const int k){
	int l=CountMin(v),r=CountMax(v),mid;
	while(l<r){
		mid=(l+r+1)/2;
		if(k<CountRank(v,mid))r=mid-1;
		else if(k<CountRank(v,mid+1)){
			return mid;
		}else l=mid;
	}
	return l;
}
template<size_t bufSize>
class Freader{
public:
	Freader():lp(buf),rp(buf){}
	char GetChar(){
		if(lp==rp){
			lp=buf;
			rp=lp+fread(buf,sizeof(char),bufSize,stdin);
			if(lp==rp)return EOF;
		}
		return *lp++;
	}
	
	friend Freader&operator>>(Freader&reader,char&obj){
		obj=reader.GetChar();
		while((!IsLawful(obj))&&(obj!=EOF))
			obj=reader.GetChar();
		return reader;
	}
	friend Freader&operator>>(Freader&reader,int&obj){
		obj=0;
		bool isNega=false;
		char c=reader.GetChar();
		while((!IsDigit(c))&&(c!=EOF)){
			if(c=='-')isNega=true;
			c=reader.GetChar();
		}
		while((IsDigit(c))&&(c!=EOF)){
			obj=(obj*10)+(int)(c-'0');
			c=reader.GetChar();
		}
		if(isNega)obj=-obj;
		return reader;
	}
	friend Freader&operator>>(Freader&reader,llong&obj){
		obj=0;
		bool isNega=false;
		char c=reader.GetChar();
		while((!IsDigit(c))&&(c!=EOF)){
			if(c=='-')isNega=true;
			c=reader.GetChar();
		}
		while((IsDigit(c))&&(c!=EOF)){
			obj=(obj*10)+(int)(c-'0');
			c=reader.GetChar();
		}
		return reader;
	}
	friend Freader&operator>>(Freader&reader,uint&obj){
		obj=0;
		char c=reader.GetChar();
		while((!IsDigit(c))&&(c!=EOF))c=reader.GetChar();
		while((IsDigit(c))&&(c!=EOF)){
			obj=(obj*10)+(int)(c-'0');
			c=reader.GetChar();
		}
		return reader;
	}
	friend Freader&operator>>(Freader&reader,ullong&obj){
		obj=0;
		char c=reader.GetChar();
		while((!IsDigit(c))&&(c!=EOF))c=reader.GetChar();
		while((IsDigit(c))&&(c!=EOF)){
			obj=(obj*10)+(int)(c-'0');
			c=reader.GetChar();
		}
		return reader;
	}
	friend Freader&operator>>(Freader&reader,string&obj){
		char c=reader.GetChar();
		obj=string();
		while(IsLawful(c)&&(c!=EOF)){
			obj+=c;
			c=reader.GetChar();
		}
		return reader;
	}
	
private:
	
	static bool IsLawful(const char c){
		if(c==' '||c=='\n'||c=='\r')return false;
		return true;
	}
	static bool IsDigit(const char c){
		if('0'<=c&&c<='9')return true;
		return false;
	}
	char buf[bufSize];
	char *lp,*rp;
};
Freader<1<<20>Fin;
template<size_t bufSize>
class Fwriter{
public:
	Fwriter():p(buf){}
	~Fwriter(){Flush();}
	
	void PutChar(const char c){
		*(p++)=c;
		if(p>=buf+bufSize)Flush();
	}
	
	friend Fwriter&operator<<(Fwriter&writer,const char obj){
		writer.PutChar(obj);
		return writer;
	}
	friend Fwriter&operator<<(Fwriter&writer,const int obj){
		int now=abs(obj);
		string s;
		while(now>0){
			s+=(now%10)+'0';
			now/=10;
		}
		if(obj<0)writer.PutChar('-');
		for(int i=s.length()-1;i>=0;i--)
			writer.PutChar(s[i]);
		return writer;
	}
	friend Fwriter&operator<<(Fwriter&writer,const string obj){
		for(size_t i=0;i<obj.length();i++)
			writer.PutChar(obj[i]);
		return writer;
	}
private:
	void Flush(){
		fwrite(buf,p-buf,1,stdout);
		p=buf;
	}
	char buf[bufSize];
	char *p;
};
Fwriter<1<<20>Fout;
#define cin Fin
#define cout Fout
void Solve(){
	int n,m;
	cin>>n>>m;
	SegmentTree_OnlyReturnNode<AVLTree<int> >tree(1,n);
	Array<int,1>arr(n);
	for(auto i:MakeRange(1,n)){
		cin>>arr[i];
		vector<AVLTree<int>*>v=tree.Query(i);
		for(auto pt:v)(*pt).Insert(arr[i]);
	}
	for(auto i:MakeRange(1,m)){
		int opt;
		cin>>opt;
		if(opt==1){
			int l,r,k;
			cin>>l>>r>>k;
			int ans=0;
			vector<AVLTree<int>*>v=tree.Query(l,r);
			for(auto pt:v)
				ans+=(*pt).CountRank(k)-1;
			cout<<ans+1<<'\n';
		}else if(opt==2){
			int l,r,k;
			cin>>l>>r>>k;
			cout<<CountKth(tree.Query(l,r),k)<<'\n';
		}else if(opt==3){
			int pos,k;
			cin>>pos>>k;
			int bef=arr[pos];
			arr[pos]=k;
			vector<AVLTree<int>*>v=tree.Query(pos);
			for(auto pt:v){
				(*pt).Delete(bef);
				(*pt).Insert(k);
			}
		}else if(opt==4){
			int l,r,k;
			cin>>l>>r>>k;
			vector<AVLTree<int>*>v=tree.Query(l,r);
			int ans=INT_MIN;
			for(auto pt:v)ans=max(ans,(*pt).FindPre(k));
			cout<<ans<<'\n';
		}else if(opt==5){
			int l,r,k;
			cin>>l>>r>>k;
			vector<AVLTree<int>*>v=tree.Query(l,r);
			int ans=INT_MAX;
			for(auto pt:v)ans=min(ans,(*pt).FindSuc(k));
			cout<<ans<<'\n';
		}
	}
}
int main(){
//	freopen("P3380_1.in","r",stdin);
//	freopen("P3380_1.ans","w",stdout);
//	ios::sync_with_stdio(false);
//	cin.tie(0);cout.tie(0);
	Solve();
	return 0;
}