ร้อยเอก Thrawn แห่ง Chiss Ascendancy ติดค้างอยู่บนดาวบ้านเกิดของชาว Paataatus! เขามีข้อมูลสำคัญยิ่งยวดที่ต้องส่งไปให้ถึงพลเรือเอก Ar'alani แต่เขาไม่สามารถรอยานอวกาศฝ่ายเดียวกันมารับได้ ดังนั้นเขาจึงต้องจัดตั้งชุดสื่อสารสามเส้า (communications triad) เพื่อส่งข้อมูลนั้นไปให้เธอ ชุดสื่อสารสามเส้าประกอบด้วยอุปกรณ์ 3 ส่วน ซึ่งทั้งหมดจะต้องวางอยู่ในระยะทางแบบยุคลิดที่ไม่เป็นศูนย์และเท่ากันทั้งหมด (กล่าวคือ อยู่ที่จุดยอดของรูปสามเหลี่ยมด้านเท่า) จึงจะสามารถส่งข้อมูลได้สำเร็จ

อย่างไรก็ตาม ความสัมพันธ์ทางการเมืองระหว่างชาว Chiss และชาว Paataatus นั้นตึงเครียด รัฐบาล Paataatus จึงไม่อนุญาตให้ Thrawn วางชิ้นส่วนของชุดสื่อสารสามเส้าไว้ที่ใดก็ได้ตามใจชอบ เมืองหลวงของ Paataatus มีรูปร่างเป็นรูปหกเหลี่ยมด้านเท่ามุมเท่าที่มีความยาวด้านเท่ากับ $l$ โดยมีถนน (Street) ที่ขนานกันและมีระยะห่างเท่ากันจำนวน $2l + 1$ สาย ทอดตัวจากทิศตะวันตกไปทิศตะวันออก กำกับหมายเลขตั้งแต่ $-l$ ถึง $l$ จากทิศใต้ไปทิศเหนือ โดยถนนหมายเลข $-l$ จะทอดตัวไปตามด้านใต้สุดของรูปหกเหลี่ยม ถนนหมายเลข $l$ จะทอดตัวไปตามด้านเหนือสุดของรูปหกเหลี่ยม และถนนหมายเลข $0$ จะตัดผ่านจุดศูนย์กลางของรูปหกเหลี่ยม

ในทำนองเดียวกัน มีถนนสายหลัก (Avenue) ที่ขนานกันและมีระยะห่างเท่ากันจำนวน $2l + 1$ สาย ทอดตัวจากทิศตะวันตกเฉียงเหนือไปยังทิศตะวันออกเฉียงใต้ กำกับหมายเลขตั้งแต่ $-l$ ถึง $l$ จากทิศตะวันตกเฉียงใต้ไปยังทิศตะวันออกเฉียงเหนือ โดยถนนสายหลักหมายเลข $-l$ จะทอดตัวไปตามด้านตะวันตกเฉียงใต้สุดของรูปหกเหลี่ยม ถนนสายหลักหมายเลข $l$ จะทอดตัวไปตามด้านตะวันออกเฉียงเหนือสุดของรูปหกเหลี่ยม และถนนสายหลักหมายเลข $0$ จะตัดผ่านจุดศูนย์กลางของรูปหกเหลี่ยม

และมีถนนบูเลอวาร์ด (Boulevard) ที่ขนานกันและมีระยะห่างเท่ากันจำนวน $2l + 1$ สาย ทอดตัวจากทิศตะวันตกเฉียงใต้ไปยังทิศตะวันออกเฉียงเหนือ กำกับหมายเลขตั้งแต่ $-l$ ถึง $l$ จากทิศตะวันออกเฉียงใต้ไปยังทิศตะวันตกเฉียงเหนือ โดยถนนบูเลอวาร์ดหมายเลข $-l$ จะทอดตัวไปตามด้านตะวันออกเฉียงใต้สุดของรูปหกเหลี่ยม ถนนบูเลอวาร์ดหมายเลข $l$ จะทอดตัวไปตามด้านตะวันตกเฉียงเหนือสุดของรูปหกเหลี่ยม และถนนบูเลอวาร์ดหมายเลข $0$ จะตัดผ่านจุดศูนย์กลางของรูปหกเหลี่ยม

นี่คือตัวอย่างผังเมืองหลวงสำหรับ $l = 2$:

ที่จุดตัดแต่ละจุดของถนน ถนนสายหลัก และถนนบูเลอวาร์ด จะมีหอคอยตั้งอยู่หนึ่งแห่ง หากหมายเลขถนนคือ $x$ หมายเลขถนนสายหลักคือ $y$ และหมายเลขถนนบูเลอวาร์ดคือ $z$ หอคอยนั้นจะมีพิกัดเป็น $(x, y, z)$ หอคอยแต่ละแห่งมีเจ้าหน้าที่ชาว Paataatus คนใดคนหนึ่งเป็นเจ้าของ

นับว่ายังโชคดีสำหรับ Thrawn ที่ตลอดอาชีพการงานของเขา เขาเคยช่วยเหลือเจ้าหน้าที่ชาว Paataatus ไว้หลายคน และตอนนี้พวกเขาก็ยินดีที่จะช่วยเหลือเขากลับ โดยอนุญาตให้เขาติดตั้งชิ้นส่วนหนึ่งของชุดสื่อสารสามเส้าไว้ในหอคอยของพวกเขาได้ พวกเขาเป็นเจ้าของหอคอยรวมกันทั้งหมด $n$ แห่ง ดังนั้น Thrawn จึงต้องเลือกหอคอย 3 แห่งในจำนวนนี้ที่มีระยะห่างระหว่างกันเท่ากันเพื่อจัดตั้งชุดสื่อสารสามเส้า ก่อนที่จะตัดสินใจเลือก Thrawn ต้องการทราบทางเลือกทั้งหมดของเขา หรืออย่างน้อยก็อยากทราบว่ามีกี่ทางเลือก จงช่วยเขานับจำนวนวิธีในการเลือกหอคอย 3 แห่งที่สามารถจัดตั้งชุดสื่อสารสามเส้าได้

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

บรรทัดแรกประกอบด้วยจำนวนเต็มสองจำนวนคือ $l$ และ $n$ — ความยาวด้านของเมืองหลวงและจำนวนหอคอยที่ยินดีช่วยเหลือ Thrawn ($1 \le l \le 500$; $1 \le n \le 3 \cdot l \cdot (l + 1) + 1$)

แต่ละบรรทัดใน $n$ บรรทัดถัดไปประกอบด้วยจำนวนเต็ม 3 จำนวนคือ $x_i, y_i, z_i$ — พิกัดของหอคอยแห่งที่ $i$ ($-l \le x_i, y_i, z_i \le l$) รับประกันว่าทุกชุดของพิกัดแทนหอคอยที่มีอยู่จริง และหอคอยทั้งหมดในข้อมูลนำเข้าแตกต่างกันทั้งหมด

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

แสดงผลจำนวนเต็มเพียงตัวเดียว — จำนวนวิธีในการเลือกหอคอยทั้ง 3 แห่งตามที่ต้องการ

ตัวอย่าง

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

2 6
-1 -2 1
2 2 0
-1 1 -2
-1 0 -1
1 1 0
0 1 -1

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

1

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

1 7
0 1 -1
1 1 0
0 -1 1
1 0 1
-1 -1 0
-1 0 -1
0 0 0

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

8

หมายเหตุ

ตารางกริดสามเหลี่ยมเพื่อความสะดวกของคุณ: