תיאור
יש לכם בנגבו (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