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 ≤ 10⁵). The second line contains integers a₁, …, a_n separated with a space, where a_i is the number of stars the natives could see in the sky i days ago (0 ≤ a_i ≤ 2 · 10⁸). In the third line you are given the number m of internal conflicts recorded in the book (1 ≤ m ≤ 10⁵). The i-th of the following m lines contains numbers x_i, y_i, and d_i, which describe the i-th internal conflict (0 ≤ x_i, y_i ≤ 2 · 10⁸; 2 ≤ d_i ≤ 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.