يلعب 小 S مع 小 F لعبة تُسمى «斗地主».
اكتشف 小 S المسكين أنه لا يستطيع التغلب على 小 F في لعب الورق، ولذلك يريد التلاعب بمرحلة خلط الأوراق.
تحتوي الرزمة على $n$ أوراق، مرقمة من الأعلى إلى الأسفل من $1$ إلى $n$. وقيمة الورقة رقم $i$ هي $f(i)$. وفي هذه المسألة، هناك احتمالان فقط للدالة $f(i)$: إما $f(i)=i$ أو $f(i)=i^2$.
تشبه طريقة الخلط الطريقة التي نستخدمها في حياتنا اليومية. وفيما يلي تعريفها بصياغة رسمية:
تتكون مرحلة الخلط من $m$ جولات تُنفذ بالترتيب. في جولة الخلط رقم $i$:
- يأخذ 小 S أول $A_i$ أوراق بدءًا من الأعلى. فتُقسم الرزمة إلى كومتين: الأولى هي الأوراق الـ $A_i$ العلوية، والثانية هي الأوراق الـ $n-A_i$ المتبقية، مع الحفاظ على الترتيب النسبي داخل كل كومة. وبوجه خاص، عندما يكون $A_i=n$ أو $A_i=0$، تكون إحدى الكومتين فارغة.
- تُدمج الكومتان لإنتاج كومة ثالثة جديدة. عندما يتبقى $X$ أوراق في الكومة الأولى و$Y$ أوراق في الثانية، تؤخذ الورقة السفلية من الكومة الأولى وتوضع أعلى الكومة الثالثة الجديدة باحتمال $\frac{X}{X+Y}$، أو تؤخذ الورقة السفلية من الكومة الثانية وتوضع أعلى الكومة الثالثة الجديدة باحتمال $\frac{Y}{X+Y}$.
- تُكرر العملية 2 حتى تصبح الكومتان فارغتين. وبهذا تكتمل جولة خلط واحدة.
ولأن الخلط عشوائي، أدرك 小 S أنه لا يستطيع معرفة الورقة الموجودة في موضع معين تحديدًا. لكنه يريد أن يسألك عن القيمة المتوقعة للورقة في موضع معين بعد جولات الخلط الـ $m$. وسيطرح عليك $Q$ استعلامات من هذا النوع.
الإدخال
اقرأ البيانات من الملف landlords.in.
يحتوي السطر الأول من الإدخال على ثلاثة أعداد صحيحة موجبة $n,m,type$، تمثل على الترتيب عدد الأوراق وعدد جولات الخلط ونوع $f(i)$. عندما يكون $type=1$، تكون $f(i)=i$، وعندما يكون $type=2$، تكون $f(i)=i^2$.
يحتوي السطر التالي على $m$ أعداد صحيحة، تمثل $A_1\sim A_m$.
يحتوي السطر التالي على عدد صحيح موجب $Q$، وهو عدد استعلامات 小 S.
يحتوي كل من الأسطر الـ $Q$ التالية على عدد صحيح موجب $c_i$، ويعني أن 小 S يريد معرفة القيمة المتوقعة للورقة في الموضع رقم $c_i$ من الأعلى إلى الأسفل. ويُضمن أن $1\le c_i\le n$.
الإخراج
اكتب الناتج في الملف landlords.out.
أخرج $Q$ أسطر إجمالًا، في كل سطر عدد صحيح يمثل قيمة الإجابة بترديد $998244353$.
أي إذا كانت الإجابة في أبسط صورة كسرية هي $\frac ab$، حيث $a$ و$b$ أوليان فيما بينهما، فأخرج العدد الصحيح $x$ الذي يحقق $bx\equiv a\pmod{998244353}$ و$0\le x<998244353$. ويمكن إثبات أن هذا العدد الصحيح $x$ وحيد.
أمثلة
الإدخال 1
4 1 1 3 1 1
الإخراج 1
249561090
ملاحظة
باحتمال $\frac14$، يكون الترتيب النهائي من الأعلى إلى الأسفل $\{1,2,3,4\}$.
وباحتمال $\frac14$، يكون الترتيب النهائي من الأعلى إلى الأسفل $\{1,2,4,3\}$.
وباحتمال $\frac14$، يكون الترتيب النهائي من الأعلى إلى الأسفل $\{1,4,2,3\}$.
وباحتمال $\frac14$، يكون الترتيب النهائي من الأعلى إلى الأسفل $\{4,1,2,3\}$.
لذلك تكون الورقة في الموضع الأول هي $4$ باحتمال $\frac14$، وتكون $1$ باحتمال $\frac34$، فتكون القيمة المتوقعة للموضع الأول $\frac74$.
ولمساعدتك على فهم عملية الخلط بصورة أوضح، نعرض فيما يلي العملية التي تؤدي إلى النتيجة $\{1,4,2,3\}$.
المثال 2
انظر الملفين landlords/landlords2.in وlandlords/landlords2.ans في مجلد المتسابق.
المثال 3
انظر الملفين landlords/landlords3.in وlandlords/landlords3.ans في مجلد المتسابق.
القيود
لجميع حالات الاختبار: $3\le n\le10^7$ و$1\le m,Q\le5\times10^5$ و$0\le A_i\le n$ و$type\in\{1,2\}$.
ترد القيود الخاصة بكل حالة اختبار في الجدول التالي:
| حالة الاختبار | $n$ | $m$ | $type=$ | خصائص أخرى |
|---|---|---|---|---|
| $1$ | $\le10$ | $\le1$ | $1$ | لا توجد |
| $2$ | $\le80$ | $\le80$ | $1$ | لا توجد |
| $3$ | $\le80$ | $\le80$ | $2$ | لا توجد |
| $4$ | $\le100$ | $\le5\times10^5$ | $2$ | جميع قيم $A_i$ متساوية |
| $5$ | $\le10^7$ | $\le5\times10^5$ | $1$ | لا توجد |
| $6$ | $\le10^7$ | $\le5\times10^5$ | $1$ | لا توجد |
| $7$ | $\le10^7$ | $\le5\times10^5$ | $1$ | لا توجد |
| $8$ | $\le10^7$ | $\le5\times10^5$ | $2$ | لا توجد |
| $9$ | $\le10^7$ | $\le5\times10^5$ | $2$ | لا توجد |
| $10$ | $\le10^7$ | $\le5\times10^5$ | $2$ | لا توجد |
يرجى الانتباه إلى أننا لا نضمن أن $Q\le n$.
نقدم هنا تعريف التوقع $\mathbb E[x]$ لمتغير عشوائي متقطع $X$:
لتكن القيم الممكنة للمتغير العشوائي المتقطع $X$ هي $X_1,X_2,\ldots,X_k$، ولتكن $\Pr[X_1],\Pr[X_2],\ldots,\Pr[X_k]$ احتمالات أخذ $X$ للقيم المقابلة. عندئذ يكون توقع $X$ هو:
$$\mathbb E[x]=\sum_{i=1}^{k}X_i\Pr[X_i]$$