Balkan2011

BOI 2011 Day 2: Trapezoid

Source: http://www.boi2011.ro/resurse/tasks/trapezoid.pdf

(หน่วยความจำ 64 MB, เวลาทำงาน 0.5 sec, คะแนนเต็ม 100 คะแนน)

เมื่อพิจารณาเส้นตรงในแนวนอนสองเส้นใดๆ สี่เหลี่ยมคางหมู Ti สามารถสร้างขึ้นระหว่างเส้นทั้งสองนี้ โดยจะประกอบด้วยเส้นแนวตั้งที่เชื่อมจุดสองจุดบนเเส้นแนวนอนด้านบนและสองจุดจากเส้นด้านล่าง (ดูรูปประกอบ) เราจะตั้งชื่อจุดเหล่านี้ว่า ai, bi, ci, และ di ที่หมายถึงจุดบนซ้าย, บนขวา, ล่างซ้าย, และล่างขวา ตามลำดับ ซึ่งเป็นเป็นจุดยอดของสี่เหลี่ยมคางหมู Ti ซับเซต S ของสี่เหลี่ยมคางหมูจะเรียกว่าอิสระต่อกันเมื่อไม่มีสองสี่เหลี่ยมคางหมูใดใน S ที่ซ้อนทับกัน

หน้าที่ของคุณ

ให้หาว่าขนาด (cardinality) ของซับเซตของสี่เหลี่ยมคางหมูที่อิสระต่อกันที่ใหญ่ที่สุด (ขนาดใหญ่ที่สุดหมายถึงมีจำนวนสมาชิกมากที่สุด) และให้หาด้วยว่ามีซับเซตของสี่เหลี่ยมคางหมูที่อิสระต่อกันทั้งหมดกี่ซับเซตที่มีขนาดใหญ่ที่สุดเท่ากัน ให้ตอบจำนวนที่สองโดยใช้เศษจากการหาร (modulo) ด้วย 30013

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

บรรทัดที่ 1 ประกอบด้วย จำนวนเต็มหนึ่งจำนวน N ที่แสดงถึงจำนวนสี่เหลี่ยมคางหมูทั้งหมด ต่อมาอีก N บรรทัด แต่ละบรรทัดประกอบด้วยจำนวนเต็มสี่จำนวน ai, bi, ci, และ di ทั้งนี้ไม่มีสี่เหลี่ยมคางหมูใดๆ ที่มีจุดยอด (จุดมุม) เดียวกัน

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

ให้แสดงคำตอบบรรทัดเดียวโดยประกอบไปด้วยจำนวนสองจำนวน คั่นด้วยช่องกลาง

จำนวนแรก คือ ขนาดของเซตของสี่เหลี่ยมคางหมูที่อิสระต่อกันที่ใหญ่ที่สุด

จำนวนที่สอง คือ จำนวนเซตที่อิสระต่อกัน ที่แตกต่างกันทั้งหมดที่เป็นไปได้ หารเอาเศษด้วย 30013

เงื่อนไข

- 1 <= N <= 100,000

- 1 <= ai, bi, ci, di <= 1,000,000,000

- ถ้าตอบถูกเฉพาะจำนวนแรกในข้อมูลส่งออก จะได้คะแนน 40% ของข้อมูลทดสอบนั้นๆ

- 40% ของข้อมูลทดสอบทั้งหมดจะมี N <= 5,000

ตัวอย่าง

ให้ดูรูปประกอบที่โจทย์ครับ