Heraclosures

프로메테우스는 프로그래머다. 그는 친구 헤라클레스가 만든 프로그래밍 언어 Heraclosures로 큰 프로그램을 작성했다. 이 프로그램에는 $N$개의 함수가 있으며, 각 함수는 $1$부터 $N$까지의 서로 다른 정수로 구분된다. 함수는 많은 명령어로 이루어지고, 그중 일부는 다른 함수를 호출하는 call 명령어다.

함수 $i$의 call 명령어가 함수 $j$를 호출하면, 함수 $i$가 계속 실행되기 전에 함수 $j$의 전체 코드가 실행된다. 한 함수는 call 명령어를 여러 개 가질 수 있고, 같은 함수를 여러 번 호출할 수 있다. call 명령어가 전혀 없는 함수도 있다. 친구 시시포스의 조언에 따라 프로메테우스는 함수 호출에 순환이 없도록 만들었으므로, 호출이 무한히 반복되는 일은 없다.

함수 $i$에는 기본 실행 시간 $B_i$가 있다. 이는 $i$가 호출하는 함수의 시간을 제외한 실행 시간이다. 실행 시간은 프로세서 사이클 단위로 재며, $B_i$는 항상 0 이상의 정수다. 함수 $i$의 전체 실행 시간 $T(i)$는 기본 실행 시간에 $i$가 직접 호출하는 모든 함수의 전체 시간을 더한 값이다.

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

여기서 $C(i)$는 $i$가 직접 호출하는 함수들의 다중집합이다. $i$가 $j$를 여러 번 호출하면 $T(j)$가 그 횟수만큼 합에 나타난다. $i$에 call 명령어가 없으면 $C(i)$는 비어 있고 $T(i) = B_i$다.

갱신 이벤트는 $B_i$를 값 $V$로 바꾼다. 갱신은 기본 실행 시간만 바꾸며, 다중집합 $C(i)$는 그대로 유지된다. 질의 이벤트는 이벤트 목록에서 그보다 앞에 있는 모든 갱신을 반영하여, 함수 $i$의 현재 전체 실행 시간 $T(i)$를 구한다.

프로메테우스는 질의마다 결과를 보고 싶어 하지 않고, 하나의 요약값을 원한다. 질의가 $q$개 있고 이벤트 순서대로 $1$부터 $q$까지 번호가 매겨져 있을 때, 요약값은 다음과 같다.

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

여기서 $T(i_k)$는 $k$번째 질의에서 지정한 함수의 전체 실행 시간이며, 그 질의 이전의 모든 갱신을 반영한다.

첫 줄에 함수의 개수 $N$ ($1 \le N \le 8000$)이 주어진다.

다음 줄에는 $N$개의 정수 $B_1, B_2, \dots, B_N$ ($0 \le B_i \le 10^9$)이 주어지며, 각 함수의 기본 실행 시간을 나타낸다.

다음 줄에는 전체 함수에 있는 call 명령어의 개수 $M$ ($1 \le M \le 8000$)이 주어진다. 이어지는 $M$개의 줄에는 두 정수 $F$와 $G$ ($1 \le F, G \le N$, $F \ne G$)가 주어지며, 함수 $F$에 함수 $G$를 호출하는 call 명령어가 있음을 뜻한다.

다음 줄에는 이벤트의 개수 $E$ ($1 \le E \le 10^6$)가 주어진다. 이어지는 $E$개의 줄은 각각 이벤트다. 대문자 U 뒤에 정수 $I$ ($1 \le I \le N$)와 $V$ ($0 \le V \le 10^9$)가 오면 $B_I$를 $V$로 설정하는 갱신이다. 대문자 Q 뒤에 정수 $J$ ($1 \le J \le N$)가 오면 $T(J)$를 구하는 질의다.

입력에는 함수 호출 순환이 없으며, 질의는 최소 하나 주어진다.

모든 질의의 요약값을 $10^9+7$로 나눈 나머지를 한 줄에 정수로 출력한다.