Задача №111793. Карать, не прощать!
Маленький мальчик Глеб еще толком не познал жизнь, но он уже ОЧЕНЬ любит КАРАТЬ, НЕ ПРОЩАТЬ! И вот в очередной раз он решил поиздеваться над бедным Лёшиком =(
Он сказал, что у него есть первая четверть плоскости, он умеет добавлять на нее прямоугольник с нижней левой точкой (0;0) и верхней правой (x;y), умеет считать площадь получившейся фигуры, умеет считать площадь объединения этой фигуры с прямоугольником на точках (x1;y1) и (x2;y2) и даже площадь пересечения.
Лёшик в печальке... =(
Спасите Лёшика, решите эту задачу. Но помните, Глеб настолько суров, что заставил решать поставленную задачу в он-лайне!!!
В первой строке задано число N (1 ≤ N ≤ 105). Далее следует описание запросов:
первое число t — тип запроса
t = 0: вводятся числа x и y, значит нужно добавить прямоугольник с координатами (0;0) и (x;y)
t = 1: вы должны вывести площадь получившейся фигуры
t = 2: вводятся числа x1, y1, x2, y2, значит нужно вывести площадь пересечения фигуры и такого прямоугольника
t = 3: вводятся числа x1, y1, x2, y2, значит нужно вывести площадь объединения фигуры и такого прямоугольника
Так как Глеб коварен, то все числа в запросах нужно еще преобразовать. Пусть ANS — ответ на предыдущий запрос. Изначально ANS = 0.
Тогда при t = 0 x = 1 + (x + ANS): mod: 109, y = 1 + (y + ANS): mod: 109.
При t = [2, 3] x1 = 1 + (x1 + ANS): mod: (5·108), y1 = 1 + (y1 + ANS): mod: (5·108), x2 = x1 + 1 + (x2 + ANS): mod: (5·108), y2 = y1 + 1 + (y2 + ANS): mod: (5·108).
После запросов типа 1, 2 или 3 ANS = ответу на этот запрос.
Выведите ответы на запросы.
В 1 примере даны запросы, которые не преобразуются по заданным формулам для простоты понимания.
4 0 2 2 1 2 1 1 3 3 3 1 1 3 3
9 0 24
4 0 2 2 1 2 1 1 3 3 3 1 1 3 3
9 0 24