小 S đang chơi một trò chơi tên là “Đấu địa chủ” với 小 F.

小 S đáng thương nhận ra mình không thắng nổi 小 F khi chơi bài, nên cậu muốn giở trò trong lúc xáo bài.

Một bộ bài có tổng cộng $n$ lá, được đánh số lần lượt từ $1$ đến $n$ từ trên xuống dưới. Điểm của lá bài mang số $i$ là $f(i)$. Trong bài toán này, $f(i)$ chỉ có hai khả năng: $f(i)=i$ hoặc $f(i)=i^2$.

Cách xáo bài khá giống trong đời sống hằng ngày. Dưới đây là định nghĩa hình thức:

Quá trình xáo bài gồm tổng cộng $m$ lượt, được thực hiện lần lượt. Trong lượt xáo thứ $i$:

1. 小 S lấy ra $A_i$ lá bài đầu tiên tính từ trên xuống. Như vậy bộ bài được chia thành hai chồng: chồng thứ nhất là $A_i$ lá trên cùng, chồng thứ hai là $n-A_i$ lá còn lại; thứ tự tương đối trong mỗi chồng không thay đổi. Đặc biệt, khi $A_i=n$ hoặc $A_i=0$, có một chồng rỗng.
2. Tiếp theo, gộp hai chồng bài để tạo ra chồng thứ ba mới. Khi chồng thứ nhất còn $X$ lá và chồng thứ hai còn $Y$ lá, với xác suất $\frac{X}{X+Y}$, lấy lá dưới cùng của chồng thứ nhất và đặt lên trên cùng của chồng thứ ba mới; với xác suất $\frac{Y}{X+Y}$, lấy lá dưới cùng của chồng thứ hai và đặt lên trên cùng của chồng thứ ba mới.
3. Lặp lại thao tác 2 cho đến khi cả hai chồng đều rỗng. Như vậy ta hoàn thành một lượt xáo bài.

Vì quá trình xáo bài là ngẫu nhiên, 小 S nhận ra mình không thể biết chính xác lá bài nào ở một vị trí. Nhưng 小 S muốn hỏi bạn: sau $m$ lượt xáo bài này, kỳ vọng điểm của lá bài ở một vị trí là bao nhiêu? 小 S sẽ hỏi bạn tổng cộng $Q$ câu hỏi như vậy.

Dữ liệu vào

Đọc dữ liệu từ tệp landlords.in.

Dòng đầu tiên chứa ba số nguyên dương $n,m,type$, lần lượt biểu diễn số lá bài, số lượt xáo bài và kiểu của $f(i)$. Khi $type=1$, $f(i)=i$. Khi $type=2$, $f(i)=i^2$.

Dòng tiếp theo chứa tổng cộng $m$ số nguyên, biểu diễn $A_1\sim A_m$.

Dòng tiếp theo chứa một số nguyên dương $Q$, biểu diễn số câu hỏi của 小 S.

Trong $Q$ dòng tiếp theo, mỗi dòng chứa một số nguyên dương $c_i$, cho biết 小 S muốn biết kỳ vọng điểm của lá bài ở vị trí thứ $c_i$ từ trên xuống dưới. Bảo đảm $1\le c_i\le n$.

Dữ liệu ra

Ghi kết quả vào tệp landlords.out.

In tổng cộng $Q$ dòng, mỗi dòng chứa một số nguyên biểu diễn giá trị của đáp án theo modulo $998244353$.

Cụ thể, giả sử đáp án sau khi rút gọn là $\frac{a}{b}$, trong đó $a$ và $b$ nguyên tố cùng nhau. In số nguyên $x$ sao cho $bx\equiv a\pmod{998244353}$ và $0\le x<998244353$. Có thể chứng minh số nguyên $x$ như vậy là duy nhất.

Ví dụ

Dữ liệu vào 1

4 1 1
3
1
1

Dữ liệu ra 1

249561090

Ghi chú

Với xác suất $\frac14$, kết quả cuối cùng từ trên xuống dưới là $\{1,2,3,4\}$.

Với xác suất $\frac14$, kết quả cuối cùng từ trên xuống dưới là $\{1,2,4,3\}$.

Với xác suất $\frac14$, kết quả cuối cùng từ trên xuống dưới là $\{1,4,2,3\}$.

Với xác suất $\frac14$, kết quả cuối cùng từ trên xuống dưới là $\{4,1,2,3\}$.

Vì vậy, cuối cùng xác suất vị trí đầu tiên là $4$ bằng $\frac14$, xác suất vị trí đầu tiên là $1$ bằng $\frac34$, nên kỳ vọng điểm ở vị trí đầu tiên là $\frac74$.

Để giúp bạn hiểu quá trình xáo bài trực quan hơn, dưới đây chúng tôi minh họa quá trình cho kết quả $\{1,4,2,3\}$.

Ví dụ 2

Xem landlords/landlords2.in và landlords/landlords2.ans trong thư mục của thí sinh.

Ví dụ 3

Xem landlords/landlords3.in và landlords/landlords3.ans trong thư mục của thí sinh.

Giới hạn

Với mọi bộ kiểm thử: $3\le n\le 10^7$, $1\le m,Q\le 5\times 10^5$, $0\le A_i\le n$, $type\in\{1,2\}$.

Giới hạn cụ thể của từng bộ kiểm thử được cho trong bảng sau:

Chú ý rằng chúng tôi không bảo đảm $Q\le n$.

Ở đây, chúng tôi đưa ra định nghĩa kỳ vọng $\mathrm{E}[x]$ của biến ngẫu nhiên rời rạc $X$:

Giả sử các giá trị có thể của biến ngẫu nhiên rời rạc $X$ là $X_1,X_2,\cdots,X_k$, và $\Pr[X_1],\Pr[X_2],\cdots,\Pr[X_k]$ là các xác suất để $X$ nhận những giá trị tương ứng. Khi đó kỳ vọng của $X$ là

$$ \mathrm{E}[x]=\sum_{i=1}^k X_i\Pr[X_i] $$