H. Easy palindrome question
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Over the past $$$n$$$ days, gg_gong have been observing the number of problems his friend has done.

He reached a conclusion that the maximum number of problems his friend did on one of the past $$$n$$$ days is $$$m$$$.

He gives you a sequence $$$a$$$ of $$$n$$$ numbers that denotes the number of problems his friend did each day. But, his friend has been lying to him. So on days where he is not sure how many problems his friend did, gg_gong replaces the corresponding positions in the sequence with $$$-1$$$.

After more detailed observation, he reached $$$k$$$ conclusions, each one given in the form of $$$u$$$ and $$$val$$$, representing the number of problems his friend did on day $$$u$$$ is not $$$val$$$.

He also reached $$$q$$$ more advanced conclusions. Each one gives two values $$$l$$$ and $$$r$$$, meaning that his friend did the same number problems on day $$$l$$$ and $$$r$$$, $$$l+1$$$ and $$$r-1$$$, and so on. In general, his friend did the same number of problems on days $$$l+k$$$ and $$$r-k$$$ where $$$l+k \lt r-k$$$.

How many total possible sequences satisfies all the information he has given you?

Input

The first line contains $$$4$$$ integers: $$$n,m,k,$$$ and $$$q$$$ $$$(1 \leq n \leq 3000,0 \leq m,q \leq 3000,0 \leq k \leq 2000000)$$$.

The second line contains $$$n$$$ integers representing $$$a$$$ $$$(-1 \leq a_i \leq m)$$$.

The next $$$k$$$ lines contains an $$$u$$$ and a $$$val$$$ $$$(1 \leq u \leq n,0 \leq val \leq m)$$$.

The next $$$l$$$ lines line each contain a $$$l$$$ and a $$$r$$$ $$$(1 \leq l \leq r \leq n)$$$, denoting the sequence from $$$l$$$ to $$$r$$$ is palindromic.

Output

Output one line containing the number of possible sequences. Since the answer can be large, output it modulo $$$1000000007$$$.

Examples
Input
10 10 5 1
-1 -1 -1 -1 -1 -1 -1 -1 -1 10
4 6
4 7
4 8
4 9
4 10
1 10
Output
7986
Input
10 10 11 1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1
4 0
4 1
4 2
4 3
4 4
4 5
4 6
4 7
4 8
4 9
4 10
1 10
Output
0