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 國嘅資料。具體嚟講，佢遺失咗 $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 尋找最短路徑嘅策略。

實現細節

你需要提交兩個檔案。

第一個檔案係 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。

留意，實際評測器同範例評測器唔同。範例評測器會以單一程序執行，從標準輸入讀取資料，並將結果寫去標準輸出同標準錯誤輸出。

範例評測器嘅輸入格式

範例評測器會從標準輸入讀入以下資料。

$$ \begin{array}{lll} 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{array} $$

範例評測器嘅輸出格式

範例評測器會向標準輸出同標準錯誤輸出寫出以下資訊（引號只係用嚟講清楚）。

• 如果程式被判為 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 都可以用作範例評測器嘅輸入。