Problem Statement

There is a grid with $N$ rows and $M$ columns.
The cell in the $i$-th row from the top and the $j$-th column from the left is called "cell $(i,j)$".
$A_i$ is written to the left of cell $(i,1)$, and $B_j$ is written above cell $(1,j)$.

In cell $(i,j)$, write the result of computing $A_i\ op\ B_j$. Let this value be $C_{i,j}$.
Here, $op$ is either + or *.
If $op$ is +, then $C_{i,j}=A_i+B_j$; if it is *, then $C_{i,j}=A_i\times B_j$.

Find the number of cells $(i,j)$ such that $C_{i,j}$ is a multiple of $K$.

Input

$N$ $M$ $K$
$op$ $B_1$ $B_2$ $\cdots$ $B_M$
$A_1$
$A_2$
$\vdots$
$A_N$

The input satisfies the following constraints.

• $1\le N\le10^5$
• $1\le M\le10^5$
• $1\le K\le10^9$
• $1\le A_i\le10^9$
• $1\le B_j\le10^9$
• $N,M,K,A_i,B_j$ are integers
• $op$ is either + or *

Output

Output the number of cells $(i,j)$ such that $C_{i,j}$ is a multiple of $K$.

Sample

3 4 13
+ 5 12 6 13
8
27
3

2

3 4 12
* 5 12 6 13
8
27
3

4