Дерево

Обмеження: 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