Distributed Queue Visibility

A distributed queue consists of \(N\) nodes numbered from \(0\) to \(N-1\), where node \(0\) is the primary node and the remaining nodes are secondary nodes. Both the primary and each secondary maintain a queue (conceptually, an infinitely long array with indices \(0,1,2,\dots\)). When an element is enqueued, the primary node appends it to its queue. Secondary nodes synchronize their queues from the primary, preserving the insertion order.

However, because synchronization speeds vary, data consistency is ensured only when an enqueued element has been synchronized to every secondary node. In other words, an element is visible if and only if it has been propagated from the primary to all secondary nodes. In the case where \(N=1\) (i.e. there are no secondary nodes), every enqueued element is deemed visible.

You are given the current state of the distributed queue by processing a sequence of operations. Your task is to determine how many elements are visible after all operations have been executed.

The two types of operations are:

• E: Enqueue an element to the primary node.
• S k: The secondary node with index \(k\) synchronizes the next pending element from the primary (if available).

For instance, suppose the primary has enqueued \(x\) elements and a particular secondary has synchronized \(y\) elements; then this secondary’s queue reflects the first \(y\) elements from the primary. An element is visible only if every secondary has synchronized it, i.e. if \(y \geq \text{index}+1\) for every secondary.

Your program should output the count of visible elements after processing all the operations.

inputFormat

The first line contains two integers (N) and (Q), where (N) ((\ge 1)) is the total number of nodes in the distributed queue (node (0) is the primary and nodes (1) to (N-1) are secondaries), and (Q) is the number of operations.

Each of the following (Q) lines contains an operation in one of the following forms:

• "E" — indicating that an element is enqueued at the primary node. • "S k" — indicating that the secondary node with index (k) synchronizes the next pending element from the primary (if there is any element that has not yet been synchronized by this secondary).

It is guaranteed that any (k) provided in a synchronization operation satisfies (1 \le k \le N-1).

outputFormat

Output a single integer representing the number of visible elements in the distributed queue after processing all Q operations. An element is considered visible if it has been synchronized to every secondary node. (For (N=1), output the total number of enqueued elements.)

sample

3 6
E
E
S 1
S 2
S 1
S 2

2