小 S sedang bermain sebuah permainan bernama “斗地主” bersama 小 F.
Malangnya, 小 S menyadari bahwa dia tidak dapat mengalahkan 小 F dalam bermain kartu, sehingga dia ingin mengakali tahap pengocokan kartu.
Satu pak berisi $n$ kartu, yang pada awalnya diberi nomor $1\sim n$ dari atas ke bawah. Skor kartu bernomor $i$ adalah $f(i)$. Dalam soal ini, $f(i)$ hanya memiliki dua kemungkinan: $f(i)=i$ atau $f(i)=i^2$.
Cara mengocok kartu mirip dengan yang biasa kita lakukan sehari-hari. Berikut definisi formalnya:
Tahap pengocokan terdiri atas $m$ putaran yang dilakukan secara berurutan. Pada putaran pengocokan ke-$i$:
- 小 S mengambil $A_i$ kartu teratas. Dengan demikian, pak kartu terbagi menjadi dua tumpukan: tumpukan pertama berisi $A_i$ kartu teratas, dan tumpukan kedua berisi $n-A_i$ kartu sisanya. Urutan relatif kartu dalam masing-masing tumpukan tidak berubah. Khususnya, jika $A_i=n$ atau $A_i=0$, salah satu tumpukan kosong.
- Selanjutnya, kedua tumpukan digabungkan untuk membentuk tumpukan ketiga yang baru. Ketika tumpukan pertama masih berisi $X$ kartu dan tumpukan kedua masih berisi $Y$ kartu, dengan peluang $\frac{X}{X+Y}$, ambil kartu paling bawah dari tumpukan pertama dan letakkan di bagian paling atas tumpukan ketiga yang baru; dengan peluang $\frac{Y}{X+Y}$, ambil kartu paling bawah dari tumpukan kedua dan letakkan di bagian paling atas tumpukan ketiga yang baru.
- Ulangi operasi $2$ hingga kedua tumpukan kosong. Dengan demikian, satu putaran pengocokan selesai.
Karena pengocokan bersifat acak, 小 S menyadari bahwa dia tidak dapat mengetahui kartu mana tepatnya yang berada pada suatu posisi. Namun, 小 S ingin menanyakan kepadamu nilai harapan skor kartu pada suatu posisi setelah $m$ putaran pengocokan tersebut. 小 S akan mengajukan total $Q$ pertanyaan seperti ini.
Masukan
Baca data dari berkas landlords.in.
Baris pertama masukan berisi tiga bilangan bulat positif $n,m,\mathit{type}$, yang masing-masing menyatakan banyaknya kartu, banyaknya putaran pengocokan, dan jenis $f(i)$. Jika $\mathit{type}=1$, $f(i)=i$. Jika $\mathit{type}=2$, $f(i)=i^2$.
Baris berikutnya berisi total $m$ bilangan bulat yang menyatakan $A_1\sim A_m$.
Baris berikutnya berisi sebuah bilangan bulat positif $Q$, yang menyatakan banyaknya kueri 小 S.
Masing-masing dari $Q$ baris berikutnya berisi sebuah bilangan bulat positif $c_i$, yang menyatakan bahwa 小 S ingin mengetahui nilai harapan skor kartu pada posisi ke-$c_i$ dari atas. Dijamin $1\le c_i\le n$.
Keluaran
Tuliskan keluaran ke berkas landlords.out.
Keluarkan total $Q$ baris. Setiap baris berisi sebuah bilangan bulat yang menyatakan nilai jawaban modulo $998244353$.
Dengan kata lain, misalkan jawaban dalam bentuk pecahan paling sederhana adalah $\frac{a}{b}$, dengan $a$ dan $b$ relatif prima. Keluarkan bilangan bulat $x$ sehingga $bx\equiv a\pmod{998244353}$ dan $0\le x<998244353$. Dapat dibuktikan bahwa bilangan bulat $x$ seperti itu unik.
Contoh
Masukan 1
4 1 1 3 1 1
Keluaran 1
249561090
Catatan
Dengan peluang $\frac14$, urutan akhir dari atas ke bawah adalah $\{1,2,3,4\}$.
Dengan peluang $\frac14$, urutan akhir dari atas ke bawah adalah $\{1,2,4,3\}$.
Dengan peluang $\frac14$, urutan akhir dari atas ke bawah adalah $\{1,4,2,3\}$.
Dengan peluang $\frac14$, urutan akhir dari atas ke bawah adalah $\{4,1,2,3\}$.
Jadi, pada akhirnya posisi pertama berisi $4$ dengan peluang $\frac14$ dan berisi $1$ dengan peluang $\frac34$. Dengan demikian, nilai harapan skor pada posisi pertama adalah $\frac74$.
Untuk membantumu memahami proses pengocokan secara lebih langsung, di bawah ini digambarkan proses yang menghasilkan urutan $\{1,4,2,3\}$.
Contoh 2
Lihat landlords/landlords2.in dan landlords/landlords2.ans di direktori peserta.
Contoh 3
Lihat landlords/landlords3.in dan landlords/landlords3.ans di direktori peserta.
Batasan dan Petunjuk
Untuk semua kasus uji: $3\le n\le 10^7$, $1\le m,Q\le5\times10^5$, $0\le A_i\le n$, $\mathit{type}\in\{1,2\}$.
Batasan khusus setiap kasus uji tercantum pada tabel berikut:
| Kasus uji | $n$ | $m$ | $\mathit{type}=$ | Sifat lainnya |
|---|---|---|---|---|
| 1 | $\le10$ | $\le1$ | $1$ | Tidak ada |
| 2 | $\le80$ | $\le80$ | $1$ | Tidak ada |
| 3 | $\le80$ | $\le80$ | $2$ | Tidak ada |
| 4 | $\le100$ | $\le5\times10^5$ | $2$ | Semua $A_i$ sama |
| 5 | $\le10^7$ | $\le5\times10^5$ | $1$ | Tidak ada |
| 6 | $\le10^7$ | $\le5\times10^5$ | $1$ | Tidak ada |
| 7 | $\le10^7$ | $\le5\times10^5$ | $1$ | Tidak ada |
| 8 | $\le10^7$ | $\le5\times10^5$ | $2$ | Tidak ada |
| 9 | $\le10^7$ | $\le5\times10^5$ | $2$ | Tidak ada |
| 10 | $\le10^7$ | $\le5\times10^5$ | $2$ | Tidak ada |
Perhatikan bahwa kami tidak menjamin $Q\le n$.
Berikut diberikan definisi nilai harapan $\mathrm{E}[x]$ dari peubah acak diskret $X$:
Misalkan nilai-nilai yang mungkin dari peubah acak diskret $X$ adalah $X_1,X_2,\cdots,X_k$, dan $\Pr[X_1],\Pr[X_2],\cdots,\Pr[X_k]$ adalah peluang $X$ mengambil masing-masing nilai tersebut. Maka nilai harapan $X$ adalah
$$ \mathrm{E}[x]=\sum_{i=1}^{k}X_i\Pr[X_i] $$