E. Шоколадка
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мебибайт
ввод
стандартный ввод или input.txt
вывод
стандартный вывод или output.txt

В нашей повседневной жизни шоколадки дарят по праздникам, просто покупают для посиделок, а иногда на них спорят. Обычная шоколадная плитка представляет собой прямоугольник из долек, который иногда приятнее ломать, чем наслаждаться самой шоколадкой.

Вот и вы проспорили своему другу Тессекарпу очередную шоколадку. А так как ваш друг четырёхмерный, он признаёт только трёхмерные плитки шоколада. Вы смогли найти такую шоколадку, а именно, подарили ему шоколадный параллелепипед размера A на B на C долек. Введём координатную сетку на этой шоколадке: оси Ox, Oy и Oz направлены соответственно вдоль измерений A, B и C, а каждая долька имеет размер 1 × 1 × 1. Сам параллелепипед имеет углы (0, 0, 0) и (A, B, C).

Тессекарп бросился ломать шоколадку, делая удары в определённые точки. Каждый удар приходится в точку с целочисленными координатами и провоцирует разбитие того куска, в котором эта точка находится, на восемь новых кусков. Конкретнее, удар оставляет после себя 3 разлома вдоль каждой из плоскостей, параллельных плоскостям Oxy, Oxz, Oyz и пересекающихся в точке удара.

После каждого удара от вас требуется вычислить объём наибольшего из новых восьми кусков и вывести остаток от деления полученного значения на 109 + 7.

Гарантируется, что каждый удар не приходился на существующий разлом или грань исходной шоколадки, то есть был строго внутри какого-либо существующего на момент этого удара куска.

Входные данные

Первая строка содержит три целых числа A, B и C — размеры шоколадки (2 ≤ A, B, C ≤ 109).

Во второй строке содержится целое число N — количество ударов (1 ≤ N ≤ 150 000).

В следующих N строках содержится по три целых числа xi, yi и zi (1 ≤ xi ≤ A - 1, 1 ≤ yi ≤ B - 1, 1 ≤ zi ≤ C - 1). i-е из этих чисел задаёт координаты i-й точки удара. Гарантируется, что в момент нанесения удара точка находится строго внутри одного из существующих кусков шоколадки (не обязательно наибольшего!).

Выходные данные

Выведите N строк, в каждой из которых содержится остаток от деления объёма наибольшего нового куска, образовавшегося после очередного разлома, на 109 + 7.

Примеры
Входные данные
10 10 10
5
4 4 7
2 2 2
6 3 3
7 8 9
8 2 5
Выходные данные
252
20
48
24
8
Входные данные
1000000000 999999999 999999998
1
1 1 1
Выходные данные
999999287