#include <stdio.h>
#include <stdlib.h>
typedef struct {
int position;
int direction;
} ant_t;
template<typename V>
int bsearch(V *arr, int sz, int k) {
int min = 0;
int max = sz;
while (max > min) {
int mid = min + (max - min) / 2;
int cmp = key(arr[mid]) - k;
if (cmp < 0) {
min = mid + 1;
} else if (cmp > 0) {
max = mid;
} else {
return mid;
}
}
return min;
}
template<typename V>
void sortInsert(V *arr, int sz, V val) {
int i = bsearch<V>(arr, sz, key(val));
while (i <= sz) {
V tmp1 = arr[i];
arr[i] = val;
val = tmp1;
i++;
}
}
enum {
LEFT,
RIGHT
};
#define MAKE_STACK(name, sz, value_type) \
struct { size_t height; value_type *vals; } name; \
name.height = 0; \
name.vals = (value_type*) malloc(sizeof(value_type) * sz);
#define push_sorted(name, val) \
(sortInsert(name.vals, name.height, val), name.height++, (void)0)
#define push(name, val) \
(name.vals[name.height++] = (val))
#define pop(name) \
(name.vals[--name.height])
#define empty(name) \
(name.height == 0)
int key(ant_t value) {
return -value.position;
}
#define maximize(name, val) \
{ if ((val) > name) name = (val); }
int main(void) {
int i;
int L, A;
while(scanf(" %d %d", &L, &A) == 2) {
ant_t ant;
char c;
MAKE_STACK(ants, A, ant_t);
MAKE_STACK(ants2, A, ant_t);
for (i = 0; i < A; i++) {
scanf(" %d %c", &ant.position, &c);
ant.direction = (c == 'R') ? RIGHT : LEFT;
push_sorted(ants, ant);
push_sorted(ants2, ant);
}
int lefts = 0;
int rights = 0;
int max_right = -1;
int max_left = -1;
while (!empty(ants)) {
ant = pop(ants);
if (ant.direction == RIGHT) {
rights++;
int len = L - ant.position;
if (len > max_right) {
max_right = len;
}
} else {
lefts++;
if (ant.position > max_left) {
max_left = ant.position;
}
}
}
for (int i = 0; i < lefts - 1; i++) {
(void)pop(ants2);
}
ant_t last_left;
ant_t last_right;
last_left.position = -1;
last_right.position = -1;
if (lefts != 0) {
last_left = pop(ants2);
}
if (rights != 0) {
last_right = pop(ants2);
}
if (max_right == max_left) {
if (last_left.position > last_right.position) {
int tmp = last_left.position;
last_left.position = last_right.position;
last_right.position = tmp;
}
printf("The last ant will fall down in %d seconds - started at %d and %d.\n", max_right, last_left.position, last_right.position);
} else if (max_right > max_left) {
printf("The last ant will fall down in %d seconds - started at %d.\n", max_right, last_right.position);
} else {
printf("The last ant will fall down in %d seconds - started at %d.\n", max_left, last_left.position);
}
}
return 0;
}