Managing Bare Branches in BST

The team of professor Fabinaris Suchbaum has recently made a significant progrees in exploration of properties of binary search trees (BST). You can read about their achievements here and here. Currently, they are investigating trees which arise in some garbage collection related applications and which are characterized by having big depth and relatively few branchings.

We say that an unempty sequence of nodes (n1, n2, ..., nM) in a BST is a bare branch of length M if the following holds:

  1. Each node in the sequence has at most one child.
  2. Node nk is the parent of node nk+1 for each k = 1, 2, ..., M−1.
  3. If node n1 is not the root of the entire BST then its parent has two children.
The aim of the team is to prevent BST from containing bare branches of length 2K−1. The value of K is given and it is fixed.

When a bare branch B of length 2K−1 occurs in the tree as a result of Insert or Delete operation it has to be immediately removed from the tree and substituted by a perfectly balanced subtree T which contains all 2K−1 nodes of B. If there exists a parent P of the root of B then P will become the parent of the root of T, otherwise the root of T will become the root of the entire BST. If there exists a child C of the deepest node of B then C will become a child of some leaf of T. The position of all nodes inside T and the position of C relatively to T are determined unambiguously because the whole tree is a search tree.

One Insert operation can result in at most one bare branch of length 2K−1. One Delete operation can result in at most two bare branches of length 2K−1. The case in which two bare branches of length 2K−1 occur is shown in Image 1 bellow.

Note 1. The order of nodes in a bare branch (top-down order) does not generally correspond to the increasing/decreasing order of keys (left-right order) in the corresponding nodes of the bare branch. Informally speaking, a bare branch may not be "straight", it may be "bent" at various nodes.

     


Image 1. Occurence of two bare branches of length 2K−1 after deletion of node d. Both bare branches are consecutively removed and substituted by perfectly balanced subtrees T1 and T2. Node v is simultaneously part of T1 and T2, node z is part of T2. Nodes u and v may not be the same, also nodes x and z may not be the same, due to Note 1 above. Smaller blue triangles represent unaffected regions of BST.

The task

You are given a value of K and a sequence of Insert and Delete operations which are to be applied on an originally empty BST. Each bare branch of length 2K−1 which arises during the process has to be immediately removed by the method described above. Calculate how many times was a bare branch removed.

Note 2. In this problem, we suppose that Delete operation substitutes a deleted node d by the leftmost node of the right subtree of d in case when d has two children.

Input

The first input line contains two integers K and N separated by spaces. Next, there are N lines, each specifies one operation. Operation Insert is specified by capital letter 'I' followed by space and an integer key. Operation Delete is specified by capital letter 'D' followed by space and an integer key. There are no duplicate keys in the input and also there are no Delete operations of non-existent keys.
It holds, 2 ≤ K ≤ 12, 2 ≤ N ≤ 1.4×106.

Output

The output consists of one text line containing one non-negative integer equal to the total number of times a bare branch of length 2K−1 was substituted by a perfectly balanced subtree during all operations specified in the input.

Example 1

Input
2 11
I 90
I 95
I 40
I 80
I 60
I 75
I 70
D 95
D 70
D 40
D 60
Output
4










Image 2.1. The change in the tree immediately after operation Insert(60), resp. Insert(70), resp. Delete(40), resp. Delete(60) in Example 1 is depicted as transformation a), resp. b), resp. c), resp. d). Nodes of the original bare branch in each case are highlighted in gray.

Example 2

Input
2 15
I 10
I 5
I 20
I 15
I 40
I 30
I 70
I 60
I 80
I 90
I 50
D 30
D 15
D 80
D 90
Output
2





Image 2.2. The change in the tree immediately after operation Delete(90) in Example 2. Nodes of the original bare branches are highlighted in gray. This change is a special case of the general case depicted in Image 1.

Example 3

Input
3 13
I 11
I 99
I 22 
I 88
I 44
I 77
I 66
I 10
I 9
I 8
I 7
I 6
I 5
Output
2

Public data

The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout and stderr is available to him/her.
Link to public data set