Карен пришла из супермаркета и собирается спать.
После принятия душа и переодевания в пижаму она заметила альбом на своей полке. Заинтересовавшись, она открыла его и увидела коллекцию карт.
Она вспомнила, что играла в них, когда была ребенком, но, несмотря на то, что она уже выросла, ее по-прежнему интересует один вопрос.
Каждая карта имеет три характеристики: сила, защита и скорость. Значения всех характеристик всех карт являются положительными целыми числами. Максимальное значение силы любой карты равно p, максимальное значение защиты равно q, максимальное значение скорости равно r.
В коллекции Карен n карт. i-я из этих карт имеет силу ai, защиту bi и скорость ci, соответственно.
Карта бьет другую карту, если хотя бы две ее характеристики строго больше соответствующих характеристик другой карты.
Карен интересует, сколько существует различных карт таких, что каждая из них бьет все карты из ее коллекции. Две карты различны, если хотя бы одна характеристика этих карт различна.
Выходные данные
Выведите одно число — число различных карт, которые бьют все карты из коллекции Карен.
Примечание
В первом примере максимально возможная сила равна 4, максимально возможная защита равна 4, а максимально возможная скорость равна 5.У Карен есть три карты:
- У первой карты сила 2, защита 2, скорость 5.
- У второй карты сила 1, защита 3, скорость 4.
- У третьей карты сила 4, защита 1, скорость 1.
Всего существуют 10 карт, которые бьют все карты из коллекции:
- Карта с силой 3, защитой 3 и скоростью 5.
- Карта с силой 3, защитой 4 и скоростью 2.
- Карта с силой 3, защитой 4 и скоростью 3.
- Карта с силой 3, защитой 4 и скоростью 4.
- Карта с силой 3, защитой 4 и скоростью 5.
- Карта с силой 4, защитой 3 и скоростью 5.
- Карта с силой 4, защитой 4 и скоростью 2.
- Карта с силой 4, защитой 4 и скоростью 3.
- Карта с силой 4, защитой 4 и скоростью 4.
- Карта с силой 4, защитой 4 и скоростью 5.
Во втором примере максимально возможная сила равна 10, максимально возможная защита равна 10, максимально возможная скорость равна 10. У Карен пять карт, у всех из них сила 1, защита 1 и скорость 1.
Каждая из 972 карт, у которых хотя бы две характеристики больше 1, бьет все карты из коллекции.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 4 4 5
2 2 5
1 3 4
4 1 1
|
10
|
|
2
|
5 10 10 10
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
|
972
|