Квантовый имитатор

Знаменитая компания по разработке аппаратного обеспечения «Zhaleza» после многолетних исследований разработала опытный образец квантового компьютера. Разработанная архитектура концептуально отличалась от используемой микропроцессорной архитектуры. Будущей областью применения своего изобретения компания видит обработку и хранение огромных объемов информации. Основным объектом манипулирования квантового компьютера является одномерный массив. На данный момент в процессоре квантового компьютера реализованы операции двух типов:

1. Инвертирование части массива, начиная с индекса L и заканчивая индексом R. Под инвертированием части массива понимается изменение прямого порядка следования элементов массива на обратный, начиная с индекса L и заканчивая индексом R, то есть элемент L меняется местами с элементом R, элемент L+1 с элементом R-1 и так далее. На псевдоязыке эту операцию можно записать следующим образом:

For i = 1 to [(R-L+1)/2] do Swap(A, L+i-1, R-i+1)

Обозначение [X] – это наибольшее целое число, не превосходящее X, где X –действительное число. Процедура Swap(A, i, j) может быть записана следующим образом:

Procedure Swap(A, i, j) 
Begin
  Tmp = A[i]
  A[i] = A[j]  
  A[j] = Tmp 
End

2. Вывод на экран суммы элементов массива, начиная с индекса L и заканчивая индексом R. На псевдоязыке процедура может быть реализована следующим образом:

Procedure PrintSum(A, L, R)
Begin
  Sum = 0
  For i = L to R do Sum = Sum + A[i]
  Print(Sum)    
End

Массив, с которыми работает квантовый компьютер, являются одномерным. Все элементы являются натуральными числами и нумеруются последовательно, начиная с единицы. Первоначально массив из N элементов заполнен числами от 1 до N, таким образом что A[1] = 1, A[2] = 2,…, A[N] = N.

Программой будем называть последовательность команд длины K, где каждая команда – это операция одного из двух типов. Ваша задача разработать имитатор работы квантового компьютера, позволяющий по заданной размерности массива N и заданной программе определить последовательность чисел выведенных квантовым компьютером на экран.

Входные данные

Первая строка входного файла INPUT.TXT содержит два целых числа N и K (1 ≤ N ≤ 10⁹, 1 ≤ K ≤ 5000). Каждая последующая строка описывает ровно одну операцию. Первый символ строки входного файла характеризует тип операции: 'I'(ASCII 73) – первый тип запроса, 'S'(ASCII 83) – второй тип запроса. Далее в строке через пробел следуют два числа, характеризующие соответствующие индексы L и R (1 ≤ L ≤ R ≤ N), разделенные одиночным пробелом.

Выходные данные

Выходной файл OUTPUT.TXT должен содержать последовательность чисел выведенных на экран квантовым компьютером. Каждое число выводится в отдельную строку. Гарантируется, что в программе присутствует операция второго типа.

Примеры

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]