30828번 - 셰프 건공이

문제

알고 있었는가, 사실 건공이는 굉장히 유능한 요리사라는 사실을. 건공이는 어떤 재료들을 받아도 가장 맛있는 음식을 만들어 낼 수 있는 엄청난 능력이 있다.

건공이는 1ドル$번 재료부터 $N$번 재료까지 총 $N$개의 재료를 가지고 있다. 각 재료는 $T_i$의 맛 수치를 가진다. 건공이가 만드는 음식의 맛은 (사용한 모든 재료의 맛들을 XOR한 값 + 사용한 모든 재료의 개수)로 나타낼 수 있다.

$Q$개의 쿼리가 주어지고 각 쿼리마다 $l$과 $r$이 주어질 때, 각 쿼리에 대하여 $l$번째 재료부터 $r$번째 재료까지 ($r - l + 1$)개의 재료 중 0ドル$개 이상을 적절히 사용하여 만들 수 있는 요리의 맛 중 최댓값을 구하여라.

입력

첫 번째 줄에 재료의 개수 $N$이 주어진다. ($ 1 \leq N \leq 500$)

두 번째 줄에 $N$개의 재료의 맛 수치 $T_1, T_2, \cdots, T_N$이 공백으로 구분되어 주어진다. (0ドル \leq T_i \leq 511$)

세 번째 줄에 쿼리의 개수 $Q$가 주어진다. (1ドル \leq Q \leq 100\ 000$)

다음 $Q$개의 줄에 $l$과 $r$이 공백으로 구분되어 주어진다. (1ドル\leq l \leq r \leq N$)

출력

$Q$개의 줄에 각 쿼리마다 건공이가 만들 수 있는 요리의 맛 중 최댓값을 한 줄씩 출력한다.

제한

힌트