There are $n-1$ types of chemical substances, all of which are soluble in water. Any two of these $n-1$ substances can react under certain conditions (the two substances can be the same). Specifically, water does not react with other chemical substances; however, for the sake of consistency, we consider that water reacts with any chemical substance $X$ to produce $X$. Thus, including water, there are a total of $n$ chemical substances.

According to relevant theory, since the products do not leave the reaction system, the product of a reaction between chemicals is independent of the order in which the substances are added. Additionally, each chemical substance has exactly one corresponding chemical substance such that the two react to produce water.

There is a row of test tubes on a table, each containing one type of chemical substance, numbered $1, 2, \dots, m$ from left to right. To demonstrate your superior experimental skills, your $i$-th experiment uses only the test tubes with numbers in the range $[L_i, R_i]$. Assuming you can create any possible reaction conditions, how many different substances (including those initially present) can you produce in the $i$-th experiment?

Input

The first line contains three positive integers $t, m, q$, representing the number of positive integers in the second line, the number of chemical test tubes on the table, and the number of experiments you perform, respectively.

The second line contains $t$ positive integers describing the properties of these chemical substances.

The next line contains $m$ positive integers in the range $[1, n]$, where the $i$-th integer indicates the type of chemical substance in the $i$-th test tube.

The next $q$ lines each contain two positive integers $L_i, R_i$, representing the range of test tube numbers you can use in the $i$-th experiment.

Output

Exactly $q$ lines, each containing a positive integer in the range $[1, n]$, representing the number of different types of substances you can theoretically produce in the $i$-th experiment.

Examples

Input 1

1 5 3
4
1 3 2 2 4
2 4
1 2
1 1

Output 1

4
2
1

Implementation Details

It is recommended to use C++ to solve this problem.

namespace LIB{
    const int N=30;
    int dim[N],dimcnt;
    template<class T>void dfs(int dep,T g,int x,int y,int z,int n){
        if(dep>dimcnt){
            g[x][y]=z;
            return;
        }
        int d=n/dim[dep];
        for(int i=0;i<n;i+=d){
            for(int j=0;j<n;j+=d){
                dfs(dep+1,g,x+i,y+j,z+(i+j)%n,d);
            }
        }
    }
    template<class T1,class T2>inline int put_reaction(int t,T1 a,T2 g){
        dimcnt=t;
        int n=1;
        for(int i=1;i<=t;i++){
            n*=dim[i]=a[i];
        }
        dfs(1,g,1,1,1,n);
        return n;
    }
}

After including the above code in your source program, you can call this function with time complexity $\mathrm O(n^2)$ to process the first two lines of the input data:

int LIB::put_reaction(t,a,g);

• The first parameter is the integer $t$ from the first line of the input.
• The second parameter is an int array containing the $t$ numbers from the second line of the input, starting from index $1$.
• The third parameter is a two-dimensional int array. After the function finishes execution, the product of the reaction between substance $i$ and substance $j$ is the substance at g[i][j].
• The function returns an int representing $n$ as described in the problem statement.

The program can generate a two-dimensional int array g based on the $t$ positive integers describing the properties of the chemicals. According to the problem statement, this array satisfies:

• The reaction between chemical substance $i$ and chemical substance $j$ produces chemical substance g[i][j].
• The product is independent of the order of addition, so g[i][j]==g[j][i] and g[g[i][j]][k]==g[i][g[j][k]] hold.
• Among the $n$ substances, exactly one is water, and its reaction properties are guaranteed to satisfy the description in the problem.
• Each row and each column of the two-dimensional array g contains exactly one instance of water.

Reference usage:

#include <cstdio>
namespace LIB{ /* ... */ }
const int N=3010;
int a[N],b[N][N];
int main(){
    int t,m,q;
    scanf("%d%d%d",&t,&m,&q);
    for(int i=1;i<=t;i++){
        scanf("%d",a+i);
    }
    int n=LIB::put_reaction(t,a,b);
    /* ... */
    return 0;
}

Constraints

For all data:

• $n\leq3000, m, q\leq10^6$
• $\forall i, 1\leq L_i\leq R_i\leq m$
• $\forall i, a_i\neq 1$