Олимпиадный тренинг

Задача . D. Очередная задача про запросы в массиве

Задача

Вам дается массив a размера n и q запросов к нему. Есть запросы двух типов:

1 l_i r_i — осуществить циклический сдвиг отрезка [l_i, r_i] вправо. То есть, для каждого такого x, что l_i ≤ x < r_i, a_x + 1 становится равным прежнему значению a_x, а a_{l_i} становится равным прежнему значению a_{r_i};
2 l_i r_i — перевернуть отрезок [l_i, r_i].

Также заданы m важных позиций в массиве b₁, b₂, ..., b_m. Для каждого такого i, что 1 ≤ i ≤ m, выведите то число, которое будет стоять на позиции b_i в массиве после обработки всех запросов.

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

В первой строке записаны три целых числа n, q и m (1 ≤ n, q ≤ 2·10⁵, 1 ≤ m ≤ 100).

Во второй строке записаны n целых чисел a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10⁹).

Дальше идут q строк. В i-й из них записаны три целых числа t_i, l_i, r_i, где t_i — тип i-го запроса, [l_i, r_i] — отрезок, на котором запрос выполняется (1 ≤ t_i ≤ 2, 1 ≤ l_i ≤ r_i ≤ n).

В последней строке записаны m целых чисел b₁, b₂, ..., b_m (1 ≤ b_i ≤ n) — важные позиции в массиве.

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

Выведите m чисел, i-е из которых равно числу на позиции b_i после обработки всех запросов.

Примеры

№	Входные данные	Выходные данные
1	6 3 5 1 2 3 4 5 6 2 1 3 2 3 6 1 1 6 2 2 1 5 3	3 3 1 5 2

time 2000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам

	Кол-во
С++ Mingw-w64	5

Комментарий учителя

Ваш ответ

выберите язык и введите исходный код

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

Загруженные файлы

Нет