두바이 쫀득 쿠키는 카다이프와 피스타치오 스프레드를 필링으로 사용하여 만드는 대한민국의 필드 마시멜로 디저트로, 현재 한국에서 선풍적인 인기를 끌고 있다. 거대한 베이커리 체인점인 RUN(Refined Unique Nourishment)은 이러한 두바이 쫀득 쿠키의 유행을 주시하기 시작했다. RUN의 이사장인 코코아는 카이스트 내부에 존재하는 RUN의 체인점들에서 두바이 쫀득 쿠키를 판매하고자 한다.

카이스트 내부에는 $1$번부터 $N$번까지 총 $N$개의 RUN의 체인점이 존재한다. 또한, 카이스트 내부에는 총 $M$개의 도로가 존재하는데, 각 도로는 서로 다른 두 개의 체인점을 연결한다. 어떠한 서로 다른 두 도로도 같은 두 체인점을 연결하지 않는다.

두바이 쫀득 쿠키의 인기로 인해서, 두바이 쫀득 쿠키의 재료를 구하는 것은 무척 어려운 일이 되었다. 따라서 $i$번째 체인점은 오직 $P_i$의 확률로만 두바이 쫀득 쿠키를 생산할 재료를 얻을 수 있다. 어떤 체인점이 두바이 쫀득 쿠키의 재료를 구하는데에 성공한다면, 해당 체인점, 그리고 이와 도로로 직접 연결된 다른 모든 체인점은 두바이 쫀득 쿠키를 한 상자씩 얻는다. 각 체인점은 다른 모든 체인점들과 독립적으로 $P_i$의 확률로 두바이 쫀득 쿠키의 재료를 얻게 됨에 유의하라.

코코아는 다음과 같은 형식의 $Q$개의 질문을 떠올렸다:

$1$번 체인점이 $S$상자의 두바이 쫀득 쿠키를 가지고 있고, $2$번 체인점이 $T$상자의 두바이 쫀득 쿠키를 가지고 있을 확률은 얼마인가?

코코아는 수완 좋은 사업가지만, 유감스럽게도 해당 질문에 대한 답변을 내놓지 못했다. 코코아를 도와 이러한 질문들에 대해 답변해주자.

제약 조건

• $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)$

부분문제

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

2. (20점) 모든 $i(1\le i\le N)$에 대해, $P_i=1$.

3. (20점) 모든 $i(1\le i\le N)$에 대해, $P_i=499{,}122{,}177=\frac{998{,}244{,}353+1}{2}$.

4. (40점) 추가 제약 조건 없음.

입력 형식

첫 번째 줄에 세 정수 $N,M,Q$가 공백으로 구분되어 주어진다.

다음 줄에 총 $N$개의 정수 $P_1 P_2 \cdots P_N$가 공백으로 구분되어 주어진다. 이는 $0\le A_i\le B_i, B_i\neq 0$을 만족하는 두 정수 $A_i,B_i$가 존재해서 $\frac{A_i}{B_i}\equiv P_i\pmod {998{,}244{,}353}$을 만족하며, $i$번 체인점이 두바이 쫀득 쿠키의 재료를 얻을 확률이 $\frac{A_i}{B_i}$이도록 할 수 있다는 것이다.

이후 $M$개의 줄에 걸쳐 도로의 정보가 주어진다. 이중 $i$번째 줄에는 두 정수 $U_i,V_i$가 공백으로 구분되어 주어지는데, 이는 $i$번째 도로가 $U_i$번 체인점과 $V_i$번 체인점을 연결하고 있다는 것을 의미한다.

이후 $Q$개의 줄에 걸쳐 코코아의 질문에 대한 정보가 주어진다. 이중 $i$번째 줄에는 두 정수 $S_i,T_i$가 공백으로 구분되어 주어지는데, 이는 코코아가 $1$번 체인점이 $S_i$상자의 두바이 쫀득 쿠키를 가지고 있고, $2$번 체인점이 $T_i$상자의 두바이 쫀득 쿠키를 가지고 있을 확률이 궁금하다는 것이다.

출력 형식

총 $Q$개의 줄에 걸쳐 코코아의 질문에 대한 답을 $998{,}244{,}353$으로 나눈 나머지를 출력하라.

예제

예제 1

입력

2 1 1
499122177 499122177
2 1
0 0

출력

748683265

설명

각 체인점들은 각각 $499 { , }122{,}177=\frac{1}{2}\pmod {998, 244, 353}$의 확률로 재료를 얻는다. 두 체인점이 각각 $S_1=T_1=0$상자의 두바이 쫀득 쿠키를 가질 확률은 $\frac{1}{4}=748, 683 , 265\pmod {998, 244, 353}$이다.

예제 2

입력

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

출력

0
590529083
0
0
0
552561203
0
323127449
0
180290484