Colin Owen Yates-Granger

Cerință

Tânărul lord Colin Owen Yates-Granger s-a calificat la Olimpiada de Iarnă de la Milano 2026, în proba de biatlon. Pentru a se antrena, el a aliniat $N$ ținte pe un rând, cu câte $1$ m între ele, numerotate de la $0$ la $N-1$, de la stânga la dreapta. El va efectua următorul exercițiu:

Colin stă în fața țintei $0$, trage un glonț în ea și merge $K$ metri spre dreapta. Apoi trage un glonț în ținta din fața sa, merge alți $K$ metri spre dreapta și tot așa. Dacă a ajuns la ținta $N-1$ fără să parcurgă toți cei $K$ metri, îi va parcurge pe cei rămași spre stânga, urmând să își continue drumul spre stânga. Dacă ajunge la ținta $0$ și nu a parcurs toți cei $K$ metri spre stânga, îi va parcurge pe restul spre dreapta, urmând să își continue drumul spre dreapta.

În ce țintă va trage Colin al $G$-lea glonț?

Date de intrare

Pe prima linie se găsesc trei numere întregi, $N$, $K$ și $G$, cu semnificatia din enunț.

Date de ieșire

Pe prima linie se va găsi un singur număr întreg, ținta în care Colin va trage al $G$-lea glonț.

Restricții și precizări

• $1 \leq N, K \leq 10^{9}$;
• $1 \leq G \leq 10^{18}$;
• Pentru teste în valoare de $15$ puncte, $G \leq 4 \ 000 \ \text{și} \ K \leq 3 \ 000$.
• Pentru alte teste în valoare de $25$ puncte, $N \leq 10^{6}$.
• Pentru alte teste în valoare de $40$ puncte, $G \leq 10^{9}.$
• Țintele în care trage Colin NU se distrug, indiferent cu câte gloanțe sunt lovite.

Exemplul 1

stdin

5 3 4

stdout

1

Explicație

Colin va lovi, pe rând, țintele $0$, $3$, $2$ și $1$. Când ajunge la ținta $4$, el mai are de mers $2$ metri, pe care îi face spre stânga. Când ajunge înapoi la ținta $0$, el mai are de făcut $1$ metru, și îl face spre dreapta.

Exemplul 2

stdin

3 2 3

stdout

0

Explicație

Colin va lovi, pe rând, țintele $0$, $2$ și $0$. Să observăm că ținta $0$ a fost lovită de două ori.