Contest problemset description

Jasio dostał na urodziny nowy zestaw klocków. Na każdym z nich napisany jest pewien ciąg nawiasów otwierających ( lub zamykających ). Jasio zastanawia się, czy jest w stanie ułożyć wszystkie klocki w pewnej kolejności obok siebie w taki sposób, żeby powstały ciąg nawiasów był poprawny?

Poprawny ciąg nawiasowań to taki, który można uzyskać nawiasując jakieś działanie matematyczne. Przykładowo, ciąg (())() jest poprawnym nawiasowaniem, natomiast ((), ) lub )( nie są poprawnymi nawiasowaniami.

Formalnie, napis S składający się z nawiasów ( oraz ) jest poprawnym nawiasowaniem, gdy

• S jest pusty,
• S jest postaci (A), gdzie A jest poprawnym nawiasowaniem,
• S jest postaci AB, gdzie A oraz B są poprawnymi nawiasowaniami.

Wejście

W pierwszym wierszu wejścia znajduje się jednak liczba naturalna N oznaczająca liczbę klocków z zestawu Jasia. W następnych N wierszach znajduje się opis napisów na każdym z klocku, i-ty wiersz zawiera ciąg nawiasów S_i.

Wyjście

W pierwszym i jedynym wierszu wyjścia należy wypisać jedno słowo, TAK, jeżeli klocki da się poukładać tak, żeby utworzyły poprawne nawiasowanie, lub NIE w przeciwnym wypadku.

Ograniczenia

1 ≤ N ≤ 1 000 000, suma długości S_i nie przekracza 1 000 000.

Podzadania

Przykład

2
)
(()

TAK

2
)()
)((

NIE

Jasio uwielbia prostokąty. Ostatnio na urodziny dostał od mamy zestaw prostokątów, które…

A z resztą, pal licho historyjkę! To zadanie jest tak trudne, że i tak nie uda Ci się go rozwiązać, więc od razu przejdźmy do sedna. Dane jest N zaznaczonych punktów na płaszczyźnie o współrzędnych całkowitoliczbowych. Możesz wykonać następującą operację: wybierz cztery liczby całkowite x₁, y₁, x₂ oraz y₂ takie, że dokładnie trzy spośród czterech punktów (x₁,y₁), (x₁,y₂), (x₂,y₁), (x₂,y₂) są zaznaczone i zaznacz również czwarty punkt.

Twoim zadaniem jest odpowiedzieć na pytanie, ile maksymalnie razy można wykonać tę operację?

Wejście

W pierwszym wierszu wejścia dana jest jedna liczba całkowita N oznaczająca liczbę zaznaczonych punktów na płaszczyźnie. W następnych N wierszach następuje opis kolejnych punktów, każdy z nich składa się z dwóch nieujemnych liczb całkowitych x oraz y, oznaczających, że punkt (x,y) jest zaznaczony.

Wyjście

Należy wypisać jedną liczbę: maksymalną liczbę operacji, jaką da się wykonać.

Ograniczenia

We wszystkich testach zachodzą warunki 1 ≤ N ≤ 1 000 000, 1 ≤ x, y ≤ 10⁹.

Przykład

3
1 1
1 2
2 2

1

2
1 1
2 2

0

6
1 1
10 8
4 1
1 3
10 3
4 8

3

Największy fizyk Bitocji, Bajtocjusz Maksimus, dokonał przełomowego odkrycia dwóch, wcześniej nieznanych cząsteczek: zerum i jedynkum. Cząsteczki zachowują się w zaskakujący sposób: jeżeli zerum znajduje się blisko jedynkum, to Bitocjusz może poruszyć te cząsteczki tak, aby zbliżyły się do siebie i anihilowały (innymi słowy, przestają istnieć i zupełnie znikają), pozostawiając po sobie dziurę, ściągającą pozostałe cząsteczki. Przykładowo, jeżeli Bajtocjusz ustawi obok siebie cząsteczki zerum i jedynkum w następujący sposób 0010011 (gdzie 0 reprezentuje cząsteczkę zerum, a 1 cząsteczkę jedynkum) oraz poruszy drugą i trzecią cząsteczkę, to te anihilują się i ciąg cząsteczek zmieni się w 00011. Bitocjusz mógłby teraz powtórzyć tę procedurę, aż żadne dwie cząsteczki zerum i jedynkum nie będą znajdowały się obok siebie.

Bitocjusz jest bardzo zajętym fizykiem, dlatego poprosił Cię o pomoc. Fizyk ustawił w ciąg kolejne cząsteczki i zastanawia się, ile maksymalnie razy może poruszyć pewną parę sąsiadujących zerum i jedynkum? Pomóż mu i napisz program, który rozstrzyga ten problem.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba naturalna N oznaczająca liczbę cząsteczek. W następnym wierszu znajduje się ciąg N znaków 0 lub 1, reprezentujących ciąg cząsteczek ustawiony przez Bitocjusza.

Wyjście

W jednym wierszu wyjścia należy wypisać jedną liczbę całkowitą, oznaczającą maksymalną liczbę razy, jaką Bitocjusz może dokonać anihilacji pewnych dwóch sąsiadujących cząsteczek.

Ograniczenia

1 ≤ N ≤ 1 000 000.

Podzadania

Przykład

5
01100

2

2
00

0