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. Однако из-за чрезвычайной сложности операции он потерял часть информации о стране IOI. А именно, Bitaro потерял сведения о длинах $K$ дорог: $X_0,X_1,\ldots,X_{K-1}$. Иными словами, он больше не знает значений $C_{X_0},C_{X_1},\ldots,C_{X_{K-1}}$. Хотя Bitaro потерял эту информацию, Aoi по-прежнему ею располагает.

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 — количество дорог, сведения о длинах которых потерял Bitaro, обозначаемое $K$.
• Параметры 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 — количество дорог, сведения о длинах которых потерял Bitaro, обозначаемое $K$.
• Параметры 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)$-м вызове ($0\le j\le Q-1$) функции answer выводится в $(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\frac{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 из архива на сайте соревнования можно использовать как входные данные для примера проверяющей программы.