The Need for Seed

বীজের প্রয়োজনে একটি রেসিং ভিডিও গেম যেটি একটি কাল্পনিক শহর ফরচুন সিটিতে হয়ে থাকে। একজন খেলোয়ার হিসেবে এখানে তোমার কাজ হলো কৃষকদের জন্য এক শহর থেকে আরেক শহরে বীজ নিয়ে যাওয়া। ফরচুন সিটিতে $N$ সংখ্যক শহর রয়েছে, যাদের নাম আমাদের সুবিধার জন্য $0$ থেকে $N-1$। শহরগুলো $M$ সংখ্যক দ্বিমুখী রাস্তা দিয়ে সংযুক্ত। প্রতিটি শহরের সাথে একটি অনন্য ধনাত্নক পূর্ণসংখ্যা $diff$ রয়েছে ্যা ঐ শহরের কাঠিন্য নির্দেশ করে। তুমি $u$ শহর থেকে যাত্রা করে $v$ শহরে যেতে বাধার মুখোমুখি হবে, যদি $diff[u] < diff[v]$ হয়। প্রতিটি রাস্তার সাথে একটি ধনাত্নক পূর্ণসংখ্যা রয়েছে যা ঐ রাস্তা অতিক্রম সময় নির্দেশ করে।

এই গেমে তোমাকে একাধিক রেস করতে হতে পারে। প্রতিটি রেসে তুমি $X_i$ শহর থেকে শুরু করবে এবং $Y_i$ শহরে যাবে। ধরে নাও, তুমি যখন কোনো বাধার সম্মুখীন হও, তোমার কাছে থাকা সব বীজ পরে নষ্ট হয়ে যায়। তাই তুমি $Y_i$ শহরে যাওয়ার সময় কোনো বাধার মুখোমুখি হতে চাও না।

তোমাকে $X_i$ শহর থেকে $Y_i$ শহরে যাওয়ার সর্বনিম্ন সময় নির্ণয় করতে হবে।

Input

ইনপুটের প্রথম লাইনে একটি পূর্ণসংখ্যা $T$ থাকবে, যা টেস্টকেসের সংখ্যা নির্দেশ করে।

প্রতিটি টেস্টকেসের শুরুতে তিনটি স্পেস দিয়ে পৃথক পূর্নসংখ্যা $N$, $M$, এবং $L$ থাকবে, যেখানে $N$ ফরচুন সিটিতে শহরের সংখ্যা নির্দেশ করে, $M$ শহরগুলোর সংযোজক রাস্তার সংখ্যা নির্দেশ করে, এবং $L$ রেসের সংখ্যা নির্দেশ করে।

পরবর্তী লাইনে $N$ সংখ্যক স্পেস দ্বারা পৃথক পূর্ণসংখ্যা $diff[0], diff[1], \dots, diff[N-1]$ থাকবে, যেখানে $diff[i]$ নির্দেশ করে $i$ তম শহরের কাঠিন্য।

পরবর্তী $M$ সংখ্যক লাইনের প্রতিটিতে তিনটি স্পেস দিয়ে পৃথক পূর্ণসংখ্যা $u$, $v$, এবং $w$ থাকবে, যা নির্দেশ করে $u$ শহর থেকে $v$ শহরে যাওয়ার দ্বিমুখী রাস্তা রয়েছে, যা অতিক্রম করতে $w$ সময় লাগে।

পরবর্তী $L$ সংখ্যক লাইনের প্রতিটিতে দুটি স্পেস দিয়ে পৃথক পূর্ণসংখ্যা $X_i$ এবং $Y_i$ থাকবে, যেখানে $X_i$ রেস শুরুর শহর এবং $Y_i$ রেস শেষ হবার শহর নির্দেশ করে।

Constraints

• $1 \leq N \leq 10^5$

• $1 \leq M \leq 10^5$

• $M \leq \frac{N(N-1)}{2}$

• $1 \leq L \leq 100$

• $1 \leq diff[i] \leq 10^9$ where $0 \leq i < N$

• $1 \leq u, v < N$

• $1 \leq w \leq 10^9$

• $1 \leq X_i, Y_i < N$ where $0 \leq i < L$

• $1 \leq T \leq 5$

Subtask #1 (40 points): $1 \leq L \leq 20$

Subtask #2 (60 points): মূল constraints

Output

প্রতিটি রেসের জন্য, $X_i$ শহর থেকে $Y_i$ শহরে যাবার রাস্তা না থাকলে $-1$ প্রিন্ট করো। অন্যথায়, $Y_i$ শহরে পৌছানোর জন্য যে সময় লাগে, তা প্রিন্ট করো। প্রতিটি রেসের আউটপুট দেয়ার পর একটি নিউলাইন প্রিন্ট করো।

Sample

Input	Output
1 3 3 2 3 2 1 0 1 1 0 2 3 1 2 1 0 2 2 0	2 -1