الوصف
لديك بانغبو (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)$.
يمكن للبانغبو الانتقال الآني. في كل خطوة، لديه $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$، فلا يمكن إجراء هذا الانتقال الآني.
هدفك هو جعل البانغبو يصل إلى الوجهة من نقطة البداية بأقل عدد ممكن من الخطوات. إذا كان من المستحيل الوصول إلى الوجهة، فاطبع $-1$.
الإدخال
يحتوي السطر الأول على عدد صحيح $T$ ($1 \le T \le 500$)، يمثل عدد حالات الاختبار.
لكل حالة اختبار:
يحتوي السطر الأول على عددين صحيحين $n, m$ ($2 \le n \le 10^3$، $1 \le m \le 10^3$)، يمثلان عدد العوائق وعدد طرق الانتقال الآني المتاحة للبانغبو على التوالي.
يحتوي السطر الثاني على ستة أعداد صحيحة $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$)، تمثل نقطة البداية والوجهة للبانغبو.
تحتوي الأسطر الـ $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