Задача . E. Тавас в пути

Тавас живет в Тавасполисе. В Тавасполисе n городов, пронумерованных от 1 до n, соединенных n - 1 двунаправленными дорогами. Между любыми двумя городами есть путь. Также у каждой дороги есть длина.

Любимые строки Таваса — двоичные строки (содержащие только 0 и 1). Для любой двоичной строки типа s = s₁s₂... s_k, определим T(s) — значение этой строки. T(s) вычисляется следующим способом:

Предположим, что в строке s ровно m блоков цифр 1 (блок цифр 1 — это максимальная подстрока s, которая содержит только единицы) длинами x₁, x₂, ..., x_m.

Определим , где f — данная последовательность чисел (в частности, если m = 0, то T(s) = 0).

Тавас любит запросы. Он просит Вас ответить на q запросов. В каждом запросе он дает вам числа v, u, l, а вам следует вывести следующее число:

Рассмотрим дороги на пути из города v в город u: e₁, e₂, ..., e_x.

Построим бинарную строку b длины x, такую, что: b_i = 1 тогда и только тогда, когда l ≤ w(e_i), где w(e) — длина дороги e.

Результатом запроса является строка T(b).