Рядки Фібоначчі#1311

Рядки Фібоначчі

1 секунда

256 мегабайтів

Середня

Рядки Фібоначчі визначаються наступним чином:

Перший фібоначчієвий рядок — це "a".
Другий фібоначчієвий рядок — це "bc".
( $n + 2$ n+2)-й фібоначчієвий рядок є конкатенацією двох попередніх фібоначчієвих рядків.

Наприклад, перші п’ять фібоначчієвих рядків:

a
bc
abc
bcabc
abcbcabc

За заданим номером рядка і позицією символа визначте, який символ стоїть на цій позиції в рядку.

Вхідні дані

Задано два цілих числа, розділені пробілом: $K$ і $P$ ( $0 < K \leq 1 0^{8}$ 0 < K \leq 10^8, $0 < P \leq 1 0^{8}$ 0 < P \leq 10^8), де $K$ — номер фібоначчієвого рядка, а $P$ — позиція для перевірки.

Вихідні дані

Виведіть один з трьох можливих символів: "a", "b" або "c". Якщо у $K$ -му рядку на позиції $P$ немає символа, виведіть "No solution".

Приклади

Приклад 1