Gnawed Books#1760
Northern European University is renowned for its library. However, in an act of envy, another famous university has unleashed bookworms into NEU. Now, the chief librarian, Alex, urgently needs to determine the extent of the damage.
All books in the library are placed on a single, very long shelf. By looking at the spine, Alex can determine a book's number without touching it. The books are numbered from left to right, starting with one. None of the books are upside down.
Alex has discovered worms in the library. He has determined where each worm started and where it finished its path. Each worm moves in a straight line, either from left to right or from right to left. To calculate the damage correctly, Alex wants to write a program that computes how many pages have been gnawed by exactly worms. Help him with this task.
The first line of the input file contains two integers and (1 \leq N \leq 10000, 1 \leq M \leq 100000) separated by a space. The second line contains positive integers p_i, where p_i is the number of pages in the -th book (p_i \leq 10000). The following lines describe the paths of the worms. Each path description consists of four positive integers: the book and page number where the worm's path starts, and the book and page number where it finishes.
The output file should contain (M+1) lines. On the -th line, output the number of pages that have been gnawed by exactly (k-1) worms.
Example 1