Вам дано неориентированное дерево, каждой вершине которого назначена магия $x_i$. Магия пути (путь в графе --- это конечная последовательность различных ребер, последовательно соединяющих вершины) определяется как произведение магии вершин на этом пути деленное на количество вершин на пути. Например, магия пути из вершин с магией $3$ и $5$ составляет $7.5 \:({3 \cdot 5 \over 2} )$. Найдите в заданном дереве путь с минимальной магией и выведите магию этого пути. \InputFile Первая строка содержит целое число $n\:(1 \le n \le 10^6)$ --- количество узлов в дереве. Каждая из следующих $n - 1$ строк содержит два целых числа $a_i$ и $b_i\:(1 \le a_i, b_i \le n)$ --- номера вершин, соединенных ребром. В $i$-ой из следующих $n$ строк записано целое число $x_i\:(1 \le x_i \le 10^9)$ --- магия $i$-ой вершины. \OutputFile Выведите магию пути с минимальным значением в виде несократимой дроби $P/Q\:(P$ и $Q$ взаимно простые числа). Во всех тестовых примерах требуемые $P$ и $Q$ меньше, чем $10^{18}$. \Examples Первый тест. Обратите внимание, что путь может начинаться и заканчиваться в одном и том же узле. Путь с минимальной магией состоит из узла с магией $3$, поэтому магия всего пути равна $3/1$. Второй тест. Путь, состоящий из вершин $2$ и $4$, является магическим $(1 \cdot 1)/2 = 1/2$. Это также путь с минимально возможной магией.