Вам надаються \(N\) інтервалів, які пронумеровані від 1 до \(N\), а саме:

• якщо \(t_i\)=1, інтервал \(i\) дорівнює \([l_i,r_i]\);

• якщо \(t_i=2\), інтервал \(i\) дорівнює \([l_i,r_i)\);

• якщо \(t_i=3\), інтервал \(i\) дорівнює \((l_i,r_i]\);

• якщо \(t_i=4\), інтервал \(i\) дорівнює \((l_i,r_i)\).

Скільки існує пар цілих чисел \((i,j)\), які задовольняють \(1 \leq i \lt j \leq N\), що інтервал \(i\) та інтервал \(j\) перетинаються?

Формат вхідних даних

Перший рядок містить ціле число \(N\) (\(2 \le N \le 2000\))

Наступні  \(N\) рядків містять цілі числа \(t_i,l_i,r_i\) (\(1 \le l_i < r_i \le 10^9\), \(1 \le t_i \le 4\))

Формат вихідних даних

У вихідний потік виведіть шукану кількість пар.

Примітка

До прикладу 1:

Інтервал 1 — це [1,2], інтервал 2 — це [2,3), а інтервал 3 — (2,4].

Існують дві пари цілих чисел (\(i,j\)), такі, що інтервал \(i\) та інтервал \(j\) перетинаються: (1,2) та (2,3). Для першої пари перетин дорівнює [2,2], а для другої пари — (2,3).

Приклад вхідних даних

3
1 1 2
2 2 3
3 2 4

Приклад вихідних даних

2

Приклад вхідних даних

19
4 210068409 221208102
4 16698200 910945203
4 76268400 259148323
4 370943597 566244098
1 428897569 509621647
4 250946752 823720939
1 642505376 868415584
2 619091266 868230936
2 306543999 654038915
4 486033777 715789416
1 527225177 583184546
2 885292456 900938599
3 264004185 486613484
2 345310564 818091848
1 152544274 521564293
4 13819154 555218434
3 507364086 545932412
4 797872271 935850549
2 415488246 685203817

Приклад вихідних даних

102