Јанко се спрема за одлазак на финале светског првенства у фудбалу 2022. године. Међутим, како су сви навијачи похрлили на утакмицу, у Дохи су велике гужве. Да ствари буду горе, Јанков хотел је на супротном крају града у односу на стадион.

Познато је да Доха изгледа као матрица димензија \(N \times M\). Поље \((i,j)\) означава поље у \(i\)-том реду и \(j\)-тој колони. Јанков хотел се налази на пољу \((1,1)\), док се стадион налази на пољу \((N, M)\). На сваком пољу матрице (укључујући и поља на којем су хотел и стадион) се налази нека група навијача - на пољу \((i,j)\) има тачно \(a_{i,j}\) навијача.

Јанко са поља \((i,j)\) искључиво може да оде на поље \((i+1,j)\) или на поље \((i,j+1)\) (уколико је одговарајуће поље на које би дошао унутар матрице). Пошто Јанко не воли гужве, одлучио је да свој пут испланира тако да на њему сусретне најмањи број навијача (где је број навијача које је срео сума свих \(a_{i,j}\) по пољима кроз која је прошао на путу до стадиона, укључујући и поља хотела и стадиона).

Чим је Јанко направио план, чуо је на вестима да ће тачно једно поље бити блокирано за јавност, те он неће моћи да прође кроз њега на путу до стадиона. Јанко нажалост није сигуран о којем пољу је реч, те вас моли да одговорите на \(Q\) различитих сценарија. У \(i\)-том сценарију, Јанко жели да зна колико ће навијача морати да сретне, ако поље \((x_i,y_i)\) буде блокирано.

Опис улаза

У првом реду стандардног улаза, налазе се два цела броја, \(N\) и \(M\), који представљају димензије Дохе.

Линија \(i\) од наредних \(N\) линија садржи \(M\) целих бројева, од којих \(j\)-ти представља \(a_{i,j}\) - број навијача на пољу \((i,j)\).

Наредна линија садржи један цео број, \(Q\), који представља број различитих сценарија које Јанко разматра.

Наредних \(Q\) линија садрже по два броја, \(x_i\) и \(y_i\), који описују поље које је блокирано у \(i\)-том сценарију.

Опис излаза

На стандардни излаз исписати \(Q\) редова, у \(i\)-том од њих потребно је исписати један цео број, који представља минималан број навијача које ће Јанко срести на путу до стадиона, уколико буде блокирано поље \((x_i,y_i)\).

Пример 1

Улаз

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

Излаз

39
36

Објашњење

• први сценарио: Уколико је блокирано поље \((1,2)\), оптималан пут за Јанка је \((1,1) \rightarrow (2,1) \rightarrow (2,2) \rightarrow (2,3) \rightarrow (2,4) \rightarrow (3,4)\). На том путу, он ће укупно срести \(39\) навијача.
• други сценарио: Уколико је блокирано поље \((2,4)\), оптималан пут за Јанка је \((1,1) \rightarrow (1,2) \rightarrow (1,3) \rightarrow (2,3) \rightarrow (3,3) \rightarrow (3,4)\). На том путу, он ће укупно срести \(36\) навијача.

Ограничења

• \(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\).
• Гарантује се да хотел и стадион никада неће бити блокирани за јавност и да ће Јанко увек моћи да стигне од хотела до стадиона.

Тест примери су подељени у пет дисјунктних група:

• У тестовима вредним 15 поена: \(N = 2\).
• У тестовима вредним 10 поена: \(Q \leq 100\), \(N, M \leq 7\).
• У тестовима вредним 15 поена: \(Q \leq 2000\), \(N \cdot M \leq 2000\).
• У тестовима вредним 20 поена: \(Q \leq 10^4\).
• У тестовима вредним 40 поена: Без додатних ограничења.