Aoi та Bitaro — шпигуни Національного інформаційного бюро країни JOI. Цього разу їхнє завдання — провести таємне розслідування в країні IOI. Bitaro проникає в країну IOI, а Aoi дає йому вказівки з країни JOI.

Перед проникненням Aoi та Bitaro отримали карту країни IOI. У країні IOI є $N$ міст, пронумерованих від $0$ до $N-1$. Крім того, у країні є $M$ доріг, пронумерованих від $0$ до $M-1$. Дорога $i$ ($0 \le i \le M-1$) двосторонньо сполучає міста $A_i$ та $B_i$ і має довжину $C_i$. Між будь-якими двома містами можна дістатися, пройшовши деякими дорогами. Bitaro пересувається між містами країни IOI цими дорогами.

Також є $Q$ планів розслідування. План $j$ ($0 \le j \le Q-1$) передбачає розслідування в місті $T_j$ країни IOI.

Спочатку всю наведену вище інформацію повідомили як Aoi, так і Bitaro. Після цього Bitaro почав проникнення в країну IOI.

Bitaro успішно втік від численних переслідувачів, переміг найманих убивць і зрештою зумів проникнути в місто $0$ країни IOI. Однак через надзвичайну складність операції Bitaro втратив частину інформації про країну IOI. Зокрема, він утратив інформацію про довжини $K$ доріг: $X_0,X_1,\ldots,X_{K-1}$. Іншими словами, Bitaro більше не знає значень $C_{X_0},C_{X_1},\ldots,C_{X_{K-1}}$. Зауважте, що Aoi досі має цю інформацію, хоча Bitaro її втратив.

Bitaro негайно повідомив Aoi, інформацію про довжини яких доріг він утратив.

Щоб виконати завдання, Bitaro хоче дізнатися найкоротший шлях від міста $0$ до кожного з міст, зазначених у $Q$ планах розслідування.

Щоб допомогти йому, Aoi надішле Bitaro рядок, кожен символ якого є 0 або 1. Через ризик перехоплення Aoi хоче мінімізувати обсяг інформації, надісланої Bitaro.

Напишіть програму, що реалізує стратегію Aoi для надсилання рядка Bitaro за відомою інформацією про країну IOI, плани розслідування та дороги, інформацію про які Bitaro втратив. Також напишіть програму, що реалізує стратегію Bitaro для пошуку найкоротших шляхів за наявною в нього інформацією та рядком, надісланим Aoi.

Деталі реалізації

Ви маєте надіслати 2 файли.

Перший файл — Aoi.cpp. Він має реалізувати стратегію Aoi та наведені нижче функції. Програма має підключати Aoi.h за допомогою директиви препроцесора #include.

std::string aoi(int N, int M, int Q, int K, std::vector<int> A,
               std::vector<int> B, std::vector<long long> C,
               std::vector<int> T, std::vector<int> X)

Ця функція викликається рівно один раз для кожного тестового випадку.

• Параметр N — кількість міст $N$ у королівстві IOI.
• Параметр M — кількість доріг $M$ у королівстві IOI.
• Параметр Q — кількість планів розслідування $Q$.
• Параметр K — кількість доріг $K$, інформацію про довжину яких Bitaro втратив.
• Параметри A, B, C — масиви довжини $M$. Вони означають, що дорога $i$ ($0 \le i \le M-1$) двосторонньо сполучає міста A[i] та B[i] і має довжину C[i].
• Параметр T — масив довжини $Q$. Він означає, що план $j$ ($0 \le j \le Q-1$) передбачає розслідування в місті T[j].
• Параметр X — масив довжини $K$. Він указує, що Bitaro втратив інформацію про довжини доріг X[0], X[1], ..., X[K-1].
• Повернене значення — рядок $s$, який Aoi надсилає Bitaro.
• Кожен символ рядка $s$ має бути 0 або 1. Якщо ця умова не виконується, ваша програма отримає вердикт Wrong Answer [1].
• Довжина рядка $s$ має бути не більшою за $12\,000$. Якщо ця умова не виконується, ваша програма отримає вердикт Wrong Answer [2].

Другий файл — Bitaro.cpp. Він має реалізувати стратегію Bitaro та наведені нижче функції. Програма має підключати Bitaro.h за допомогою директиви препроцесора #include.

void bitaro(int N, int M, int Q, int K, std::vector<int> A, std::vector<int> B,
            std::vector<long long> C, std::vector<int> T, std::vector<int> X,
            std::string s)

Ця функція викликається рівно один раз після виклику функції aoi.

• Параметр N — кількість міст $N$ у королівстві IOI.
• Параметр M — кількість доріг $M$ у королівстві IOI.
• Параметр Q — кількість планів розслідування $Q$.
• Параметр K — кількість доріг $K$, інформацію про довжину яких Bitaro втратив.
• Параметри A, B, C — масиви довжини $M$. Вони означають, що дорога $i$ ($0 \le i \le M-1$) двосторонньо сполучає міста A[i] та B[i] і має довжину C[i].
• Параметр T — масив довжини $Q$. Він означає, що план $j$ ($0 \le j \le Q-1$) передбачає розслідування в місті T[j].
• Параметр X — масив довжини $K$. Він указує, що Bitaro втратив інформацію про довжини доріг X[0], X[1], ..., X[K-1].
• Аргумент s — рядок, кожен символ якого є 0 або 1; це рядок, надісланий Aoi до Bitaro.

У файлі Bitaro.cpp ваша програма може викликати наведену нижче функцію.

void answer(const std::vector<int> &e)

Під час $(j+1)$-го виклику цієї функції ($0 \le j \le Q-1$) потрібно повідомити найкоротший шлях від міста $0$ до міста $T_j$, яке є ціллю плану розслідування $j$.

• Параметр e — масив, що представляє найкоротший шлях від міста $0$ до міста $T_j$.
• Нехай $n$ — довжина масиву e. Елементи e[0], e[1], ..., e[n-1] — номери доріг найкоротшого шляху від міста $0$ до міста $T_j$ у порядку проходження.
• Якщо існує кілька найкоротших шляхів, можна вибрати будь-який із них.
• Кожен елемент параметра e має бути від $0$ до $M-1$. Якщо ця умова не виконується, ваша програма отримає вердикт Wrong Answer [3].
• Послідовність доріг, задана аргументом e, має утворювати шлях від міста $0$ до міста $T_j$. Формально мають виконуватися наведені нижче умови.

Має існувати послідовність чисел $u_0,u_1,\ldots,u_n$, для якої:

• $u_0=0$.
• $u_n=T_j$.
• Дорога e[k] (де $0 \le k \le n-1$) сполучає міста $u_k$ та $u_{k+1}$.

Якщо ці умови не виконуються, ваша програма отримає вердикт Wrong Answer [4].

• Якщо послідовність доріг, задана аргументом e, не є найкоротшим шляхом від міста $0$ до міста $T_j$ серед усіх шляхів, що починаються в місті $0$ і закінчуються в місті $T_j$, ваша програма отримає вердикт Wrong Answer [5]. Тут довжина шляху визначається як сума довжин використаних доріг.
• Функцію answer потрібно викликати рівно $Q$ разів. Якщо на момент завершення функції bitaro кількість викликів функції answer не дорівнює $Q$, ваша програма отримає вердикт Wrong Answer [6].

Важливі зауваження

• Ваша програма може реалізовувати інші функції для внутрішнього використання або використовувати глобальні змінні. Надіслані файли буде скомпільовано разом із програмою перевірки в один виконуваний файл. Усі глобальні змінні та внутрішні функції слід оголошувати в безіменному просторі імен, щоб уникнути конфліктів з іншими файлами. Під час оцінювання програму буде запущено як два процеси: Aoi та Bitaro. Процеси Aoi та Bitaro не можуть спільно використовувати глобальні змінні.
• Ваша програма не має використовувати стандартний ввід і стандартний вивід. Вона не має жодним способом обмінюватися інформацією з іншими файлами. Однак програма може виводити налагоджувальну інформацію в стандартний потік помилок.

Компіляція та тестовий запуск

З вебсторінки змагання можна завантажити архів, що містить приклад програми перевірки для тестування вашої програми. Архів також містить приклад вихідного файлу вашої програми.

Приклад програми перевірки міститься у файлі grader.cpp. Щоб протестувати свою програму, помістіть grader.cpp, Aoi.cpp, Bitaro.cpp, Aoi.h, Bitaro.h в один каталог і виконайте наведену нижче команду компіляції. Натомість можна запустити compile.sh з архіву.

g++ -std=gnu++20 -O2 -o grader grader.cpp Aoi.cpp Bitaro.cpp

У разі успішної компіляції буде створено виконуваний файл grader.

Зауважте, що справжня програма перевірки відрізняється від прикладу. Приклад програми перевірки виконується як один процес, що читає вхідні дані зі стандартного вводу та записує результати в стандартний вивід і стандартний потік помилок.

Вхідні дані прикладу програми перевірки

Приклад програми перевірки читає такі дані зі стандартного вводу.

$$ \begin{gathered} N\ M\\ A_0\ B_0\ C_0\\ A_1\ B_1\ C_1\\ \vdots\\ A_{M-1}\ B_{M-1}\ C_{M-1}\\ Q\\ T_0\ T_1\ \ldots\ T_{Q-1}\\ K\\ X_0\ X_1\ \ldots\ X_{K-1} \end{gathered} $$

Вихідні дані прикладу програми перевірки

Приклад програми перевірки виводить наведену нижче інформацію в стандартний вивід і стандартний потік помилок (лапки наведено для ясності).

• Якщо ваша програма отримала вердикт Wrong Answer [1], [2], [3], [4] або [6], приклад програми перевірки записує його тип, наприклад Wrong Answer [1], у стандартний потік помилок. У стандартний вивід нічого не виводиться.
• Інакше довжина рядка $s$, поверненого функцією aoi, виводиться в стандартний потік помилок у форматі Accepted: 2024. Крім того, довжина шляху під час $(j+1)$-го виклику функції answer ($0 \le j \le Q-1$) виводиться в $(j+1)$-й рядок стандартного виводу. Приклад програми перевірки не перевіряє, чи є шлях найкоротшим.

Якщо ваша програма задовольняє умови кількох типів Wrong Answer, приклад програми перевірки повідомляє лише один із них.

Обмеження

Усі вхідні дані задовольняють такі умови:

• $2 \le N \le 10\,000$.
• $1 \le M \le 20\,000$.
• $1 \le Q \le 16$.
• $1 \le K \le 300$.
• $0 \le A_i < B_i \le N-1$ ($0 \le i \le M-1$).
• $(A_i,B_i) \ne (A_j,B_j)$ ($0 \le i < j \le M-1$).
• $1 \le C_i \le 10^{12}$ ($0 \le i \le M-1$).
• $1 \le T_j \le N-1$ ($0 \le j \le Q-1$).
• $T_j \ne T_k$ ($0 \le j < k \le Q-1$).
• $0 \le X_k \le M-1$ ($0 \le k \le K-1$).
• $X_k \ne X_l$ ($0 \le k < l \le K-1$).
• З будь-якого міста можна дістатися до будь-якого іншого, пройшовши деякими дорогами.
• Усі вхідні значення є цілими числами.

Оцінювання

Якщо в будь-якому тестовому випадку ваша програма отримала будь-який вердикт Wrong Answer [1]–[6] (див. «Деталі реалізації») або будь-яку помилку виконання (TLE — перевищення обмеження часу, MLE — перевищення обмеження пам'яті, аварійне завершення тощо), ви отримаєте $0$ балів.

Інакше оцінка залежить від максимальної довжини рядка $s$, поверненого функцією aoi, серед усіх тестових випадків цієї задачі. Позначимо цю довжину через $L$.

• Якщо $1561 \le L \le 12\,000$, оцінка дорівнює $\left\lfloor\dfrac{100\,000}{L-560}\right\rfloor$ балів.
• Якщо $0 \le L \le 1560$, оцінка дорівнює $100$ балів.

Тут $\lfloor x\rfloor$ позначає найбільше ціле число, що не перевищує $x$.

Приклад взаємодії

Нижче наведено приклад вхідних даних для прикладу програми перевірки та відповідні виклики функцій.

Вхідні дані 1

3 3
1 2 1
0 2 2
0 1 3
2
2 1
2
0 1

Приклад викликів функцій

Примітка

Найкоротший шлях від міста $0$ до міста $1$ можна отримати, пройшовши дорогами $1$ та $0$ саме в такому порядку або лише дорогою $2$. Тому під час другого виклику функції answer у цьому прикладі також дозволено викликати answer([2]).

Файл sample-01-in.txt, який можна завантажити із сайту змагання, відповідає прикладу вхідних даних 1.

Файли sample-01-in.txt та sample-02-in.txt з матеріалів, доступних для завантаження на сайті змагання, можна використовувати як вхідні дані для прикладу програми перевірки.