Problem Statement

You are given the first $K$ terms $a_0,\dots, a_{K-1}$ of an integer sequence $(a_i)_{i \geq 0}$, and $K$ integers $c_1, \dots,c_K$. The terms of $(a_i)_{i \geq 0}$ from the $K$-th term onward are defined by the following recurrence:

• $\displaystyle a_i = \sum_{k=1}^K c_k a_{i-k} \quad (i \geq K)$.

All elements of an array $(x_0, \dots, x_{N-1})$ of length $N$ are initialized to $0$, and then the following operations $j = 1,\dots, M$ are performed in order, starting from operation $1$:

• $($Operation $j)$:$\quad l_j \leq i < r_j$ For each integer $i$ satisfying the above, update $x_i \gets x_i + a_{i-l_j}$.

For each integer $i$ $(0 \leq i < N)$, find the value of $x_i$ after all operations, modulo $10^9 + 7$.

Input

The input is given in the following format:

$K \quad N \quad M$
$a_0 \quad a_1 \quad \cdots \quad a_{K-1}$
$c_1 \quad c_2 \quad \cdots \quad c_K$
$l_1 \quad r_1$
$l_2 \quad r_2$
$\ \vdots$
$l_M \quad r_M$

• All input values are integers.
• $1 \leq K \leq 200$
• $1 \leq N \leq 10^5$
• $1 \leq M \leq 10^5$
• $0 \leq a_i \leq 10^9 \quad (0 \leq i < K)$
• $0 \leq c_i \leq 10^9 \quad (1 \leq i \leq K)$
• $0 \leq l_j < r_j \leq N \quad (1 \leq j \leq M)$

Output

On line $(i+1)$ $(0 \leq i < N)$, print the value of $x_i$ after all operations, modulo $10^9 + 7$. Print a newline at the end.

Sample

2 6 3
3 1
1 2
2 4
0 5
3 6

3
1
10
13
24
7

4 10 6
38357 29371 11020 79402
86940 11636 45261 69281
2 8
1 9
5 6
2 7
0 6
3 10

38357
67728
117105
187521
18341484
711694633
729776525
364121460
472238231
652635015