在一塊方方正正的土地中,市長準備進行都市更新。這塊土地是 N×M 的矩形,左上角座標 (0,0),左下角座標 (N−1,0),右上角座標 (0,M−1),右下角座標 (N−1,M−1)。每一個座標 (i,j) 的位置都有一棟價值 aij 的建築物,一旦這個位置被都更,這棟建築就要被剷平。
市長想選一塊方正的矩形區域作為都更預定地,其中左上角為 (u,l),右下角為 (d,r),矩形兩軸平行都市邊界。他一共會提出 Q 種方案,想問你每種方案分別要剷除多少價值的建築物。
輸入第一行是三個以空白分隔的整數 N,M,Q,分別代表都市的長寬和市長提出的方案數。
接下來有 N 行每行 M 個以空白分割的整數,其中第 i 行第 j 個數字表示 ai−1,j−1。
接下來 Q 行,每行四個以空白分割的整數 u,l,d,r,代表市長提出的都更方案。
輸入保證 1≤N,M≤500,1≤aij≤109,1≤Q≤300000,0≤u≤d<N,0≤l≤r<M。
輸出 Q 行,每行包含一個整數,代表該筆詢問需要剷除建築的價值。