Rectangles-2#1480
Due to the large number of purchases of suburban plots, two large and proud states (let us call them "first" and "second") have established a series of agreements regarding land plots near their common border.
To better understand these arrangements, consider the border between these states on a map hung on a wall, so that north is at the top. We use an orthonormal coordinate system where the OX axis is directed from west to east, and the OY axis from south to north.
Divide the OX axis into equal segments. The -th segment has the coordinates [i-1, i]. Associate with each such segment a vertical strip formed by all possible lines parallel to OY passing through this segment. For each strip, introduce a level given by some integer z_i. Points in the strip of the -th segment lying above level z_i belong to the first state, and those below z_i belong to the second state.
If a citizen of one of the states wants to buy a rectangular plot of land with sides parallel to the coordinate axes, he can do so if his native state dominates the selected region. This happens if the state dominates in more vertical strips (associated with the relevant segments on OX) than the other state. On a given strip, a state is said to dominate if the area in the region belonging to that state is strictly greater than the area belonging to the other state in that strip.
You are asked to write a program that, for a requested region, determines the dominating state and allows changing the border.
The first line contains (1 \leq n \leq 50000) — the number of segments dividing the OX axis.
The second line contains integers z_i (0 \leq z_i \leq 10^9), defining the border level between the states for each segment.
The third line contains (1 \leq m \leq 100000) — the number of queries.
The next lines each contain a query in one of two formats:
"C x z": Set the level of strip number to (1 \leq x \leq n, 1 \leq z \leq 10^9).
"Q x_1 y_1 x_2 y_2": For the rectangle from strip x_1 to x_2 (1 \leq x_1 \leq x_2 \leq n), and vertical range y_1 to y_2 (0 \leq y_1 < y_2 \leq 10^9), determine the dominating state.
All numbers in the input are integers.
For each query of the form "Q x_1 y_1 x_2 y_2", print if the first state dominates in this region, if the second state dominates, and if neither state dominates.
Example 1