// 28-5-7: Magická operace (ještě rychlejší řešení)
// Autor: Medvěd

#include <assert.h>

#include "magic.h"

// Maximální počet prvků a úrovní rekurze
#define MAXL 20
#define MAX (1<<MAXL)

int *nums;		// Posloupnost na vstupu
int len;		// Její délka
int len2;		// ... zaokrouhlená nahoru na mocninu dvojky
int p[MAXL][MAX];	// Jednotlivá patra stromu rekurze
int levels;		// Počet pater
int bit[MAX];		// Předpočítané pozice nejvyšší jedničky

// Předvýpočet: úroveň l, interval od i do j
void pc(int l, int i, int j)
{
	assert(i <= j);
	if (i == j)
		return;
	int s = (i+j)/2;
	if (s >= len) {
		pc(l+1, i, s);
		return;
	}
	int jj = (j < len) ? j : len-1;
	p[l][s] = nums[s];
	for (int k=s-1; k>=i; k--)
		p[l][k] = magic_op(nums[k], p[l][k+1]);
	p[l][s+1] = nums[s+1];
	for (int k=s+2; k<=jj; k++)
		p[l][k] = magic_op(p[l][k-1], nums[k]);
	pc(l+1, i, s);
	pc(l+1, s+1, j);
}

// Předvýpočet všech úrovní
void precalc(void)
{
	len2 = 1;
	levels = 0;
	while (len2 < len) {
		len2 *= 2;
		levels++;
	}
	bit[0] = 0;
	for (int i=1; i<len2; i++)
		bit[i] = bit[i/2] + 1;
	pc(0, 0, len2-1);
}

// Dotaz
int query(int qi, int qj)
{
	if (qi == qj)
		return nums[qi];
	int b = levels - bit[qi ^ qj];
	// printf("== %d,%d => level %d/%d\n", qi, qj, b, levels);
	return magic_op(p[b][qi], p[b][qj]);
}

// Hlavní program
int main(void) {
	magic_init();
	magic_get_numbers(&nums, &len);
	precalc();
	magic_begin();

	for (int i=0; i<magic_num_queries(); i++) {
		magic_query q = magic_get_query();
		magic_answer(query(q.from, q.to));
	}

	magic_cleanup();
	return 0;
}