| Codeforces Round 310 (Div. 1) |
|---|
| Закончено |
Андроид Андреид — известный на всю галактику детектив. Сейчас он не расследует никакое дело и от скуки ест шоколад.
Плитку шоколада можно представить в виде таблицы n × n, в которой каждая клетка символизирует одну дольку. В таблице столбцы пронумерованы от 1 до n слева направо, а строки — сверху вниз. Будем называть побочной диагональ, идущую из нижнего левого угла таблицы в верхний правый. Первым делом Андреид съедает все дольки, лежащие ниже побочной диагонали. Затем, с оставшейся треугольной частью он делает q следующих действий: сначала он выбирает дольку на побочной диагонали и либо направление "вверх", либо направление "влево", а затем начинает есть все дольки, начиная с выбранной клетки, двигаясь в выбранном направлении, пока он не дойдет до уже съеденной дольки или края шоколадки.
После каждого действия он хочет знать, сколько долек было им съедено в результате этого действия.
В первой строке заданы целые числа n (1 ≤ n ≤ 109) и q (1 ≤ q ≤ 2·105) — размер таблицы и количество действий.
В следующих q строках даны описания действий: в i-й из них идут числа xi и yi (1 ≤ xi, yi ≤ n, xi + yi = n + 1) — номера столбца и строки выбранной клетки, а также символ, означающий направление (L — влево, U — вверх).
Выведите q строк, на i-й из них должно быть количество съеденных долек в результате i-го действия.
6 5
3 4 U
6 1 L
2 5 L
1 6 U
4 3 U
4
3
2
1
2
10 6
2 9 U
10 1 U
1 10 U
8 3 L
10 1 L
6 5 U
9
1
10
6
0
2
Иллюстрации к тестам из условия:
Дольки, съеденные в одном и том же действии закрашены одинаковым цветом. На дольках, лежащих на побочной диагонали, написаны номера действий, в результате которых эти дольки были съедены.
Во втором тесте из условия пятым действием Андреид пытается во второй раз начать есть шоколад, начиная с клетки на пересечении 10-го столбца и 1-й строки, но эта клетка уже пуста, поэтому он не съедает ничего.
