For an array b of length m we define the function f as 

 f(b) = \begin{cases} b[1] &   if  m = 1 \\\ f(b[1] ⊕ b[2],b[2] ⊕ b[3],...,b[m-1] ⊕ b[m]) &   otherwise, \end{cases}  

where ⊕ is [bitwise exclusive OR](https://en.wikipedia.org/wiki/Bitwise_operation#XOR).

For example, f(1,2,4,8)=f(1⊕2,2⊕4,4⊕8)=f(3,6,12)=f(3⊕6,6⊕12)=f(5,10)=f(5⊕10)=f(15)=15

You are given an array a and a few queries. Each query is represented as two integers l and r. The answer is the maximum value of f on all continuous subsegments of the array a_l, a_{l+1}, …, a_r.

Input

The first line contains a single integer n (1 ≤ n ≤ 5000) — the length of a.

The second line contains n integers a_1, a_2, ..., a_n (0 ≤ a_i ≤ 2^{30}-1) — the elements of the array.

The third line contains a single integer q (1 ≤ q ≤ 100 000) — the number of queries.

Each of the next q lines contains a query represented as two integers l, r (1 ≤ l ≤ r ≤ n).

Output

Print q lines — the answers for the queries.

Examples

Input

3
8 4 1
2
2 3
1 2


Output

5
12


Input

6
1 2 4 8 16 32
4
1 6
2 5
3 4
1 2


Output

60
30
12
3

Note

In first sample in both queries the maximum value of the function is reached on the subsegment that is equal to the whole segment.

In second sample, optimal segment for first query are [3,6], for second query — [2,5], for third — [3,4], for fourth — [1,2].
/*
 * Author Ayub Subhaniya
 * Institute DA-IICT
 */

import java.io.*;
import java.math.*;
import java.util.*;

public class Tester
{

    InputStream in;
    PrintWriter out;

    long mod=(long)1e9+7;
    int MAX=(int)1e5+7;
    double eps=1e-6;

    void solve()
    {
        int n=ni();
        int a[]=na(n);
        int num[][] = new int[n+1][n+1];
        for (int l=1;l<=n;l++)
        {
            for (int i=1;i+l-1<=n;i++)
            {
                num[l][i]=(l==1?a[i-1]:num[l-1][i]^num[l-1][i+1]);
                //tr(l,i,num[l][i]);
            }
        }
        int max[][]=new int[n+1][n+1];
        for (int l=1;l<=n;l++)
            for (int i=1;i+l-1<=n;i++)
            {
                //tr(i,i+l-1,i+l-2,l,i);
                max[i][i+l-1]=l==1?num[l][i]:max(max(max[i][i+l-2],max[i+1][i+l-1]),num[l][i]);
                //tr(max[i][i+l-1]);
            }
        int q=ni();
        while (q-->0)
        {
            out.println(max[ni()][ni()]);
        }
    }

    class Pair implements Comparable<Pair>
    {
        int x;
        int y;
        int z;
        Pair(int a,int b,int c)
        {
            x=a;
            y=b;
            z=c;
        }

        @Override
        public boolean equals(Object o)
        {
            Pair other = (Pair)o;
            return x == other.x && y == other.y;
        }
        public String toString()
        {
            return x+" "+y+" "+z;
        }

        @Override
        public int compareTo(Pair o)
        {
            if (x==o.x)
                return Integer.compare(y, o.y);
            else
                return Integer.compare(x, o.x);
        }
        @Override public int hashCode()
        {
            return Objects.hash(x, y);
        }
    }

    long pow(long x, long n, long M) {
        x%=M;
        long result = 1;
        while (n > 0) {
            if (n % 2 == 1)
                result = (result * x) % M;
            x = (x * x) % M;
            n = n / 2;
        }
        return result;
    }

    long modInverse(long A, long M) {
        extendedEuclid(A, M);
        return (EEx % M + M) % M;
    }
    long EEd, EEx, EEy;

    void extendedEuclid(long A, long B) {
        if (B == 0) {
            EEd = A;
            EEx = 1;
            EEy = 0;
        } else {
            extendedEuclid(B, A % B);
            long temp = EEx;
            EEx = EEy;
            EEy = temp - (A / B) * EEy;
        }
    }

    int max(int a,int b)
    {
        if(a>b)
            return a;
        else
            return b;
    }

    int min(int a,int b)
    {
        if(a>b)
            return b;
        else
            return a;
    }

    long max(long a,long b)
    {
        if(a>b)
            return a;
        else
            return b;

    }


    long min(long a,long b)
    {
        if(a>b)
            return b;
        else
            return a;

    }

    long add(long a,long b)
    {
        long x=(a+b);
        while(x>=mod) x-=mod;
        return x;

    }


    long sub(long a,long b)
    {
        long x=(a-b);
        while(x<0) x+=mod;
        return x;

    }


    long mul(long a,long b)
    {
        a%=mod;
        b%=mod;
        long x=(a*b);
        return x%mod;

    }

    void run() throws Exception
    {
        String INPUT = "/Users/ayubsubhaniya/IdeaProjects/Test/src/input.txt";
        in = oj ? System.in : new FileInputStream(INPUT);
        out = new PrintWriter(System.out);

        long s = System.currentTimeMillis();
        solve();
        out.flush();
        tr(System.currentTimeMillis() - s + "ms");

    }
    public static void main(String[] args) throws Exception
    {
        new Tester().run();
    }

    private byte[] inbuf = new byte[1024];
    public int lenbuf = 0, ptrbuf = 0;

    private int readByte()
    {
        if (lenbuf == -1)
            throw new InputMismatchException();
        if (ptrbuf >= lenbuf)
        {
            ptrbuf = 0;
            try
            {
                lenbuf = in.read(inbuf);
            }
            catch (IOException e)
            {
                throw new InputMismatchException();
            }
            if (lenbuf <= 0)
                return -1;
        }
        return inbuf[ptrbuf++];
    }

    private boolean inSpaceChar(int c)
    {
        return !(c >= 33 && c <= 126);
    }

    private int skip()
    {
        int b;
        while ((b = readByte()) != -1 && inSpaceChar(b))
            ;
        return b;
    }

    private double nd()
    {
        return Double.parseDouble(ns());
    }

    private char nc()
    {
        return (char) skip();
    }

    private String ns()
    {
        int b = skip();
        StringBuilder sb = new StringBuilder();
        while (!(inSpaceChar(b)))
        { // when nextLine, (inSpaceChar(b) && b != ' ')
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }

    private char[] ns(int n)
    {
        char[] buf = new char[n];
        int b = skip(), p = 0;
        while (p < n && !(inSpaceChar(b)))
        {
            buf[p++] = (char) b;
            b = readByte();
        }
        return n == p ? buf : Arrays.copyOf(buf, p);
    }

    private char[][] nm(int n, int m)
    {
        char[][] map = new char[n][];
        for (int i = 0; i < n; i++)
            map[i] = ns(m);
        return map;
    }

    private int[] na(int n)
    {
        int[] a = new int[n];
        for (int i = 0; i < n; i++)
            a[i] = ni();
        return a;
    }

    private int ni()
    {
        int num = 0, b;
        boolean minus = false;
        while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
            ;
        if (b == '-')
        {
            minus = true;
            b = readByte();
        }

        while (true)
        {
            if (b >= '0' && b <= '9')
            {
                num = num * 10 + (b - '0');
            }
            else
            {
                return minus ? -num : num;
            }
            b = readByte();
        }
    }

    private long nl()
    {
        long num = 0;
        int b;
        boolean minus = false;
        while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
            ;
        if (b == '-')
        {
            minus = true;
            b = readByte();
        }

        while (true)
        {
            if (b >= '0' && b <= '9')
            {
                num = num * 10 + (b - '0');
            }
            else
            {
                return minus ? -num : num;
            }
            b = readByte();
        }
    }

    private boolean oj = System.getProperty("ONLINE_JUDGE") != null;

    private void tr(Object... o)
    {
        if (!oj)
            System.out.println(Arrays.deepToString(o));
    }

}

