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 OX is directed from west to east, and OY - from south to north. Consider n equal to the value of the segments on the axis OX, i-th of these segments has coordinates [i-1, i]. Each of them to associate a vertical bar, formed by all possible lines parallel to 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 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 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.
In the first line of the input file contains n - number of segments into which the axis OX (1 ≤ n ≤ 50000). In the second row - n numbers z_i, determining the boundary between the states (0 ≤ z_i ≤ 10^9). The third row is set to m - the number of requests to your program (1 ≤ m ≤ 100000). This is followed by m lines with requests. Each request has the form "C x z" or "Q x_1 y_1 x_2 y_2". Request form "C x z" means that the level of vertical stripes number x becomes equal to z (1 ≤ x ≤ n, 1 ≤ z ≤ 10^9). Request form "Q x_1 y_1 x_2 y_2" (1 ≤ x_1 ≤ x_2 ≤ n, 0 ≤ y_1 < y_2 ≤ 10^9) means that you want to display the state, dominant in the area, the left boundary of which is a vertical strip Room x_1 (inclusive), right abroad - a vertical stripe number x_2 (inclusive) and to the south and north section bounded coordinates y_1 and y_2, respectively. All the numbers in the input file are integers.
For each query of the form "Q x_1 y_1 x_2 y_2" output 1 if in this region is dominated by the former State, 2, and the second, and 0 if none of the advantages of not.