輸入的第一行有一個正整數 N $(1 \leq N \leq 20)$，代表地圖大小為 N×N。
接下去有 N 行，第 i 行有 N 個正整數 $e_{ij}$ $ (1 \leq e_{ij} \leq1000, 1 \leq i, j \leq N)$，代表地圖中每個位置 (i, j) 的敵軍兵力數。數值之間以至少一個空白隔開。
下一行有一個正整數 Q $(1 \leq Q \leq N^ 4)$，代表可能的詢問數。
再接下去有 Q 行，每行有四個正整數 $x_{q0}, y_{q0}, x_{q1}, y_{q1} $ $(1 \leq x_{q0}, y_{q0}, x_{q1}, y_{q1} \leq N, 1 \leq q \leq Q)$。$(x_{q0}, y_{q0}) $為雷恩的出發位置，$(x_{q1}, y_{q1})$ 為雷恩的目的位置。數值之間以一個空白隔開。

請輸出 Q 筆答案，每個答案$a_q$ 一行，代表一發死光炸彈支援下，從 $(x_{q0}, y_{q0}) $到$(x_{q1}, y_{q1})$ 最安全路線的敵軍兵力總數。

本題共有四組測試資料。
第一組測試資料所有$e_{ij} = 1$。佔 10 分。
第二組測試資料若i ≠ j 則 $e_{ij} = 1$，其餘 (i = j)且 $e_{ij} = 1000$。佔 10 分。
第三組測試資料所有詢問的目的位置均相同 $(x_{11} = x_{21} = x_{31} = … = x_{Q1}, y_{11} = y_{21} = y_{31}= … = y_{Q1})$，佔40 分。
第四組測試資料，沒有特別的條件限制，佔 40 分。

臺北市104 學年度高級中學資訊學科能力競賽程式設計試題第五題
Set by Paupière
若測資有誤請儘快聯絡管管(?