Андроид Андреид — известный на всю галактику детектив. Сейчас он не расследует никакое дело и от скуки ест шоколад.
Плитку шоколада можно представить в виде таблицы n × n, в которой каждая клетка символизирует одну дольку. В таблице столбцы пронумерованы от 1 до n слева направо, а строки — сверху вниз. Будем называть побочной диагональ, идущую из нижнего левого угла таблицы в верхний правый. Первым делом Андреид съедает все дольки, лежащие ниже побочной диагонали. Затем, с оставшейся треугольной частью он делает q следующих действий: сначала он выбирает дольку на побочной диагонали и либо направление "вверх", либо направление "влево", а затем начинает есть все дольки, начиная с выбранной клетки, двигаясь в выбранном направлении, пока он не дойдет до уже съеденной дольки или края шоколадки.
После каждого действия он хочет знать, сколько долек было им съедено в результате этого действия.
Выходные данные
Выведите q строк, на i-й из них должно быть количество съеденных долек в результате i-го действия.
Примечание
Иллюстрации к тестам из условия:
Дольки, съеденные в одном и том же действии закрашены одинаковым цветом. На дольках, лежащих на побочной диагонали, написаны номера действий, в результате которых эти дольки были съедены.
Во втором тесте из условия пятым действием Андреид пытается во второй раз начать есть шоколад, начиная с клетки на пересечении 10-го столбца и 1-й строки, но эта клетка уже пуста, поэтому он не съедает ничего.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6 5
3 4 U
6 1 L
2 5 L
1 6 U
4 3 U
|
4
3
2
1
2
|
|
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
|