กู๊ดมาร์เก็ต (acm15_good_market)

• Problem
• Submit
• Status
• Discussion
• Solution
• Analytics

Time limit:

1000 ms

Memory limit:

64 MB

ตลาดนัดยอดนิยมของเหล่าฮิปสเตอร์แห่งใหม่ได้เปิดตัวขึ้นมีชื่อว่า Goods Market ในวันแรกที่เปิดตลาดนัดแห่งใหม่นี้จะมีร้านค้าเปิดอยู่ N ร้าน หลังจากนั้นจะมีร้านค้าเข้ามาเช่าเพิ่มขึ้นได้เรื่อยๆ อย่างไม่จำกัดจำนวน  โดยข้อดีของการที่มาตั้งร้านขายของที่ Goods Market คือ พ่อค้าแม่ค้าที่มาตั้งร้านขายของสามารถเป็นคนกำหนดราคาค่าเช่าได้เอง 

แต่มีกฎข้อหนึ่งบอกไว้ว่า เมื่อไรที่เจ้าของ Goods Market เห็นว่าค่าเช่าที่ควรขึ้นราคา  ร้านทั้งหมดที่ขายของอยู่ที่ Goods Market ณ ขณะนั้น  จะต้องเสียค่าเช่าเพิ่มขึ้นด้วย 1 ขั้น ในอัตรา K บาท ตามที่เจ้าของ Goods Market กำหนดไว้    เช่น  ถ้ากำหนดว่า 1 ขั้น  คือ 100 บาท  ทุก ๆ ครั้งที่มีการประกาศขึ้นค่าเช่า  ร้านทั้งหมดที่เคยเช่าก่อนมีการประกาศทั้งหมด จะต้องขึ้นค่าเช่าจากเดิม 100 บาท  ในกรณีที่มีการประกาศขึ้นค่าเช่าหลายครั้ง  เช่น สมมติมีการขึ้นราคาค่าเช่า 2 ครั้ง  ร้านค้าที่เข้ามาเช่าก่อนการประกาศขึ้นค่าเช่าทั้งสองครั้ง  จะต้องจ่ายค่าเช่าเท่ากับ  ราคาที่เสนอตอนเข้ามาขายครั้งแรก+200 บาท  ส่วนร้านค้าที่เข้ามาเช่าภายหลังการประกาศขึ้นค่าเช่าครั้งแรก แต่ก่อนประกาศขึ้นค่าเช่าครั้งที่สองจะต้องจ่ายเพิ่มจากที่เสนอค่าเช่าครั้งแรกสุดเพียง 100 บาท

ตลาดแห่งนี้มีคนเข้ามาขายของเยอะมากจากการที่ตลาดแห่งนี้เปิดให้คนมาเช่าที่ได้อย่างไม่จำกัดจำนวน  เจ้าของต้องการแก้ปัญหานี้โดยการกำหนดนโยบายคัดร้านออก  โดยจะให้ร้านที่มีค่าเช่าถูกที่สุดออกจากตลาด 1 ร้าน  โดยเวลาที่จะคัดร้านออกก็ขึ้นอยู่กับการตัดสินใจของเจ้าของตลาดเช่นเดิม

ถ้า Goods Market มีการดำเนินการ M ครั้ง  โดยการดำเนินการมีทั้งหมด 3 ประเภท คือ 

(1) มีร้านค้าใหม่เพิ่มเข้ามา โดยเสนอราคาเช่าของร้าน P บาท

(2) ประกาศเพิ่มค่าเช่าร้านทุกร้าน

(3) ประกาศคัดร้านออก

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

Input

บรรทัดแรกประกอบด้วยจำนวนเต็ม T (1 ≤ T ≤ 20) แทนจำนวนชุดทดสอบ ซึ่งในแต่ละชุดทดสอบจะประกอบด้วยข้อมูลต่างๆ ดังนี้

บรรทัดแรกประกอบด้วย  จำนวนเต็ม N, M, K (1 ≤ N, M ≤ 100,000  และ 1 ≤ K ≤ 100)

บรรทัดต่อมา  รับจำนวนเต็ม  N ตัว  เป็นจำนวนเต็ม Xi โดย Xi คือ ค่าเช่าของร้านที่ i   (1 ≤ Xi ≤ 10,000,000)

M บรรทัดต่อมา แต่ละบรรทัด รับจำนวนเต็ม A คือ คำสั่งที่จะดำเนินการเป็นเลข (1) เพิ่มร้านค้า (2) เพิ่มค่าเช่า (3)คัดร้านค้าออก โดยถ้าเป็นคำสั่งที่ (1) จะรับจำนวนเต็ม P เพิ่มอีก 1 ค่า คือ ค่าเช่าที่ร้านค้านั้นเสนอมา (1 ≤ P ≤ 10,000,000)

Output

แต่ละบรรทัดประกอบด้วย คำตอบของแต่ละชุดทดสอบ โดยแต่ละบรรทัดจะประกอบด้วยจำนวนเต็มสองจำนวน  จำนวนแรก คือ จำนวนร้านที่เหลือในตลาด Goods Market  จำนวนที่สอง คือ ผลรวม ค่าเช่าของร้านที่เหลือทั้งหมด

Editor:

Source: ACM ICPC 2015 Thailand Local Central Group B