Lýsing
Þú átt krúttlegan Bangboo sem tekur þátt í „Mikla ævintýri Marcels“.
Þessi Bangboo hreyfist í þrívíðu rúmi. Upphafspunktur hans er $(S_x, S_y, S_z)$ og áfangastaður hans er $(T_x, T_y, T_z)$. Líta má á hann sem einingartening með miðju í $(S_x, S_y, S_z)$. Það eru $n$ hindranir í þrívíða rúminu, og hver þeirra er einingarteningur með miðju í $(x_i, y_i, z_i)$. Tryggt er að hnit upphafspunktsins, áfangastaðarins og allra hindrana séu innbyrðis ólík, og að það verði að vera hindranir í $(S_x, S_y, S_z - 1)$ og $(T_x, T_y, T_z - 1)$.
Bangbooinn getur fjarflutt sig. Í hverju skrefi hefur hann $m$ tiltækar fjarflutningsaðferðir. Gerum ráð fyrir að hann sé núna í $(x, y, z)$. $i$-ta fjarflutningsaðferðin sendir hann í $(x + a_i, y + b_i, z + c_i)$, og eftir það fellur hann í frjálsu falli. Formlega mun hann fjarflytjast í $(x + a_i, y + b_i, d)$, þar sem $d$ er hæsta gildið sem uppfyllir $d \le z + c_i$ þannig að hindrun sé í $(x + a_i, y + b_i, d - 1)$. Ef hindrun er í $(x + a_i, y + b_i, z + c_i)$, eða ef ekkert slíkt $d$ er til, þá er ekki hægt að framkvæma þennan fjarflutning.
Markmið þitt er að láta Bangbooinn komast á áfangastaðinn frá upphafspunktinum í sem fæstum skrefum. Ef ómögulegt er að komast á áfangastaðinn, prentaðu $-1$.
Inntak
Fyrsta línan inniheldur heiltölu $T$ ($1 \le T \le 500$), sem táknar fjölda prófunartilfella.
Fyrir hvert prófunartilfelli:
Fyrsta línan inniheldur tvær heiltölur $n, m$ ($2 \le n \le 10^3$, $1 \le m \le 10^3$), sem tákna fjölda hindrana og fjölda fjarflutningsaðferða sem Bangbooinn hefur, í sömu röð.
Önnur línan inniheldur sex heiltölur $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$), sem tákna upphafspunkt og áfangastað Bangbooins.
Næstu $n$ línur innihalda hver um sig þrjár heiltölur $x_i, y_i, z_i$ ($0 \le x_i, y_i, z_i \le 10^9$), sem tákna hnit $i$-tu hindrunarinnar. Tryggt er að það verði að vera hindranir í $(S_x, S_y, S_z - 1)$ og $(T_x, T_y, T_z - 1)$.
Næstu $m$ línur innihalda hver um sig þrjár heiltölur $a_i, b_i, c_i$ ($|a_i|, |b_i|, |c_i| \le 10^9$), sem tákna $i$-tu fjarflutningsaðferðina.
Fyrir hvert prófunartilfelli er tryggt að öll hnit í inntakinu séu innbyrðis ólík, og að allar fjarflutningsaðferðir séu innbyrðis ólíkar.
Tryggt er að summa $n$ yfir öll prófunartilfelli fari ekki yfir $10^3$, og að summa $m$ yfir öll prófunartilfelli fari ekki yfir $10^3$.
Úttak
Fyrir hvert prófunartilfelli skal prenta eina heiltölu á einni línu, sem táknar lágmarksfjölda skrefa sem þarf til að komast á áfangastaðinn frá upphafspunktinum. Ef ómögulegt er að komast á áfangastaðinn, prentaðu $-1$.
Dæmi
Inntak 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
Úttak 1
5 -1