Uolevin sukuyritys myy omenoita torilla, mutta viime vuosina liiketoiminta on ollut raskaasti tappiollista. Niinpä Uolevi tilasi kaveriltaan Jarkalta tutkimuksen siitä, miten omenan kilohinta vaikuttaa liikevoittoon.

Jarkan työn tuloksena syntyi taulukko $v_0,v_1,\ldots,v_{n-1}$, missä $v_k$ tarkoittaa liikevoittoa, kun omenan kilohinta on $k$. Taulukosta selviää, että tiettyyn rajaan asti kilohinnan kasvattaminen lisää liikevoittoa, mutta tämän jälkeen se vähentää liikevoittoa.

Jarkka suhtautuu kuitenkin vakavasti tietoturvaan ja toimitti taulukon kryptattuna. Jokaista taulukon arvoa $v_k$ vastaa neljä arvoa $a_k$, $b_k$, $c_k$ ja $d_k$. Näistä pystyy laskemaan arvon $v_k$ käyttämällä seuraavaa algoritmia:

[switch]

int decrypt(uint32_t a, uint32_t b, uint32_t c, uint32_t d) {
	for(int i = 0; i < 10000; ++i) {
		c *= a; d ^= a; c *= b; a ^= c; d += b; a += c;
		b -= a; b *= c; c ^= d; c *= d; d ^= a; c += b;
		a ^= c; d -= b; c += b; b *= a; d -= a; c -= d;
		a += c; c ^= b; b *= a; a ^= d; c -= d; d -= a;
		c -= a; d -= b; c += d; b -= c; c += b; c += d;
		b *= c; b -= d; b *= a; b ^= c; d -= b; d -= a;
	}
	
	a %= 1000000u;
	return (int)a - 500000;
}

private static int decrypt(int a, int b, int c, int d) {
	for(int i = 0; i < 10000; ++i) {
		c *= a; d ^= a; c *= b; a ^= c; d += b; a += c;
		b -= a; b *= c; c ^= d; c *= d; d ^= a; c += b;
		a ^= c; d -= b; c += b; b *= a; d -= a; c -= d;
		a += c; c ^= b; b *= a; a ^= d; c -= d; d -= a;
		c -= a; d -= b; c += d; b -= c; c += b; c += d;
		b *= c; b -= d; b *= a; b ^= c; d -= b; d -= a;
	}
	
	while(a < 0) a -= 1000000000;
	a %= 1000000;
	return a - 500000;
}

[/switch]

Ongelmana on kuitenkin, että algoritmin silmukassa on 10000 kierrosta ja arvojen purkaminen on hidasta. Voisitko auttaa Uolevia etsimään aineistosta tehokkaasti kilohinnan, joka tuottaa suurimman liikevoiton?

Syöte

Syötteen ensimmäisellä rivillä on luku $n$, taulukon $v$ koko.

Seuraavaksi syötteessä on jokaiselle $k = 0, 1, \ldots, n-1$ yksi rivi, jossa on välein eroteltuna luvut $a_k$, $b_k$, $c_k$ ja $d_k$.

Tuloste

Ohjelman tulee tulostaa yksi rivi, jolla on kilohinta $h$ siten, että $v_h$ on suurin mahdollinen.

Rajat

• $2 \leq n \leq 10^5$
• $0 \leq a_k, b_k, c_k, d_k < 10^6$
• $-5\cdot 10^5 \leq v_k < 5 \cdot 10^5$
• $v_0 < \ldots < v_{h - 1} < v_h > v_{h + 1} > \ldots > v_{n-1}$

Esimerkki

Syöte:

4
879479 618085 843425 972716
232376 383233 639282 763757
252843 370229 101963 278328
8702 979114 391694 473238

Tuloste:

2

Syötteessä taulukko $v$ on [-90601, 149544, 241747, 237726], ja maksimi löytyy kohdasta 2 (241747).

[rem]
Eräänä kauniina aamuna Uolevi heräsi siihen tosiasiaan, että hänen uransa vapaana tutkijana ei kerrytä hänelle kovinkaan kummoista eläkettä. Siksi Uolevi päätti alkaa yrittäjäksi, liikeideanaan myydä torilla omenoita. Kuitenkin liiketoiminta on tähän mennessä ollut raskaasti tappiollista. Uolevi epäilee syyksi väärää hinnoittelua. Siksi hän tilaa Annalta laajan markkinatutkimuksen, jonka tarkoituksena on selvittää paras mahdollinen hinnoittelu.

Tutkimuksen tuloksena Anna tuottaa taulukon $V_0, V_1, \ldots, V_{n - 1}$, missä $V_i$ on Uolevin arvioitu liikevoitto mikäli omenan kilohinnaksi asetetaan $i$. Sopimuksen mukaisesti Anna toimittaa taulukon Uoleville ennen deadlinea. Anna on kuitenkin salannut taulukon hyvien tietoturvanormien mukaisesti itse keksimällään salausalgoritmilla, ja toimittaa Uoleville purkuohjelman vasta, kun maksu on suoritettu.

Tappiollisen liiketoiminnan seurauksena Uolevin käteiskassa on kuitenkin melkein tyhjä, ja luottotiedotkaan eivät ole enää kunnossa. Kunnian miehenä Uolevi aikoo tietysti maksaa Annalle tehdystä työstä, mutta se on mahdollista vasta kun Uolevi saa liiketoimintansa taas voitolliseksi. Ainoaksi vaihtoehdoksi jää siis Annan salauksen murtaminen.

Annan salauksessa luku $V_i$ esitetään neljänä lukuna $A_i, B_i, C_i, D_i$. Monen yön uurastuksen jälkeen Uolevi on onnistunut keksimään seuraavan C++-funktion, joka osaa selvittää luvun $V_i$ luvuista $A_i, B_i, C_i, D_i$:

int decrypt(uint32_t a, uint32_t b, uint32_t c, uint32_t d) {
	for(int i = 0; i < 10000; ++i) {
		c *= a; d ^= a; c *= b; a ^= c; d += b; a += c;
		b -= a; b *= c; c ^= d; c *= d; d ^= a; c += b;
		a ^= c; d -= b; c += b; b *= a; d -= a; c -= d;
		a += c; c ^= b; b *= a; a ^= d; c -= d; d -= a;
		c -= a; d -= b; c += d; b -= c; c += b; c += d;
		b *= c; b -= d; b *= a; b ^= c; d -= b; d -= a;
	}
	
	a %= 1000000u;
	return (int)a - 500000;
}

Kuitenkin tällä funktiolla koko taulukon $V$ lukujen selvittämiseen menisi Uolevin tietokoneella kauemmin kuin mitä Uolevilla on aikaa. Uolevilla ei myöskään ole rahaa uuteen tietokoneeseen. Uolevi tahtoo tietää vain hinnan $h$ jolla $V_h$ on suurin mahdollinen. Uolevi muistaa Annan loppuraportista, että taulukon $V$ arvot ensin kasvavat ja sitten laskevat.

Syöte

Syötteen ensimmäisellä rivillä on luku $n$, taulukon $V$ pituus. Seuraavaksi syötteessä on jokaiselle $i = 0, 1, \ldots, n - 1$ yksi rivi, jossa on välein eroteltuna luvut $A_i$, $B_i$, $C_i$ ja $D_i$.

Tuloste

Ohjelman tulee tulostaa yksi rivi, jolla on luku $h$ siten, että $V_h$ on suurin mahdollinen.

Rajat

$2 \leq n \leq 10^5$
$0 \leq A_i, B_i, C_i, D_i < 10^6$
$-5\cdot 10^5 \leq V_i < 5\cdot 10^5$
$V_0 < V_1 < \ldots < V_{h - 1} < V_h > V_{h + 1} > \ldots > V_{n - 2} > V_{n - 1}$

Esimerkki

Syöte:

4
879479 618085 843425 972716
232376 383233 639282 763757
252843 370229 101963 278328
8702 979114 391694 473238

Tuloste:

2

Syötteessä taulukko V on [-90601, 149544, 241747, 237726], ja maksimi löytyy kohdasta 2 (241747).
[/rem]