คำอธิบายโจทย์
คุณมี Bangboo สุดน่ารักอยู่ตัวหนึ่ง และมันกำลังเข้าร่วมใน "การผจญภัยครั้งใหญ่ของ Marcel"
Bangboo ตัวนี้เคลื่อนที่ในปริภูมิสามมิติ จุดเริ่มต้นของมันคือ $(S_x, S_y, S_z)$ และจุดหมายปลายทางคือ $(T_x, T_y, T_z)$ คุณสามารถมองว่ามันเป็นลูกบาศก์หนึ่งหน่วยที่มีจุดศูนย์กลางอยู่ที่ $(S_x, S_y, S_z)$ ในปริภูมิสามมิตินี้มีสิ่งกีดขวาง $n$ ชิ้น ซึ่งแต่ละชิ้นเป็นลูกบาศก์หนึ่งหน่วยที่มีจุดศูนย์กลางอยู่ที่ $(x_i, y_i, z_i)$ รับประกันว่าพิกัดของจุดเริ่มต้น จุดหมายปลายทาง และสิ่งกีดขวางทั้งหมดจะแตกต่างกันเป็นคู่ๆ และจะต้องมีสิ่งกีดขวางอยู่ที่ $(S_x, S_y, S_z - 1)$ และ $(T_x, T_y, T_z - 1)$ เสมอ
Bangboo สามารถเทเลพอร์ตได้ ในแต่ละก้าว มันมีวิธีเทเลพอร์ตให้เลือก $m$ วิธี สมมติว่าปัจจุบันมันอยู่ที่ $(x, y, z)$ วิธีเทเลพอร์ตวิธีที่ $i$ จะส่งมันไปยัง $(x + a_i, y + b_i, z + c_i)$ หลังจากนั้นมันจะตกอย่างอิสระ กล่าวอย่างเป็นทางการ มันจะเทเลพอร์ตไปยัง $(x + a_i, y + b_i, d)$ โดยที่ $d$ คือค่าที่มากที่สุดที่สอดคล้องกับ $d \le z + c_i$ และมีสิ่งกีดขวางอยู่ที่ $(x + a_i, y + b_i, d - 1)$ หากมีสิ่งกีดขวางอยู่ที่ $(x + a_i, y + b_i, z + c_i)$ หรือไม่มีค่า $d$ ดังกล่าว จะไม่สามารถทำการเทเลพอร์ตนี้ได้
เป้าหมายของคุณคือการทำให้ Bangboo เดินทางจากจุดเริ่มต้นไปยังจุดหมายปลายทางโดยใช้จำนวนก้าวน้อยที่สุด หากเป็นไปไม่ได้ที่จะไปถึงจุดหมายปลายทาง ให้แสดงผล $-1$
ข้อมูลนำเข้า
บรรทัดแรกประกอบด้วยจำนวนเต็ม $T$ ($1 \le T \le 500$) แทนจำนวนกรณีทดสอบ
สำหรับแต่ละกรณีทดสอบ:
บรรทัดแรกประกอบด้วยจำนวนเต็มสองจำนวน $n, m$ ($2 \le n \le 10^3$, $1 \le m \le 10^3$) แทนจำนวนสิ่งกีดขวางและจำนวนวิธีเทเลพอร์ตที่ Bangboo สามารถใช้ได้ตามลำดับ
บรรทัดที่สองประกอบด้วยจำนวนเต็มหกจำนวน $S_x, S_y, S_z, T_x, T_y, T_z$ ($0 \le S_x, S_y, S_z, T_x, T_y, T_z \le 10^9$) แทนจุดเริ่มต้นและจุดหมายปลายทางของ Bangboo
อีก $n$ บรรทัดถัดไป แต่ละบรรทัดประกอบด้วยจำนวนเต็มสามจำนวน $x_i, y_i, z_i$ ($0 \le x_i, y_i, z_i \le 10^9$) แทนพิกัดของสิ่งกีดขวางชิ้นที่ $i$ รับประกันว่าจะต้องมีสิ่งกีดขวางอยู่ที่ $(S_x, S_y, S_z - 1)$ และ $(T_x, T_y, T_z - 1)$ เสมอ
อีก $m$ บรรทัดถัดไป แต่ละบรรทัดประกอบด้วยจำนวนเต็มสามจำนวน $a_i, b_i, c_i$ ($|a_i|, |b_i|, |c_i| \le 10^9$) แทนวิธีเทเลพอร์ตวิธีที่ $i$
สำหรับแต่ละกรณีทดสอบ รับประกันว่าพิกัดทั้งหมดในข้อมูลนำเข้าแตกต่างกันเป็นคู่ๆ และวิธีเทเลพอร์ตทั้งหมดแตกต่างกันเป็นคู่ๆ
รับประกันว่าผลรวมของ $n$ จากทุกกรณีทดสอบรวมกันไม่เกิน $10^3$ และผลรวมของ $m$ จากทุกกรณีทดสอบรวมกันไม่เกิน $10^3$
ข้อมูลส่งออก
สำหรับแต่ละกรณีทดสอบ ให้แสดงผลจำนวนเต็มหนึ่งจำนวนในหนึ่งบรรทัด แทนจำนวนก้าวที่น้อยที่สุดที่ต้องใช้ในการเดินทางจากจุดเริ่มต้นไปยังจุดหมายปลายทาง หากเป็นไปไม่ได้ที่จะไปถึงจุดหมายปลายทาง ให้แสดงผล $-1$
ตัวอย่าง
ข้อมูลนำเข้า 1
2 6 4 3 3 3 5 5 5 3 3 2 5 5 4 5 5 7 4 5 5 2 3 2 4 1 1 -1 0 3 2 -2 -1 1 4 9 1 0 0 3 2 0 0 1 1 1 1 0 0 0 1 1 0 1 1 2 1 1 1 1 1 2
ข้อมูลส่งออก 1
5 -1