【問題G16】稀疏矩陣。            [回前頁]

如果一個m × n(列 × 行)的矩陣有許多的元素為0，這個矩陣就會被稱為「稀疏」。其實稀疏的定義並不明確，在這裡我們假設m × n的矩陣其非零的元素一定會小於或等於(m × n) / 5個，並將其視為稀疏。為了減少記憶體空間的使用量，我們將矩陣中的每一個非零元素以「列 行 值」的方式來表示，列與行的編號均是由1開始編號。例如：

    圖一：4 × 5稀疏矩陣

上圖4 × 5的稀疏矩陣，我們可以下列的方式表示非零的資料

2 5 5

3 1 1

4 2 2

4 3 4

現在我們要設計一個程式，讀取一個以上述表示法所表示的稀疏矩陣元素，然後顯示出輸入檔所指定的位置(以「列 行」定位)的元素值。
以上圖為例，如果指定的位置是 4  3 ，則輸出第4列第3行的值，也就是「4」。
如果指定的位置是 3  5 ，則輸出第3列第5行的值，也就是「0」。

■    輸入檔說明

輸入檔中含有多組測試資料，
每組測試資料的第一列，含有二個以空格分隔的整數m  n：

m( 0 < m < 10000 )，表示矩陣的列數。

n( 0 < n < 10000 )，表示矩陣的行數。

每組測試資料的第二列含有一個整數，k( 0 < k < 10000 )，表示該組稀疏矩陣的非零元素個數。

接下來有k列資料，每列含有三個整數，分別以空格分隔，其內容如下：

第一個整數 ri ( 1 < ri < m )，表示該非零元素的列編號；

第二個整數 ci ( 1 < ci < n )，表示該非零元素的行編號；

第三個整數 vi ( 1 < vi < 10000 )，表示該非零元素的值。

(其中i是由1到k)

接下來的一列(第k+3列)有一個整數z，表示要顯示的元素個數，

接下來有z列資料，每列含有二個整數，分別以空格分隔，其內容如下：

第一個整數 arj ( 1 < arj < m )，表示要顯示的稀疏矩陣元素列編號；

第二個整數 acj ( 1 < acj < n )，表示要顯示的稀疏矩陣元素行編號；

(其中j是由1到z)

當該組測試資料的第一列均為0時，表示輸入檔結束，該筆資料及其後續所有資料均不需處理。

■    輸出檔說明

對每一組測試資料均輸出一列資料，每列包含z個整數，並以1個空格分隔。每一個整數，表示所要顯示的非零元素值(依輸入檔讀入的次序來輸出結果)。

■    範例輸入

■    範例輸出