Matrix Value with Row/Column Toggle

We are given a matrix of size (2^n \times 2^n) initially filled with white cells. A cell can be either white or black. The value of a matrix is defined recursively as follows:

1. If all cells in the matrix are of the same color, its value is (1) coin.
2. Otherwise, split the matrix into four equally sized submatrices, and then the value is equal to the sum of the values of the four submatrices plus (1) coin.

You are given (q) queries. In each query, you are given a toggle instruction for either a row or a column. For a query with type R and index (x), you must flip the color of all cells in row (x) (i.e. white becomes black and black becomes white). Similarly, for a query with type C and index (x), you must flip the color of all cells in column (x). After each query, you need to compute and output the new value of the whole matrix.

Note: The indices for rows and columns are 1-indexed.

inputFormat

The first line contains two integers (n) and (q) where the matrix is of size (2^n \times 2^n) and (q) is the number of queries.

Each of the next (q) lines contains a character and an integer. The character is either R or C denoting whether to toggle a row or a column respectively, followed by an integer (x) (1-indexed) representing the row or column to be toggled.

outputFormat

After each query, output the value of the matrix on a new line.

sample

1 1
R 1

5