Сбившаяся лента на заводе

На заводе лента-конвейер возит коробки по кругу. У мастера есть пульт с тремя кнопками, и он нажимает их подряд, пытаясь «поймать» нужную коробку у входа.

Коробки стоят в ряд (слева направо — от входа к выходу). Команды действуют так:

• L — первую коробку переложить в конец ленты.
• R — последнюю коробку переложить в начало ленты.
• T — развернуть направление ленты: порядок коробок становится обратным.

Нужно узнать, в каком порядке окажутся коробки после всех нажатий.

Формат ввода

• В первой строке два целых числа n и q — число коробок и число нажатий.
• Во второй строке n целых чисел a1, a2, ..., an — номера коробок слева направо.
• В третьей строке строка s длины q, состоящая только из символов L, R, T — команды пульта по порядку.

Формат вывода Выведите n чисел — номера коробок слева направо после выполнения всех команд.

Ограничения

• 2 ≤ n ≤ 8000
• 1 ≤ q ≤ 8000
• -10^9 ≤ ai ≤ 10^9

Пример Ввод:

5 6
10 20 30 40 50
LTLRTR

Вывод:

10 20 30 40 50

Ключевое наблюдение: команда T не обязана реально переворачивать весь ряд (это O(n) каждый раз). Достаточно помнить, «смотрим» ли мы на ленту в обычном направлении или в перевёрнутом. Тогда команды L и R просто меняются местами: то, что было «первым», становится «последним», и наоборот.

Приём: двусторонняя очередь (deque) + флаг rev (перевёрнуто/нет). Deque умеет быстро (за O(1)) доставать и добавлять элементы с обоих концов, что идеально соответствует операциям.

План:

• Считай массив коробок в deque.
• Заведи rev = False.
• Иди по строке команд:
• Если T: сделай rev = not rev.
• Если L:
• при rev == False: «первую в конец» = x = popleft(); append(x)
• при rev == True: на самом деле это «последнюю в начало».
• Если R:
• при rev == False: «последнюю в начало»
• при rev == True: на самом деле это «первую в конец».
• В конце, если rev == True, выводи элементы в обратном порядке (можно пройтись reversed(deque)), не делая дорогих операций внутри цикла.

Сложность: O(n + q) по времени, память O(n).

Частая ошибка: при rev == True забыть, что L и R меняют смысл местами, и продолжать двигать «слева направо» как обычно.