2170 . 地圖編修 (Map)
TopCoder
Description
在這世界上有一種外星人，跟活在三度空間的地球人不一樣，他們是活在$ N$ 維的空間中，所以想當然，這種外星人的地圖也是透過 $N$ 維的單位向量來表示特定位置的座標。有一天，外星人的皇帝突發奇想，覺得透過單位向量來作為地圖的依據太無聊了，他決定重新定義所謂的「座標軸」，並且座標軸之間也不一定需要是正交的關係。
以上圖為例，這是一個二維的座標圖，空白的點代表外星人皇宮的位置。在原先的座標軸中，外星人皇宮的位置可以用座標[5, 3]來表示，因為該點的位置可以用5個向量1和3個向量2來表示。在皇帝修改座標軸之後，雖然外星人皇宮的位置沒有改變，但座標卻改成 [1, 1]，因為該位置可以用1個向量1和1個向量2來表示。
要注意的是，每個維度都是環形的概念，也就是座標的範圍都在 $0$ 到 $M-1$ 之間，超過的部分會回到 $0$ 後再繼續前進。同時，因為外星人不喜歡小數點，因此所有的座標都是整數。相關的例子可以參考範例測資。請寫一個程式來幫忙進行座標的轉換。
Input Format
第一列有兩個正整數 $N, M$，其中 $N$ 代表維度的個數， $0 < N \leq M$， $M$ 必為質數且最大為 $65537$。第二列則是有 $N$ 個數字，代表在原始座標軸皇宮的座標位置。接下來 $N$ 列則是代表皇帝所決定的座標軸的向量，每一列都有 $N$ 個數字，數字大小介於 $0$ 到 $1000$，但若 $M \leq 1000$，則介於 $0$ 到 $M-1$。
Output Format
請輸出給定的原始座標在新的座標軸底下的座標位置。(測資保證唯一解。)
Sample Input 1
2 101
5 3
3 1
2 2
Sample Output 1
Sample Input 2
10 11
3 2
4 7
Sample Output 2
Sample Input 3
69 59 89
5 4 2
3 6 7
2 0 1
Sample Output 3
Hints
範例 1 說明：
1*[3 1] + 1*[2 2]
=[5 3]
範測 2 說明：
2*[3 2] + 1*[4 7]
=[10 11]
範測 3 說明：
10*[5 4 2] + 20 *[3 6 7] + 30 *[2 0 1]
= [170 160 190] 對 101 取餘數
= [69 59 89]
本題共有三組測試資料：
第一組測試資料，$N = 2$，共 17 分；
第二組測試資料，$N = 3$，共 27 分；
第三組測試資料，$N \leq 100$，共 56 分。
Problem Source
108 北市賽 pB
testdata set by Omelet
10/29 更新subtask測資&rejudge
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~4 | $N=2$ | 17 |
| 2 | 5~9 | $N=3$ | 27 |
| 3 | 0~24 | $N\leq 100$ | 56 |