F. Сегментүүд дээрх Xor-ууд

хугацааны хязгаарлалт 10 секунд

санах ойн хязгаарлалт 512 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Танд $n$ ширхэг бүхэл тоо бүхий $a_{i}$ цуваа болон $m$ ширхэг асуултууд өгөгджээ.Асуулт бүр нь 2 бүхэл тоо $(l_{j}, r_{j})$-аар өгөгдөнө.

Функцийг гэж тодорхойлъё.Уг функц нь зөвхөн $u ≤ v$-уудын хувьд тодорхойлогдсон.

Асуулт бүрийн хувьд $l_{j} ≤ x, y ≤ r_{j},  a_{x} ≤ a_{y}$ байх бүх тоонуудын $f(a_{x}, a_{y})$ функцийн утгуудын хамгийн их утгыг олно уу.

Оролт

Эхний мөрөнд цувааны урт болон асуултын тоог илэрхийлэх 2 бүхэл тоо $n, m$ ($1 ≤ n ≤ 5*10^{4},  1 ≤ m ≤ 5*10^{3}$) өгөгдөнө.

2-дахь мөрөнд $a$ цувааны элементүүд болох $n$ ширхэг бүхэл тоонууд $a_{i}$ ($1 ≤ a_{i} ≤ 10^{6}$) өгөгдөнө.

Дараагийн $m$ мөрийн мөр болгонд $j$-дэх асуултын параметрүүд болох 2 бүхэл тоо $l_{j}, r_{j}$ ($1 ≤ l_{j} ≤ r_{j} ≤ n$) өгөгдөнө.

Гаралт

Асуулт бүрийн хувьд $l_{j} ≤ x, y ≤ r_{j},  a_{x} ≤ a_{y}$ байх бүх тоонуудын $f(a_{x}, a_{y})$ функцийн утгуудын хамгийн их утга болох $a_{j}$-ыг салангид мөрөнд хэвлэнэ.

Орчуулсан: Баатархүү

Жишээ тэстүүд

Оролт
6 3
1 2 3 4 5 6
1 6
2 5
3 4
Гаралт
7
7
7
Оролт
1 1
1
1 1
Гаралт
1
Оролт
6 20
10 21312 2314 214 1 322
1 1
1 2
1 3
1 4
1 5
1 6
2 2
2 3
2 4
2 5
2 6
3 4
3 5
3 6
4 4
4 5
4 6
5 5
5 6
6 6
Гаралт
10
21313
21313
21313
21313
21313
21312
21313
21313
21313
21313
2314
2315
2315
214
215
323
1
323
322
Сэтгэгдлүүдийг ачааллаж байна...