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

Задача . E. Инопланетная ДНК


Задача

Темы: Деревья снм Структуры данных *2800

Профессор Байтоцы проводит опыты над инопланетными ДНК. Он обнаружил, что эта ДНК подвержена повторяющимся мутациям — каждая мутация проходит одинаково: некоторая непрерывная подпоследовательность инопланетной ДНК активируется, копируется, после чего копия подпоследовательности искажается и вставляется сразу после неискаженной подпоследовательности в ДНК. Искаженная копия активированной непрерывной подпоследовательности образуется следующим образом: сначала соединяются все элементы подпоследовательности на четных позициях, далее к ним присоединяются все элементы подпоследовательности на нечетных позициях. Таким образом, если активированная подпоследовательность состоит из 11 элементов и имеет вид s1s2... s11, то ее искаженная копия выглядит как s2s4s6s8s10s1s3s5s7s9s11.

Например, если исходная последовательность была «ACTGG», а мутация произошла на отрезке [2, 4] (то есть активирована подпоследовательность «CTG»), то мутировавшая ДНК выглядит так: «ACTGTCGG». Искаженная копия активированной подпоследовательности выделена жирным шрифтом.

Профессор Байтоцы записал исходную последовательность ДНК и затронувшую ее последовательность мутаций. Теперь он просит Вас восстановить первые k элементов последовательности ДНК после всех мутаций.

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

В первой строке входного файла содержится исходная последовательность ДНК, состоящая из не более чем 3·106 символов «A», «C», «T» и «G».

Во второй строке записано единственное целое число k (1 ≤ k ≤ 3·106).

В третьей строке записано единственное целое число n (0 ≤ n ≤ 5000) — количество мутаций. Следующие n строк описывают мутации в хронологическом порядке — каждая мутация описывается двумя целыми числами li и ri (1 ≤ li ≤ ri ≤ 109), что означает, что непрерывная подпоследовательность ДНК [li, ri] активировалась и скопировалась, при этом ее копия исказилась и присоединилась.

Гарантированно, что входные данные корректны, то есть, никакая мутация не происходит на несуществующей подпоследовательности ДНК, и что итоговая последовательность ДНК содержит не меньше k элементов.

Считается, что элементы последовательности ДНК нумеруются, начиная с 1, и что запись [l, r] обозначает непрерывную подпоследовательности последовательности ДНК, состоящую из r - l + 1 элементов, начинающуюся в l-ом элементе последовательности ДНК и заканчивающуюся в r-ом элементе последовательности ДНК.

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

Выведите единственную строку, которая содержит первые k букв из мутировавшей последовательности ДНК.

Примечание

Во втором примере после первой мутации последовательность превратилась в «ACCAGTACGT». После второй — в «ACCAGTACCGACATCGT».


Примеры
№Входные данныеВыходные данные
1 GAGA
4
0 
GAGA
2 ACGTACGT
16
2
1 2
2 8 
ACCAGTACCGACATCG

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

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w645
Комментарий учителя

Ваш ответ

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


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

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