// template {{{
#![allow(clippy::many_single_char_names)]

#[allow(dead_code)]
mod ngtio {
    use ::std::collections::VecDeque;

    pub struct Buffer {
        buf: VecDeque<String>,
    }

    impl Buffer {
        pub fn new() -> Self {
            Self {
                buf: VecDeque::new(),
            }
        }

        fn load(&mut self) {
            while self.buf.is_empty() {
                let mut s = String::new();
                let length = ::std::io::stdin().read_line(&mut s).unwrap();
                if length == 0 {
                    break;
                }
                self.buf.extend(s.split_whitespace().map(|s| s.to_owned()));
            }
        }

        pub fn string(&mut self) -> String {
            self.load();
            self.buf
                .pop_front()
                .unwrap_or_else(|| panic!("入力が終了したのですが。"))
        }

        pub fn string_char_vec(&mut self) -> Vec<char> {
            let s = self.string();
            s.chars().collect::<Vec<_>>()
        }

        pub fn string_char_vec_trusted_len(&mut self, len: usize) -> Vec<char> {
            let s = self.string();
            let s = s.chars().collect::<Vec<_>>();
            assert_eq!(s.len(), len, "あら、思ったのと長さ違いますね……");
            s
        }

        pub fn char(&mut self) -> char {
            let string = self.string();
            let mut chars = string.chars();
            let res = chars.next().unwrap();
            assert!(
                chars.next().is_none(),
                "char で受け取りたいのも山々なのですが、さては 2 文字以上ありますね？"
            );
            res
        }

        pub fn read<T: ::std::str::FromStr>(&mut self) -> T
        where
            <T as ::std::str::FromStr>::Err: ::std::fmt::Debug,
        {
            self.string()
                .parse::<T>()
                .expect("Failed to parse the input.")
        }

        pub fn read_vec<T: ::std::str::FromStr>(&mut self, len: usize) -> Vec<T>
        where
            <T as ::std::str::FromStr>::Err: ::std::fmt::Debug,
        {
            (0..len).map(|_| self.read::<T>()).collect()
        }
    }

    macro_rules! define_primitive_reader {
        ($($ty:tt,)*) => {
            impl Buffer {
                $(
#[inline]
                    pub fn $ty(&mut self) -> $ty {
                        self.read::<$ty>()
                    }
                )*
            }
        }
    }

    define_primitive_reader! {
        u8, u16, u32, u64, usize,
        i8, i16, i32, i64, isize,
    }

    impl Default for Buffer {
        fn default() -> Self {
            Self::new()
        }
    }
}

#[allow(unused_imports)]
use std::{collections, iter, mem, ops};
// }}}
// segtree {{{
#[allow(dead_code)]
mod segtree {
    #![warn(missing_docs)]

    pub use traits::{Value, Wrapper};
    pub use values::{Add, Affine, Cat, First, Inversion, Max, Min, Mul, Second};

    use std::{cmp, iter, ops};

    #[derive(Debug, Clone)]
    pub struct Segtree<T>
    where
        T: Value,
    {
        geta: usize,
        table: Vec<T>,
    }

    impl<T: Value> Segtree<T> {
        #[inline]
        pub fn is_empty(&self) -> bool {
            self.table.is_empty()
        }

        #[inline]
        pub fn len(&self) -> usize {
            (self.table.len() + 1) / 2
        }

        pub fn from_slice(src: &[T]) -> Self {
            iter::FromIterator::from_iter(src.iter().cloned())
        }

        pub fn as_slice(&self) -> &[T] {
            &self.table[self.geta..]
        }

        fn update_node_unckecked(&mut self, i: usize) {
            let (left, right) = self.table.split_at_mut(i * 2 + 1);
            left[i] = right[0].op(&right[1]);
        }

        pub fn update(&mut self, mut i: usize, x: T) {
            assert!(i <= self.len(), "添字がはみ出していてですね……");
            i += self.len() - 1;
            self.table[i] = x;
            while i != 0 {
                i = (i - 1) / 2;
                self.update_node_unckecked(i);
            }
        }

        pub fn modify<F>(&mut self, mut i: usize, mut modifier: F)
        where
            F: FnMut(&mut T),
        {
            assert!(i <= self.len(), "添字がはみ出していてですね……");
            i += self.len() - 1;
            modifier(&mut self.table[i]);
            while i != 0 {
                i = (i - 1) / 2;
                self.update_node_unckecked(i);
            }
        }

        pub fn fold(&self, range: impl ops::RangeBounds<usize>) -> Option<T> {
            let mut start = match range.start_bound() {
                ops::Bound::Excluded(&x) => x + 1,
                ops::Bound::Included(&x) => x,
                ops::Bound::Unbounded => 0,
            };
            let mut end = match range.end_bound() {
                ops::Bound::Excluded(&x) => x,
                ops::Bound::Included(&x) => x + 1,
                ops::Bound::Unbounded => self.len(),
            };

            assert!(start <= end, "変な区間を渡すのをやめませんか？");
            assert!(end <= self.len(), "添字がはみ出していてですね……");

            if start == end {
                None
            } else if start + 1 == end {
                Some(self.table[self.geta + start].clone())
            } else {
                start += self.geta;
                end += self.geta;
                let mut left = self.table[start].clone();
                start += 1;
                end -= 1;
                let mut right = self.table[end].clone();

                while start != end {
                    if start % 2 == 0 {
                        left.op_assign_from_the_right(&self.table[start]);
                        start += 1;
                    }
                    if end % 2 == 0 {
                        end -= 1;
                        right.op_assign_from_the_left(&self.table[end]);
                    }
                    start = (start - 1) / 2;
                    end = (end - 1) / 2;
                }

                Some(left.op(&right))
            }
        }

        pub fn partition_point(&self, start: usize, mut pred: impl FnMut(&T) -> bool) -> usize {
            let mut i = self.geta + start;
            if !pred(&self.table[i]) {
                start
            } else if self
                .fold(start..)
                .map(|folded| pred(&folded))
                .unwrap_or(true)
            {
                self.len()
            } else {
                let mut value = self.table[i].clone();
                i += 1;

                loop {
                    match i % 2 {
                        0 => {
                            let next_value = value.op(&self.table[i]);
                            if !pred(&next_value) {
                                break;
                            }
                            i += 1;
                            value = next_value;
                        }
                        1 => {
                            i /= 2;
                        }
                        _ => unreachable!(),
                    }
                }

                loop {
                    let next_value = value.op(&self.table[i]);
                    if pred(&next_value) {
                        i += 1;
                        value = next_value;
                    }
                    let next_i = i * 2 + 1;
                    if self.table.len() < next_i {
                        break;
                    }
                    i = next_i;
                }

                i - self.geta
            }
        }

        pub fn reverse_partition_point(
            &self,
            end: usize,
            mut pred: impl FnMut(&T) -> bool,
        ) -> usize {
            let mut i = self.geta + end;
            if end == 0 || !pred(&self.table[i - 1]) {
                end
            } else if self.fold(..end).map(|folded| pred(&folded)).unwrap_or(true) {
                0
            } else {
                i -= 1;
                let mut value = self.table[i].clone();

                while i != 0 {
                    match i % 2 {
                        0 => {
                            let next_value = self.table[i - 1].op(&value);
                            if !pred(&next_value) {
                                break;
                            }
                            i -= 1;
                            value = next_value;
                        }
                        1 => {
                            i = (i - 1) / 2;
                        }
                        _ => unreachable!(),
                    }
                }

                loop {
                    if i != 0 {
                        let next_value = self.table[i - 1].op(&value);
                        if pred(&next_value) {
                            i -= 1;
                            value = next_value;
                        }
                    }
                    let next_i = i * 2 + 1;
                    if self.table.len() < next_i {
                        break;
                    }
                    i = next_i;
                }

                i - self.geta
            }
        }
    }

    impl<T> Segtree<T>
    where
        T: Value + Wrapper,
    {
        #[inline]
        pub fn update_inner(&mut self, i: usize, x: T::Inner) {
            self.update(i, T::from_inner(x));
        }

        #[inline]
        pub fn modify_inner<F>(&mut self, i: usize, mut modifier: F)
        where
            F: FnMut(&mut T::Inner),
        {
            self.modify(i, |x| modifier(x.get_mut()));
        }

        #[inline]
        pub fn fold_inner(&self, range: impl ops::RangeBounds<usize>) -> Option<T::Inner> {
            self.fold(range).map(Wrapper::into_inner)
        }

        #[inline]
        pub fn partition_point_inner(
            &self,
            start: usize,
            mut pred: impl FnMut(&T::Inner) -> bool,
        ) -> usize {
            self.partition_point(start, |x| pred(x.get()))
        }

        #[inline]
        pub fn lower_bound_inner_by(
            &self,
            start: usize,
            mut cmp: impl FnMut(&T::Inner) -> cmp::Ordering,
        ) -> usize {
            self.partition_point_inner(start, |x| cmp(x) == cmp::Ordering::Less)
        }

        #[inline]
        pub fn upper_bound_inner_by(
            &self,
            start: usize,
            mut cmp: impl FnMut(&T::Inner) -> cmp::Ordering,
        ) -> usize {
            self.partition_point_inner(start, |x| cmp(x) != cmp::Ordering::Greater)
        }

        #[inline]
        pub fn lower_bound_inner_by_key<U: Ord>(
            &self,
            start: usize,
            value: &U,
            mut key: impl FnMut(&T::Inner) -> U,
        ) -> usize {
            self.lower_bound_inner_by(start, |x| key(x).cmp(value))
        }

        #[inline]
        pub fn upper_bound_inner_by_key<U: Ord>(
            &self,
            start: usize,
            value: &U,
            mut key: impl FnMut(&T::Inner) -> U,
        ) -> usize {
            self.upper_bound_inner_by(start, |x| key(x).cmp(value))
        }

        #[inline]
        pub fn reverse_partition_point_inner(
            &self,
            start: usize,
            mut pred: impl FnMut(&T::Inner) -> bool,
        ) -> usize {
            self.reverse_partition_point(start, |x| pred(x.get()))
        }

        #[inline]
        pub fn reverse_lower_bound_inner_by(
            &self,
            end: usize,
            mut cmp: impl FnMut(&T::Inner) -> cmp::Ordering,
        ) -> usize {
            self.reverse_partition_point_inner(end, |x| cmp(x) == cmp::Ordering::Less)
        }

        #[inline]
        pub fn reverse_upper_bound_inner_by(
            &self,
            end: usize,
            mut cmp: impl FnMut(&T::Inner) -> cmp::Ordering,
        ) -> usize {
            self.reverse_partition_point_inner(end, |x| cmp(x) != cmp::Ordering::Greater)
        }

        #[inline]
        pub fn reverse_lower_bound_inner_by_key<U: Ord>(
            &self,
            end: usize,
            value: &U,
            mut key: impl FnMut(&T::Inner) -> U,
        ) -> usize {
            self.reverse_lower_bound_inner_by(end, |x| key(x).cmp(value))
        }

        #[inline]
        pub fn reverse_upper_bound_inner_by_key<U: Ord>(
            &self,
            end: usize,
            value: &U,
            mut key: impl FnMut(&T::Inner) -> U,
        ) -> usize {
            self.reverse_upper_bound_inner_by(end, |x| key(x).cmp(value))
        }

        pub fn to_vec_inner(&self) -> Vec<T::Inner> {
            self.as_slice().iter().cloned().map(T::into_inner).collect()
        }
    }

    impl<T> Segtree<T>
    where
        T: Value + Wrapper,
        T::Inner: Ord,
    {
        #[inline]
        pub fn lower_bound_inner(&self, start: usize, value: &T::Inner) -> usize {
            self.partition_point_inner(start, |x| x < value)
        }

        #[inline]
        pub fn upper_bound_inner(&self, start: usize, value: &T::Inner) -> usize {
            self.partition_point_inner(start, |x| x <= value)
        }

        #[inline]
        pub fn reverse_lower_bound_inner(&self, end: usize, value: &T::Inner) -> usize {
            self.reverse_partition_point_inner(end, |x| x < value)
        }

        #[inline]
        pub fn reverse_upper_bound_inner(&self, end: usize, value: &T::Inner) -> usize {
            self.reverse_partition_point_inner(end, |x| x <= value)
        }
    }

    impl<T: Value> iter::FromIterator<T> for Segtree<T> {
        fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Segtree<T> {
            let mut iter = iter.into_iter();
            if let Some(head) = iter.next() {
                let mut table = iter.collect::<Vec<_>>();
                let tmp = table.to_vec();
                table.push(head);
                table.extend(tmp.into_iter());

                let geta = table.len() / 2;

                for i in (0..geta).rev() {
                    table[i] = table[2 * i + 1].op(&table[2 * i + 2]);
                }

                if !table.is_empty() {
                    let mut i = table.len();
                    while i != 0 {
                        i = (i - 1) / 2;
                    }
                }

                Self { geta, table }
            } else {
                Self {
                    geta: 0,
                    table: Vec::new(),
                }
            }
        }
    }

    impl<T: Value, I: std::slice::SliceIndex<[T]>> std::ops::Index<I> for Segtree<T> {
        type Output = I::Output;

        #[inline]
        fn index(&self, index: I) -> &Self::Output {
            std::ops::Index::index(self.as_slice(), index)
        }
    }

    mod traits {
        pub trait Value: Clone {
            fn op(&self, rhs: &Self) -> Self;

            fn op_assign_from_the_right(&mut self, rhs: &Self) {
                *self = self.op(rhs);
            }

            fn op_assign_from_the_left(&mut self, rhs: &Self) {
                *self = rhs.op(self);
            }
        }

        pub trait Wrapper {
            type Inner;

            fn get(&self) -> &Self::Inner;

            fn get_mut(&mut self) -> &mut Self::Inner;

            fn into_inner(self) -> Self::Inner;

            fn from_inner(src: Self::Inner) -> Self;
        }
    }

    mod values {
        use super::{Value, Wrapper};
        use std::{cmp, ops};

        macro_rules! impl_wrapper {
            (impl Wrapper for $struct_name:ident {}) => {
                impl<T> Wrapper for $struct_name<T> {
                    type Inner = T;

                    #[inline]
                    fn get(&self) -> &Self::Inner {
                        &self.0
                    }
                    #[inline]
                    fn get_mut(&mut self) -> &mut Self::Inner {
                        &mut self.0
                    }
                    #[inline]
                    fn into_inner(self) -> Self::Inner {
                        self.0
                    }
                    #[inline]
                    fn from_inner(src: Self::Inner) -> Self {
                        Self(src)
                    }
                }
            };
        }

        #[derive(Debug, Clone, PartialEq, Eq)]
        pub struct Cat(pub String);
        impl Value for Cat {
            #[inline]
            fn op(&self, rhs: &Self) -> Self {
                Cat(self.0.chars().chain(rhs.0.chars()).collect())
            }
        }
        impl Wrapper for Cat {
            type Inner = String;

            #[inline]
            fn get(&self) -> &Self::Inner {
                &self.0
            }
            #[inline]
            fn get_mut(&mut self) -> &mut Self::Inner {
                &mut self.0
            }
            #[inline]
            fn into_inner(self) -> Self::Inner {
                self.0
            }
            #[inline]
            fn from_inner(src: Self::Inner) -> Self {
                Self(src)
            }
        }

        #[derive(Debug, Clone, PartialEq, Eq)]
        pub struct Add<T>(pub T);
        impl<T> Value for Add<T>
        where
            T: Clone + ops::Add<Output = T>,
        {
            fn op(&self, rhs: &Self) -> Self {
                Add(self.0.clone() + rhs.0.clone())
            }
        }
        impl_wrapper! { impl Wrapper for Add {} }

        #[derive(Debug, Clone, PartialEq, Eq)]
        pub struct Mul<T>(pub T);
        impl<T> Value for Mul<T>
        where
            T: Clone + ops::Mul<Output = T>,
        {
            fn op(&self, rhs: &Self) -> Self {
                Mul(self.0.clone() * rhs.0.clone())
            }
        }
        impl_wrapper! { impl Wrapper for Mul {} }

        #[derive(Debug, Clone, PartialEq, Eq)]
        pub struct Min<T>(pub T);
        impl<T> Value for Min<T>
        where
            T: Clone + cmp::Ord,
        {
            fn op(&self, rhs: &Self) -> Self {
                Min(self.0.clone().min(rhs.0.clone()))
            }
        }
        impl_wrapper! { impl Wrapper for Min {} }

        #[derive(Debug, Clone, PartialEq, Eq)]
        pub struct Max<T>(pub T);
        impl<T> Value for Max<T>
        where
            T: Clone + cmp::Ord,
        {
            fn op(&self, rhs: &Self) -> Self {
                Max(self.0.clone().max(rhs.0.clone()))
            }
        }
        impl_wrapper! { impl Wrapper for Max {} }

        #[derive(Debug, Clone, PartialEq, Eq)]
        pub struct Inversion {
            zeros: usize,
            ones: usize,
            inv: usize,
        }
        impl Inversion {
            pub fn inv(&self) -> usize {
                self.inv
            }
            pub fn try_into_bool(self) -> Option<bool> {
                match self {
                    Self {
                        zeros: 1,
                        ones: 0,
                        inv: 0,
                    } => Some(false),
                    Self {
                        zeros: 0,
                        ones: 1,
                        inv: 0,
                    } => Some(true),
                    _ => None,
                }
            }
            pub fn zero() -> Self {
                Self {
                    zeros: 1,
                    ones: 0,
                    inv: 0,
                }
            }
            pub fn one() -> Self {
                Self {
                    zeros: 0,
                    ones: 1,
                    inv: 0,
                }
            }
            pub fn from_bool(b: bool) -> Self {
                if b {
                    Self::one()
                } else {
                    Self::zero()
                }
            }
        }
        impl Value for Inversion {
            fn op(&self, rhs: &Self) -> Self {
                let zeros = self.zeros + rhs.zeros;
                let ones = self.ones + rhs.ones;
                let inv = self.inv + rhs.inv + self.ones * rhs.zeros;
                Self { zeros, ones, inv }
            }
        }

        #[derive(Debug, Clone, PartialEq, Eq)]
        pub struct First<T>(pub T);
        impl<T: std::fmt::Debug + Clone> Value for First<T> {
            fn op(&self, _rhs: &Self) -> Self {
                self.clone()
            }
        }
        impl_wrapper! { impl Wrapper for First {} }

        #[derive(Debug, Clone, PartialEq, Eq)]
        pub struct Second<T>(pub T);
        impl<T: std::fmt::Debug + Clone> Value for Second<T> {
            fn op(&self, rhs: &Self) -> Self {
                rhs.clone()
            }
        }
        impl_wrapper! { impl Wrapper for Second {} }

        #[derive(Debug, Clone, PartialEq, Eq)]
        pub struct Affine<T> {
            a: T,
            b: T,
        }
        impl<T: std::fmt::Debug + Clone> Value for Affine<T>
        where
            T: ops::Add<Output = T> + ops::Mul<Output = T>,
        {
            fn op(&self, rhs: &Self) -> Self {
                let a = self.a.clone() * rhs.a.clone();
                let b = self.b.clone() + self.a.clone() * rhs.b.clone();
                Affine { a, b }
            }
        }
    }
}
// }}}
// dbg {{{
#[allow(dead_code)]
mod dbg {
    #[macro_export]
    macro_rules! lg {
        () => {
            $crate::eprintln!("[{}:{}]", $crate::file!(), $crate::line!());
        };
        ($val:expr) => {
            match $val {
                tmp => {
                    eprintln!("[{}:{}] {} = {:?}",
                        file!(), line!(), stringify!($val), &tmp);
                    tmp
                }
            }
        };
        ($val:expr,) => { $crate::lg!($val) };
        ($($val:expr),+ $(,)?) => {
            ($($crate::lg!($val)),+,)
        };
    }

    #[macro_export]
    macro_rules! lg_nl {
        () => {
            eprintln!("[{}:{}]", $crate::file!(), $crate::line!());
        };
        ($val:expr) => {
            match $val {
                tmp => {
                    eprintln!("[{}:{}] {}:\n{:?}", file!(), line!(), stringify!($val), tmp);
                    tmp
                }
            };
        };
    }

    #[macro_export]
    macro_rules! msg {
        () => {
            compile_error!();
        };
        ($msg:expr) => {
            $crate::eprintln!("[{}:{}][{}]", $crate::file!(), $crate::line!(), $msg);
        };
        ($msg:expr, $val:expr) => {
            match $val {
                tmp => {
                    eprintln!("[{}:{}][{}] {} = {:?}",
                        file!(), line!(), $msg, stringify!($val), &tmp);
                    tmp
                }
            }
        };
        ($msg:expr, $val:expr,) => { msg!($msg, $val) };
        ($msg:expr, $($val:expr),+ $(,)?) => {
            ($(msg!($msg, $val)),+,)
        };
    }

    #[macro_export]
    macro_rules! tabular {
        ($val:expr) => {
            $crate::lg_nl!(crate::dbg::Tabular($val))
        };
    }

    #[macro_export]
    macro_rules! boolean_table {
        ($val:expr) => {
            $crate::lg_nl!(crate::dbg::BooleanTable($val));
        };
    }

    #[macro_export]
    macro_rules! boolean_slice {
        ($val:expr) => {
            $crate::lg!(crate::dbg::BooleanSlice($val));
        };
    }

    use std::fmt::{Debug, Formatter};

    #[derive(Clone)]
    pub struct Tabular<'a, T: Debug>(pub &'a [T]);
    impl<'a, T: Debug> Debug for Tabular<'a, T> {
        fn fmt(&self, f: &mut Formatter) -> std::fmt::Result {
            for i in 0..self.0.len() {
                writeln!(f, "{:2} | {:?}", i, &self.0[i])?;
            }
            Ok(())
        }
    }

    #[derive(Clone)]
    pub struct BooleanTable<'a>(pub &'a [Vec<bool>]);
    impl<'a> Debug for BooleanTable<'a> {
        fn fmt(&self, f: &mut Formatter) -> std::fmt::Result {
            for i in 0..self.0.len() {
                writeln!(f, "{:2} | {:?}", i, BooleanSlice(&self.0[i]))?;
            }
            Ok(())
        }
    }

    #[derive(Clone)]
    pub struct BooleanSlice<'a>(pub &'a [bool]);
    impl<'a> Debug for BooleanSlice<'a> {
        fn fmt(&self, f: &mut Formatter) -> std::fmt::Result {
            write!(
                f,
                "{}",
                self.0
                    .iter()
                    .map(|&b| if b { "1 " } else { "0 " })
                    .collect::<String>()
            )?;
            Ok(())
        }
    }
}
// }}}

use segtree::{Max, Segtree};

fn main() {
    let mut buf = ngtio::Buffer::new();
    let n = buf.usize() - 2;
    let q = buf.usize();
    let mut seg0 = iter::repeat(0)
        .take(n)
        .chain(iter::once(n))
        .map(Max)
        .collect::<Segtree<Max<usize>>>();
    let mut seg1 = iter::repeat(0)
        .take(n)
        .chain(iter::once(n))
        .map(Max)
        .collect::<Segtree<Max<usize>>>();

    let mut ans = n * n;
    for _ in 0..q {
        let (me, other) = match buf.u32() {
            1 => (&mut seg0, &seg1),
            2 => (&mut seg1, &seg0),
            _ => panic!(),
        };
        let i = buf.usize() - 2;
        let j = other.upper_bound_inner(0, &i);
        me.modify(i, |x| x.0 = j);
        ans -= j;
    }
    println!("{}", ans);
}


Measured memory_bytes: 11260