眾所周知，神魔之塔是一款發行已久的遊戲，而角色的強度越來越誇張，
在遊戲剛推出時，毒龍還需要靠伊登隊慢慢磨，而現在新角色隨便手轉傷害便會破兆，
但這都不是重點，重點是在某片遙遠的大陸上，也存在著這麼一座神魔之塔。
這座神魔之塔其實早期也不能稱之為「塔」，因為他最初只有一層，但第一層的神魔覺得這樣太廢了，因此決定擴建神魔之塔到 $n$ 層。每層神魔之塔在蓋好後，其中會孕育一顆魔胎，而這顆魔胎的初始戰力為 $1$，但這麼弱的神魔實在是太遜咖了，因此在魔胎即將孵化之時，在他樓下的所有神魔都會幫他進行洗禮以提升他的戰力，而由於住的越高獲得的視野越好，因此住在較高樓層的神魔需要幫忙洗禮較多次。我們稱一次強度為 $k$ 的洗禮，會使得受洗神魔的戰力變為原本的 $k$ 倍，則住在第 $i$ 層的神魔幫第 $j$ 層的神魔洗禮時，需要進行 $i$ 次強度為 $gcd(i, j)$ 的洗禮。
值得注意的是，由於第一層的神魔誕生時，沒有樓下的其他神魔幫忙洗禮，因此他的戰力只有 $1$ 。同時，我們也可以預見，位於質數層的神魔即使有其他神魔的洗禮，戰力也只會有 $1$，但正如那句老話：「人生全靠投胎，失敗只能重開。」想來對於神魔而言，這句話也是成立的。
然而，富有正義感的城之內覺得這樣會讓神魔之塔的整體戰力太過強大，因此為了限制神魔之塔，他決定翻開覆蓋的陷阱卡「六芒星的束縛」，該卡的作用會讓過去進行的某些特定強度的洗禮無效，只留下其中 $m$ 種強度分別為 $c_1, c_2, ..., c_m$ 的洗禮仍然有效。也就是說，若過去某神魔受到了這 $m$ 種強度以外的洗禮，則該洗禮對神魔戰力的影響將會消失。
神魔之塔的眾神魔在受到「六芒星的束縛」影響後，都感受到了自身戰力或多或少的降低，因此，為了反抗，他們決定融合第 $a$ 樓到第 $b$ 樓的神魔，以產生一個戰力超群的大神魔Ex，而他的戰力會是被融合的所有神魔戰力的乘積。但由於事關重大，因此神魔們希望進行 $q$ 次模擬融合，第 $i$ 次模擬會融合第 $a_i$ 樓到第 $b_i$ 樓的所有神魔，請你輸出該次融合產生的大神魔Ex的戰力會有多少。若答案過大，則對 $998244353$ 取模。
輸入有多行。
第一行包含三個正整數 $n, m, q$ ，意義如題目所述。
第二行包含 $m$ 個正整數 $c_1, c_2, ..., c_m$ ，意義如題目所述。
接下來一共 $q$ 行，每行包含兩個正整數，其中第 $i$ 行包含 $a_i, b_i$ ，意義如題目所述。
輸出一共 $q$ 行，其中第 $i$ 行輸出第 $i$ 次模擬產生的大神魔Ex戰力為多少。
請注意，答案需對 $998244353$ 取模。
- $1\le n, q \le 10^{5}$
- $1\le m \le 100$
- $1\le a_i \le b_i \le n$
- $1\le c_i \le n$
\subtasks
\testfile{0-01.in}
\testfile{0-01.out}
\testfile{0-02.in}
\testfile{0-02.out}
範例測資1中，第 $10$ 層的神魔會受到的洗禮如下：
第 $1$ 層的神魔進行 $1$ 次強度為 $gcd(1, 10)=1$ 的洗禮，但該強度的洗禮無效。
第 $2$ 層的神魔進行 $2$ 次強度為 $gcd(2, 10)=2$ 的洗禮。
第 $3$ 層的神魔進行 $3$ 次強度為 $gcd(3, 10)=1$ 的洗禮，但該強度的洗禮無效。
第 $4$ 層的神魔進行 $4$ 次強度為 $gcd(4, 10)=2$ 的洗禮。
第 $5$ 層的神魔進行 $5$ 次強度為 $gcd(5, 10)=5$ 的洗禮。
第 $6$ 層的神魔進行 $6$ 次強度為 $gcd(6, 10)=2$ 的洗禮。
第 $7$ 層的神魔進行 $7$ 次強度為 $gcd(7, 10)=1$ 的洗禮，但該強度的洗禮無效。
第 $8$ 層的神魔進行 $8$ 次強度為 $gcd(8, 10)=2$ 的洗禮。
第 $9$ 層的神魔進行 $9$ 次強度為 $gcd(9, 10)=1$ 的洗禮，但該強度的洗禮無效。
因此，第 $10$ 層的神魔的戰力變為 $2^{2+4+6+8} \cdot 5^{5} =3276800000 =282066941 \pmod {998244353}$ 。