โจทย์ข้อนี้เป็นโจทย์โต้ตอบ (interactive problem) อย่าลืมล้างบัฟเฟอร์เอาต์พุตหลังจากการพิมพ์ทุกครั้ง คุณสามารถล้างเอาต์พุตได้โดยใช้:

• fflush(stdout) หรือ cout.flush() ใน C/C++;
• System.out.flush() ใน Java และ Kotlin;
• sys.stdout.flush() ใน Python.

แนวคิดของเกม วาดภาพประกอบโดย Nano Banana Pro

คุณกำลังเข้าร่วมในเกมวางแผนผลัดกันเล่นที่รู้จักกันในชื่อ Revolver Roulette

เกมเริ่มต้นด้วยปืนลูกโม่ที่บรรจุกระสุนไว้ $6$ นัดพอดี กระสุนแต่ละนัดเป็น กระสุนจริง (live) หรือ กระสุนด้าน (blank) อย่างเป็นอิสระต่อกันด้วยความน่าจะเป็นที่เท่ากัน ผู้เล่นทั้งสองฝ่ายทราบจำนวนกระสุนจริงและกระสุนด้านที่เหลืออยู่ในลูกโม่ในขณะนั้นเสมอ แต่ไม่ทราบลำดับที่แน่นอน

ผู้เล่นแต่ละคนเริ่มต้นด้วยพลังชีวิต (HP) $5$ แต้ม และไอเทม $2$ ชิ้น หาก HP ของผู้เล่นคนใดลดลงเหลือ $0$ หรือต่ำกว่า ผู้เล่นคนนั้นจะถูกคัดออกและผู้เล่นอีกฝ่ายจะเป็นผู้ชนะ ผู้เล่นจะผลัดกันดำเนินแอ็กชันในเทิร์นของตน

ขั้นตอนในแต่ละเทิร์น

ในระหว่างเทิร์นของตน ผู้เล่นที่กำลังอยู่ในเทิร์นสามารถดำเนินแอ็กชันต่อไปนี้ได้ไม่จำกัดจำนวนครั้ง:

• ใช้ไอเทมใดๆ
• ดำเนินแอ็กชันการยิงใดๆ

เทิร์นจะสิ้นสุดลงก็ต่อเมื่อแอ็กชันการยิงส่งผลให้เทิร์นเปลี่ยนไปเป็นของผู้เล่นอีกฝ่าย หรือมีผู้เล่นคนใดคนหนึ่งถูกคัดออก

แอ็กชันการยิง

ผู้เล่นที่กำลังอยู่ในเทิร์นต้องเลือกแอ็กชันการยิงอย่างใดอย่างหนึ่งต่อไปนี้:

• Fire at Opponent: ผู้เล่นที่อยู่ในเทิร์นยิงกระสุนนัดถัดไปใส่ผู้เล่นอีกฝ่าย หากเป็นกระสุนจริง ผู้เล่นอีกฝ่ายจะเสีย $1$ HP ไม่ว่ากระสุนจะเป็นประเภทใด เทิร์นจะเปลี่ยนไปเป็นของผู้เล่นอีกฝ่าย
• Fire at Self: ผู้เล่นที่อยู่ในเทิร์นยิงกระสุนนัดถัดไปใส่ตัวเอง หากเป็นกระสุนจริง ผู้เล่นที่อยู่ในเทิร์นจะเสีย $1$ HP และเทิร์นจะเปลี่ยนไปเป็นของผู้เล่นอีกฝ่าย มิฉะนั้นหากเป็นกระสุนด้าน ผู้เล่นที่อยู่ในเทิร์นจะได้ครองเทิร์นต่อและดำเนินแอ็กชันต่อไปได้

ไอเทม

เมื่อไอเทมถูกใช้งาน ไอเทมนั้นจะถูกใช้หมดไป และผู้เล่นที่อยู่ในเทิร์นจะยังคงครองเทิร์นอยู่ไม่ว่าไอเทมจะเป็นประเภทใด ไอเทมทั้งหมดจะเปิดเผยให้ผู้เล่นทั้งสองฝ่ายเห็น เมื่อผู้เล่นได้รับไอเทมใหม่ (รวมถึงไอเทมเริ่มต้นแต่ละชิ้น) ไอเทมจะถูกสุ่มอย่างสม่ำเสมอจากสี่ประเภทต่อไปนี้:

• Dummy: ยิงกระสุนนัดถัดไปใส่หุ่นซ้อม การกระทำนี้จะใช้กระสุนนัดนั้นไปและไม่ถือว่าเป็นแอ็กชันการยิง
• Magnifier: แอบดูกระสุนนัดถัดไปเพื่อเปิดเผยว่ากระสุนนัดถัดไปเป็นกระสุนจริงหรือกระสุนด้าน ผู้เล่นทั้งสองฝ่ายจะทราบผลลัพธ์นี้
• Converter: สลับประเภทของกระสุนนัดถัดไป (กระสุนจริง $\leftrightarrow$ กระสุนด้าน) ผู้เล่นทั้งสองฝ่ายจะเห็นจำนวนกระสุนจริงและกระสุนด้านที่อัปเดตแล้ว

• Cage: ได้รับเอฟเฟกต์แบบใช้ครั้งเดียวที่ป้องกันไม่ให้เทิร์นสิ้นสุดลงในแอ็กชันการยิงครั้งถัดไปที่ตามปกติจะทำให้จบเทิร์น กล่าวคือ:

  • หากผู้เล่นดำเนินการ Fire at Opponent ในภายหลัง (ไม่ว่ากระสุนจะเป็นกระสุนจริงหรือกระสุนด้าน) เอฟเฟกต์จะทำงานและเทิร์นจะไม่สิ้นสุดลง
  • หากผู้เล่นดำเนินการ Fire at Self ในภายหลังและกระสุนเป็นกระสุนจริง เอฟเฟกต์จะทำงานและเทิร์นจะไม่สิ้นสุดลง (ผู้เล่นยังคงเสีย $1$ HP แต่ได้ครองเทิร์นต่อ)

  เอฟเฟกต์จะถูกใช้หมดไปทันทีหลังจากที่ทำงานหนึ่งครั้ง ในแต่ละเทิร์นสามารถใช้ไอเทม Cage ได้อย่างมากหนึ่งชิ้น

การบรรจุกระสุนใหม่ (Reloading)

เมื่อลูกโม่ว่างเปล่า กระสุนใหม่ $6$ นัดจะถูกบรรจุทันที (แต่ละนัดเป็นกระสุนจริงหรือกระสุนด้านอย่างเป็นอิสระต่อกันด้วยความน่าจะเป็นที่เท่ากัน) ผู้เล่นทั้งสองฝ่ายจะได้รับแจ้งจำนวนกระสุนจริงและกระสุนด้านชุดใหม่ นอกจากนี้ ผู้เล่นแต่ละคนจะได้รับไอเทมเติมจนครบสูงสุด $2$ ชิ้น (ผู้เล่นที่มีไอเทม $k$ ชิ้นจะได้รับไอเทมใหม่ $(2 - k)$ ชิ้น โดยแต่ละชิ้นสุ่มอย่างสม่ำเสมอและเป็นอิสระต่อกันจากสี่ประเภทข้างต้น)

เป้าหมาย

คุณคือผู้เล่นที่ได้เริ่มเทิร์นแรก และเป้าหมายของคุณคือการเอาชนะเกมด้วยการคัดคู่ต่อสู้ออก

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

บรรทัดแรกประกอบด้วยจำนวนเต็มสองจำนวน $n$ และ $w$ แสดงว่าคุณต้องชนะอย่างน้อย $w$ เกมจากทั้งหมด $n$ เกมจึงจะได้รับการยอมรับ มีชุดทดสอบเพียงสามชุดเท่านั้น:

• ชุดทดสอบตัวอย่าง: $n = 1$ และ $w = 0$. ($0\%$)
• ชุดทดสอบลับ 1: $n = 2\,000$ และ $w = 1\,000$. ($50\%$)
• ชุดทดสอบลับ 2: $n = 20\,000$ และ $w = 11\,000$. ($55\%$)

สามารถพิสูจน์ได้ว่าเมื่อผู้เล่นทั้งสองฝ่ายเล่นอย่างเหมาะสมที่สุด ผู้เล่นที่ได้เริ่มเทิร์นแรกจะชนะประมาณ $56.89\%$ ของจำนวนเกมทั้งหมด

โปรโตคอลการโต้ตอบ

เริ่มต้นเกม

โปรแกรมของคุณทำหน้าที่เป็นผู้เล่นที่ได้เริ่มเทิร์นแรกแข่งขันกับอินเทอร์แอกเตอร์ เมื่อเริ่มต้นแต่ละเกม อินเทอร์แอกเตอร์จะพิมพ์จำนวนเต็ม $g$:

• หาก $g = 0$ เกมทั้งหมดในการรันปัจจุบันเสร็จสมบูรณ์แล้ว โปรแกรมของคุณจะต้องหยุดทำงานทันที
• มิฉะนั้น $g$ คือหมายเลขเกมปัจจุบัน ($1 \le g \le n$)

เนื่องจากปัญหาทางเทคนิค โปรแกรมของคุณจะถูกรัน สองครั้ง ในแต่ละชุดทดสอบ:

• อินเทอร์แอกเตอร์สามารถตัดสินใจว่าจะเริ่มต้นโปรแกรมของคุณใหม่หรือไม่ โดยการส่งค่า $g = 0$ มาให้ได้ทุกเมื่อ

คุณจะได้รับค่า $n$ และ $w$ เดียวกันสำหรับการรันแต่ละครั้งในชุดทดสอบ ดังนั้น $n$ จึง ไม่ได้ เท่ากับจำนวนเกมในการรันปัจจุบันเสมอไป รับประกันว่าแต่ละเกม $1, \dots, n$ จะถูกเล่นครบหนึ่งครั้งพอดีในการรันทั้งสองครั้งรวมกัน นอกเหนือจากนี้ โปรแกรมของคุณสามารถเพิกเฉยต่อเงื่อนไขการรันสองครั้งได้อย่างปลอดภัย

สถานะเกม

จากนั้น อินเทอร์แอกเตอร์จะพิมพ์บรรทัดสถานะเกมซึ่งประกอบด้วยจำนวนเต็มไม่ติดลบ $13$ จำนวน:

$$t \quad l \quad b \quad h_1 \quad d_1 \quad m_1 \quad c_1 \quad k_1 \quad h_2 \quad d_2 \quad m_2 \quad c_2 \quad k_2$$

• $t \in \{0, 1, 2\}$: สถานะเทิร์น
• $l, b$ ($1 \le l + b \le 6$): จำนวนกระสุนจริงและกระสุนด้านที่เหลืออยู่ในลูกโม่ในขณะนั้น
• $h_1$ ($0 \le h_1 \le 5$): HP ปัจจุบันของคุณ
• $d_1, m_1, c_1, k_1$ ($0 \le d_1 + m_1 + c_1 + k_1 \le 2$): จำนวนไอเทม Dummy, Magnifier, Converter และ Cage ที่คุณถืออยู่ในปัจจุบัน
• $h_2$ ($0 \le h_2 \le 5$): HP ปัจจุบันของคู่ต่อสู้
• $d_2, m_2, c_2, k_2$ ($0 \le d_2 + m_2 + c_2 + k_2 \le 2$): จำนวนไอเทม Dummy, Magnifier, Converter และ Cage ที่คู่ต่อสู้ถืออยู่

กรณี $t = 0$ (จบเกม)

เกมปัจจุบันสิ้นสุดลงแล้ว อินเทอร์แอกเตอร์จะดำเนินการไปยังเกมถัดไป (พิมพ์ค่า $g$ ใหม่)

กรณี $t = 1$ (เทิร์นของคุณ)

คุณต้องพิมพ์จำนวนเต็มหนึ่งจำนวนเพื่อเลือกแอ็กชัน:

1. Fire at Opponent.
2. Fire at Self.
3. ใช้ไอเทม Dummy.
4. ใช้ไอเทม Magnifier.
5. ใช้ไอเทม Converter.
6. ใช้ไอเทม Cage.

หากแอ็กชันไม่ถูกต้อง (เช่น ใช้ไอเทมที่คุณไม่มี หรือใช้ไอเทม Cage มากกว่าหนึ่งครั้งในเทิร์นเดียวกัน) สถานะเกมจะไม่เปลี่ยนแปลง อินเทอร์แอกเตอร์จะพิมพ์ $0$ และบรรทัดสถานะเดิม ($13$ จำนวนเต็ม) ซ้ำอีกครั้ง แม้ว่าจะยังเป็นเทิร์นของคุณ แต่คุณต้องเลือกแอ็กชันที่ถูกต้องอื่นเพื่อดำเนินเกมต่อ

มิฉะนั้น แอ็กชันจะมีผลและอินเทอร์แอกเตอร์จะพิมพ์จำนวนเต็มผลลัพธ์:

• สำหรับแอ็กชัน $1$–$5$: คืนค่า $1$ หากกระสุนนัดถัดไปก่อนทำแอ็กชันเป็นกระสุนจริง คืนค่า $2$ หากเป็นกระสุนด้าน
• สำหรับแอ็กชัน $6$: คืนค่า $1$ (ไม่เปิดเผยข้อมูลกระสุน)

จากนั้นอินเทอร์แอกเตอร์จะพิมพ์บรรทัดสถานะเกมที่อัปเดตแล้ว

กรณี $t = 2$ (เทิร์นของคู่ต่อสู้)

อินเทอร์แอกเตอร์จะจำลองแอ็กชันของคู่ต่อสู้และพิมพ์ออกมาสองบรรทัด:

• รหัสแอ็กชัน $a \in \{1, \dots, 6\}$
• จำนวนเต็มผลลัพธ์ ($1$ หรือ $2$ ตามที่อธิบายไว้ข้างต้น)

คู่ต่อสู้ของคุณจะไม่ทำแอ็กชันที่ผิดกฎเด็ดขาด หลังจากนั้นทันที อินเทอร์แอกเตอร์จะพิมพ์บรรทัดสถานะเกมถัดไป ($13$ จำนวนเต็ม)

สำหรับแต่ละรอบของเกม ตัวจำลองเกมจะใช้ตัวสร้างตัวเลขสุ่มเทียมที่มีเมล็ดพันธุ์สุ่ม (random seed) ตายตัว นอกจากนี้ คู่ต่อสู้ในอินเทอร์แอกเตอร์ยังใช้กลยุทธ์แบบกำหนดตายตัว (deterministic) การตัดสินใจเริ่มต้นโปรแกรมของคุณใหม่เป็นอิสระจากขั้นตอนการโต้ตอบ ดังนั้น ลำดับของแอ็กชันที่เหมือนกันจะนำไปสู่สถานะเกมเดียวกันเสมอ

มีเครื่องมือทดสอบเตรียมไว้ให้เพื่อช่วยในการพัฒนาและทดสอบโปรแกรมของคุณ

ตัวอย่าง

ตัวอย่างที่ 1, รอบที่ 1

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

1 0
1
1 3 3 5 0 0 0 2 5 1 0 1 0

1
1 3 3 5 0 0 0 1 5 1 0 1 0

1
1 2 3 5 0 0 0 1 4 1 0 1 0

0
1 2 3 5 0 0 0 1 4 1 0 1 0

2
1 2 2 5 0 0 0 1 4 1 0 1 0

1
2 1 2 5 0 0 0 1 3 1 0 1 0
5
2
2 2 1 5 0 0 0 1 3 1 0 0 0
1
1
1 1 1 4 0 0 0 1 3 1 0 0 0

1
2 0 1 4 0 0 0 1 2 1 0 0 0
3
2
2 2 4 4 0 1 0 1 2 0 1 0 1
2
1
1 1 4 4 0 1 0 1 1 0 1 0 1

1
1 1 4 4 0 0 0 1 1 0 1 0 1

1
0 0 4 4 0 0 0 1 0 0 1 0 1
0

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

6


1


6


2


1








1








4


1

ตัวอย่างที่ 1, รอบที่ 2

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

1 0
0

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