Heraclosures

Prometheus is a programmer. He wrote a large program in Heraclosures, a programming language invented by his friend Heracles. The program has $N$ functions, each identified by a unique integer from $1$ to $N$. Each function consists of many instructions, some of which are call instructions that invoke other functions.

When a call instruction in function $i$ calls function $j$, the full code of function $j$ runs before function $i$ continues. A function may contain several call instructions, and it may call the same function several times. Some functions have no call instructions at all. Following advice from his friend Sisyphus, Prometheus made sure the function calls form no cycles, so no call loop can run forever.

Function $i$ has a base execution time $B_i$, which is its execution time excluding the functions it calls. Execution times are measured in processor cycles, so $B_i$ is always a non-negative integer. The total execution time of function $i$, written $T(i)$, is its base time plus the total time of every function it calls directly:

$T(i) = B_i + \sum_{j \in C(i)} T(j)$

Here $C(i)$ is the multiset of functions that $i$ calls directly. If $i$ calls $j$ several times, $T(j)$ appears that many times in the sum. If $i$ has no call instructions, $C(i)$ is empty and $T(i) = B_i$.

An update sets $B_i$ to a value $V$. The update changes only the base time, and the multiset $C(i)$ stays the same. A query asks for the current total execution time $T(i)$ of function $i$, using all updates that appear before it in the event list.

Prometheus wants one summary value instead of each query result. With $q$ queries numbered 1 to $q$ in event order, the summary is

$\left( \sum_{k=1}^{q} k \cdot T(i_k) \right) \bmod (10^9+7)$

where $T(i_k)$ is the total execution time of the function in the $k$-th query, using all updates before that query.

The first line contains an integer $N$ ($1 \le N \le 8000$), the number of functions.

The next line contains $N$ integers $B_1, B_2, \dots, B_N$ ($0 \le B_i \le 10^9$), the base execution time of each function.

The next line contains an integer $M$ ($1 \le M \le 8000$), the number of call instructions among all functions. Each of the next $M$ lines contains two integers $F$ and $G$ ($1 \le F, G \le N$, $F \ne G$), meaning function $F$ contains a call instruction to function $G$.

The next line contains an integer $E$ ($1 \le E \le 10^6$), the number of events. Each of the next $E$ lines is either an update, written as the uppercase letter U followed by two integers $I$ ($1 \le I \le N$) and $V$ ($0 \le V \le 10^9$), which sets $B_I$ to $V$, or a query, written as the uppercase letter Q followed by an integer $J$ ($1 \le J \le N$), which asks for $T(J)$.

The input has no call cycles, and there is at least one query.

Print a single integer, the summary result of all queries modulo $10^9+7$.