A Simple Problem
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

Given an integer array A with length of N. Index starts from 1.
Given M queries, each query has an index interval as [L,R] and a value interval as [X,Y]. 
For every query, if the minimum value MIN of A[L...R] is no larger than Y and no less than X, the answer of this query is MIN, otherwise the answer is 0.
You need to construct an array to make the sum of the answers of all queries as large as possible.
Attention: The  elements in the array A shouldn't exceed 500000 or lower than 1.

输入描述:

First line contains two integers N, M
Each of the next 5 lines represents a query. Each lines have four integers L, R, X, Y. The meaning of L, R, X, Y is the same as mentioned above.

输出描述:

Print a single integer Z - the maximum possible sum of the answers of all queries.
After that print N integers A[1], A[2], ... , A[n], indicating the i-th number of the array A. If there are multiple solutions, please print any of them.
示例1

输入

复制 
5 5
1 3 5 7 
2 4 7 8
3 5 9 9 
1 4 4 5
2 5 3 10

输出

复制 
35
5 8 10 10 9

说明

The answer of first query is 7 because 7 is the minimum number in 7, 10, 10(A[1], A[2], A[3]) and 7 >= 5 && 7 <= 7.
The answer of 4-th query is 0 because the minimum number in 7, 10, 10, 8 is 7 but 7 > 5.