Дерево

Обмеження: 2 сек., 512 МіБ

Успішно склавши ЗНО з географії, Зеник вирішив приємно провести вечір та розв’язати таку цікаву задачу.

Задано зв’язний граф з $n$ вершин, з’єднаних $n-1$ ребрами. Вершини графа пронумеровані цілими числами від 1 до $n$ включно.

Початково в кожній вершині записано число нуль. Окрім цього, задано набір з $m$ простих шляхів у цьому графі, причому кожен шлях заданий як послідовність вершин. Задані шляхи пронумеровані цілими числами від 1 до $m$ включно.

Необхідно обробити $k$ запитів таких двох типів.

• + $p_i$ $a_i$ — додати $a_i$ до чисел, записаних на всіх вершинах на $p_i$-ому шляху.

• ? $p_i$ — знайти суму чисел, записаних на всіх вершинах $p_i$-ого шляху.

Допоможіть Зенику розв’язати цю задачу.

Вхідні дані

У першому рядку задано три цілих числа $n$, $m$, $k$ — кількість вершин, кількість шляхів та кількість запитів відповідно.

Наступні $n-1$ рядків описують ребра дерева $u_i$, $v_i$.

Наступні $m$ рядків описують шляхи, по одному на рядок. Перше число $c_i$ позначає кількість вершин на шляху, а наступні $c_i$ чисел описують вершини шляху в порядку обходу.

Останні $k$ рядків описують запити згідно з форматом, описаним в умові.

Вихідні дані

Для кожного запиту другого типу виведіть ціле число — відповідь на нього.

Обмеження

$1 \le n, m, k \le 2 \cdot 10^5$,

$1 \le u_i, v_i, c_i \le n$,

$0 \le a_i \le 10^9$,

Загальний розмір усіх заданих шляхів не перевищує $2 \cdot 10^5$.

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
7 4 7 1 2 1 3 3 4 3 5 3 6 4 7 3 1 3 5 3 6 3 4 4 7 4 3 5 2 3 1 ? 4 + 3 7 + 4 4 ? 4 ? 1 + 2 1 ? 3	0 15 22 34