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