Задача H. Миллион Z

Входной файл:input.txt   Ограничение времени:5 сек
Выходной файл:output.txt   Ограничение памяти:8 Мб

Условие

Дана строка, состоящая из одного миллиона букв "Z". Определим операцию замены, которая характеризуется тремя параметрами (α, i, j) и состоит в замене на букву α букв строки начиная с позиции i до позиции j. Требуется определить, сколько различных букв будет в строке после выполнения заданной последовательности операций замены.

Формат входного файла

В первой строке входного файла содержится число замен N. В следующих N строках содержатся тройки α i j, где α — заглавная латинская буква, i и j — целые числа.

Формат выходного файла

Выходной файл должен содержать единственное целое число — количество различных букв в результирующей строке.

Ограничения

0 ≤ N ≤ 1000, 1 ≤ i ≤ j ≤ 106

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
3
A 1 50
X 90 1000
D 30 1000000
2

0.090s 0.012s 13