D. Карен и карты
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Карен пришла из супермаркета и собирается спать.

После принятия душа и переодевания в пижаму она заметила альбом на своей полке. Заинтересовавшись, она открыла его и увидела коллекцию карт.

Она вспомнила, что играла в них, когда была ребенком, но, несмотря на то, что она уже выросла, ее по-прежнему интересует один вопрос.

Каждая карта имеет три характеристики: сила, защита и скорость. Значения всех характеристик всех карт являются положительными целыми числами. Максимальное значение силы любой карты равно p, максимальное значение защиты равно q, максимальное значение скорости равно r.

В коллекции Карен n карт. i-я из этих карт имеет силу ai, защиту bi и скорость ci, соответственно.

Карта бьет другую карту, если хотя бы две ее характеристики строго больше соответствующих характеристик другой карты.

Карен интересует, сколько существует различных карт таких, что каждая из них бьет все карты из ее коллекции. Две карты различны, если хотя бы одна характеристика этих карт различна.

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

Первая строка содержит четыре целых числа n, p, q и r (1 ≤ n, p, q, r ≤ 500000) — число карт в коллекции, максимально возможная сила, максимально возможная защита, максимально возможная скорость, соответственно.

Каждая из следующих n строк содержит три целых числа. А именно, i-я строка содержит ai, bi и ci (1 ≤ ai ≤ p, 1 ≤ bi ≤ q, 1 ≤ ci ≤ r) — силу, защиту и скорость i-й карты из коллекции, соответственно.

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

Выведите одно число — число различных карт, которые бьют все карты из коллекции Карен.

Примеры
Входные данные
3 4 4 5
2 2 5
1 3 4
4 1 1
Выходные данные
10
Входные данные
5 10 10 10
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
Выходные данные
972
Примечание

В первом примере максимально возможная сила равна 4, максимально возможная защита равна 4, а максимально возможная скорость равна 5.У Карен есть три карты:

  • У первой карты сила 2, защита 2, скорость 5.
  • У второй карты сила 1, защита 3, скорость 4.
  • У третьей карты сила 4, защита 1, скорость 1.

Всего существуют 10 карт, которые бьют все карты из коллекции:

  1. Карта с силой 3, защитой 3 и скоростью 5.
  2. Карта с силой 3, защитой 4 и скоростью 2.
  3. Карта с силой 3, защитой 4 и скоростью 3.
  4. Карта с силой 3, защитой 4 и скоростью 4.
  5. Карта с силой 3, защитой 4 и скоростью 5.
  6. Карта с силой 4, защитой 3 и скоростью 5.
  7. Карта с силой 4, защитой 4 и скоростью 2.
  8. Карта с силой 4, защитой 4 и скоростью 3.
  9. Карта с силой 4, защитой 4 и скоростью 4.
  10. Карта с силой 4, защитой 4 и скоростью 5.

Во втором примере максимально возможная сила равна 10, максимально возможная защита равна 10, максимально возможная скорость равна 10. У Карен пять карт, у всех из них сила 1, защита 1 и скорость 1.

Каждая из 972 карт, у которых хотя бы две характеристики больше 1, бьет все карты из коллекции.