Туземные племена островного государства, расположенного в Тихом океане между 35 и 36 градусами южной широты, часто воюют друг с другом. Недавно учёные узнали, что туземцы описывают все междоусобные конфликты в специальной книге, и даже смогли эту книгу прочитать.

К сожалению, у туземцев нет календаря, поэтому они запоминают сутки по количеству звёзд, которые были видны на небе ночью. Для каждой прошедшей междоусобицы туземцы записывали в книге три числа: x — количество звёзд на небе в первые сутки конфликта, y — количество звёзд на небе в последние сутки конфликта и d — продолжительность конфликта в сутках, включая первые и последние сутки.

Учёные смогли вычислить, сколько звёзд было видно туземцам на небе в каждые из n последних суток. Помогите им определить по этой информации, когда туземцы могли воевать друг с другом.

В первой строке записано целое число n (2 ≤ n ≤ 10⁵). Во второй строке через пробел записаны целые числа a₁, …, a_n, где a_i — количество звёзд, которые туземцы видели на небе i суток назад (0 ≤ a_i ≤ 2 · 10⁸). В третьей строке записано целое число m — количество описанных в книге междоусобиц (1 ≤ m ≤ 10⁵). В i-й из следующих m строк записаны целые числа x_i, y_i и d_i — описание i-й междоусобицы (0 ≤ x_i, y_i ≤ 2 · 10⁸; 2 ≤ d_i ≤ 50).

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