== include(page="template/taskheader" task_id="pesaptecarari") ==

<Insert name>, mare iubitor de alcool si olimpic la informatica tocmai a descoperit conceptul de pub crawling (https://en.wikipedia.org/wiki/Pub_crawl). Foarte entuziasmat, s-a informat si a aflat de $N$ puburi care sunt conectate intre ele prin strazi uni-directionale. El s-a hotarat sa porneasca intr-un pub crawl din barul identificat cu numarul 1 care este langa scoala sa, pana la barul $N$, situat langa Strada Cramei, unde protagonistul nostru locuieste. In urma unei atente analize el a aflat un indice alcoolic pentru fiecare pub. Stiind un coeficient de siguranta $K$, el vrea sa-si planifice traseul astfel incat produsul indicilor alcoolici de pe drum sa contina $K$ la o putere cat mai mica. Daca reuseste sa determine un astfel de drum optim eroul nostru va ajunge acasa cu success. Se garanteaza ca isprava este posibila. <Insert Name> nu poate dezlega acest mister singur, motiv pentru care va cere ajutorul.

Georgel, mare iubitor de alcool si olimpic la informatica tocmai a descoperit conceptul de pub crawling (https://en.wikipedia.org/wiki/Pub_crawl). Foarte entuziasmat, s-a informat si a aflat de $N$ puburi care sunt conectate intre ele prin strazi uni-directionale. El s-a hotarat sa porneasca intr-un pub crawl din barul identificat cu numarul 1 care este langa scoala sa, pana la barul $N$, situat langa Strada Cramei, unde protagonistul nostru locuieste. In urma unei atente analize el a aflat un indice alcoolic pentru fiecare pub. Stiind un coeficient de siguranta $K$, el vrea sa-si planifice traseul astfel incat produsul indicilor alcoolici de pe drum sa contina $K$ la o putere cat mai mica. Daca reuseste sa determine un astfel de drum optim eroul nostru va ajunge acasa cu success. Se garanteaza ca isprava este posibila. Georgel nu poate dezlega acest mister singur, motiv pentru care va cere ajutorul.

h2. Date de intrare

* $1$ ≤ $N$ ≤ $10^5^$
* $1$ ≤ $M$ ≤ $7 * 10^5^$

* $1$ ≤ $K$ ≤ $10^12^$

* $2$ ≤ $K$ ≤ $10^12^$

* $0$ ≤ $A[~i~]$ ≤ $10^12^$
* $1$ ≤ $x$ ≤ $N$
* $1$ ≤ $y$ ≤ $N$