Réchauffement climatique

Le réchauffement climatique est un sujet plutôt chaud en ce moment, un grand nombre de scientifiques tentent de modéliser l'évolution du climat pour les décennies à venir. L'un deux a élaboré une méthode qui, d'après lui, fournit un certain nombre de prévisions quant au climat futur en un point donné de la Terre. Chaque prévision est de la forme: "entre le jour X et le jour Y, la température à cet endroit atteindra un maximum de K degrés", où les paramètres X, Y et K prennent des valeurs entières.

Le scientifique est convaincu que ses prévisions sont extrêmement précises, tandis que vous n'êtes pas aussi sûr que lui. Vous voulez écrire un programme qui indique si, pour un point donné de la Terre, les prévisions du scientifique sont cohérentes. Par cohérent, on entend qu'il est possible de trouver une séquence de températures M₁, M₂, ... M_N, M_i étant la température maximale au jour i, pour lesquelles toutes les prévisions sont satisfaites. Une prévision (X, Y, K) est satisfaite si, entre le jour X et le jour Y (inclus), la température ne dépasse jamais K, et il existe au moins un jour dont la température maximale atteint exactement K.

• 1 <= T <= 5, où T est le nombre de points sur Terre où vous souhaitez tester la méthode du scientifique;
• 1 <= N <= 100 000, où N est le nombre de jours étudiés pour un emplacement;
• 1 <= P <= 50 000, où P est le nombre de prévisions faites pour un emplacement;
• 1 <= X <= Y <= N, où X et Y sont les jours impliqués dans la prévision (où 1 est le premier jour de la période d'étude et N le dernier);
• 1 <= K <= 100 000, où K est une température maximale prévue (mesurée en centièmes de degrés Kelvin).

De plus, dans 30% des cas, toutes les périodes d'étude satisferont P <= 100.

Votre programme doit lire sur l'entrée standard. La première ligne contiendra un unique entier T, le nombre de points où vous souhaitez tester la méthode du scientifique. Les lignes suivantes contiendront la description des T tests, l'un après l'autre.

Chaque description commence par une ligne contenant les deux entiers N et P, séparés par un espace. Les P lignes suivantes contiennent chacune une prévision. Chaque prévision est décrite par trois entiers X, Y et K, séparés par des espaces.

Votre programme doit écrire exactement T lignes sur la sortie standard. La i^ème de ces lignes doit contenir un unique entier, correspondant à la description du i^ème test. Pour chaque test, cet entier doit être '1' si les prévisions correspondantes sont cohérentes, ou '0' s'il est impossible de satisfaire toutes les contraintes à cet endroit.

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

1
0

Les données d'exemple contiennent deux descriptions de test. Le premier test cherche à vérifier trois prévisions sur une durée de cinq jours. Ces prévisions sont les suivantes:

• parmi les jours 1 et 2: au moins un jour aura une température maximale de 2, et aucun jour ne dépassera la température 2;
• parmi les jours 4 et 5: au moins un jour aura une température maximale de 1, et aucun jour ne dépassera la température 1;
• parmi les jours 2, 3 et 4: au moins un jour aura une température maximale de 3, et aucun jour ne dépassera la température 3.

La séquence de températures 1, 2, 3, 1, 1 satisfait ces prévisions. Par conséquent, cet ensemble de prévisions est cohérent.

Le second test cherche à vérifier quatre prévisions sur une durée de quatre jours. Ces prévisions sont les suivantes:

• le jour 3 doit avoir une température maximale de 4;
• le jour 4 doit avoir une température maximale de 3;
• parmi les jours 1, 2, 3 et 4: au moins un jour aura une température maximale de 2, et aucun jour ne dépassera la température 2;
• parmi les jours 1 et 2: au moins un jour aura une température maximale de 1, et aucun jour ne dépassera la température 1.

Clairement, la troisième prévision entre en conflit avec les deux premières, donc cet ensemble de prévisions n'est pas cohérent.

Calcul du score

Le score pour chaque test d'entrée sera de 100% si la bonne séquence de réponses est fournie sur la sortie standard, ou de 0% sinon.