Сипаттамасы
Сізде сүйкімді Банбу (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$ жолдың әрқайсысында $i$-ші кедергінің координаттарын білдіретін үш бүтін сан $x_i, y_i, z_i$ берілген ($0 \le x_i, y_i, z_i \le 10^9$). $(S_x, S_y, S_z - 1)$ және $(T_x, T_y, T_z - 1)$ нүктелерінде міндетті түрде кедергілер болатынына кепілдік беріледі.
Келесі $m$ жолдың әрқайсысында $i$-ші телепортация тәсілін білдіретін үш бүтін сан $a_i, b_i, c_i$ берілген ($|a_i|, |b_i|, |c_i| \le 10^9$).
Әрбір тест жағдайы үшін барлық кіріс координаттары қос-қостан әртүрлі және барлық телепортация тәсілдері қос-қостан әртүрлі екеніне кепілдік беріледі.
Барлық тест жағдайлары бойынша $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