Indigenous tribes of an island country located in the Pacific Ocean
between the 35th and 36th degrees of southern latitude are often at war
with each other. Recently, scientists have found that the natives describe
all internal conflicts in a special book.
Since the aborigines have no calendar, they remember a day by the number
of stars that can be seen in the sky in the evening. For each of the
conflicts, the aborigines write in the book three integers: the number of
stars in the sky that are seen on the first evening of the conflict x,
the number of stars in the sky that are seen on the last evening of the
conflict y, and the length d of the conflict in days including the
first and the last days.
The scientists know how many stars the native could seen in the sky each
of the last n evenings. Help the scientists to determine when the
natives could be at war with each other using this information and the
records in the book.
The first line contains the integer n (2 ≤ n ≤ 105).
The second line contains integers a1, …,
an separated with a space, where
ai is the number of stars the natives could see in the
sky i days ago (0 ≤ ai ≤ 2 · 108). In
the third line you are given the number m of internal conflicts
recorded in the book (1 ≤ m ≤ 105). The i-th of
the following m lines contains numbers xi,
yi, and di, which describe the
i-th internal conflict (0 ≤ xi,
yi ≤ 2 · 108; 2 ≤ di ≤ 50).
Output a line of length n consisting of zeros and ones. If the
aborigines could be at war i days ago, then there must be one in the
i-th position of the line.
6 5 4 3 2 1
2 4 3
4 5 2
1 6 5
Problem Author: Dmitry Ivankov
Problem Source: XII USU Open Personal Contest (March 19, 2011)