Танд $a_{1}, a_{2}, ..., a_{n}$ бүхэл тоон дараалал болон эерэг бүхэл тоо $h$ өгөгдөнө. Таны зорилго бол дарааллыг $2$ хэсэгт хуваах явдал юм. Хуваагдсан хэсгүүд заавал дараалласан элементүүдээс бүтэх албагүй бөгөөд элемент бүр хуваасан $2$ хэсгийн аль нэгэнд нь байх шаардлагатай. Энэ $2$ хэсгийн аль нэг нь хоосон байх боломжтой.

Дараалал дахь тоон байрлалаар $f(a_{i}, a_{j})$ ялгаатай $2$ тооны функц үүсгэе. Хэрвээ $a_{i}$ ба $a_{j}$ нь адил хэсэгт байрлавал $f(a_{i}, a_{j}) = a_{i} + a_{j}$, харин тус тусдаа байрлавал $f(a_{i}, a_{j}) = a_{i} + a_{j} + h$ байна.

Байх боломжтой бүх функц $f$-ийг тодорхойл. Функц $f$-ийн хамгийн их утга болон хамгийн бага утгуудын хоорондын ялгааг чанар гэж нэрлэе.

Таны даалгавар бол өгөгдсөн $a$ дарааллын чанарыг хамгийн бага байхаар $2$ хэсэгт хуваах юм.

Оролт

Эхний мөрөнд $n$, $h$ $(2 ≤ n ≤ 10^{5}, 0 ≤ h ≤ 10^{8})$ бүхэл тоонууд өгөгдөнө.

Хоёр дахь мөрөнд $n$ ширхэг зайгаар тусгаарлагдсан тоонууд $a_{1}, a_{2}, ..., a_{n}$ $(0 ≤ a_{i} ≤ 10^{8})$ өгөгдөнө.

Гаралт

Эхний мөрөнд олох ёстой хамгийн бага чанарыг хэвлэнэ.

Хоёр дахь мөрөнд $2$ хэсгийг тайлбарлан хэвлэнэ. Та $n$ ширхэг зайгаар тусгаарлагдсан бүхэл тоо хэвлэх ёстой бөгөөд хэрвээ $a_{i}$ эхний хэсэгт багтаж байгаа бол $1$ харин сүүлийн хэсэгт багтаж байгаа бол $2$ гэж хэвлэнэ.

Хэрвээ хэд хэдэн боломжит хари байвал аль нэгийг нь хэвлэнэ үү.

Эхний жишээнд функц $f$-ийн утгууд: $f(1, 2) = 1 + 2 + 2 = 5$, $f(1, 3) = 1 + 3 + 2 = 6$ ба $f(2, 3) = 2 + 3 = 5$. Тиймээс чанар нь $1$.

Хоёр дахь жишээнд $h$-ийн утга их тул эцсийн хэсгүүдийн аль нэг нь хоосон байх нь ашигтай.