0185. Первороты

Имя входного файла: input.txt
Имя выходного файла: output.txt
Ограничение по времени: 250 ms
Ограничение по памяти: 16 megabytes

На столе расположено в ряд N (1 ≤ N ≤ 30000) монет. Монеты могут лежать вверх как орлом, так и решкой. Некто выбирает какой-то отрезок из подряд идущих монет и переворачивает все монеты в отрезке. Так он делает K (1 ≤ K ≤ 30000) раз. Найдите финальное расположение монет.

Формат входного файла

В первой строке входного файла записано натуральное число N. Вторая строка содержит строку из N символов - начальное расположение монет. Символ "1" указывает на то, что соответствующая монета лежит вверх орлом, если монета лежит вверх решкой, в строке записан символ "0". В третьей строке записано натуральное число K - количество совершенных переворотов. Далее следует K строк, содержащих описания переворотов. Переворот описывается парой целых чисел A, B (1 ≤ A ≤ B ≤ N), где A - левая граница переворота, а B - правая. Монеты нумеруются слева направо, границы в отрезок включаются.

Формат выходного файла

Выведите N символов "1" или "0", где символ "1" указывает на то, что соответствующая монета лежит вверх орлом, в противном случае выводите "0".

Пример:

input.txtoutput.txt
5 01010 1 1 3 10110


Источник: Petrozavodsk Winter 2003. SaratovSU #3 Training Contest, Wednesday, February 05

Обсудить       Отправить решение



Версия для печати