Dubai Chewy Cookies are a popular dessert in South Korea, made using kadaif and pistachio spread as fillings, resembling a field marshmallow-style treat. They are currently gaining explosive popularity in Korea. RUN (Refined Unique Nourishment), a massive bakery chain, has begun paying close attention to this trend. Cocoa, the chairman of RUN, plans to sell Dubai Chewy Cookies at RUN's chain stores located inside KAIST.

There are a total of $N$ RUN chain stores inside KAIST, from $1$-st to $N$-th. Additionally, there are $M$ roads within KAIST, each connecting two distinct chain stores. No two different roads connect the same pair of chain stores.

Due to the popularity of Dubai Chewy Cookies, obtaining their ingredients has become very difficult. Thus, the $i$-th chain store can obtain the ingredients needed to produce Dubai Chewy Cookies only with probability $P_i$. If a chain store successfully obtains the ingredients, then that store and all other stores directly connected to it by roads each receive one box of Dubai Chewy Cookies. Note that each chain store independently obtains ingredients with probability $P_i$.

Cocoa has come up with $Q$ queries of the following form:

What is the probability that chain store $1$ has $S$ boxes of Dubai Chewy Cookies and chain store $2$ has $T$ boxes?

Although Cocoa is a capable businessman, she unfortunately could not determine the answers to these questions. Help Cocoa by answering these queries.

Constraints

• $2\le N\le 2{,}000, 0\le M\le \min(100{,}000, \frac{N(N-1)}{2}), 1\le Q\le 5{,}000$

• $0\le P_i<998{,}244{,}353(1\le i\le N)$

• $0\le S_i,T_i\le N(1\le i\le Q)$

Subtasks

1. (20 points) $N\le 10, M\le 10, Q\le 10$.

2. (20 points) For all $i(1\le i\le N)$, $P_i = 1$.

3. (20 points) For all $i(1\le i\le N)$, $P_i = 499{,}122{,}177 = \frac{998{,}244{,}353 + 1}{2}$.

4. (40 points) No additional constraints.

Input

The first line contains three integers $N, M, Q$ separated by spaces.

The next line contains $N$ integers $P_1, P_2, \cdots, P_N$ separated by spaces. This means that there exist integers $A_i, B_i$ with $0 \le A_i \le B_i$ and $B_i \ne 0$ such that
$\frac{A_i}{B_i} \equiv P_i \pmod{998{,}244{,}353}$,
and the probability that the $i$-th chain store obtains the ingredients is $\frac{A_i}{B_i}$.

The next $M$ lines describe the roads. The $i$-th line contains two integers $U_i, V_i$, indicating that the $i$-th road connects chain stores $U_i$ and $V_i$.

The next $Q$ lines describe Cocoa's queries. The $i$-th line contains two integers $S_i, T_i$, meaning that Cocoa wants to know the probability that chain store $1$ has $S_i$ boxes and chain store $2$ has $T_i$ boxes.

Output

Output $Q$ lines, each containing the answer to the corresponding query modulo $998{,}244{,}353$.

Example

Example 1

Input

2 1 1
499122177 499122177
2 1
0 0

Output

748683265

Explanation

In the first example, each chain store has a probability of $499,122,177 = \frac{1}{2} \pmod{998,244,353}$ of obtaining the ingredients. The probability that both stores have $S_1=T_1=0$ boxes of Dubai Chewy Cookies is $\frac{1}{4}=748,683,265 \pmod{998,244,353}$.

Example 2

Input

4 4 10
438226577 431856520 350400838 386921826
2 3
4 1
1 2
3 1
0 2
1 1
2 4
3 1
1 3
3 3
4 4
2 2
0 4
3 2

Output

0
590529083
0
0
0
552561203
0
323127449
0
180290484