จะมีสักกี่คนที่ประสบความสำเร็จได้เหมือนกับ wcysai?
บริษัท R เป็นบริษัทผลิตเงินที่ก่อตั้งโดย wcysai โดยมีรายได้ต่อปีมากกว่า 100 ล้าน มีพนักงาน $n$ คนทำงานอยู่ที่บริษัท R และพนักงานแต่ละคนอาศัยอยู่ในบ้านหลังหนึ่ง บ้านของพนักงานบางคนเชื่อมต่อกันด้วยถนนสองทิศทาง รับประกันว่าเมื่อเริ่มต้นจากบ้านของพนักงานคนใดก็ตาม จะสามารถเดินทางไปยังบ้านของพนักงานคนอื่นได้ผ่านทางถนน
พนักงานแบ่งออกเป็นสองประเภท ได้แก่ ผู้จัดการ (ประเภท A) และคนงาน (ประเภท B) ผู้จัดการทำงาน $a$ ชั่วโมงต่อวัน ในขณะที่คนงานทำงาน $b$ ชั่วโมงต่อวัน เห็นได้ชัดว่าคนงานต้องทำงานนานกว่าผู้จัดการ ดังนั้น $a < b$ พนักงานแต่ละคนมีเวลาเริ่มทำงาน $s_i$ หากพนักงานคนนี้ต้องทำงาน $m$ ชั่วโมง ($m = a$ หรือ $m = b$) เวลาเลิกงานของพวกเขาคือ $t_i = s_i + m$
อย่างไรก็ตาม พนักงานไม่เคยต้องการเป็นคนที่ทำงานหนักที่สุด ดังนั้น เมื่อพวกเขาเริ่มทำงาน พวกเขาจะตรวจสอบว่ามีเพื่อนบ้านคนใด (กล่าวคือ พนักงานที่บ้านเชื่อมต่อกันโดยตรงด้วยถนน) เริ่มทำงานไปก่อนแล้วหรือไม่ ในทำนองเดียวกัน เมื่อพวกเขาเลิกงาน พวกเขาจะตรวจสอบว่ามีเพื่อนบ้านคนใดที่ยังไม่เลิกงานหรือไม่ หากผลการสังเกตทั้งสองเป็นจริง พวกเขาจะรู้สึกพึงพอใจ กล่าวอย่างเป็นทางการคือ พนักงานจะพึงพอใจก็ต่อเมื่อมีเพื่อนบ้านที่มีเวลาเริ่มทำงานเร็วกว่าตน อย่างแท้จริง และมีเพื่อนบ้านที่มีเวลาเลิกงานช้ากว่าตน อย่างแท้จริง (เพื่อนบ้านทั้งสองคนนี้อาจเป็นคนเดียวกันหรือคนละคนก็ได้) มิฉะนั้น พนักงานจะไม่พึงพอใจเพราะรู้สึกว่าตนเองเป็นคนที่ทำงานหนักที่สุด
ตอนนี้ ในฐานะผู้ช่วยคนเก่งของ wcysai คุณสามารถจัดเวลาเริ่มทำงานของพนักงานแต่ละคนได้อย่างอิสระ คุณต้องการจัดตารางเวลาของพนักงานทุกคนอย่างเหมาะสมเพื่อให้จำนวนคนที่ไม่พึงพอใจมีน้อยที่สุด สังเกตว่าคุณสามารถกำหนดเวลาเริ่มทำงานเป็น จำนวนจริงไม่ลบใดๆ ก็ได้ (ดูรายละเอียดในรูปแบบข้อมูลส่งออก)
ข้อมูลนำเข้า
บรรทัดแรกประกอบด้วยจำนวนเต็ม $T$ ($1 \le T \le 10^5$) แทนจำนวนชุดทดสอบ
สำหรับแต่ละชุดทดสอบ บรรทัดแรกประกอบด้วยจำนวนเต็มไม่ลบสี่ตัวคือ $n$, $m$, $a$ และ $b$ ($1 \le n, m \le 5 \cdot 10^5$, $1 \le a < b \le 10^6$) แทนจำนวนพนักงาน จำนวนถนน ชั่วโมงทำงานของผู้จัดการ และชั่วโมงทำงานของคนงาน ตามลำดับ
บรรทัดถัดไปประกอบด้วยสตริงความยาว $n$ ที่ประกอบด้วยตัวอักษร A และ B เท่านั้น ตัวอักษรตัวที่ $i$ แทนประเภทของพนักงานคนที่ $i$
อีก $m$ บรรทัดถัดไป แต่ละบรรทัดประกอบด้วยจำนวนเต็มไม่ลบสองตัวคือ $u, v$ ($1 \le u, v \le n$) แทนถนนหนึ่งสาย
รับประกันว่าหากมองบ้านของพนักงานเป็นจุดยอดและถนนเป็นเส้นเชื่อม กราฟจะไม่มีเส้นเชื่อมซ้ำหรือวงวนในตัวเอง และเป็นกราฟเชื่อมโยง
รับประกันว่าผลรวมของ $n$ และผลรวมของ $m$ ในทุกชุดทดสอบจะไม่เกิน $5 \cdot 10^5$
ข้อมูลส่งออก
สำหรับแต่ละชุดทดสอบ ให้แสดงผลหนึ่งบรรทัดที่ประกอบด้วยจำนวนเต็มไม่ลบ $n$ ตัว คือ $s'_i$ ($0 \le s'_i \le 10^{18}$) กล่าวโดยเฉพาะคือ ให้ $s_i$ แทนเวลาที่พนักงานคนที่ $i$ เริ่มทำงาน แล้ว $s_i = \frac{s'_i}{10^6}$ หากมีตารางเวลาที่เหมาะสมที่สุดหลายแบบที่ทำให้จำนวนคนที่ไม่พึงพอใจน้อยที่สุด ให้แสดงผลแบบใดก็ได้
ตัวอย่าง
ข้อมูลนำเข้า 1
5 2 1 1 5 AA 1 2 3 3 1 5 ABA 1 2 1 3 2 3 5 4 2 4 BABBB 1 2 1 5 2 3 2 4 6 9 1 5 BABBAB 1 2 1 3 1 4 2 6 3 4 3 5 3 6 4 5 5 6 7 7 2 5 BBAAABB 1 2 1 3 1 5 2 4 3 6 3 7 6 7
ข้อมูลส่งออก 1
0 1 1 0 2 2 1 0 3 4 2 3 1 4 4000005 0 3000003 3000004 3000002 3000005 3000006 1 0