Сашко се уморил от тежкия градски живот и решил да се пресели на село. За да се занимава с нещо, той решил да развъжда овце. За целта той си купил в селото правоъгълно парче земя, което може да се представи като мрежа от клетки с размери $n \times m$, в което редовете са номерирани отгоре надолу с числата от $1$ до $n$, а колоните са номерирани отляво надясно с числата от $1$ до $m$.

За своя участък Сашко си купил $n$ овце, за всяка от които отделил цял ред. В началото $i$-тата овца била поставена в клетка с координати $(i, a_i)$ (в ред с номер $i$ и колона с номер $a_i$). Сашко установил, че овцете се преместват само хоризонтално по следните правила:

\begin{itemize}

\item Ако участъкът има само една колона, овцете не се преместват.

\item Отначало $i$-тата овца се намира в клетка ($i, a_i$), а също така всяка овца има своя посока, на къде ще се движи --- или наляво, или надясно. При това не съществува овца, която се намира в първата колона и върви наляво, или такава, която се намира в последната колона и върви надясно.

\item Всяка секунда всяка овца се премества една колона наляво, ако посоката и е наляво или една колона надясно, ако посоката и е надясно.

\item Ако след преместване овцата се окаже в колона $1$ и се движи наляво, или ако овцата се окаже в последната колона и се движи надясно, тя порменя посоката си на движение на противоположната. По този начин овцете никога не излизат извън участъка.

\end{itemize}

\begin{center}
  \includegraphics[scale=0.75]{sheep-move.1}

\vspace{0.5cm}
\begin{minipage}{14cm}
{\footnotesize Тук е нарисуван пример за движение на овцете, ако в началото първата овца се намира в колона $1$ и се движи надясно, а втората се намира в колона $3$ и се движи наляво. На първата картинка е нарисувано състоянието в началото, на втората - след една секунда, на третата - след  $2$ секунди след началото на движението, на четвъртата - след $3$ секунди след началото на движението.}
\vspace{0.5cm}
\end{minipage}
\end{center}

На Сашко не му харесва, че овцете се движат така хаотично и затова той иска да направи така, че всички овце да се движат еднакво. Това означава, че всички овце трябва да са в една и съща колона и да имат една и съща посока на движение. За да постигне това, Сашко може да ореже своя участък няколко (възможно, нула) пъти по следния начин:

\begin{itemize}

\item Той избира момент $t$ (колко секунди са минали от началото на движението на овцете) и броя колони $x$, които ще останат в участъка след орязването.

\item Всички овце в момент $t$ трябва да се намират строго в участъка с размер $n \times x$. Това означава, че за произволно $i$ от $1$ до $n$, $i$-тата овца в момента $t$ трябва да се намира в клетка ($i, y_i$), където $1 \leq y_i \leq x$. В противен случай такова орязване на участка  е недопустимо.

\item След тази операция, от момента $t$ нататък, броят на колоните в участъка ще се намали на $x$.

\item Всяка овца, която след тази операция се намира в последната колона и се движи надясно, ще промени посоката си на движение на противоположната.

\end{itemize}

Подробни примери за процеса на оразване на участъка са дадени в описанието към тестовете от условието.

На първо време Сашко иска да разбере, дали след няколко орязвания на участъка може да се постигне всички овце да се движат еднакво. Ако това е възможно, Сашко иска да знае, какъв е максималния брой колони, които могат да останат в участъка и как да стане това. Помогнете на Сашко да реши тази задача!