معجون دورنوردی (Teleportation Potion)

پروفسور بالتازار به دلیل کهولت سن دیگر توانایی راه رفتن ندارد، برای همین او تصمیم گرفته است تا با تولید چند معجون بدون راه رفتن و با فناوری جدید دورنوردی در آزمایشگاه خودش حرکت کند. آزمایشگاه پروفسور بالتازار به شکل یک مسیر است که روی آن $n$ اتاق وجود دارد که به ترتیب از چپ به راست با شماره‌های $0$ تا $n-1$ شماره‌گذاری شده‌اند.

دانش پروفسور بالتازار از علم دورنوردی محدود است و نمی‌تواند بین هر دو اتاقی که دلش می‌خواهد دورنوردی کند. برای انجام دورنوردی‌ها، پروفسور بالتازار روی هر اتاق $i$ یک دستگاه دورنورد نصب کرده که شماره مدل آن از نوع $A_i$ است. همچنین پروفسور $k$ معجون دورنورد دارد که انواع مختلفی از دورنوردی را ممکن می‌کنند.

پروفسور به کمک علم محدودش از دانش دورنوردی می‌تواند از هر اتاقی مانند $u$ به کمک معجون دورنوردی نوع $j$ به اولین اتاقی در سمت راست $u$ مانند $v$ برود، به طوری که بیت $j$ اُم $A_{u}$ و $A_{v}$ متفاوت باشد (دقت کنید که اگر سمت راست $u$ چنین اتاقی نباشد نمی‌توان از این معجون استفاده کرد). پروفسور برای انجام این حرکت باید $W_{u,j}$ تومان هزینه پرداخت کند.

پروفسور که اخیرا بازنشسته شده و با مشکلات مالی مواجه شده است، نمی‌تواند هزینه‌ی زیادی برای تولید معجون‌های دورنوردی کند. از طرفی پروفسور بسیار پیر شده و حساب کردن این هزینه‌ها برای او بسیار سخت است. از این رو از شما خواسته تا به ازای چندین زوج مرتب $s$ و $t$ به او بگویید که کمترین هزینه‌ای که پروفسور باید برای انجام دورنوردی پرداخت کند تا از اتاق $s$ به اتاق $t$ برسد چقدر است. همچنین اگر چنین کاری ممکن نبود، آن را به پروفسور اطلاع دهید.

در این سوال شما اجازه‌ی خواندن از ورودی یا نوشتن در خروجی را ندارید. تنها راه تبادل اطلاعات با استفاده از توابعی که در ادامه معرفی می‌کنیم خواهد بود. در صورت هرگونه تلاش برای خواندن از ورودی یا نوشتن در خروجی یا استفاده از تابع `exit` نمره شما صفر می‌شود:

vector<long long> solve(int n, int q, int k, vector<int> A, 
                        vector<vector<int>> W, vector<pair<int, int>> Q)

• n: تعداد اتاق‌ها.
• q: تعداد پرسش‌هایی که باید به آن جواب دهید.
• k: تعداد انواع مختلف معجون‌های دورنورد.
• A: آرایه‌ای به طول $n$ که مدل دستگاه دورنورد در اتاق $i$اُم را نشان می‌دهد.
• W: آرایه‌ی دوبعدی به طول $n \times k$ که خانه‌ی $(i,j)$ آن نشان‌دهنده هزینه دورنوردی نوع $j$ در اتاق $i$اُم است.
• Q: یک آرایه به طول $q$ که خانه‌ی $i$اُم آن یک pair از خانه‌ی شروع و خانه‌ی پایانی است.

این تابع یک بار صدا زده می‌شود. خروجی تابع باید یک vector باشد که عضو $i$اُم آن برابر با پاسخ پرسش $i$اُم است. در صورتی که رسیدن از اتاق $s$ به $t$ ممکن‌ نبود، این مقدار را برابر $-1$ قرار دهید.

• $1 \leq n \leq 2 \times 10^5$
• $1 \leq q \leq 5 \times 10^6$
• $1 \leq k \leq 10$
• $0 \leq A_i < 2^k$
• $0 \leq W_{i,j} \leq 10^9$
• $0\leq s \leq t < n$

فایل‌های مربوط به سوال را دانلود کنید. راه حل خود را درون teleportation.cpp پیاده‌سازی کنید. برای کامپایل و اجرا کردن برنامه باید compile_cpp.sh را اجرا کنید. سپس فایل اجرایی teleportation را که توسط compile_cpp.sh تولید شده است،‌ اجرا کنید.

فرمت ورودی ارزیاب نمونه:

n q k
A[0] A[1] ... A[n-1]
W[0][0] W[0][1] ... W[0][k-1]
W[1][0] W[1][1] ... W[1][k-1]
⋮
W[n-1][0] W[n-1][1] ... W[n-1][k-1]
s[0] t[0]
s[1] t[1]
⋮
s[q-1] t[q-1]

پاسخ برگردانده شده در $q$ خط، ‌یک خط برای هر کوئری چاپ می‌شود.

اگر اندازه‌ی آرایه‌ی برگردانده شده برابر $q$ نباشد، پیغام خطا چاپ می‌شود.

در کوئری اول ورودی یک، پروفسور در حرکت اول خود (از خانه‌ی ۰‌اُم) اگر از معجون نوع ۰ استفاده کند، با هزینه‌ی ۲ به خانه‌ی ۱ می‌رود و اگر از معجون نوع ۱ استفاده کند، با هزینه‌ی ۰ به خانه‌ی ۲ می‌رود. همچنین مسیر بهینه برای رسیدن از ۰ به ۴ برابر مسیر $0 \rightarrow 2 \rightarrow 3 \rightarrow 3$ است که در حرکت اول از معجون نوع ۱ و در دو حرکت دیگر از معجون نوع ۰ استفاده شده است. دقت کنید که پرش از خانه‌ی $2$ به کمک معجون نوع ۱ غیر ممکن است.

در کوئری آخر ورودی یک، می‌توان ثابت کرد که رسیدن از خانه‌ی ۴ به خانه‌ی ۵ به کمک هیچ معجونی ممکن نیست.