У Китти есть дерево , состоящее из вершин, пронумерованных от до . Ее друг Алекс дал ей множеств, каждое из которых содержит набор вершин. Китти нужно вычислить следующее выражение для каждого набора:
где:
обозначает неупорядоченную пару вершин из множества.
обозначает количество ребер на уникальном (кратчайшем) пути между узлами и .
По заданному дереву и множествам из различных вершин вычислите значение выражения для каждого набора. Значение выражения следует выводить по модулю для каждого теста в новой строке.
Первая строка содержит два целых числа: количество вершин в дереве и количество запросов .
Каждая из последующих строк содержит два целых числа и , описывающих неориентированное ребро между вершинами и .
Далее следуют строк. Каждый тест задается двумя строками в следующем формате:
Первая строка содержит размер набора ;
Вторая строка содержит целых чисел — элементы множества , сумма по всем не превышает .
Выведите строк, где -ая строка содержит значение выражения для -го запроса по модулю .