题目背景

珂朵莉又双叒叕给你了一个序列 $a$。

“***！”Xudongning 生气地说，“***好你个珂朵莉，亿天天动不动就给我亿个序列，造的恨死珂朵莉了。”

好基友 Anli_li 朝 Xudongning 翻了个白眼，说道：“你不会你就别说人家行吗？看人家多可爱呀。”

Xudongning 都快要吐出来了：“***的可癌又有什么用？还不是给我增加了做题负担？？? ”

Anli_li 说到：“玩不起就玩不起，竟然还骂人，好一个九年义务教育的优胜者。”

Xudongning 怼了回去：“这道题你会吗？你就搁着说我？配吗！”

Anli_li：“……”

他俩根本不知道该怎么做，这个艰巨的任务就交给你了！

仅供娱乐，请勿当真。

题目描述

珂朵莉给你了一个序列 $a$，每次查询给一个区间 $[l,r]$，查询

$$\min_{l\le i < j\le r} a_i \oplus a_j$$

其中 $\oplus$ 指按位异或。

输入格式

第一行两个整数 $n,m$，表示序列长度与询问个数。

第二行 $n$ 个整数，表示序列 $a$。

之后 $m$ 行，每行两个整数 $l,r$ 表示询问区间。

输出格式

共 $m$ 行，每行一个整数表示答案。

输入输出样例 #1

输入 #1

4 4
1 2 3 7
1 2
1 4
2 4
3 4

输出 #1

3
1
1
4

说明/提示

需要亿点常数优化，时限为 std 的 $1.5$ 倍以上。

$1\le n, m\le 10^5.$

$1\le a_i \le 2^{31} - 1.$

$1\le l < r\le n.$