Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3668
Launching the Spacecraft

Time Limit: 2 Seconds      Memory Limit: 65536 KB

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 Li to Ri is larger than or equal to Ai (if not, the spacecraft won't launch) and less than or equal to Bi (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.

Input

The 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 Li,Ri, Ai, Bi (LiRi).

Output

The 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 Input

2 2
1 2 0 4
1 1 2 4

Sample Output

4 0

Author: LU, Yi
Contest: ZOJ Monthly, November 2012
Submit    Status