Автомат

Вхідні дані

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

1 \leq ∣ s ∣ \leq 1 0^{5}

1 \leq |\textbf{s}| \leq 10^5

Вихідні дані

У першому рядку виведіть два числа $n$ і $k$ ( $1 \leq k \leq 2 n$ 1 \leq k \leq 2n) — кількість станів і кількість переходів. Далі виведіть $k$ рядків, у кожному з яких по два числа $a_{i}$ a_i, $b_{i}$ b_i ( $1 \leq a_{i}, b_{i} \leq n$ 1 \leq a_i, b_i \leq n) та літеру $c_{i}$ c_i ( $^{'} a^{'} \leq c_{i} \leq^{'} z^{'}$ 'a' \leq c_i \leq 'z'), що означають наявність переходу зі стану $a_{i}$ a_i у $b_{i}$ b_i по літері $c_{i}$ c_i. Переходи можна виводити у довільному порядку. Якщо розв'язків декілька, виведіть будь-який із них.

Приклади

Приклад 1

Loading