
ZOJ Problem Set  3668
After the escape from the jaws of death, you find an abandoned spacecraft which can help you escape from the dangerous planet. Unfortunately, launching the spacecraft need to give energy to the N(0 < N ≤ 1000) stored stones. The N stored stones is number from 1 to N. According to reading the manual, you known that there have M(M ≤ 10000) requirements. The ith requirement is the total energy from L_{i} to R_{i} is larger than or equal to A_{i} (if not, the spacecraft won't launch) and less than or equal to B_{i} (if not, the spacecraft will be broken). It is time for you to calculate plan to give energy to the N(0 < N ≤ 1000) stored stones. The energy to each stone must be a integer between 10000 and 10000. InputThe input consist of multiple cases. For each test case, the first line contains two integers N, M which indicates the number of the stored stones and the number of the requirements. Then followed by M lines, each line contains four integers L_{i},R_{i}, A_{i}, B_{i} (L_{i} ≤ R_{i}). OutputThe output contains one line per case. It contains N integers to show the plan if the plan is exist (If there are more than one plans, output the one has the largest energy. If there are still more than one plans, output the lexicographical largest one.). If there is no plan, please output "The spacecraft is broken!". Sample Input2 2 1 2 0 4 1 1 2 4 Sample Output4 0 Author: LU, Yi Contest: ZOJ Monthly, November 2012 