stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include<iostream>

using namespace std;



int cost[101][101],t[101][101];

bool tf,cf;



int wf(int p,int q,int r,int m){

	if(r){

		if(tf){

			for(int k=1 ; k <= m ; ++k){

				for(int i=1 ; i <= m ; ++i){

					for(int j=1 ; j <= m ; ++j){

						if(t[i][j] > t[i][k] + t[k][j]) t[i][j] = t[i][k] + t[k][j];

					}

				}

			}

			tf = false;

			return t[p][q];

		}else return t[p][q];

	}else if(cf){

		for(int k=1 ; k <= m ; ++k){

			for(int i=1 ; i <= m ; ++i){

				for(int j=1 ; j <= m ; ++j){

						if(cost[i][j] > cost[i][k] + cost[k][j]) cost[i][j] = cost[i][k] + cost[k][j];

				}

			}

		}

		cf = false;

		return cost[p][q];

	}

	else return cost[p][q];

}



int main(){

	int a,b,c,d,n,m,k,p,q,r;

	

	while(cin >> n >> m && n && m){

		for(int i=1 ; i <= m ; ++i){

			for(int j=1 ; j <= m ; ++j){

				cost[i][j] = 10000;

				t[i][j] = 10000;

			}

		}

		cf = true;

		tf = true;

		for(int i=0 ; i < n ; ++i){

			cin >> a >> b >> c >> d;

			cost[a][b] = c;

			cost[b][a] = c;

			t[a][b] = d;

			t[b][a] = d;

		}

		cin >> k;

		for(int i=0 ; i < k ; ++i){

			cin >> p >> q >> r;

			cout << wf(p,q,r,m) << endl;

		}

	}

	return 0;

} 

// Faster C++ solution for the same problem (measured speedup: 3.594023345852441x):
#include<cstdio>

#include<algorithm>

#include<queue>



#define INF 1<<29



using namespace std;



int main(){

	while(1){

		int n,m;

		scanf("%d%d",&m,&n);

		if(m==0 && n==0){

			break;

		}

		int cost[101][101];

		int time[101][101];

		

		for(int i=0;i<101;i++)

		for(int j=0;j<101;j++)

		cost[i][j]=time[i][j]=INF;

		

		for(int i=0;i<m;i++){

			int a,b,c,d;

			scanf("%d%d%d%d",&a,&b,&c,&d);

			cost[a][b]=cost[b][a]=c;

			time[a][b]=time[b][a]=d;

		}

		

		for(int k=1;k<=n;k++){

			for(int i=1;i<=n;i++){

				for(int j=1;j<=n;j++){

					cost[i][j]=min(cost[i][j],cost[i][k]+cost[k][j]);

					time[i][j]=min(time[i][j],time[i][k]+time[k][j]);

				}

			}

		}

		

		scanf("%d",&m);

		for(int i=0;i<m;i++){

			int a,b,c;

			scanf("%d%d%d",&a,&b,&c);

			if(c==0){

				printf("%d\n",cost[a][b]);

			}else{

				printf("%d\n",time[a][b]);

			}

		}

	}

}
// Slower C++ solution:
#include<cstdio>

#include<algorithm>

#include<queue>



#define INF 1<<29



class state{

	public:

	int p,v;

	state(){}

	state(int a,int b){

		p=a;v=b;

	}

	bool operator < (const state &a) const{

		return v > a.v;

	}

};

using namespace std;



int main(){

	while(1){

		int n,m;

		scanf("%d%d",&m,&n);

		if(n==0 && m==0){

			break;

		}

		int cost[101][101];

		int time[101][101];

		

		for(int i=0;i<101;i++)

		for(int j=0;j<101;j++)

		cost[i][j]=time[i][j]=INF;

		

		for(int i=0;i<m;i++){

			int a,b,c,d;

			scanf("%d%d%d%d",&a,&b,&c,&d);

			cost[a][b]=cost[b][a]=c;

			time[a][b]=time[b][a]=d;

		}

		

		scanf("%d",&m);

		for(int i=0;i<m;i++){

			int st,en,va;

			scanf("%d%d%d",&st,&en,&va);

			

			priority_queue<state> aa;

			

			int meen[101];

			int visit[101]={0};

			

			for(int i=0;i<101;i++){meen[i]=INF;}

			

			aa.push(state(st,0));

			meen[st]=0;

			int ans=0;

			while(1){

				state u = aa.top();

				aa.pop();

				

				if(u.p==en){

					ans=u.v;

					break;

				}

				

				visit[u.p]=1;

				

				for(int i=1;i<=n;i++){

					if(visit[i]==0){

						int val=cost[i][u.p];

						if(va==1){

							val=time[i][u.p];

						}

						if(val+u.v < meen[i]){

							meen[i]=val+u.v;

							aa.push(state(i,meen[i]));

						}

					}

				}

			}

			printf("%d\n",ans);

		}

	}

}

// Faster C++ solution for the same problem (measured speedup: 3.591133576405401x):
#include<cstdio>

#include<algorithm>

#include<queue>



#define INF 1<<29



using namespace std;



int main(){

	while(1){

		int n,m;

		scanf("%d%d",&m,&n);

		if(m==0 && n==0){

			break;

		}

		int cost[101][101];

		int time[101][101];

		

		for(int i=0;i<101;i++)

		for(int j=0;j<101;j++)

		cost[i][j]=time[i][j]=INF;

		

		for(int i=0;i<m;i++){

			int a,b,c,d;

			scanf("%d%d%d%d",&a,&b,&c,&d);

			cost[a][b]=cost[b][a]=c;

			time[a][b]=time[b][a]=d;

		}

		

		for(int k=1;k<=n;k++){

			for(int i=1;i<=n;i++){

				for(int j=1;j<=n;j++){

					cost[i][j]=min(cost[i][j],cost[i][k]+cost[k][j]);

					time[i][j]=min(time[i][j],time[i][k]+time[k][j]);

				}

			}

		}

		

		scanf("%d",&m);

		for(int i=0;i<m;i++){

			int a,b,c;

			scanf("%d%d%d",&a,&b,&c);

			if(c==0){

				printf("%d\n",cost[a][b]);

			}else{

				printf("%d\n",time[a][b]);

			}

		}

	}

}
// Slower C++ solution:
#include<iostream>

#include<vector>

#define rep(i,a) for(int i = 0 ; i < a ; i++)

using namespace std;



int main(void){

  int n,m;

  while(cin>>n>>m,n+m){

    vector<vector<vector<int> > > dp(2,vector<vector<int> >(100,vector<int>(100,1<<22)));

    rep(i,n){

      int a,b,c,t;

      cin>> a >> b >> c >> t;

      dp[0][--a][--b] = c;

      dp[0][b][a] = c;

      dp[1][a][b] = t;

      dp[1][b][a] = t;

    }

    

    rep(k,m)rep(i,m)rep(j,m)rep(o,2)

      dp[o][i][j] = min(dp[o][i][j],dp[o][i][k]+dp[o][k][j]);

      

    int k;

    cin>>k;

    rep(i,k){

      int p,q,r;

      cin >> p >> q >> r;

      cout<< dp[r][--p][--q] << endl;

    }

  }

}

// Faster C++ solution for the same problem (measured speedup: 1.236874396148171x):
#include<iostream>

using namespace std;

#define rep(i,a) for(int i=0;i<a;i++)

int main(void){

  int maze[2][100][100];

  int n,m;

  int a,b,c,t;

  while(cin>>m>>n,n+m){

    rep(i,n)rep(j,n)rep(k,2)maze[k][i][j]=100000;

    rep(i,m){

      cin>>a>>b>>c>>t;

      maze[0][--a][--b]=c;

      maze[1][a][b]=t;

      maze[0][b][a]=c;

      maze[1][b][a]=t;

    }

    rep(k,n)rep(i,n)rep(j,n)rep(l,2)

      maze[l][i][j]=min(maze[l][i][j],maze[l][i][k]+maze[l][k][j]);

    cin>>m;

    //cout<<endl;rep(i,n)rep(j,n)cout<<maze[1][i][j]<<(j==n-1?'\n':' ');

    

    rep(i,m){

      cin>>a>>b>>c;

      cout<<maze[c][--a][--b]<<endl;

    }

  }

}
// Slower C++ solution:
#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

#include <cstring>

using namespace std;



#define REP(i,k,n) for(int i=k;i<n;++i)

#define rep(i,n) REP(i,0,n)



int N,M,K;

const int MAXN=128;

const int INF=1e+9;

int G1[MAXN][MAXN];

int G2[MAXN][MAXN];



int main()

{

	while(cin>>M>>N&&(M||N))

	{

		rep(i,N){ rep(j,N){ G1[i][j]=G2[i][j]=(i==j?0:INF); } }



		rep(i,M)

		{ 

			int a,b,c,d;

			cin>>a>>b>>c>>d; --a; --b;

			G1[a][b]=G1[b][a]=c;

			G2[a][b]=G2[b][a]=d;

		}



		rep(point,N) rep(from,N) rep(to,N)

		{

			G1[from][to] = min(G1[from][to],G1[from][point]+G1[point][to]);

			G2[from][to] = min(G2[from][to],G2[from][point]+G2[point][to]);

		}



		cin>>K;

		rep(i,K)

		{

			int a,b,c; cin>>a>>b>>c; --a; --b;

			cout<<(c?G2[a][b]:G1[a][b])<<endl;

		}

	}



	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 3.485546870461097x):
#include <stdio.h>

#include <limits.h>

 

int n,m;

 

int Selection(int start,int goal,int Graph[101][101])

{

    int i;

    int min,minp = start;

    int Station[101];

    int Decided[101] = {0,};

 

    for(i=0;i<101;i++)

    {

        Station[i] = INT_MAX;

    }

 

    Station[start] = 0;

 

    while(Decided[goal] == 0)

    {

        for(i=0;i<m+1;i++)

        {

            if(Graph[minp][i] == -1) continue;

 

            if(Station[i] > Graph[minp][i] + Station[minp])

            {

                Station[i] = Graph[minp][i] + Station[minp];

            }

        }

 

        min = INT_MAX;

        for(i=0;i<m+1;i++)

        {

            if(min > Station[i] && Decided[i] != 1)

            {

                min = Station[i];

                minp = i;

            }

        }

        Decided[minp] = 1;

    }

 

    return Station[goal];

}

 

int main()

{

    int Gcost[101][101];

    int Gtime[101][101];

 

    int i,j;

    int a,b,time,cost;

    int k,start,goal,r;

    int ans;

 

    while(1)

    {

        for(i=0;i<101;i++)

        {

            for(j=0;j<101;j++)

            {

                Gcost[i][j] = -1;

                Gtime[i][j] = -1;

            }

        }

 

        scanf("%d%d",&n,&m);

        if(n == 0 && m==0) break;

 

        for(i=0;i<n;i++)

        {

            scanf("%d%d%d%d",&a,&b,&cost,&time);

            Gcost[a][b] = cost;

            Gcost[b][a] = cost;

            Gtime[a][b] = time;

            Gtime[b][a] = time;

        }

 

        scanf("%d",&k);

        for(i=0;i<k;i++)

        {

            scanf("%d%d%d",&start,&goal,&r);

            if(r==0) ans = Selection(start,goal,Gcost);

            else if(r==1) ans = Selection(start,goal,Gtime);

            printf("%d\n",ans);

        }

    }

 

    return 0;

}
// Slower C++ solution:
#include<iostream>

#include<algorithm>

using namespace std;



int main(){

  int n,m,a,b,cost,time,k,p,q,r;

  int t[100][100],c[100][100];



  for(;;){

    cin >> n >> m;

    if(!n && !m)break;



    for(int i=0;i<m;i++){

      for(int j=0;j<m;j++){

	if(i==j){

	  t[i][j] = 0;

	  c[i][j] = 0;

	}else{

	  t[i][j] = 1000000;

	  c[i][j] = 1000000;

	}

      }

    }



    for(int i=0;i<n;i++){

      cin >> a >> b >> cost >> time;

      t[a-1][b-1] = time;

      t[b-1][a-1] = time;

      c[a-1][b-1] = cost;

      c[b-1][a-1] = cost;

    }



    for(int x=0;x<m;x++){

      for(int i=0;i<m;i++){

	for(int j=0;j<m;j++){

	  t[i][j] = min(t[i][j],t[i][x] + t[x][j]);

	  c[i][j] = min(c[i][j],c[i][x] + c[x][j]);

	}

      }

    }



    cin >> k;

    for(int i=0;i<k;i++){

      cin >> p >> q >> r;

      if(r)cout << t[p-1][q-1] << endl;

      else cout << c[p-1][q-1] << endl;

    }

  }

}

// Faster C++ solution for the same problem (measured speedup: 5.104477469810489x):
#include<cstdio>

#include<algorithm>

using namespace std;



int main(){

  int n,m,a,b,cost,time,k,p,q,r;

  int t[100][100],c[100][100];



  for(;;){

    scanf("%d %d",&n,&m);

    if(!n && !m)break;



    for(int i=0;i<m;i++){

      for(int j=0;j<m;j++){

	if(i==j){

	  t[i][j] = 0;

	  c[i][j] = 0;

	}else{

	  t[i][j] = 1000000;

	  c[i][j] = 1000000;

	}

      }

    }



    for(int i=0;i<n;i++){

      scanf("%d %d %d %d",&a,&b,&cost,&time);

      t[a-1][b-1] = time;

      t[b-1][a-1] = time;

      c[a-1][b-1] = cost;

      c[b-1][a-1] = cost;

    }



    for(int x=0;x<m;x++){

      for(int i=0;i<m;i++){

	for(int j=0;j<m;j++){

	  t[i][j] = min(t[i][j],t[i][x] + t[x][j]);

	  c[i][j] = min(c[i][j],c[i][x] + c[x][j]);

	}

      }

    }



    scanf("%d",&k);

    for(int i=0;i<k;i++){

      scanf("%d %d %d",&p,&q,&r);

      if(r)printf("%d\n",t[p-1][q-1]);

      else printf("%d\n",c[p-1][q-1]);

    }

  }

}
// Slower C++ solution:
#include<iostream>

#include<set>

#define loop(i,a,b) for(int i=a;i<b;i++)

#define rep(i,a) loop(i,0,a)

#define INF 1e8

using namespace std;

int n,m,k,a,b,c,alt,p,q,r;

long long cost[101][101],tm[101][101],d[101];

bool used[101];



void dfunc(int s,int r){

	rep(i,101){

		used[i]=true;

		d[i]=INF;

	}

	d[s]=0;

	while(1){

		int mem=INF,now=-1;

		rep(i,101){

			if(used[i] && mem>d[i]){

				now=i;

				mem=d[i];

			}

		}

		if(now==-1)break;

		used[now]=false;

		rep(i,101){

			if(r==0){

				if(cost[now][i]!=INF)d[i]=min(d[i],d[now]+cost[now][i]);

			}else{

				if(tm[now][i]!=INF)d[i]=min(d[i],d[now]+tm[now][i]);

			}

		}

	}

}



int main(){

	while(cin>>n>>m,n||m){

		rep(i,101)rep(j,101){

			cost[i][j]=INF;

			tm[i][j]=INF;

		}

		rep(i,n){

			cin>>a>>b>>c>>alt;

			a--;

			b--;

			cost[b][a]=cost[a][b]=c;

			tm[b][a]=tm[a][b]=alt;

		}

		cin>>k;

		rep(i,k){

			cin>>p>>q>>r;

			dfunc(p-1,r);

			cout<<d[q-1]<<endl;

		}

	}

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.1665035193311788x):
#include<iostream>

#define loop(i,a,b) for(int i=a;i<b;i++)

#define rep(i,a) loop(i,0,a)

#define INF 1e9

using namespace std;

typedef long long ll;



ll min(ll a,ll b){

	if(a>b)return b;

	else return a;

}





int main(){

	int n,m,a,b,cost,time,l,p,q,r;

	while(cin>>n>>m,n||m){

		ll mt[m][m],mc[m][m];

		rep(i,m)rep(j,m)mt[i][j]=mc[i][j]=INF;

		rep(i,n){

			cin>>a>>b>>cost>>time;

			mt[a-1][b-1]=mt[b-1][a-1]=time;

			mc[a-1][b-1]=mc[b-1][a-1]=cost;

		}

		rep(k,m){

			rep(i,m){

				rep(j,m){

					mt[i][j]=min(mt[i][j],mt[i][k]+mt[k][j]);

					mc[i][j]=min(mc[i][j],mc[i][k]+mc[k][j]);

				}

			}

		}

		cin>>l;

		rep(i,l){

			cin>>p>>q>>r;

			if(r==0)cout<<mc[p-1][q-1]<<endl;

			else cout<<mt[p-1][q-1]<<endl;

		}

	}

	return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int INF = 0x3f3f3f3f;

const LL mod = 1e9 + 7;

const int N = 200005;



struct Seg {

    int val[N << 2], lazy[N << 2];

    void init(int n) {

        for (int i = 1; i <= 4 * n; i++) {

            val[i] = n;

            lazy[i] = INF;

        }

    }

    void push_up(int u) {

        val[u] = min(val[u << 1], val[u << 1 | 1]);

    }

    void push_down(int u) {

        if (lazy[u] != INF) {

            val[u << 1] = min(val[u << 1], lazy[u]);

            val[u << 1 | 1] = min(val[u << 1 | 1], lazy[u]);

            lazy[u << 1] = min(lazy[u << 1], lazy[u]);

            lazy[u << 1 | 1] = min(lazy[u << 1 | 1], lazy[u]);

            lazy[u] = INF;

        }

    }

    void update(int u, int l, int r, int x, int y, int v) {

        if (x <= l && r <= y) {

            val[u] = min(val[u], v);

            lazy[u] = min(lazy[u], v);

            return;

        }

        int mid = l + r >> 1;

        push_down(u);

        if (x <= mid) update(u << 1, l, mid, x, y, v);

        if (y > mid) update(u << 1 | 1, mid + 1, r, x, y, v);

        push_up(u);

    }

    int query(int u, int l, int r, int x) {

        if (l == r) return val[u];

        int mid = l + r >> 1;

        push_down(u);

        if (x <= mid)

            return query(u << 1, l, mid, x);

        else

            return query(u << 1 | 1, mid + 1, r, x);

    }

} T1, T2;



int a[N];

int main() {

    int n, q;

    cin >> n >> q;

    T1.init(n);

    T2.init(n);

    LL ans = (n - 2LL) * (n - 2);

    while (q--) {

        int op, x;

        cin >> op >> x;

        if (op == 1) {

            int g = T2.query(1, 1, n, x);

            ans -= g - 2;

            T1.update(1, 1, n, 1, g, x);



        } else {

            int g = T1.query(1, 1, n, x);

            ans -= g - 2;

            T2.update(1, 1, n, 1, g, x);

        }

    }

    cout << ans << endl;

    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 3.8118367335479033x):
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int INF = 0x3f3f3f3f;

const LL mod = 1e9 + 7;

const int N = 200005;



int n, q;

struct Node {

    int c[N];

    int sum(int x) {

        int res = n;

        while (x) {

            res = min(res, c[x]);

            x -= x & -x;

        }

        return res;

    }

    void add(int x, int d) {

        while (x <= n) {

            c[x] = min(c[x], d);

            x += x & -x;

        }

    }

} T1, T2;

int main() {

    cin >> n >> q;

    LL ans = (n - 2LL) * (n - 2);

    for (int i = 1; i <= n; i++) T1.c[i] = T2.c[i] = n;

    while (q--) {

        int op, x;

        cin >> op >> x;

        if (op == 1) {

            int z = T1.sum(n - x + 1);

            T2.add(n - z + 1, x);

            ans -= z - 2;

        } else {

            int z = T2.sum(n - x + 1);

            T1.add(n - z + 1, x);

            ans -= z - 2;

        }

    }

    cout << ans << endl;

    return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

#define rep(i,n) for(int i = 0; i < (n); ++i)

#define srep(i,s,t) for(int i = s; i < t; ++i)

#define drep(i,n) for(int i = (n)-1; i >= 0; --i)

using namespace std;

typedef long long int ll;

typedef pair<int,int> P;

#define yn {puts("Yes");}else{puts("No");}

#define MAX_N 200005



int main() {

    int x[MAX_N] = {}, y[MAX_N] = {};

    int n, q;

    scanf("%d%d", &n,&q);

    ll ans = (ll)(n-2)*(n-2);

    srep(i,2,n){

        x[i] = n;

        y[i] = n;

    }

    int xx = n;

    int yy = n;

    while(q--){

        int t, z;

        scanf("%d%d", &t,&z);

        if(t == 1){

            if(z < xx){

                ans -= yy - 2;

                srep(i,z,xx) x[i] = yy;

                xx = z;

            }else{

                ans -= x[z] - 2;

            }

        }else{

            if(z < yy){

                ans -= xx - 2;

                srep(i,z,yy) y[i] = xx;

                yy = z;

            }else{

                ans -= y[z] - 2;

            }

        }

    }

    cout << ans << endl;

    return 0;

}






// Faster C++ solution for the same problem (measured speedup: 2.02060154236903x):
#include <bits/stdc++.h>

#define rep(i,n) for(int i = 0; i < (n); ++i)

#define srep(i,s,t) for(int i = s; i < t; ++i)

#define drep(i,n) for(int i = (n)-1; i >= 0; --i)

using namespace std;

typedef long long int ll;

typedef pair<int,int> P;

#define yn {puts("Yes");}else{puts("No");}

#define MAX_N 200005



#define ch() getchar()

#define pc(x) putchar(x)

template<typename T>inline void read(T&x){

	int f;char c;

	for(f=1,c=ch();c<'0'||c>'9';c=ch())if(c=='-')f=-f;

	for(x=0;c<='9'&&c>='0';c=ch())x=x*10+(c&15);x*=f;

}



int x[MAX_N], y[MAX_N];



int main() {

    int n, q;

    read(n); read(q);

    ll ans = (ll)(n-2)*(n-2);

    int xx = n;

    int yy = n;

    while(q--){

        int t, z;

        read(t), read(z);

        if(t == 1){

            if(z < xx){

                ans -= yy - 2;

                srep(i,z+1,xx) x[i] = yy;

                xx = z;

            }else{

                ans -= x[z] - 2;

            }

        }else{

            if(z < yy){

                ans -= xx - 2;

                srep(i,z+1,yy) y[i] = xx;

                yy = z;

            }else{

                ans -= y[z] - 2;

            }

        }

    }

    printf("%lld\n", ans);

    return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

#define rep(i,n) for(int i = 0; i < (n); ++i)

#define srep(i,s,t) for(int i = s; i < t; ++i)

#define drep(i,n) for(int i = (n)-1; i >= 0; --i)

using namespace std;

typedef long long int ll;

typedef pair<int,int> P;

#define yn {puts("Yes");}else{puts("No");}

#define MAX_N 200005

int main() {

    int x[MAX_N] = {}, y[MAX_N] = {};

    int n, q;

    scanf("%d%d", &n,&q);

    ll ans = (ll)(n-2)*(n-2);

    srep(i,2,n){

        x[i] = n;

        y[i] = n;

    }

    int xx = n;

    int yy = n;

    while(q--){

        int t, z;

        scanf("%d%d", &t,&z);

        if(t == 1){

            if(z < xx){

                ans -= yy - 2;

                srep(i,z+1,xx) x[i] = yy;

                xx = z;

            }else{

                ans -= x[z] - 2;

            }

        }else{

            if(z < yy){

                ans -= xx - 2;

                srep(i,z+1,yy) y[i] = xx;

                yy = z;

            }else{

                ans -= y[z] - 2;

            }

        }

    }

    printf("%lld\n", ans);

    return 0;

}






// Faster C++ solution for the same problem (measured speedup: 2.015833481612059x):
#include <bits/stdc++.h>

#define rep(i,n) for(int i = 0; i < (n); ++i)

#define srep(i,s,t) for(int i = s; i < t; ++i)

#define drep(i,n) for(int i = (n)-1; i >= 0; --i)

using namespace std;

typedef long long int ll;

typedef pair<int,int> P;

#define yn {puts("Yes");}else{puts("No");}

#define MAX_N 200005



#define ch() getchar()

#define pc(x) putchar(x)

template<typename T>inline void read(T&x){

	int f;char c;

	for(f=1,c=ch();c<'0'||c>'9';c=ch())if(c=='-')f=-f;

	for(x=0;c<='9'&&c>='0';c=ch())x=x*10+(c&15);x*=f;

}



int x[MAX_N], y[MAX_N];



int main() {

    int n, q;

    read(n); read(q);

    ll ans = (ll)(n-2)*(n-2);

    int xx = n;

    int yy = n;

    while(q--){

        int t, z;

        read(t), read(z);

        if(t == 1){

            if(z < xx){

                ans -= yy - 2;

                srep(i,z+1,xx) x[i] = yy;

                xx = z;

            }else{

                ans -= x[z] - 2;

            }

        }else{

            if(z < yy){

                ans -= xx - 2;

                srep(i,z+1,yy) y[i] = xx;

                yy = z;

            }else{

                ans -= y[z] - 2;

            }

        }

    }

    printf("%lld\n", ans);

    return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

#define rep(i,n) for(int i = 0; i < (n); ++i)

#define srep(i,s,t) for(int i = s; i < t; ++i)

#define drep(i,n) for(int i = (n)-1; i >= 0; --i)

using namespace std;

typedef long long int ll;

typedef pair<int,int> P;

#define yn {puts("Yes");}else{puts("No");}

#define MAX_N 200005



#define ch() getchar()

#define pc(x) putchar(x)

template<typename T>inline void read(T&x){

	int f;char c;

	for(f=1,c=ch();c<'0'||c>'9';c=ch())if(c=='-')f=-f;

	for(x=0;c<='9'&&c>='0';c=ch())x=x*10+(c&15);x*=f;

}



int main() {

    int x[MAX_N] = {}, y[MAX_N] = {};

    int n, q;

    scanf("%d%d", &n,&q);

    ll ans = (ll)(n-2)*(n-2);

    srep(i,2,n){

        x[i] = n;

        y[i] = n;

    }

    int xx = n;

    int yy = n;

    while(q--){

        int t, z;

        // scanf("%d%d", &t,&z);

        read(t), read(z);

        if(t == 1){

            if(z < xx){

                ans -= yy - 2;

                srep(i,z+1,xx) x[i] = yy;

                xx = z;

            }else{

                ans -= x[z] - 2;

            }

        }else{

            if(z < yy){

                ans -= xx - 2;

                srep(i,z+1,yy) y[i] = xx;

                yy = z;

            }else{

                ans -= y[z] - 2;

            }

        }

    }

    printf("%lld\n", ans);

    return 0;

}






// Faster C++ solution for the same problem (measured speedup: 2.014599463963148x):
#include <bits/stdc++.h>

#define rep(i,n) for(int i = 0; i < (n); ++i)

#define srep(i,s,t) for(int i = s; i < t; ++i)

#define drep(i,n) for(int i = (n)-1; i >= 0; --i)

using namespace std;

typedef long long int ll;

typedef pair<int,int> P;

#define yn {puts("Yes");}else{puts("No");}

#define MAX_N 200005



#define ch() getchar()

#define pc(x) putchar(x)

template<typename T>inline void read(T&x){

	int f;char c;

	for(f=1,c=ch();c<'0'||c>'9';c=ch())if(c=='-')f=-f;

	for(x=0;c<='9'&&c>='0';c=ch())x=x*10+(c&15);x*=f;

}



int x[MAX_N], y[MAX_N];



int main() {

    int n, q;

    read(n); read(q);

    ll ans = (ll)(n-2)*(n-2);

    int xx = n;

    int yy = n;

    while(q--){

        int t, z;

        read(t), read(z);

        if(t == 1){

            if(z < xx){

                ans -= yy - 2;

                srep(i,z+1,xx) x[i] = yy;

                xx = z;

            }else{

                ans -= x[z] - 2;

            }

        }else{

            if(z < yy){

                ans -= xx - 2;

                srep(i,z+1,yy) y[i] = xx;

                yy = z;

            }else{

                ans -= y[z] - 2;

            }

        }

    }

    printf("%lld\n", ans);

    return 0;

}