just now

Anil • 0

Hyderabad

Problem Statement: Paint Ball

Amrita has placed N white drawing sheets (represented as rectangles) on a table in her garden. Some sheets lay on top of others, but none of the sheet borders intersect (meaning they are either completely disjoint or strictly nested).

Her brother fires M paintballs of various colors at the sheets. Due to the force of the gun, once a paintball hits a sheet, the color spreads to all of the sheets beneath it.

Given the coordinates of the sheets and the paintballs, write a program to output N lines, where the i^{th} line contains the number of unique colors spread on the i^{th} sheet.

Input Format:

• The first line contains N (number of sheets) and M (number of paintballs).
• The next N lines contain four integers: P_i, Q_i (lower-left corner) and R_i, S_i (upper-right corner) of the ith sheet.
• The next M lines contain three integers: X_j, Y_j (landing coordinates) and K_j (color label) of the jth paintball.

Example Summary:

If a sheet is placed from (1, 1) to (4, 5) and a paintball of color 1 hits at (3, 2), the sheet receives color 1. If another sheet is placed underneath it, the color spreads to that nested parent sheet as well.