% Idee: Heno Ivanov
% Tekst: Tähvend Uustalu

\documentclass[a4paper,11pt]{article}
\usepackage[et]{../../eio}

\begin{document}
\begin{ol}{\eio}{\fv 7.02.2026}{\yle}{}
\begin{yl}{5}{Topsiturniir}{tops}{2 sek / 12 sek}{100 punkti}

  Juku avastas pärast laadal trikimeister Käbekäpa topsimängu mängimist, et on sellistes
  mängudes päris osav. Nüüd osaleb ta turniiridel, kus mängitakse mängust raskemat versiooni.

  Laual on $N$ ($1 \le N \le 3 \cdot 10^5$) topsi; iga topsi all on pall. Alguses on
  vasakult $k$-nda topsi all pall numbriga $k$. Mäng koosneb $Q$ ($1 \le Q \le 3 \cdot 10^5$)
  päringust; päringuid on kolme tüüpi:
  \begin{xenum}
  \item \label{change} Antud $L$ ja $R$. Topside $L \ldots R$ (loendatuna vasakult alates ühest) järjekord
    pööratakse ümber.
  \item \label{ord} Antud $X$. Leia, milline pall on vasakult $X$-nda topsi all.
  \item \label{pos} Antud $Y$. Leia, mitmenda topsi all on pall $Y$.
  \end{xenum}

  \sis
  Sisendi esimesel real on kaks täisarvu $N$ ja $Q$. Järgneb $Q$ rida, mis kirjeldavad päringuid.
  Igaüks neist on ühel järgmistest kujudest:
  \begin{xitem}
    \item ``$1 \; L \; R$'' (kus $1 \le L \le R \le N$);
    \item ``$2 \; X$'' (kus $1 \le X \le N$);
    \item ``$3 \; Y$'' (kus $1 \le Y \le N$).
  \end{xitem}
  On teada, et sisendis on vähemalt üks \ref{ord}. või \ref{pos}. tüüpi päring.

  \val
  Väljasta eraldi reale iga \ref{ord}. ja \ref{pos}. tüüpi päringu vastus: täisarv lõigust
  $1 \ldots N$.

  \nde[0]{3cm}{3cm}

  \hnd \testidgrupis
  \begin{xenum0}
  \item (0 punkti) \naitedlyhem
  \item (20 punkti) $N, Q \le 1\,000$.
  \item (60 punkti) Iga \ref{change}. tüüpi päring on kujul $L = a 2^b$, $R = (a + 1) 2^b - 1$, kus
    $a$ ja $b$ on täisarvud.
  \item (20 punkti) \piiranguteta
  \end{xenum0}

  Programm, mis vastab testigrupi raames korrektselt kõikidele \ref{ord}. tüüpi päringutele,
  aga eksib mõne \ref{pos}. tüüpi päringuga, teenib selle testigrupi eest $60\,\%$ punktidest.
  Nende punktide teenimiseks peab iga \ref{pos}. tüüpi päringu vastus siiski olema täisarv
  lõigust $1 \ldots N$.
\end{yl}
\end{ol}
\end{document}
