题目描述
请实现一个数据结构，支持求区间最大值问题。
输入
第一行输入2个用空格隔开的正整数n,m。
第二行输入n个非负整数a1,a2,···,an，表示数组a中的数。
接下来m行，每行输入2个正整数(l,r)表示一次询问，询问max{ai}, 1≤i≤r。
第二行输入n个非负整数a1,a2,···,an，表示数组a中的数。
接下来m行，每行输入2个正整数(l,r)表示一次询问，询问max{ai}, 1≤i≤r。
输出
记第i次询问的答案为qi，输出1个整数
，其中⊕表示异或运算。
，其中⊕表示异或运算。 样例输入 Copy
8 8
9 3 1 7 5 6 0 8
1 6
1 5
2 7
2 6
1 8
4 8
3 7
1 8
样例输出 Copy
118
提示
【样例解释】
样例所列区间最大值答案分别为9,9,7,7,9,8,7,9
【数据范围】
对于20%的数据，1≤n≤500,1≤m≤1000。
对于100%的数据，1≤n≤5×105,1≤m≤106,1≤l≤r≤n,0≤ai≤5×105。
样例所列区间最大值答案分别为9,9,7,7,9,8,7,9
【数据范围】
对于20%的数据，1≤n≤500,1≤m≤1000。
对于100%的数据，1≤n≤5×105,1≤m≤106,1≤l≤r≤n,0≤ai≤5×105。