Baka je napravila veliku tortu kvadratnog oblika za svoje unuke. Kao ukras, uzduž i popreko je stavila šlag preko torte, podelivši je na n x n kvadratnih polja jednake veličine. Na kraju je na svako polje prosula određen broj čokoladnih mrvica.

Baka seče tortu na sledeći način: Prvo odabere jednu od četiri strane torte sa koje će da krene da seče, a zatim odabere između kojih redova, odnosno kolona, će da seče tortu. Posle toga se ne menja ni pravac, ni smer sečenja dok se sečenje ne završi. Ukoliko je ovo prvo sečenje u tom pravcu i smeru, baka seče od ivice torte. Ako je ranije već sekla u tom pravcu i smeru, onda seče od mesta završetka poslednjeg sečenja u tom pravcu i smeru. Nakon što počne da seče parče, ne zaustavlja se do njegove suprotne ivice, odnosno dok ga potpuno ne preseče. Ništa se ne seče ako je torta več presečena celom dužinom u datom pravcu.

Pošto svi njeni unuci mnogo vole čokoladne mrvice, baka ne želi da neko dobije ni premalo, a ni previše mrvica na parčetu.

Vama je dato je q upita jednog od sledeća dva tipa:

• 1 a b - torta se seče u smeru a (jednom od četiri kao na slici). Ako je horizontalno sečenje, torta se seče između redova b i b + 1. Ako je vertikalno sečenje, torta se seče između kolona b i b + 1.
• 2 l h - potrebno je odgovoriti koliko parčadi trenutno postoji takvih da je broj mrvica na parčetu u intervalu [l, h].

Ulaz:

(Ulazni podaci se učitavaju iz datoteke mrvice.in.) U prvom redu ulaza se nalaze brojevi n i q (1 ≤ n≤ 500, 1 ≤ q ≤ 100.000), dimenzija torte i broj upita. U sledećih nredova nalazi se po n brojeva, broj mrvica na svakom polju torte. Svako polje će imati najmanje jednu, a najviše 2*10⁹ mrvica. Zatim sledi q redova koji predstavljaju već opisane upite formata t i j, gde t ∈ {1,2}. Ako je t = 1, onda 0 ≤ i ≤ 3 i 1 ≤ j ≤ n - 1. Ako je t = 2, onda 1 ≤ i ≤ j ≤ 10¹⁵. Upiti se izvrxavaju u redosledu datom na ulazu.

Izlaz:

(Izlazni podaci se ispisuju u datoteku mrvice.out.) Za svaki upit tipa 2 iz ulaza ispisati u novi red izlaza odgovor na taj upit (odgovore ispisivati u odgovarajućem redosledu). Postojaće bar jedan upit tipa 2.

Primer 1:

4 6
3 12 8 5
4 1 2 9
7 6 6 3
10 4 2 8
1 2 1
1 3 3
2 9 15
1 3 3
2 13 14
2 17 100

2
2
1

Objašnjenje.

Za dati primer, sečenja su prikazana na slikama:

Posle 1. sečenja	Posle 2. sečenja	Posle 3. sečenja

Napomena.

• U 20% test primera biće n, q≤ 100.
• U 40% test primera broj upita tipa 1 neće preći 1.000.

#include <algorithm>
#include <cstdio>
#define MAXN 510
#define MAXQ 100010
#define INF 1LL<<60LL

using namespace std;

typedef struct
{
  int vrsta;
  long long a,b;      
} upit;

typedef struct
{
  long long nsuma,dsuma1,dsuma2;      
} suma;

typedef struct
{
  int glr, glk, ddr, ddk;     
  long long suma;   
} parce;

int dr[4]={1,0,-1,0};
int dk[4]={0,-1,0,1};
int torta[MAXN][MAXN],mesto[4][MAXN],n,q,br,trenred,trenkol,dokle,brojsuma=1;
int brparcadi=1,parcadmat[MAXN][MAXN],trenparce,glr,glk,ddr,ddk;
int brojac[MAXQ*2];
long long sume[2*MAXQ],pocsuma;
parce parcad[MAXQ];
upit upiti[MAXQ];
suma upitSume[MAXQ];

int seci(int strana, int red, int kol)
{
  if (strana==0 && red>mesto[2][kol] ||
      strana==1 && kol<mesto[3][red] ||
      strana==2 && red<mesto[0][kol] ||
      strana==3 && kol>mesto[1][red] ||
      parcadmat[red][kol]!=parcadmat[red-dr[strana]][kol-dk[strana]])
    return 0;
  return 1;
}

int nadjisumu(long long s)
{
  int l=1,d=brojsuma,sr;
  while (l<=d)
  {
    sr=(l+d)/2;
    if (sume[sr]==s)
      return sr;
    if (s<sume[sr])
      d=sr-1;
    else
      l=sr+1;    
  }  
  return 0;
}

int nadjigranicu(long long s)
{
  int l=1,d=brojsuma,sr;
  while (l+1<d)
  {
    sr=(l+d)/2;
    if (s<sume[sr])
      d=sr;
    else
      l=sr;      
  }  
  if (sume[d]<=s)
    return d;
  else
    return l;
}

void dodaj(int poz, int kol)
{
  for (int i=poz; i<=brojsuma; i+=(i & -i))
    brojac[i]+=kol;     
}

int prebroj(int poz)
{
  int broj=0;  
  for (int i=poz; i>0; i-=(i & -i))
    broj+=brojac[i];  
  return broj;  
} 

int main()
{
  freopen("mrvice.in","r",stdin);
  freopen("mrvice.out","w",stdout);
  scanf("%d %d",&n,&q);
  for (int i=1; i<=n; i++)
    for (int j=1; j<=n; j++)
    {
      scanf("%d",&torta[i][j]);
      pocsuma+=(long long)torta[i][j];  
    }  
  sume[1]=pocsuma;
  for (int i=0; i<=3; i++)
    for (int j=1; j<n; j++)
      if (i==1 || i==2)
        mesto[i][j]=n;
      else
        mesto[i][j]=1;
  parcad[0].glr=1;
  parcad[0].glk=1;
  parcad[0].ddr=n;
  parcad[0].ddk=n;
  parcad[0].suma=sume[1];
  for (int i=0; i<q; i++)
  {
    scanf("%d %lld %lld",&upiti[i].vrsta,&upiti[i].a,&upiti[i].b);    
    if (upiti[i].vrsta==1)
      if (upiti[i].a&1 && mesto[3][upiti[i].b]>mesto[1][upiti[i].b] ||
         (upiti[i].a&1)==0 && mesto[2][upiti[i].b]<mesto[0][upiti[i].b])
        upiti[i].vrsta=0;
      else
      {  
        if (upiti[i].a&1)
        {
          trenred=upiti[i].b;
          trenkol=mesto[upiti[i].a][upiti[i].b]+dk[upiti[i].a];
        }
        else
        {
          trenkol=upiti[i].b; 
          trenred=mesto[upiti[i].a][upiti[i].b]+dr[upiti[i].a];
        }  
        
        while (seci(upiti[i].a,trenred,trenkol))
        {
          trenred+=dr[upiti[i].a];
          trenkol+=dk[upiti[i].a];  
        }
        
        if (upiti[i].a&1)
        {
          mesto[upiti[i].a][trenred]=trenkol;
          trenparce=parcadmat[trenred][trenkol-dk[upiti[i].a]];
          parcad[brparcadi].glk=parcad[trenparce].glk;
          parcad[brparcadi].ddk=parcad[trenparce].ddk;
          if (trenred-parcad[trenparce].glr<parcad[trenparce].ddr-trenred)
          {
            parcad[brparcadi].glr=parcad[trenparce].glr;
            parcad[brparcadi].ddr=trenred;
            parcad[trenparce].glr=trenred+1;                                                                                          
          }
          else
          {
            parcad[brparcadi].glr=trenred+1;
            parcad[brparcadi].ddr=parcad[trenparce].ddr;
            parcad[trenparce].ddr=trenred;                  
          }
        }
        else
        {
          mesto[upiti[i].a][trenkol]=trenred;
          trenparce=parcadmat[trenred-dr[upiti[i].a]][trenkol];
          parcad[brparcadi].glr=parcad[trenparce].glr;
          parcad[brparcadi].ddr=parcad[trenparce].ddr;
          if (trenkol-parcad[trenparce].glk<parcad[trenparce].ddk-trenkol)
          {
            parcad[brparcadi].glk=parcad[trenparce].glk;
            parcad[brparcadi].ddk=trenkol;
            parcad[trenparce].glk=trenkol+1;                                                                                          
          }
          else
          {
            parcad[brparcadi].glk=trenkol+1;
            parcad[brparcadi].ddk=parcad[trenparce].ddk;
            parcad[trenparce].ddk=trenkol;                  
          }          
        }
        
        for (int r=parcad[brparcadi].glr; r<=parcad[brparcadi].ddr; r++)
          for (int k=parcad[brparcadi].glk; k<=parcad[brparcadi].ddk; k++)
          {
            parcadmat[r][k]=brparcadi;
            parcad[brparcadi].suma+=(long long)torta[r][k];  
          }
          
        upitSume[i].nsuma=parcad[trenparce].suma;  
        parcad[trenparce].suma-=parcad[brparcadi].suma;
        upitSume[i].dsuma1=parcad[trenparce].suma;
        upitSume[i].dsuma2=parcad[brparcadi].suma;
        sume[++brojsuma]=upitSume[i].dsuma1;
        sume[++brojsuma]=upitSume[i].dsuma2;
        brparcadi++;        
      }    
  } 
  sume[++brojsuma]=-INF;
  sume[++brojsuma]=INF;  
  sort(sume+1,sume+brojsuma+1);
  br=1;  
  for (int i=2; i<=brojsuma; i++)
    if (sume[i]!=sume[i-1])
      sume[++br]=sume[i];
  brojsuma=br;
 
  dodaj(nadjisumu(pocsuma),1);
  for (int i=0; i<q; i++)
    if (upiti[i].vrsta==1)
    {                
      dodaj(nadjisumu(upitSume[i].dsuma1),1);
      dodaj(nadjisumu(upitSume[i].dsuma2),1);      
      dodaj(nadjisumu(upitSume[i].nsuma),-1);
    }
    else
      if (upiti[i].vrsta==2) 
        printf("%d\n",prebroj(nadjigranicu(upiti[i].b))-prebroj(nadjigranicu(upiti[i].a-1)));               
  return 0;  
}