Universal Cup Judging System

Universal Cup

时间限制: 2.0 s 内存限制: 1024 MB 总分: 100 可 Hack ✓
统计

الوصف

لديك بانغبو (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

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.