triunghiuri

Se consideră $N$ puncte din plan, având coordonate numere naturale, relativ la un reper cartezian XOY, oricare două puncte fiind distincte.

Figura 1 din enunțul original al problemei triunghiuri.Mărește schema ↗

Cerință

Cunoscând $N$ și coordonatele celor $N$ puncte, să se determine:

1. Numărul maxim de puncte care au aceeași abscisă.
2. Numărul triunghiurilor care se pot desena respectând următoarele condiții:
   • au toate vârfurile în puncte dintre cele date;
   • au o latură paralelă cu OX;
   • nu au laturi paralele cu OY;

Date de intrare

Datele de intrare se citesc din fișierul triunghiuri.in, care are următoarea structură:

Pe prima linie se află numărul $p$, care indică cerința ce trebuie rezolvată ($p$ are valoarea $1$ sau $2$);
Pe a doua linie se află numărul natural $N$, reprezentând numărul punctelor date;
Pe următoarele $N$ linii se găsesc câte două valori naturale $x \ y$, separate prin câte un spațiu, reprezentând coordonatele punctelor date.

Date de ieșire

Fișierul triunghiuri.out va avea următoarea structură:

Dacă $p = 1$ se va scrie în fișier, pe prima linie, numărul maxim de puncte care au aceeași abscisă (cerința $1$).
Dacă $p = 2$ se va scrie în fișier, pe prima linie, numărul triunghiurilor care se pot desena respectând condițiile date, modulo $1 \ 000 \ 003$, adică restul împărțirii numărului de triunghiuri la $1 \ 000 \ 003$ (cerința $2$).

Restricții și precizări

• $3 \leq N \leq 100 \ 000$;
• $0 \leq x, y \leq 1 000$;
• Se acordă $25$ de puncte pentru rezolvarea corectă a cerinței $1$ și $65$ de puncte pentru rezolvarea corectă a cerinței $2$.

Exemplul 1

triunghiuri.in

1
5
2 1
1 4
3 4
3 2
6 4

triunghiuri.out

2

Explicație

Se rezolvă cerința 1. Sunt maximum două puncte care au aceeași abscisă, ($3, 4$) și ($3, 2$)

Exemplul 2

triunghiuri.in

2
5
2 1
1 4
3 4
3 2
6 4

triunghiuri.out

4

Explicație

Se rezolvă cerința $2$. Se pot trasa $4$ triunghiuri care satisfac cerințele.
Dacă notăm cele $5$ puncte din fișier cu $A, B, C, D, E$ (ca în imagine),
atunci, cele $4$ triunghiuri care satisfac cerințele sunt: $ABC$, $ACE$, $ABE$ și $BDE$.