Due to the large number of purchases suburban areas, two large, but no less proud of the state (we call them conditionally "first" and "second"), established a number of agreements relating to land near their border. To better understand innovation, we consider the border between these countries on a map that hangs on the wall so that north is at the top. We introduce the orthonormal coordinate system in which the axis \textbf{OX} is directed from west to east, and \textbf{OY} - from south to north. Consider n equal to the value of the segments on the axis \textbf{OX}, \textbf{i}-th of these segments has coordinates \[\textbf{i-1}, \textbf{i}\]. Each of them to associate a vertical bar, formed by all possible lines parallel to \textbf{OY} and passing through the segment itself. Now, to divide the state, consider the contrived system of levels based on the introduction of vertical bands. For each band, define the level, which is defined by a number \textbf{z_i}. Points belonging to the vertical strip of the corresponding segment, which lie above the level belong to the first state, and below - the second. When the native of one of the countries want to buy a rectangular plot of land with sides parallel to coordinate axes (plots of other species do not matter), he can do it, if its native state is dominated by a selected area. This occurs when the state dominates more than any other state, part of the vertical stripes, formed by the segments on the axis \textbf{OX}. For the vertical strips feature dominance is defined as follows: if the land area on this strip, owned by one of the states, strictly greater than the area belonging to another, the first of them is dominant in this band. You are asked to write a program that could determine the state, dominant in the area, and change the border between the states. \InputFile In the first line of the input file contains \textbf{n} - number of segments into which the axis \textbf{OX} (\textbf{1} ≤ \textbf{n} ≤ \textbf{50000}). In the second row - \textbf{n} numbers \textbf{z_i}, determining the boundary between the states (\textbf{0} ≤ \textbf{z_i} ≤ \textbf{10^9}). The third row is set to \textbf{m} - the number of requests to your program (\textbf{1} ≤ \textbf{m} ≤ \textbf{100000}). This is followed by \textbf{m} lines with requests. Each request has the form "\textbf{C x z}" or "\textbf{Q x_1 y_1 x_2 y_2}". Request form "\textbf{C x z}" means that the level of vertical stripes number \textbf{x} becomes equal to \textbf{z} (\textbf{1} ≤ \textbf{x} ≤ \textbf{n}, \textbf{1} ≤ \textbf{z} ≤ \textbf{10^9}). Request form "\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}) means that you want to display the state, dominant in the area, the left boundary of which is a vertical strip Room \textbf{x_1} (inclusive), right abroad - a vertical stripe number \textbf{x_2} (inclusive) and to the south and north section bounded coordinates \textbf{y_1} and \textbf{y_2}, respectively. All the numbers in the input file are integers. \OutputFile For each query of the form "\textbf{Q x_1 y_1 x_2 y_2}" output \textbf{1} if in this region is dominated by the former State, \textbf{2}, and the second, and \textbf{0} if none of the advantages of not.