小 S กำลังเล่นเกมที่ชื่อว่า “斗地主” กับ 小 F

小 S ผู้น่าสงสารพบว่าตนเล่นไพ่เอาชนะ 小 F ไม่ได้ จึงต้องการเล่นตุกติกในขั้นตอนการสับไพ่

ไพ่สำรับหนึ่งมีทั้งหมด $n$ ใบ โดยมีหมายเลขจากบนลงล่างเป็น $1\sim n$ ไพ่หมายเลข $i$ มีคะแนนเท่ากับ $f(i)$ ในโจทย์นี้ $f(i)$ มีได้เพียงสองแบบเท่านั้น คือ $f(i)=i$ หรือ $f(i)=i^2$

วิธีสับไพ่ค่อนข้างคล้ายกับที่ใช้ในชีวิตประจำวัน ต่อไปนี้เราจะนิยามด้วยภาษาอย่างเป็นทางการ:

ขั้นตอนการสับไพ่แบ่งเป็นทั้งหมด $m$ รอบ โดยดำเนินการทั้ง $m$ รอบตามลำดับ ในการสับไพ่รอบที่ $i$:

1. 小 S จะหยิบไพ่ $A_i$ ใบแรกนับจากบนลงล่างออกมา ทำให้สำรับแบ่งเป็นสองกอง: กองแรกคือไพ่ $A_i$ ใบบนสุด และกองที่สองคือไพ่ $n-A_i$ ใบที่เหลือ โดยลำดับสัมพัทธ์ภายในแต่ละกองไม่เปลี่ยนแปลง โดยเฉพาะอย่างยิ่ง เมื่อ $A_i=n$ หรือ $A_i=0$ จะมีกองหนึ่งว่าง
2. จากนั้นรวมไพ่ทั้งสองกองเพื่อสร้างกองที่สามขึ้นมาใหม่ เมื่อกองแรกเหลือไพ่ $X$ ใบ และกองที่สองเหลือไพ่ $Y$ ใบ จะหยิบไพ่ใบล่างสุดของกองแรกไปวางไว้บนสุดของกองที่สามที่สร้างขึ้นใหม่ด้วยความน่าจะเป็น $\frac{X}{X+Y}$ และจะหยิบไพ่ใบล่างสุดของกองที่สองไปวางไว้บนสุดของกองที่สามที่สร้างขึ้นใหม่ด้วยความน่าจะเป็น $\frac{Y}{X+Y}$
3. ทำขั้นตอนที่ 2 ซ้ำจนไพ่ทั้งสองกองว่าง การสับไพ่หนึ่งรอบจึงเสร็จสิ้น

เนื่องจากขั้นตอนการสับไพ่เป็นการสุ่ม 小 S จึงพบว่าตนไม่สามารถรู้ได้แน่นอนว่าไพ่ใบใดอยู่ที่ตำแหน่งหนึ่ง แต่ 小 S ต้องการถามคุณว่า หลังผ่านการสับไพ่ $m$ รอบแล้ว ไพ่ที่ตำแหน่งหนึ่งมีคะแนนคาดหมายเท่าใด 小 S จะถามคำถามลักษณะนี้ทั้งหมด $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{a}{b}$ โดย $a$ และ $b$ เป็นจำนวนเฉพาะสัมพัทธ์ ให้ส่งออกจำนวนเต็ม $x$ ที่ทำให้ $bx\equiv a\pmod{998244353}$ และ $0\le x<998244353$ สามารถพิสูจน์ได้ว่าจำนวนเต็ม $x$ ดังกล่าวมีเพียงค่าเดียว

ตัวอย่าง

ข้อมูลนำเข้า 1

4 1 1
3
1
1

ข้อมูลส่งออก 1

249561090

หมายเหตุ

ผลลัพธ์สุดท้ายจากบนลงล่างเป็น $\{1,2,3,4\}$ ด้วยความน่าจะเป็น $\frac14$

ผลลัพธ์สุดท้ายจากบนลงล่างเป็น $\{1,2,4,3\}$ ด้วยความน่าจะเป็น $\frac14$

ผลลัพธ์สุดท้ายจากบนลงล่างเป็น $\{1,4,2,3\}$ ด้วยความน่าจะเป็น $\frac14$

ผลลัพธ์สุดท้ายจากบนลงล่างเป็น $\{4,1,2,3\}$ ด้วยความน่าจะเป็น $\frac14$

ดังนั้น ในตอนสุดท้าย ตำแหน่งแรกเป็น $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\le 10^7$, $1\le m,Q\le 5\times 10^5$, $0\le A_i\le n$, $type\in\{1,2\}$

ข้อจำกัดเฉพาะของแต่ละกรณีทดสอบแสดงในตารางต่อไปนี้:

โปรดสังเกตว่าเรา ไม่ได้รับประกัน ว่า $Q\le n$

ต่อไปนี้คือนิยามของค่าคาดหมาย $\mathbb E[x]$ ของตัวแปรสุ่มแบบไม่ต่อเนื่อง $X$:

ให้ค่าที่เป็นไปได้ของตัวแปรสุ่มแบบไม่ต่อเนื่อง $X$ คือ $X_1,X_2,\cdots,X_k$ และให้ $\Pr[X_1],\Pr[X_2],\cdots,\Pr[X_k]$ เป็นความน่าจะเป็นที่ $X$ จะมีค่าตรงกับแต่ละค่านั้น แล้วค่าคาดหมายของ $X$ คือ

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