V.I.P.

The complete graph $G$ has $N$ vertices. There are $M$ edge activation records and $N$ vertex weights. Initially, every edge is inactive. Each of the $M$ records is one of the following, and every edge is activated at most once among the $M$ records.

• $i$ $j$: Makes the edge connecting vertices $i$ and $j$ an active edge.

A path that visits vertices in increasing order of weight and does not use any inactive edge is called a V.I.P. (Very Important Path). For each query below, count the number of ***V.I.P.***s.

• $p\,q$: Flips the activation state of the edge connecting vertices $p$ and $q$. Output the number of ***V.I.P.***s in the changed graph, then restore the original activation state.

The first line contains the number of vertices $N$, the number of active edges $M$, and the number of queries $Q$, separated by spaces. $(1 \leq N \leq 10^5; 0 \leq M \leq \min(\frac{N(N-1)}{2}, 2 \times 10^5); 1 \leq Q \leq 10^5)$

The second line contains the vertex weights $w_1, w_2, \ldots, w_N$, separated by spaces, where $w_i$ is the weight of vertex $i$. $(1 \leq w_i \leq 10^9)$

From line 3 to line $M + 2$, line $i + 2$ contains the two endpoints $u_i$ and $v_i$ of the $i$-th active edge, separated by a space. $(1 \leq u_i, v_i \leq N; u_i \neq v_i)$

From line $M + 3$ to line $M + Q + 2$, line $M + i + 2$ contains the $i$-th query $p_i$ and $q_i$, separated by a space. $(1 \leq p_i, q_i \leq N; p_i \neq q_i)$

For each query, output the number of ***V.I.P.***s. Since the answer can be very large, output it modulo $10^9+7$.

In graph theory, a path is a sequence of adjacent vertices that visits each vertex at most once. A sequence of $X$ vertices $P = {v_1, v_2, \cdots, v_{X-1}, v_X}$ with $X \geq 1$ is a path if $v_i \neq v_j$ whenever $i \neq j$, and for each $1 \leq i \leq X - 1$ there is an edge whose endpoints are $v_i$ and $v_{i+1}$ (with $v_i \neq v_{i+1}$).

An increasing sequence is a sequence $a$ of length $n$ that satisfies $a_1 < a_2 < \cdots < a_{n-1} < a_n$.