Un programa tiene \(N\) funciones y \(M\) instrucciones de llamada, sin ciclos entre las llamadas. La función \(i\) tiene un tiempo base \(B_i\) y su tiempo total es

\[T(i) = B_i + \sum_{j \in C(i)} T(j),\]

donde \(C(i)\) es el multiconjunto de funciones que \(i\) llama directamente (si \(i\) llama varias veces a \(j\), \(T(j)\) se suma varias veces).

Se procesan \(E\) eventos en orden: una actualización cambia \(B_i\) a un valor \(V\), y una consulta pide \(T(i)\) con los valores vigentes. Si hay \(q\) consultas, numeradas de \(1\) a \(q\), y la \(k\)-ésima pide la función \(i_k\), imprime

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

Entrada

La primera línea tiene un entero \(N\) \((1 \le N \le 8000)\).

La segunda línea tiene \(N\) enteros \(B_1, \dots, B_N\) \((0 \le B_i \le 10^9)\).

La tercera línea tiene un entero \(M\) \((1 \le M \le 8000)\).

Cada una de las siguientes \(M\) líneas tiene dos enteros \(F\) y \(G\) \((1 \le F, G \le N,\ F \ne G)\): la función \(F\) tiene una llamada a \(G\) (puede repetirse).

La siguiente línea tiene un entero \(E\) \((1 \le E \le 10^6)\), y siguen \(E\) líneas con los eventos: U I V \((1 \le I \le N,\ 0 \le V \le 10^9)\) cambia \(B_I\) a \(V\), y Q J \((1 \le J \le N)\) consulta \(T(J)\).

Se garantiza que no hay ciclos y que hay al menos una consulta.

Salida

Una línea con el resultado resumido.

Notas

En el primer ejemplo los tiempos consultados son \(230\), \(120\) y \(100\); en el segundo, \(94\), \(42\), \(42\) y \(84\).

Ejemplo 1

Entrada

3
10 20 100
3
1 2
2 3
1 3
3
Q 1
Q 2
Q 3

Salida

770

Ejemplo 2

Entrada

2
42 10
2
2 1
2 1
5
Q 2
Q 1
U 2 0
Q 1
Q 2

Salida

640

Regional Latinoamericana 2024 del ICPC, problema H («Heraclosures»). Versión en español redactada para este juez; el enunciado oficial, en inglés, está aquí abajo.