| Codeforces Round 326 (Div. 1) |
|---|
| Закончено |
На днях Duff стала солдатом армии. Malek — её командир.
В их стране, Andarz Gu, есть n городов (пронумерованных от 1 до n) и n - 1 дорог. Каждая дорога соединяет два различных города. Между любыми двумя городами существует уникальный путь.
Также в Andarz Gu живут m людей (пронумерованных от 1 до m). У каждого человека есть номер. Номер i-го человека равен i, и он/она живет в городе номер ci. Обратите внимание, в одном городе могут жить несколько людей, либо не жить вовсе.
Malek любит отдавать приказы. Поэтому он попросил Duff ответить на q запросов. В каждом запросе он дает ей числа v, u и a.
Чтобы ответить на запрос:
Предположим, что x людей живут в городах, лежащих на пути из города v в город u. Предположим, что номера этих людей — p1, p2, ..., px, если выписать их в возрастающем порядке.
Пусть k = min(x, a). Duff должна назвать Malek'у числа k, p1, p2, ..., pk, именно в таком порядке. Иными словами, Malek хочет знать a минимумов на этом пути (или меньше, если дано меньше a людей).
Duff сейчас очень занята, так что она попросила тебя помочь ей ответить на запросы.
В первой строке ввода записано три целых числа, n, m и q (1 ≤ n, m, q ≤ 105).
В следующих n - 1 строках записаны дороги. В каждой строке записано два целых числа, v и u, номера городов, соединённых очередной дорогой (1 ≤ v, u ≤ n, v ≠ u).
В следующей строке записано m целых чисел c1, c2, ..., cm (1 ≤ ci ≤ n, 1 ≤ i ≤ m).
В следующих q строках записаны запросы. Каждый из них состоит из трёх целых чисел, v, u и a (1 ≤ v, u ≤ n и 1 ≤ a ≤ 10).
Для каждого запроса выведите числа k, p1, p2, ..., pk через пробел в одной строке.
5 4 5
1 3
1 2
1 4
4 5
2 1 4 3
4 5 6
1 5 2
5 5 10
2 3 3
5 3 1
1 3
2 2 3
0
3 1 2 4
1 2
В тесте из условия страна Andarz Gu имеет следующий вид (номера людей, живущих в каждом городе, подписаны рядом с соответствующим городом):
