Mlađani Zi će uskoro da diplomira. Njegovi drugari su
odlučili da mu za poklon naprave beskonačnu veliku tortu. Nakon
što su tortu ispekli, nafilovali i ukrasili, drugari su odlučili
da tortu iseku u automatskom sekaču. Automatski sekač je
naprava koju su Zijevi drugari, elektroničari napravili tokom
studija. Sekač radi na sledećem principu: torta se ubaci u
sekač, zatim se unese željeni broj rezova n. Sekač će
zatim iseći tortu tačno n puta. Ukoliko posmatramo tortu kao
beskonačnu pravu, svaki rez predstavlja pravu u toj ravni.
Automatski sekač će odabrati položaj n rezova nasumično,
i nakon završenog sečenja će odštampati izveštaj o
položaju svakog od n rezova. Sekač je isprogramiran tako da se
nikad neće desiti da tri različita reza prolaze kroz istu
tačku na torti. U izveštaju sekača svaki rez je opisan dvema
tačkama u ravni torte kroz koje prolazi dati rez.
Nakon što su isekli tortu, Zijevi drugari su gledali sekačev izveštaj ne bi
li utvrdili na koliko parčića je torta isečena. Obično je mlađani Zi taj
koji bi pomogao drugarima u rešavanju sličnih problema. Pošto je torta
iznenađenje, drugari su odlučili da vas priupitaju za pomoć.
Pomozite Zijevim drugarima da, koristeći izveštaj sekača odrede na koliko
parčića je torta isečena.
Ulaz:
(Ulazni podaci se nalaze u datoteci torta.in) U prvom redu ulazne datoteke nalazi se prirodan
broj n (1 ≤ n ≤ 106), koji predstavlja broj
rezova koje je sekač napravio. U svakom od narednih n redova
nalaze se četiri cela broja x1, y1, x2, y2 razdvojenih
razmakom, koji predstavljaju koordinate dveju tačaka kroz koje
dati rez prolazi. Ukoliko tortu zamislimo kao beskonačnu ravan,
dati rez predstavlja pravu koja prolazi kroz tačke (x1, y1) i
(x2, y2). Svaka od koordinata je u opsegu od -10 do 109.
Nikoja tri reza neće prolaziti kroz istu tačku na torti.
Izlaz:
(Izlazne podatke upisati u datoteku torta.out) U prvi red izlazne datoteke treba upisati
prirodan broj k, koji predstavlja broj parčića na koje je
torta isečena po modulu 1.000.003.
Primer 1:
torta.in
|
|
torta.out
|
4
0 0 0 1
1 0 1 1
2 0 2 1
3 0 3 1
|
|
5
|
Primer 2:
torta.in
|
|
torta.out
|
3
0 0 1 2
1 2 2 0
0 0 2 0
|
|
7
|
Primer 3:
torta.in
|
|
torta.out
|
3
0 0 0 1
1 0 1 1
0 0 1 0
|
|
6
|