Wstęp do programowania w C++

Czerwone mrówki

Przyrodnik Jasiu postanowił zbadać wścieklice, mrówki popularnie nazywane czerwonymi. W tym celu udał się do pobliskiego lasu, aby je poobserwować. Zdziwił się trochę, gdy zauważył, że kolonia czerwonych mrówek wymieszała się z kolonią rudnic. Postanowił zrobić trochę zdjęć. Po powrocie do domu zabrał się do analizowania zrobionych przez siebie zdjęć. Naszego przyrodnika interesuje, jaka jest liczebność wszystkich mrówek w najmniejszym prostokątnym obszarze, do którego należą wszystkie mrówki czerwone. Boki takiego prostokątnego obszaru muszą być równoległe do osi układu współrzędnych. Każda mrówka na zdjęciu opisana została za pomocą współrzędnych kartezjańskich oraz wartości 1 albo 0, gdzie 1 oznacza mrówkę czerwoną, a 0 oznacza mrówkę czarną. Teraz wystarczy już tylko napisać program, aby zaoszczędzić naszemu przyrodnikowi trochę czasu.

Wejście
W pierwszym wierszu wejścia znajduje się liczba całkowita d (1 ≤ d ≤ 100) oznaczająca liczbę zestawów danych - zdjęć. W pierwszym wierszu każdego zestawu znajduje się liczba całkowita n (2 ≤ n ≤ 10⁵) oznaczająca liczebność mrówek na zdjęciu. W kolejnych n wierszach podane są po trzy liczby całkowite x, y, k (0 ≤ x, y ≤ 10³, k={0,1}), gdzie wartości x, y oznaczają współrzędne kartezjańskie mrówki, a k to jej kolor. Dla k = 1 mrówka jest czerwona, dla k = 0 mrówka jest czarna. Można założyć, że żadna mrówka nie łazi po innej mrówce oraz, że rozmiar plików wejściowych nie przekracza 4 MB.

Wyjście
Dla każdego zestawu należy wypisać w osobnym wierszu jedną liczbę - liczebność wszystkich mrówek zawierających się w najmniejszym prostokątnym obszarze, do którego należą wszystkie mrówki czerwone.


Przykład

Wejście
1
9
6 3 1
1 2 0
7 2 0
5 1 1
2 5 0
4 4 0
1 4 1
3 3 0
5 7 0

Wyjście
6

Rysunek do przykładu
Mrówki czerwone jak i brzeg prostokątnego obszaru został oznaczony kolorem czerwonym. W prostokącie tym znajduje się łącznie sześć mrówek.