Aoi 和 Bitaro 是隸屬於 JOI 國國家情報局的間諜。他們這次的任務是潛入 IOI 國進行秘密調查。Bitaro 潛入 IOI 國，而 Aoi 則在 JOI 國向 Bitaro 下達指示。

潛入之前，Aoi 和 Bitaro 取得了 IOI 國的地圖。IOI 國有 $N$ 座城市，編號為 $0$ 至 $N-1$。此外，IOI 國有 $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$）是調查 IOI 國的城市 $T_j$。

上述所有資訊起初都告知了 Aoi 和 Bitaro。接著，Bitaro 開始潛入 IOI 國。

Bitaro 成功躲過了眾多追兵，擊敗了刺客，終於潛入 IOI 國的城市 $0$。然而，由於潛入行動極為艱難，Bitaro 遺失了部分關於 IOI 國的資訊。具體而言，Bitaro 遺失了 $K$ 條道路的長度資訊，這些道路為 $X_0,X_1,\ldots,X_{K-1}$。換句話說，Bitaro 不再知道 $C_{X_0},C_{X_1},\ldots,C_{X_{K-1}}$ 的值。請注意，雖然 Bitaro 遺失了這些資訊，Aoi 仍然保有這些資訊。

Bitaro 立刻向 Aoi 報告自己遺失了哪些道路的長度資訊。

為了完成任務，Bitaro 希望知道從城市 $0$ 到 $Q$ 個調查計畫各自目標城市的一條最短路徑。

Aoi 會傳送一個每個字元都是 0 或 1 的字串給 Bitaro，以協助他。由於有被攔截的風險，Aoi 希望盡量減少傳送給 Bitaro 的內容。

請撰寫程式，根據 IOI 國、調查計畫以及 Bitaro 遺失資訊的道路等資訊，實作 Aoi 向 Bitaro 傳送字串的策略。同時，請撰寫程式，根據 Bitaro 所持有的資訊以及 Aoi 傳送的字串，實作 Bitaro 找出最短路徑的策略。

實作細節

你需要提交 2 個檔案。

第一個檔案是 Aoi.cpp。這個檔案用來實作 Aoi 的策略，必須實作以下函式。程式必須使用前置處理指令 #include 引入 Aoi.h。

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$ 是 IOI 國的城市數量 $N$。
• 參數 $M$ 是 IOI 國的道路數量 $M$。
• 參數 $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] 的長度資訊。
• 回傳值是 Aoi 傳送給 Bitaro 的字串 $s$。
• 字串 $s$ 的每個字元都必須是 0 或 1。若不符合此條件，程式會被判定為 Wrong Answer [1]。
• 字串 $s$ 的長度最多為 $12\,000$。若不符合此條件，程式會被判定為 Wrong Answer [2]。

第二個檔案是 Bitaro.cpp。這個檔案用來實作 Bitaro 的策略，必須實作以下函式。程式必須使用前置處理指令 #include 引入 Bitaro.h。

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$ 是 IOI 國的城市數量 $N$。
• 參數 $M$ 是 IOI 國的道路數量 $M$。
• 參數 $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$ 到第 $j$ 個調查計畫的目標城市 $T_j$ 的最短路徑。

• 參數 $e$ 是代表從城市 $0$ 到城市 $T_j$ 的最短路徑的陣列。
• 設陣列 $e$ 的長度為 $n$。元素 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$ 的路徑中最短的路徑，程式會被判定為 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。

請注意，實際評測程式與範例評測程式不同。範例評測程式會以單一行程執行，從標準輸入讀取資料，並將結果寫入標準輸出與標準錯誤輸出。

範例評測程式的輸入格式

範例評測程式從標準輸入讀取以下資料。

N M
A_0 B_0 C_0
A_1 B_1 C_1
...
A_{M-1} B_{M-1} C_{M-1}
Q
T_0 T_1 ... T_{Q-1}
K
X_0 X_1 ... X_{K-1}

範例評測程式的輸出格式

範例評測程式會將以下資訊輸出至標準輸出與標準錯誤輸出（引號僅為了清楚表示）。

• 若程式被判定為 Wrong Answer [1]、[2]、[3]、[4] 或 [6]，範例評測程式會將其類型以 Wrong Answer [1] 這樣的形式寫入標準錯誤輸出，不會向標準輸出輸出任何內容。
• 否則，函式 aoi 回傳字串 $s$ 的長度會以 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 分。

否則，評分依據是此題所有測試資料中，函式 aoi 回傳字串 $s$ 的最大長度，記為 $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 都可以用作範例評測程式的輸入。