0185. Первороты

Input file name:	input.txt
Output file name:	output.txt
Time limit:	250 ms
Memory limit:	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.txt	output.txt
5 01010 1 1 3	10110

Source: Petrozavodsk Winter 2003. SaratovSU #3 Training Contest, Wednesday, February 05

Discuss       Submit a solution