Дается матрица \(A\) размера \(N*N\) и \(Q\) запросов. Запросы могут быть двух типов: 1. \(type=1\) состоит из чисел \(x, y, val\), необходимо заменить \(a_{x,y}=y\). 2. \(type=2\) состоит из чисел \(l1, r1, l2, r2\) найдите сумма на подпрямоугольнике \((l1, r1)\) до \((l2, r2)\).

Входные данные

В первой строке дается \(N\) \((1 \leq N \leq 10^3)\). Во второй строке дается матрица \(N*N\), \(A\) \((1 \leq A_{i,j} \leq 10^5)\). В следующей строке дается \(Q\). \((1 \leq Q \leq 10^5)\). Далее даются Q запросов из двух видов.

Примеры

Ввод 1

4
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
3
2 2 2 3 3
1 4 4 0
2 4 2 4 4

Ответ 1

34
29