ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

USU Open Personal Contest 2011

About     Problems     Submit solution     Judge status     Standings
Contest is over

H. Indigenous Wars

Time limit: 1.0 second
Memory limit: 64 MB
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)
To submit the solution for this problem go to the Problem set: 1827. Indigenous Wars