Псевдоавтомат

Вхідні дані

У єдиному рядку слово $S$ , яке складається з рядкових латинських літер.

Вихідні дані

У першому рядку два числа $N$ і $K$ — кількість станів та кількість переходів. Далі $K$ рядків, у кожному з яких по два числа $a_{i}$ a_i, $b_{i}$ b_i та літера $c_{i}$ c_i, які позначають наявність переходу зі стану $a_{i}$ a_i у $b_{i}$ b_i по літері $c_{i}$ c_i. Переходи можна виводити у довільному порядку. Якщо розв'язків декілька, можете вивести довільний з них.

Обмеження

$1 \leq ∣ S ∣ \leq 5000$ 1 \le |S| \le 5000

$1 \leq a_{i}, b_{i} \leq N$ 1 \le a_i, b_i \le N

$^{'} a^{'} \leq c_{i} \leq^{'} z^{'}$ 'a' \le c_i \le 'z'

Приклади

Приклад 1

Loading