Problem: There is a grid with N rows and N columns of squares. Let (i, j) be the square at the i-th row from the top and the j-th column from the left.

Each of the central (N-2) \times (N-2) squares in the grid has a black stone on it. Each of the 2N - 1 squares on the bottom side and the right side has a white stone on it.

Q queries are given. We ask you to process them in order. There are two kinds of queries. Their input format and description are as follows:

* `1 x`: Place a white stone on (1, x). After that, for each black stone between (1, x) and the first white stone you hit if you go down from (1, x), replace it with a white stone.
* `2 x`: Place a white stone on (x, 1). After that, for each black stone between (x, 1) and the first white stone you hit if you go right from (x, 1), replace it with a white stone.



How many black stones are there on the grid after processing all Q queries?

Constraints

* 3 \leq N \leq 2\times 10^5
* 0 \leq Q \leq \min(2N-4,2\times 10^5)
* 2 \leq x \leq N-1
* Queries are pairwise distinct.

Input

Input is given from Standard Input in the following format:


N Q
Query_1
\vdots
Query_Q


Output

Print how many black stones there are on the grid after processing all Q queries.

Examples

Input

5 5
1 3
2 3
1 4
2 2
1 2


Output

1


Input

200000 0


Output

39999200004


Input

176527 15
1 81279
2 22308
2 133061
1 80744
2 44603
1 170938
2 139754
2 15220
1 172794
1 159290
2 156968
1 56426
2 77429
1 97459
2 71282


Output

31159505795

Solution (in JAVA):

Solution:
import java.io.*;
import java.util.*;

public class Main {
  private static final UpdateRangeGetRangeSegmentTree.Operator OPERATOR = new UpdateRangeGetRangeSegmentTree.Operator(){
    @Override
    public int multiplyLazyValue(int lazy, int count) {
      return lazy;
    }

    @Override
    public int applyOffset(int lazy, int offset) {
      return lazy;
    }

    @Override
    public int mergeLazyValue(int oldLazy, int newLazy) {
      if (oldLazy == -1) {
        return newLazy;
      }
      return Math.min(oldLazy, newLazy);
    }

    @Override
    public int apply(int value, int lazy) {
      return Math.min(value, lazy);
    }

    @Override
    public int mergeValue(int smallIndexValue, int largeIndexValue) {
      return Math.min(smallIndexValue, largeIndexValue);
    }

    @Override
    public int getUnitValue() {
      return Integer.MAX_VALUE;
    }
    
  };

  private static long solve(int n, int q, int[][] txs) {
    int[] initialValues = new int[n];
    Arrays.fill(initialValues, n);
    UpdateRangeGetRangeSegmentTree segmentTree1 = new UpdateRangeGetRangeSegmentTree(OPERATOR, initialValues);
    UpdateRangeGetRangeSegmentTree segmentTree2 = new UpdateRangeGetRangeSegmentTree(OPERATOR, initialValues);
    long answer = (long)(n - 2) * (long)( n - 2);
    for (int[] tx : txs) {
      int type = tx[0];
      int x = tx[1];
      /*
      for (int i = 0; i < n; i++) {
        System.err.printf("i: %d, 1: %d, 2: %d\n", i, segmentTree1.get(i), segmentTree2.get(i));
      }
      */
      if (type == 1) {
        int v = segmentTree1.get(x);
//        System.err.printf("x: %d, v: %d\n", x, v);
        segmentTree2.update(0, v, x);
        answer -= v - 2;
      } else {
        int v = segmentTree2.get(x);
//        System.err.printf("x: %d, v: %d\n", x, v);
        segmentTree1.update(0, v, x);
        answer -= v - 2;
      }
//      System.err.println(answer);
    }
    return answer;
  }

  private static void execute(ContestReader reader, ContestWriter out) {
    int n = reader.nextInt();
    int q = reader.nextInt();
    int[][] txs = reader.nextInt(q, 2);
    out.println(solve(n, q, txs));
  }
  
  public static void main(String[] args) {
    ContestReader reader = new ContestReader(System.in);
    ContestWriter out = new ContestWriter(System.out);
    execute(reader, out);
    out.flush();
  }
}

class ContestWriter extends PrintWriter {
  ContestWriter(PrintStream printStream) {
    super(printStream);
  }

  public void printList(List<? extends Object> list) {
    for (Object object : list) {
      println(object);
    }
  }

  public void printListOneLine(List<? extends Object> list) {
    List<String> stringList = new ArrayList<>();
    for (Object object : list) {
      stringList.add(object.toString());
    }
    println(String.join(" ", stringList));
  }
}

// Verify ABC177 F
// https://atcoder.jp/contests/abc177/tasks/abc177_f

class UpdateRangeGetRangeSegmentTree {
  public interface Operator {
    int multiplyLazyValue(int lazy, int count);
    int applyOffset(int lazy, int offset);
    int mergeLazyValue(int oldLazy, int newLazy);
    int apply(int value, int lazy);
    int mergeValue(int smallIndexValue, int largeIndexValue);
    int getUnitValue();
  }
  
  private final Operator operator;
  private final int n;
  private final int[] lazies;
  private final int[] values;
  
  public UpdateRangeGetRangeSegmentTree(Operator operator, int[] initialValues) {
    this.operator = operator;
    
    int tempN = 1;
    while (tempN < initialValues.length) {
      tempN *= 2;
    }
    n = tempN;
    lazies = createTArray(2 * n -1);
    Arrays.fill(lazies, -1);
    values = createSArray(2 * n -1);
    for (int i = 0; i < initialValues.length; i++) {
      values[i + n - 1] = initialValues[i];
    }
    for (int i = initialValues.length; i < n; i++) {
      values[i + n - 1] = this.operator.getUnitValue();
    }
    for (int i = n - 2; i >= 0; i--) {
      values[i] = this.operator.mergeValue(values[2 * i + 1], values[2 * i + 2]);
    }
    
    /*
    for (int i = 0; i < 2 * n - 1; i++) {
      System.err.printf("%d %d %d\n", i, values[i], lazies[i]);
    }
    */
  }

  @SuppressWarnings("unchecked")
  private int[] createTArray(int size) {
    return new int[size];    
  }
  
  @SuppressWarnings("unchecked")
  private int[] createSArray(int size) {
    return new int[size];    
  }
  
  private void eval(int k, int l, int r) {
    if (lazies[k] == -1) {
      return;
    }
    values[k] = operator.apply(values[k], operator.multiplyLazyValue(lazies[k], r - l));
    if (r - l > 1) {
      lazies[2 * k + 1] = operator.mergeLazyValue(lazies[2 * k + 1], lazies[k]);
      lazies[2 * k + 2] = operator.mergeLazyValue(lazies[2 * k + 2], operator.applyOffset(lazies[k], (r - l) / 2));
    }
    lazies[k] = -1;
  }
  
  private void update(int a, int b, int lazy, int k, int l, int r) {
    eval(k, l, r);
    if (b <= l || r <= a) {
      return;
    }
    if (a <= l && r <= b) {
      lazies[k] = operator.mergeLazyValue(lazies[k], lazy);
      eval(k, l, r);
    } else {
      update(a, b, lazy, 2 * k + 1, l, (l + r) / 2);
      update(a, b, operator.applyOffset(lazy, (r - l) / 2), 2 * k + 2, (l + r) / 2, r);
      values[k] = operator.mergeValue(values[2 * k + 1], values[2 * k + 2]);
    }
  }
  
  public void update(int a, int b, int lazy) {
    update(a, b, lazy, 0, 0, n);
  }
  
  public void update(int a, int lazy) {
    update(a, a + 1, lazy);
  }
  
  private int getRange(int a, int b, int k, int l, int r) {
    if (b <= l || r <= a) {
      return operator.getUnitValue();
    }
    eval(k, l, r);
    if (a <= l && r <= b) {
      return values[k];
    }
    int vl = getRange(a, b, 2 * k + 1, l, (l + r) / 2);
    int vr = getRange(a, b, 2 * k + 2, (l + r) / 2, r);
    return operator.mergeValue(vl, vr);
  }
  
  public int getRange(int a, int b) {
    return getRange(a, b, 0, 0, n);
  }
  
  public int get(int a) {
    return getRange(a, a + 1);
  }
}


class ContestReader {
  private static final int BUFFER_SIZE = 1024;
  
  private final InputStream stream;
  private final byte[] buffer;
  private int pointer;
  private int bufferLength;
  
  ContestReader(InputStream stream) {
    this.stream = stream;
    this.buffer = new byte[BUFFER_SIZE];
    this.pointer = 0;
    this.bufferLength = 0;
  }
  
  private boolean hasNextByte() {
    if (pointer < bufferLength) {
      return true;
    }
    
    pointer = 0;
    try {
      bufferLength = stream.read(buffer);
    } catch (IOException e) {
      throw new RuntimeException(e);
    }
    return bufferLength > 0;
  }
  
  private int readByte() {
    if (hasNextByte()) {
      return buffer[pointer++];
    } else {
      return -1;
    }
  }
  
  private static boolean isPrintableChar(int c) {
    return 33 <= c && c <= 126;
  }
  
  public boolean hasNext() {
    while (hasNextByte() && !isPrintableChar(buffer[pointer])) {
      pointer++;
    }
    return hasNextByte();
  }
  
  public String next() {
    if (!hasNext()) {
      throw new NoSuchElementException();
    }
    StringBuilder sb = new StringBuilder();
    while(true) {
      int b = readByte();
      if (!isPrintableChar(b)) {
        break;
      }
      sb.appendCodePoint(b);
    }
    return sb.toString();
  }
  
  public String nextLine() {
    if (!hasNext()) {
      throw new NoSuchElementException();
    }
    StringBuilder sb = new StringBuilder();
    while(true) {
      int b = readByte();
      if (!isPrintableChar(b) && b != 0x20) {
        break;
      }
      sb.appendCodePoint(b);
    }
    return sb.toString();
  }
  
  public char nextChar() {
    return next().charAt(0);
  }
  
  public int nextInt() {
    if (!hasNext()) {
      throw new NoSuchElementException();
    }
    
    int n = 0;
    boolean minus = false;
    
    {
      int b = readByte();
      if (b == '-') {
        minus = true;
      } else if ('0' <= b && b <= '9') {
        n = b - '0';
      } else {
        throw new NumberFormatException();
      }
    }
    
    while(true){
      int b = readByte();
      if ('0' <= b && b <= '9') {
        n *= 10;
        n += b - '0';
      } else if (b == -1 || !isPrintableChar(b)) {
        return minus ? -n : n;
      } else {
        throw new NumberFormatException();
      }
    }
  }
  
  public long nextLong() {
    if (!hasNext()) {
      throw new NoSuchElementException();
    }
    
    long n = 0;
    boolean minus = false;
    
    {
      int b = readByte();
      if (b == '-') {
        minus = true;
      } else if ('0' <= b && b <= '9') {
        n = b - '0';
      } else {
        throw new NumberFormatException();
      }
    }
    
    while(true){
      int b = readByte();
      if ('0' <= b && b <= '9') {
        n *= 10;
        n += b - '0';
      } else if (b == -1 || !isPrintableChar(b)) {
        return minus ? -n : n;
      } else {
        throw new NumberFormatException();
      }
    }
  }
  
  public double nextDouble() {
    return Double.parseDouble(next());
  }
  
  public String[] next(int n) {
    String[] array = new String[n];
    for (int i = 0; i < n; i++) {
      array[i] = next();
    }
    return array;
  }
  
  public String[] nextLine(int n) {
    String[] array = new String[n];
    for (int i = 0; i < n; i++) {
      array[i] = nextLine();
    }
    return array;
  }
  
  public char[] nextChar(int n) {
    char[] array = new char[n];
    for (int i = 0; i < n; i++) {
      array[i] = nextChar();
    }
    return array;
  }
  
  public int[] nextInt(int n) {
    int[] array = new int[n];
    for (int i = 0; i < n; i++) {
      array[i] = nextInt();
    }
    return array;
  }
  
  public long[] nextLong(int n) {
    long[] array = new long[n];
    for (int i = 0; i < n; i++) {
      array[i] = nextLong();
    }
    return array;
  }
  
  public double[] nextDouble(int n) {
    double[] array = new double[n];
    for (int i = 0; i < n; i++) {
      array[i] = nextDouble();
    }
    return array;
  }
  
  public char[] nextCharArray() {
    return next().toCharArray();
  }
  
  public String[][] next(int n, int m) {
    String[][] matrix = new String[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        matrix[i][j] = next();
      }
    }
    return matrix;
  }
  
  public int[][] nextInt(int n, int m) {
    int[][] matrix = new int[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        matrix[i][j] = nextInt();
      }
    }
    return matrix;
  }
  
  public char[][] nextChar(int n, int m) {
    char[][] matrix = new char[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        matrix[i][j] = nextChar();
      }
    }
    return matrix;
  }
  
  public long[][] nextLong(int n, int m) {
    long[][] matrix = new long[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        matrix[i][j] = nextLong();
      }
    }
    return matrix;
  }
  
  public double[][] nextDouble(int n, int m) {
    double[][] matrix = new double[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        matrix[i][j] = nextDouble();
      }
    }
    return matrix;
  }
  
  public char[][] nextCharArray(int n) {
    char[][] matrix = new char[n][];
    for (int i = 0; i < n; i++) {
      matrix[i] = next().toCharArray();
    }
    return matrix;
  }
}

class MyAssert {
  public static void myAssert(boolean flag, String message) {
    if (!flag) {
      throw new RuntimeException(message);
    }
  }
 
  public static void myAssert(boolean flag) {
    myAssert(flag, "");
  }
}