ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1827. Войны туземцев

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Туземные племена островного государства, расположенного в Тихом океане между 35 и 36 градусами южной широты, часто воюют друг с другом. Недавно учёные узнали, что туземцы описывают все междоусобные конфликты в специальной книге, и даже смогли эту книгу прочитать.
К сожалению, у туземцев нет календаря, поэтому они запоминают сутки по количеству звёзд, которые были видны на небе ночью. Для каждой прошедшей междоусобицы туземцы записывали в книге три числа: x — количество звёзд на небе в первые сутки конфликта, y — количество звёзд на небе в последние сутки конфликта и d — продолжительность конфликта в сутках, включая первые и последние сутки.
Учёные смогли вычислить, сколько звёзд было видно туземцам на небе в каждые из n последних суток. Помогите им определить по этой информации, когда туземцы могли воевать друг с другом.

Исходные данные

В первой строке записано целое число n (2 ≤ n ≤ 105). Во второй строке через пробел записаны целые числа a1, …, an, где ai — количество звёзд, которые туземцы видели на небе i суток назад (0 ≤ ai ≤ 2 · 108). В третьей строке записано целое число m — количество описанных в книге междоусобиц (1 ≤ m ≤ 105). В i-й из следующих m строк записаны целые числа xi, yi и di — описание i-й междоусобицы (0 ≤ xi, yi ≤ 2 · 108; 2 ≤ di ≤ 50).

Результат

Выведите строку длины n, состоящую из нулей и единиц. На i-й позиции должна стоять единица, если i суток назад туземцы могли воевать.

Пример

исходные данныерезультат
6
6 5 4 3 2 1
3
2 4 3
4 5 2
1 6 5
011110
Автор задачи: Дмитрий Иванков
Источник задачи: XII открытое личное первенство УрГУ (19 марта 2011)