SP23930 OVERLAP - Overlapping Words

A large package of chocolate has arrived to the kindergarten. Each child has received one chocolate. To teach the children to share, the teachers have decided that each child will share her/his chocolate with others. The children are given a crossword puzzle filled by M x M characters. Each child has to find a word (any word) in the crossword. After each child found a word, the chocolates are shared as follows: each child will share her/his chocolate with the children whose words overlap with her/his word in at least one common field. Write a program that, for given positions of the words that the children have found in the crossword, for each child prints the number of children with whom she/he will share her/his chocolate. **Input** The first line contains an integer N (1 The second line contains an integer M (1 Each of the following N lines contains four integers R1, S1, R2, S2 from the interval \[1, M\]. They indicate that the word of the child is on the successive fields from (R1, S1) to (R2, S2), including these fields. These fields will always be in the same row or the same column. Moreover, (R1 = R2 and S1 < S2) or (S1 = S2 and R1 < R2) will hold. **Output** Print the required N numbers, where K-th number corresponds to the K-th child in the input.

N/A

N/A