题目描述

贪玩的小t又来出题了…… 小t给你一个长度为 $n$ 的序列，并且给你提出了 $q$ 个问题，给你一个区间 [$l$, $r$],保证 $1 \\leq l \\leq r \\leq n$,请你依次回答出这个区间所有数字的最大值、最小值、异或和、最大公约数。

输入格式

第一行输入两个数字 $n$ 和 $q$，表示序列的长度和询问的个数。 第二行 $n$ 个数字，表示序列的每一个数字。 接下来 $q$ 行，每行两个数字 $l$ 和 $r$，表示询问的区间。 $1 \\leq n,q\\leq 2 \ imes 10^5$ $1 \\leq l \\leq r \\leq n$ $1 \\leq a_i \\leq 10^9$

输出格式

输出 $q$ 行，依次输出每次询问区间的最大值、最小值、异或和、最大公约数。

样例

5 2 
4 6 7 8 9 
1 2 
1 5

6 4 2 2 
9 4 4 1

提示

by 励翔 2022春第三次排位赛