Саша устал от тяжелой городской жизни и решил уехать в деревню. Чтобы чем-то занять свой быт, он решил заняться разведением овец. Для этого он приобрел в деревне прямоугольный участок, который можно представить в виде клетчатого поля $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}

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

Саша хочет в первую очередь узнать, можно ли, обрезая участок несколько раз, добиться того, чтобы все овцы двигались одинаково. Если такое возможно, то Саша хочет знать, какое максимальное количество столбцов может остаться на участке и как именно ему этого добиться. Помогите Саше решить эту задачу!