У зв'язку з великою кількістю покупок дачних ділянок, дві великих, але від того не менш гордих держави (назвемо їх умовно "перше" та "друге"), встановили ряд угод, які стосуються ділянок землі біля їх границь. Щоб краще зрозуміти нововведення, розглянемо границю між цими державами на карті, яка висить на стіні так, що північ знаходиться зверху. Введемо ортоноровану систему координат, у якій вісь \textbf{OX} направлено з заходу на схід, а \textbf{OY} - з півдня на північ. Розглянемо \textbf{n} рівних за величиною відрізків на осі \textbf{OX}, \textbf{i}-ий з цих відрізків має координати \[\textbf{i-1}, \textbf{i}\]. Кожному з них співставимо вертикальну полосу, утворену усіма можливими прямими, паралельними \textbf{OY} і які проходять через сам відрізок. Тепер, щоб розділити держави, розглянемо придуману систему рівнів, яка базується на введених вертикальних полосах. Для кожної полоси визначимо її рівень, який задається деяким числом \textbf{z_i}. Точки, які належать вертикальній полосі відповідного відрізка, і лежать вище рівня, належать першій державі, а нижче - другій. Коли корінний житель однієї з держав бажає придбати прямокутну ділянку землі зі сторонами, паралельними осям координат (ділянки іншого виду нікого не цікавлять), він може це зробити, якщо його рідна держава домінує на вибраній ділянці. Це відбувається, якщо держава домінує на більшій, ніж інша державв, частині вертикальних полос, утворених відрізками на осі \textbf{OX}. Для вертикальних полос властивість домінування визначається наступним чином: якщо площа ділянки на цій полосі, яка належить одній з держав, строго більша площі, яка належить іншій, то перша з них домінує на цій полосі. Вас просять написати програму, яка могла б визначати державу, яка домінує на ділянці, а також змінювати границю між державами. \InputFile У першому рядку вхідного файлу записано \textbf{n} - кількість відрізків, на які поділено вісь \textbf{OX} (\textbf{1} ≤ \textbf{n} ≤ \textbf{50000}). У другому рядку - \textbf{n} чисел \textbf{z_i}, яуі визначають границю між державами (\textbf{0} ≤ \textbf{z_i} ≤ \textbf{10^9}). У третьому рядку задано \textbf{m} - число запитів до Вашої програми (\textbf{1} ≤ \textbf{m} ≤ \textbf{100000}). Далі йде \textbf{m} рядків з запитами. Кожен запит має вид "\textbf{C x z}" або "\textbf{Q x_1 y_1 x_2 y_2}". Запит виду "\textbf{C x z}" означає, що рівень вертикальної полоси номер \textbf{x} став рівним \textbf{z} (\textbf{1} ≤ \textbf{x} ≤ \textbf{n}, \textbf{1} ≤ \textbf{z} ≤ \textbf{10^9}). Запит виду "\textbf{Q x_1 y_1 x_2 y_2}" (\textbf{1} ≤ \textbf{x_1} ≤ \textbf{x_2} ≤ \textbf{n}, \textbf{0} ≤ \textbf{y_1} < \textbf{y_2} ≤ \textbf{10^9}) означає, що потрібно вивести державу, яка домінує на ділянці, лівою границею якої є вертикальна полоса номер \textbf{x_1} (включно), правою границею - вертикальна полоса номер \textbf{x_2} (включно), а з півдня і з півдня ділянку обмежено координатами \textbf{y_1} і \textbf{y_2} відповідно. Усі числа у вхідному файлі цілі. \OutputFile Для кожного запиту виду "\textbf{Q x_1 y_1 x_2 y_2}" виведіть \textbf{1}, якщо на цій ділянці домінує перша держава, \textbf{2}, якщо друга, і \textbf{0}, якщо у жодної з держав переваг немає.