7105 - 陣列和問題 2   

Description

給一個 m ´ n 大小的二維陣列(array) A,並且每個數都是非負整數,此外給一個非負整數 x。現在湯姆想要知道是否存在一個較小的子陣列(sub-array) A’,裡面的數加起來的和是x。例如:一個 ´ 3 大小的陣列 A (如下圖所示)x = 20,則以 a2,1 為左上角、a3,2 為右下角的子陣列 A’ 的和等於 x = 20。請寫一個程式幫湯姆判斷找出這個陣列。

 

注意!本題測試資料的範圍較大,請參考 Input 說明。

 

Input

測試資料的第一行是一個正整數 T (T £ 20),表示接下來有 T 筆測試資料。

每一筆測試資料包含三個部份,第一部分是兩個正整數 m  n (1 £ mn £ 50) 表示陣列大小為 m ´ n。第二部分有 m 行,每一行有 n 個數字,兩個整數之間以一個空白隔開,第 i 行代表在陣列中的第 i 列的 n 個數字。第三部分是一個非負整數 x

每筆測資保證陣列中所有的數字和小於 1,000,000,000

Output

每一筆測資各占一行,如果存在一個子陣列 (sub-array) 的和是 x,輸出四個整數 r1c1r2c2,表示以  為左上角, 為右下角的子陣列的和為 x,否則輸出No。每筆測資保證最多只會存在一個子陣列的和為 x

Sample Input  Download

Sample Output  Download

Tags




Discuss