#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
struct Max(usize);

impl ops::Add for Max {
    type Output = Self;
    fn add(self, rhs: Self) -> Self {
        Self(self.0.max(rhs.0))
    }
}

impl ops::AddAssign for Max {
    fn add_assign(&mut self, rhs: Self) {
        *self = *self + rhs;
    }
}

impl std::iter::Sum for Max {
    fn sum<I: Iterator<Item = Self>>(iter: I) -> Self {
        iter.fold(Max(0), ops::Add::add)
    }
}
fn main() {
    let mut buf = ngtio::Buffer::new();
    let n = buf.usize() - 2;
    let q = buf.usize();
    let mut init = vec![Max(0); n + 1];
    init[n] = Max(n);
    let mut a = fenwick::Fenwick::from_zero_slice(Max(0), &init);
    let mut b = fenwick::Fenwick::from_zero_slice(Max(0), &init);

    let mut ans = n * n;
    for _ in 0..q {
        let (me, other) = match buf.u32() {
            1 => (&mut a, &b),
            2 => (&mut b, &a),
            _ => panic!(),
        };
        let i = buf.usize() - 2;
        let j = other.upper_bound(&Max(i));
        me.add(i, Max(j));
        ans -= j;
    }
    println!("{}", ans);
}

// template {{{
#[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};
// }}}
// 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(())
        }
    }
}
// }}}
// fenwick {{{
#[allow(dead_code)]
mod fenwick {
    use std::{fmt, iter, ops};

    #[derive(Debug, Clone)]
    pub struct Fenwick<T> {
        table: Vec<T>,
    }

    impl<'a, T> Fenwick<T>
    where
        T: Clone + fmt::Debug + ops::Add<Output = T> + ops::AddAssign + iter::Sum<T>,
    {
        pub fn new(zero: T) -> Self {
            Fenwick { table: vec![zero] }
        }

        pub fn from_zero_slice(zero: T, src: &[T]) -> Self {
            let mut table = iter::once(zero)
                .chain(src.iter().cloned())
                .collect::<Vec<_>>();
            let n = table.len();
            (1..n)
                .map(|i| (i, i + lsb(i)))
                .filter(|&(_, j)| j < n)
                .for_each(|(i, j)| {
                    let x = table[i].clone();
                    table[j] += x
                });
            Self { table }
        }

        pub fn push(&mut self, mut x: T) {
            let i = self.table.len();
            let lsb_i = lsb(i);
            x += iter::successors(Some(1), |&d| Some(2 * d))
                .take_while(|&d| d != lsb_i)
                .map(|d| self.table[i - d].clone())
                .sum::<T>();
            self.table.push(x);
        }

        pub fn prefix_sum(&self, i: usize) -> T {
            iter::successors(Some(i), |&i| Some(i - lsb(i)))
                .take_while(|&i| i != 0)
                .map(|i| self.table[i].clone())
                .sum::<T>()
        }

        pub fn add(&mut self, i: usize, x: T) {
            let n = self.table.len();
            iter::successors(Some(i + 1), |&i| Some(i + lsb(i)))
                .take_while(|&i| i < n)
                .for_each(|i| self.table[i] += x.clone());
        }

        pub fn partition_point(&self, pred: impl Fn(usize, &T) -> bool) -> (usize, T) {
            let mut j = 0;
            let mut current = self.table[0].clone();
            for d in iter::successors(Some(self.table.len().next_power_of_two() / 2), |&d| {
                Some(d / 2)
            })
            .take_while(|&d| d != 0)
            {
                assert!(
                    pred(0, &self.table[0]),
                    "pred(0, zero) のほうよろしくお願いいたします！"
                );
                if j + d < self.table.len() {
                    let next = current.clone() + self.table[j + d].clone();
                    if pred(j + d, &next) {
                        current = next;
                        j += d;
                    }
                }
            }
            (j, current)
        }

        #[inline]
        pub fn lower_bound(&self, x: &T) -> usize
        where
            T: Ord,
        {
            self.partition_point(|_, y| y < x).0
        }

        #[inline]
        pub fn upper_bound(&self, x: &T) -> usize
        where
            T: Ord,
        {
            self.partition_point(|_, y| y <= x).0
        }

        #[inline]
        pub fn lower_bound_from(&self, i: usize, x: &T) -> usize
        where
            T: Ord,
        {
            let bi = self.prefix_sum(i);
            let res = self.partition_point(|_, y| y < &(bi.clone() + x.clone())).0;
            assert!(i <= res, "逆戻りしていませんか？");
            res
        }

        #[inline]
        pub fn upper_bound_from(&self, i: usize, x: &T) -> usize
        where
            T: Ord,
        {
            let bi = self.prefix_sum(i);
            let res = self
                .partition_point(|_, y| y <= &(bi.clone() + x.clone()))
                .0;
            assert!(i <= res, "逆戻りしていませんか？");
            res
        }
    }

    impl<'a, T> Fenwick<T>
    where
        T: Clone
            + fmt::Debug
            + ops::Add<Output = T>
            + ops::AddAssign
            + ops::Sub<Output = T>
            + ops::SubAssign
            + iter::Sum<T>,
    {
        pub fn sum(&self, range: impl ops::RangeBounds<usize>) -> T {
            let start = match range.start_bound() {
                ops::Bound::Unbounded => 0,
                ops::Bound::Included(&x) => x,
                ops::Bound::Excluded(&x) => x + 1,
            };
            let end = match range.end_bound() {
                ops::Bound::Excluded(&x) => x,
                ops::Bound::Included(&x) => x + 1,
                ops::Bound::Unbounded => self.table.len() - 1,
            };
            assert!(start <= end, "変な区間を渡すのをやめませんか？");
            assert!(end < self.table.len(), "残念範囲外です！");
            self.prefix_sum(end) - self.prefix_sum(start)
        }

        pub fn access(&self, i: usize) -> T {
            assert!(i < self.table.len() - 1, "残念範囲外です！");
            self.prefix_sum(i + 1) - self.prefix_sum(i)
        }

        pub fn set(&mut self, i: usize, x: T) {
            assert!(i < self.table.len() - 1, "残念範囲外です！");
            self.add(i, x - self.access(i));
        }
    }

    fn lsb(x: usize) -> usize {
        x & x.wrapping_neg()
    }
}
// }}}


Measured memory_bytes: 6792