János a 2022-es labdarúgó-világbajnokság döntőjére szeretne eljutni. Mivel az összes szurkoló a meccsre özönlött, Dohában nagy a tömeg. A helyzetet még az is nehezíti, hogy János hotelje a város másik részén helyezkedik el a standionhoz viszonyítva.

Mint ismeretes, Doha egy \(N \times M\)-es mátrixnak feleltethető meg. Az \((i,j)\) mező az \(i\)-dik sor j-dik oszlopában található mezőt jelöli. János hotelje az \((1,1)\) mezőn helyezkedik el, míg a stadion az \((N, M)\) mezőn. A mátrix minden mezőjén (beleértve azokat a mezőket is, ahol a hotel és a stadion van), szurkolók egy csoportja található ‒ az \((i,j)\) mezőn pontosan \(a_{i,j}\) szurkoló van.

János az \((i,j)\) mezőről kizárólag az \((i+1,j)\) vagy az \((i,j+1)\) mezőre tud lépni (amennyiben a mező, amelyre érkezne a mátrixon belül van. Mivel Jánosnak tömegiszonya van, úgy döntött, hogy az útvonalat úgy tervezi meg, hogy a lehető legkevesebb szurkolóval találkozzon (ahol az \(a_{i,j}\) értékek összege adja meg, hogy útközben hány szurkolóval találkozott a stadion felé vezető úton, beleértve a hotel és a stadion mezőjét is).

Amint János elkészítette a tervet, a híradóban bemondták, hogy pontosan egy mezőt fognak lezárni a nyilvánosság elől, így ezen nem fog tudni áthaladni a stadion felé vezető úton. János nem tudja, hogy pontosan melyik mezőről is van szó, ezért titeket kér meg arra, hogy választ adjatok a \(Q\) különböző forgatókönyvre. János szeretné tudni, hogy az \(i\)-dik forgatókönyvben hány szurkolóval kell találkoznia, ha az \((x_i,y_i)\) mező van lezárva.

A bemenet leírása

A szabványos bemenet első sorában két egész szám található: \(N\) és \(M\), amelyek Doha méretét jelölik.

A további \(N\) sor \(i\)-dik sora \(M\) egész számot tartalmaz, ahol a \(j\)-dik az \(a_{i,j}\)-t jelöli ‒ az \((i,j)\) mezőn található szurkolók száma.

A következő sor egy \(Q\) egész számot tartalmaz, amely a János által vizsgált különböző forgatókönyvek számát jelöli.

A további \(Q\) sor mindegyike két egész számot tartalmaz: \(x_i\)-t és \(y_i\)-t, amelyek az \(i\)-dik forgatókönyvben lezárt mezőt jelölik.

A kimenet leírása

A szabványos kimeneten \(Q\) sort kell megjeleníteni, ahol az \(i\)-dik sorban egy egész számot kell kiíratni, amely azon szurkolók minimális számát jelöli, akikkel János találkozni fog a stadion felé vezető úton, amennyiben az \((x_i,y_i)\) mező van lezárva.

1. példa

Bemenet

3 4
1 2 3 4
5 6 7 8
9 10 11 12
2
1 2
2 4

Kimenet

39
36

A példa magyarázata

• első forgatókönyv: amennyiben az \((1,2)\) mező van lezárva, János számára az optimális útvonal az alábbi: \((1,1) \rightarrow (2,1) \rightarrow (2,2) \rightarrow (2,3) \rightarrow (2,4) \rightarrow (3,4)\). Ezen az útvonalon összesen \(39\) szurkolóval fog találkozni.
• második forgatókönyv: amennyiben a \((2,4)\) mező van lezárva, János számára az optimális útvonal az alábbi: \((1,1) \rightarrow (1,2) \rightarrow (1,3) \rightarrow (2,3) \rightarrow (3,3) \rightarrow (3,4)\). Ezen az útvonalon összesen \(36\) szurkolóval fog találkozni.

Korlátozások

• \(2 \leq N, M\).
• \(4 \leq N \cdot M \leq 10^6\).
• \(1 \leq Q \leq 5 \cdot 10^5\).
• \(1 \leq a_{i,j} \leq 10^9\).
• \(1 \leq x_i \leq N\).
• \(1 \leq y_i \leq M\).
• A hotel és a stadion garantáltan nem lesz lezárva a nyilvánosság részére, és az is garantált, hogy János minden esetben el tud jutni a hoteltól a stadionig.

A tesztpéldák öt diszjunkt csoportba vannak sorolva:

• A \(15\) pontot érő tesztpéldákban: nincsenek további korlátozások: \(N = 2\).
• A \(10\) pontot érő tesztpéldákban: nincsenek további korlátozások: \(Q \leq 100\), \(N, M \leq 7\).
• A \(15\) pontot érő tesztpéldákban: nincsenek további korlátozások: \(Q \leq 2000\), \(N \cdot M \leq 2000\).
• A \(20\) pontot érő tesztpéldákban: nincsenek további korlátozások: \(Q \leq 10^4\).
• A \(40\) pontot érő tesztpéldákban: nincsenek további korlátozások.