Time Limit: 1 seconds
Memory Limit: 16 Mb
Global warming is a rather hot topic these days, leading several scientists to try to model the behaviour of the climate for the coming decades. One of these scientists has devised a method which he claims can tell you, for a given point on earth, a number of predictions about the future climate at this location. Each prediction is of the form: "between day X and day Y, the temperature at this place will reach a maximum value of K degrees", where X, Y and K are parameters with integer values.
The scientist seems convinced that these predictions are absolutely accurate, while you are a little doubtful about this point. You wish to write a program to find out, given a place on earth, whether the set of predictions made by the scientist is coherent. By coherent, we mean it is possible to find an actual sequence of temperatures M1, M2, ...MN for which Mi is the maximal temperature on day i, and where all of the predictions are satisfied. A prediction (X, Y, K) is satisfied if, between day X and day Y (inclusive), the temperature never rises above K and there exists at least one day in that period where the temperature is exactly K.
Your program must read from standard input. The first line will contain the single integer T, the number of places at which you wish to test the scientist's method. Following this will be a description of each of the T tests, one after another.
Each description will begin with a single line containing the two integers N P separated by a single space. Following this will be P lines each containing a single prediction. Each prediction will be described by three integers X Y K separated by spaces.
Your program must write precisely T lines to standard output. The ith of these lines must contain a single integer, corresponding to the ith test description. For each test, this integer should be `1' if the corresponding predictions are coherent, or `0' if it is not possible to satisfy all of the predictions at this place.
2 5 3 1 2 2 4 5 1 2 4 3 4 4 3 3 4 4 4 3 1 4 2 1 2 1
The sample data contains two test descriptions. The first test seeks to verify three predictions over a five day period. These predictions state that:
The second test seeks to verify four predictions over a four day period. These predictions are:
The score for each input scenario will be 100% if the correct sequence of answers is output, or 0% otherwise.