## Directi Interview Question for Software Developers

- 0of 0 votes

AnswersYou are given a grid with 3 rows and N columns. Each cell in the grid contains the value 0 initially. You perform several operations of the following type on the grid

- evostorm96 November 15, 2017 in India

Pick a row, say r. Pick a start column and end column, say s and e. Of course 1 ≤ s ≤ e ≤ N. Now, set all values in the grid in row r, from column s to column e to 1.

After you perform all the operations, you wish to find subgrids in this grid (or rectangles, if you please) which contain only 1s. Most importantly, you wish to find the rectangle that has the largest area. Print the area of this rectangle.

Input

The first line of input contains a number T, the number of test cases. The first line of each test case contains the number N and M respectively, separated by a single space. N is the number of columns in the grid. M is the number of operations you perform on the grid. Each of the next M lines contain three integers R, C1 and C2 respectively to describe the operation. R is the row in which the operation is performed. C1 and C2 are the start and end columns respectively. You may assume that 1 ≤ C1 ≤ C2 ≤ N.| Report Duplicate | Flag | PURGE

Directi Software Developer

**Country:**India

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.