TopCoder

Thumb fhvirus icon.001
FHVirus
"FHVirus 是一種由主要由IO組合而成的病毒。"

User's AC Ratio

93.3% (28/30)

Submission's AC Ratio

29.4% (62/211)

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

輸入範例 2
2 101
10 11
3 2
4 7

輸入範例 3
3 101
69 59 89
5 4 2
3 6 7
2 0 1

Sample Output

輸出範例 1
1 1

輸出範例 2
2 1

輸出範例 3
10 20 30

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

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 3000 262144 65536 1 3
1 3000 262144 65536 1 3
2 3000 262144 65536 1 3
3 3000 262144 65536 1 3
4 3000 262144 65536 1 3
5 3000 262144 65536 2 3
6 3000 262144 65536 2 3
7 3000 262144 65536 2 3
8 3000 262144 65536 2 3
9 3000 262144 65536 2 3
10 3000 262144 65536 3
11 3000 262144 65536 3
12 3000 262144 65536 3
13 3000 262144 65536 3
14 3000 262144 65536 3
15 3000 262144 65536 3
16 3000 262144 65536 3
17 3000 262144 65536 3
18 3000 262144 65536 3
19 3000 262144 65536 3
20 3000 262144 65536 3
21 3000 262144 65536 3
22 3000 262144 65536 3
23 3000 262144 65536 3
24 3000 262144 65536 3