Gnawed Books
A Thousand Worms!______________
from the dialogue of preference players
Saint Petersburg State University is renowned for its library. However, in an act of envy, another university has unleashed bookworms into SPSU. Now, the chief librarian, Vasya, urgently needs to assess the damage.
The library's N books are arranged on a single, very long shelf. By examining the spine, Vasya can identify each book's number without needing to touch it. The books are numbered sequentially from left to right, starting at one, and none are upside down.
Vasya has found M worms in the library. He has identified the starting and ending points of each worm's path. Each worm travels in a straight line, either from left to right or from right to left. To precisely evaluate the damage, Vasya wants to develop a program that calculates how many pages have been gnawed by exactly k worms. Your task is to assist him in this endeavor.
Input
The first line of the input file contains two numbers, N and M (1 ≤ N ≤ 10000, 1 ≤ M ≤ 100000), separated by a space. The second line lists N positive integers p_i, representing the number of pages in the i-th book (p_i ≤ 10000). The following M lines describe the paths of the worms. Each path description consists of four positive integers: the book number and page number where the worm's path begins, and the book number and page number where it ends.
Output
The output file should contain (M+1) lines. On the k-th line, output the number of pages that have been gnawed by exactly (k-1) worms.