Problem: Global Warming

Want to try solving this problem? You can submit your code online if you log in or register.

Global Warming

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 M₁, M₂, ...M_N for which M_i 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.

Constraints

1 <= T <= 5, where T is the number of places on earth at which you plan to test the scientist's method;
1 <= N <= 100,000, where N is the number of days being studied for any one place;
1 <= P <= 50,000, where P is the number of predictions made for any one place;
1 <= X <= Y <= N, where X and Y are days involved in a prediction (where 1 is the first day of the study period and N is the last);
1 <= K <= 100,000, where K is a predicted maximum temperature (measured in hundredths of degrees Kelvin).

Furthermore, for 30% of the available marks, each study period will satisfy P <= 100.

Input

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.

Output

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.

Sample Input

Sample Output

1
0

Explanation

The sample data contains two test descriptions. The first test seeks to verify three predictions over a five day period. These predictions state that:

out of days 1 and 2, one of these days must have a maximum temperature of 2, and none of these days should exceed 2;
out of days 4 and 5, one of these days must have a maximum temperature of 1, and none of these days should exceed 1;
out of days 2, 3 and 4, one of these days must have a maximum temperature of 3, and none of these days should exceed 3.

One such possibility that satisfies these predictions is the sequence of temperatures 1, 2, 3, 1, 1. Thus this set of predictions can be satisfied.

The second test seeks to verify four predictions over a four day period. These predictions are:

day 3 must have a maximum temperature of 4;
day 4 must have a maximum temperature of 3;
out of days 1, 2, 3 and 4, one of these days must have a maximum temperature of 2, and none of these days should exceed 2;
out of days 1 and 2, one of these days must have a maximum temperature of 1, and none of these days should exceed 1.

Clearly, the third statement conflicts with the first and second, and so this set of predictions cannot be satisfied.

Scoring

The score for each input scenario will be 100% if the correct sequence of answers is output, or 0% otherwise.