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