Задача . C. Duff в армии

На днях Duff стала солдатом армии. Malek — её командир.

В их стране, Andarz Gu, есть n городов (пронумерованных от 1 до n) и n - 1 дорог. Каждая дорога соединяет два различных города. Между любыми двумя городами существует уникальный путь.

Также в Andarz Gu живут m людей (пронумерованных от 1 до m). У каждого человека есть номер. Номер i-го человека равен i, и он/она живет в городе номер c_i. Обратите внимание, в одном городе могут жить несколько людей, либо не жить вовсе.

Malek любит отдавать приказы. Поэтому он попросил Duff ответить на q запросов. В каждом запросе он дает ей числа v, u и a.

Чтобы ответить на запрос:

Предположим, что x людей живут в городах, лежащих на пути из города v в город u. Предположим, что номера этих людей — p₁, p₂, ..., p_x, если выписать их в возрастающем порядке.

Пусть k = min(x, a). Duff должна назвать Malek'у числа k, p₁, p₂, ..., p_k, именно в таком порядке. Иными словами, Malek хочет знать a минимумов на этом пути (или меньше, если дано меньше a людей).

Duff сейчас очень занята, так что она попросила тебя помочь ей ответить на запросы.