Given a tree of N nodes, where each node is uniquely numbered in between [1, N]. Each node also has a value which is initially 0. You need to perform following two operations in the tree.  

Update Operation
Report Operation

Update Operation

U r t a b

Adds $a^{b}$ + $(a+1)^{b} $+ $(b+1)^{a} $to all nodes in the subtree rooted at t, considering that tree is rooted at r (see explanation for more details).  

Report Operation

R r t m

Output the sum of all nodes in the subtree rooted at t, considering that tree is rooted at r. Output the sum modulo m (see explanation for more details).

Input Format

First line contains N, number of nodes in the tree. 

Next N-1 lines contain two space separated integers x and y which denote that there is an edge between node x and node y. 

Next line contains Q, number of queries to follow. 

Next Q lines follow, each line will be either a report operation or an update operation.  

Output Format

For each report query output the answer in a separate line.

Constraints

1 ≤ N ≤ 100000 

1 ≤ Q ≤ 100000 

1 ≤ m ≤ 101 

1 ≤ r, t, x, y ≤ N 

x ≠ y 

1 ≤ a, b ≤ $10^{18}  $

Notes

There will be at most one edge between a pair of nodes.
There will be no loop.
Tree will be completely connected. 

Sample Input

4
1 2
2 3
3 4
4
U 3 2 2 2
U 2 3 2 2
R 1 2 8
R 4 3 9

Sample Output

2
3

Explanation

Initially Values in each node : [0,0,0,0] 

The first query is U 3 2 2 2. Here, tree is rooted at 3. It looks like 

    3(0)
   / \
  /   \
 2(0)  4(0)
 |
 |
 1(0)

For the sub tree rooted at 2 ( nodes 2 and 1 ), we add $a^{b}$  +$ (a+1)^{b}$ + $(b+1)^{a}$ =$ 2^{2}$ + $3^{2}$ + $3^{2}$ = 22. After first update operation, nodes 1, 2, 3, and 4 will have values 22, 22, 0 and 0 respectively.  

    3(0)
   / \
  /   \
 2(22) 4(0)
 |
 |
 1(22)

The second query is U 2 3 2 2. Here, tree is rooted at 2. It looks like

    2(22)
   / \
  /   \
 1(22) 3(0)
       |
       |
       4(0)

For the sub tree rooted at 3 (nodes 3 and 4), we add $a^{b}$ + $(a+1)^{b}$ + $(b+1)^{a}$ = $2^{2}$ + $3^{2}$ + $3^{2} $= 22. After second update operation, nodes 1, 2, 3, and 4 each have values 22,22,22,22 respectively.  

    2(22)
   / \
  /   \
 1(22) 3(22)
       |
       |
       4(22)

The first report query is R 1 2 8 asks for the sum modulo 8 of the subtree rooted at 2, when the tree is rooted at 1. The tree looks like 

1(22)
 \
  \
   2*(22)
   |
   |
   3*(22)
   |
   |
   4*(22)

The sum of the values of nodes 2, 3 and 4 are 

(22 + 22 + 22) % 8 = 2

The second report query is R 4 3 9 asks for the sum modulo 9 of the subtree rooted at 3 when the tree is rooted at 4. The tree looks like 

4(22)
 \
  \
   3*(22)
   |
   |
   2*(22)
   |
   |
   1*(22)

The sum of the values of nodes 3, 2 and 1 are 

(22 + 22 + 22) % 9 = 3

Time Limits: 

C, C++: 4s | Java and other JVM based languages: 10s | Python, Python3 = 45s | Other interpreted Language: 30s | C#, Haskell: 10s | Rest: 3 times of default.

Source: hackerrank | Difficulty: MEDIUM_HARD
Tags: Data structures


Solutions:
def implementOps(n, ops):
	arr = [0] * n
	res = []
	for op in ops:
		z = op[0]
		if z == 'U':
			(x, y, a, b) = list(map(int, op[1:]))
			t = a ** b + (a + 1) ** b + (b + 1) ** a
			if int(x) > int(y):
				for i in range(y):
					arr[i] += t
			else:
				for i in range(x, len(arr)):
					arr[i] += t
		else:
			(x, y, m) = list(map(int, op[1:]))
			if int(x) > int(y):
				res.append(sum(arr[:y]) % m)
			else:
				res.append(sum(arr[x:]) % m)
	return res
n = int(input())
edges = []
for i in range(n - 1):
	edges.append(list(map(int, input().split())))
q = int(input())
ops = []
for i in range(q):
	ops.append(input().split())
res = implementOps(n, ops)
for v in res:
	print(v)


class SummationGraph:

	def __init__(self, n):
		self.n = n
		self.adjacency_list = {}
		[self.adjacency_list.setdefault(x, []) for x in range(1, n + 1)]
		self.data = {}
		[self.data.setdefault(x, 0) for x in range(1, n + 1)]
		self.reports = []

	def add_edge(self, x, y):
		self.adjacency_list[x].append(y)
		self.adjacency_list[y].append(x)

	def query(self, query):
		if query[0] == 'U':
			self.update(query[1], query[2], query[3], query[4])
		elif query[0] == 'R':
			self.report(query[1], query[2], query[3])

	def update(self, root, subtree, a, b):
		visited = {subtree: True}
		valid = [subtree]
		for node in self.adjacency_list[subtree]:
			visited[node] = True
			if node != root:
				try:
					children = []
					self.root_exclusive_dfs_visitor(root, node, visited, children)
					valid.append(node)
					valid.extend(children)
				except:
					pass
		val = self.calc(a, b)
		for node in valid:
			self.data[node] += val

	def root_exclusive_dfs_visitor(self, root, subtree, visited, valid):
		for node in self.adjacency_list[subtree]:
			if node not in visited:
				if subtree == root:
					raise Exception
				visited[node] = True
				valid.append(node)
				self.root_exclusive_dfs_visitor(root, node, visited, valid)

	def report(self, root, subtree, mod):
		visited = {subtree: True}
		valid = [subtree]
		for node in self.adjacency_list[subtree]:
			visited[node] = True
			if node != root:
				try:
					children = []
					self.root_exclusive_dfs_visitor(root, node, visited, children)
					valid.append(node)
					valid.extend(children)
				except:
					pass
		sum = 0
		for node in valid:
			sum += self.data[node]
		self.reports.append(sum % mod)

	def calc(self, a, b):
		return a ** b + (a + 1) ** b + (b + 1) ** a
n = int(input())
edges = []
for i in range(n - 1):
	edges.append(tuple(map(int, input().split(' '))))
q = int(input())
queries = []
for i in range(q):
	row = input().split(' ')
	row[1:] = list(map(int, row[1:]))
	queries.append(tuple(row))
graph = SummationGraph(n)
for edge in edges:
	graph.add_edge(edge[0], edge[1])
for operation in queries:
	graph.query(operation)
print(*graph.reports, sep='\n')


class Node:

	def __init__(self):
		self.updates = []
		self.neighbors = []

def can_lead_to_root(nodes, root, source, current):
	if current == root:
		return True
	return any((can_lead_to_root(nodes, root, current, n) for n in nodes[current].neighbors if n != source))

def neighbor_leading_to_root(nodes, root, t):
	for neighbor in nodes[t].neighbors:
		if can_lead_to_root(nodes, root, t, neighbor):
			return neighbor

def apply_query_coming_from_source(nodes, current, query, source):
	nodes[current].updates.append(query)
	for neighbor in nodes[current].neighbors:
		if neighbor != source:
			apply_query_coming_from_source(nodes, neighbor, query, current)

def update(nodes, root, t, query):
	nodes[t].updates.append(query)
	q = neighbor_leading_to_root(nodes, root, t)
	for neighbor in nodes[t].neighbors:
		if neighbor != q:
			apply_query_coming_from_source(nodes, neighbor, query, t)

def calculate_node_value(nodes, number, modulo):
	result = 0
	for (a, b) in nodes[number].updates:
		result += pow(a, b, m) + pow(a + 1, b, m) + pow(b + 1, a, m)
	return result

def report_coming_from_source(nodes, current, source, modulo):
	result = calculate_node_value(nodes, current, modulo)
	for neighbor in nodes[current].neighbors:
		if neighbor != source:
			result += report_coming_from_source(nodes, neighbor, current, modulo)
	return result

def report(nodes, root, t, m):
	q = neighbor_leading_to_root(nodes, root, t)
	return report_coming_from_source(nodes, t, q, m) % m

def display(nodes):
	for i in range(1, n + 1):
		print(i, nodes[i].updates)
n = int(input())
nodes = [Node() for _ in range(n + 1)]
for _ in range(n - 1):
	(x, y) = map(int, input().split())
	nodes[x].neighbors.append(y)
	nodes[y].neighbors.append(x)
q = int(input())
for _ in range(q):
	query = input().split()
	if len(query) == 4:
		(r, t, m) = map(int, query[1:])
		print(report(nodes, r, t, m))
	else:
		(r, t, a, b) = map(int, query[1:])
		update(nodes, r, t, (a, b))


def Tree(L):
	NL = []
	while len(L) != 0:
		for (i, j) in L:
			if i == r:
				NL.append([i, j])
				L.remove([i, j])
			elif j == r:
				NL.append([j, i])
				L.remove([i, j])
			elif len(NL) != 0:
				for k in range(len(NL)):
					if i == NL[k][-1]:
						NL[k].append(j)
						L.remove([i, j])
					elif j == NL[k][-1]:
						NL[k].append(i)
						L.remove([i, j])
	return NL
n = int(input())
Connections = [list(map(int, input().split())) for _ in range(n - 1)]
q = int(input())
T = [0] * n
for _ in range(q):
	L = input().split()
	if L[0] == 'U':
		(r, t, a, b) = map(int, L[1:])
		v = a ** b + (a + 1) ** b + (b + 1) ** a
		L = Tree(Connections[:])
		for i in L:
			if t == i[1]:
				for j in i[1:]:
					T[j - 1] += v
	elif L[0] == 'R':
		(r, t, m) = map(int, L[1:])
		L = Tree(Connections[:])
		Sum = 0
		for i in L:
			if t == i[1]:
				for j in i[1:]:
					Sum += T[j - 1]
		print(Sum % m)


import collections
graph = collections.defaultdict(list)
n = int(input())
val = [0] * (n + 1)
for i in range(0, n - 1):
	(a, b) = map(int, input().split())
	graph[a].append(b)
	graph[b].append(a)

def dfsu(root, visited, flag, up, target):
	if flag == 1:
		val[root] = val[root] + up
	if root == target:
		val[target] = val[target] + up
		flag = 1
	visited[root] = 1
	if root in graph:
		for i in graph[root]:
			if visited[i] == 0:
				dfsu(i, visited, flag, up, target)

def dfsr(root, visited, flag, target):
	res = 0
	if flag == 1:
		res = res + val[root]
	if root == target:
		res = val[target] + res
		flag = 1
	visited[root] = 1
	if root in graph:
		for i in graph[root]:
			if visited[i] == 0:
				res = res + dfsr(i, visited, flag, target)
	return res
q = int(input())
for i in range(0, q):
	l = list(input().split())
	if l[0] == 'U':
		a = int(l[3])
		b = int(l[4])
		s = a ** b + (a + 1) ** b + (b + 1) ** a
		dfsu(int(l[1]), [0] * (n + 1), 0, s, int(l[2]))
	if l[0] == 'R':
		print(dfsr(int(l[1]), [0] * (n + 1), 0, int(l[2])) % int(l[3]))


import sys
lines = []
for line in sys.stdin:
	lines.append(line.strip('\n'))
n_nodes = int(lines[0])
structure = []
for (idx, l) in enumerate(lines[1:]):
	pair = l.split(' ')
	if len(pair) == 2:
		structure.append(list(map(lambda x: int(x), pair)))
	else:
		n_queries = int(l)
		break
queries = []
for q in lines[idx + 2:]:
	queries.append(q.split(' '))

class Node:

	def __init__(self, idx, value):
		self.parents = set()
		self.children = set()
		self.value = value
		self.idx = idx + 1

	def add_parent(self, parent):
		self.parents.add(parent)

	def add_child(self, child):
		self.children.add(child)

	def set_value(self, value):
		self.value

	def switch_child(self, child):
		try:
			self.children.remove(child)
		except ValueError:
			pass
		self.add_parent(child)

	def switch_parent(self, parent):
		try:
			self.parents.remove(parent)
		except ValueError:
			pass
		self.add_child(parent)

	def switch_parents(self):
		for parent in self.parents.copy():
			self.switch_parent(parent)
			parent.switch_parents()
			parent.switch_child(self)

	def print_val(self, ignore=None, centre=10):
		if self is not None:
			print('{}{},({}){}'.format(' ' * centre, self.idx, self.value, ' ' * centre))
		left = self.children - {ignore}
		for l in left:
			l.print_val(ignore=self, centre=centre - 5)

	def update_val(self, val, ignore=None):
		if self is not None:
			self.value += val
		left = self.children - {ignore}
		for l in left:
			l.update_val(ignore=self, val=val)

	def get_sum(self, init=0, ignore=None):
		if self is not None:
			init += self.value
		else:
			return 0
		left = self.children - {ignore}
		for l in left:
			return init + l.get_sum(ignore=self, init=init)
		return 0

class Tree:

	def __init__(self, n_nodes, structure):
		self.nodes = [Node(idx, value=0) for idx in range(n_nodes)]
		self.structure = structure
		self._create_tree()
		self.root = None

	def _create_tree(self):
		for (child, parent) in self.structure:
			child = child - 1
			parent = parent - 1
			self.nodes[child].add_parent(self.nodes[parent])
			self.nodes[parent].add_child(self.nodes[child])

	def _set_root(self, idx):
		idx = idx - 1
		self.root = self.nodes[idx]
		self.root.switch_parents()

	def print_tree(self):
		if self.root is None:
			print('Root is not set, setting to first node')
			self._set_root(1)
		self.root.print_val()

	def get_subtree(self, subroot):
		self.nodes[subroot - 1].print_val()

	def _update_sub(self, sub, val):
		self.nodes[sub - 1].update_val(val)

	def _get_sum(self, sub):
		return self.nodes[sub - 1].get_sum()

	def update_operation(self, root, sub, a, b):
		val = a ** b + (a + 1) ** b + (b + 1) ** a
		self._set_root(root)
		self._update_sub(sub, val)

	def report_operation(self, root, sub, modulo):
		self._set_root(root)
		print(self._get_sum(sub) % modulo)
tree = Tree(n_nodes, structure)
for q in queries:
	if q[0] == 'U':
		(root, subroot, a, b) = list(map(int, q[1:]))
		tree.update_operation(root, subroot, a, b)
	else:
		(root, subroot, modulo) = list(map(int, q[1:]))
		tree.report_operation(root, subroot, modulo)


def log(text):
	if False:
		print(text)

def add_edge(graph, node1, node2):
	log('add edge [%d, %d]' % (node1, node2))
	if node1 in graph:
		graph[node1].add(node2)
	else:
		graph[node1] = set([node2])
	if node2 in graph:
		graph[node2].add(node1)
	else:
		graph[node2] = set([node1])

def add_score(scores, key, score):
	if key in scores:
		scores[key] += score
	else:
		scores[key] = score

def formula(a, b):
	log('a^b = %d' % pow(a, b))
	log('(a+1)^b = %d' % pow(a + 1, b))
	log('(b+1)^a = %d' % pow(b + 1, a))
	return pow(a, b) + pow(a + 1, b) + pow(b + 1, a)

def update(tree_graph, scores, prev, root, sub, score):
	log('update: %s, %s, %s, %s' % (prev, root, sub, score))
	if root == sub:
		log('found sub: %s' % sub)
		add_score(scores, root, score)
		for c in tree_graph[root]:
			if not c == prev:
				update(tree_graph, scores, root, c, c, score)
	else:
		for c in tree_graph[root]:
			if not c == prev:
				update(tree_graph, scores, root, c, sub, score)
	log('scores: %s' % scores)

def sum_score(tree_graph, scores, prev, root, sub, sum):
	log('sum_score: %s, %s, %s, %s' % (prev, root, sub, sum))
	if root == sub:
		log('found sub: %s' % sub)
		for c in tree_graph[root]:
			if not c == prev:
				sum += sum_score(tree_graph, scores, root, c, c, sum)
		sum += scores[root]
	else:
		for c in tree_graph[root]:
			if not c == prev:
				sum += sum_score(tree_graph, scores, root, c, sub, sum)
	return sum
num_nodes = int(input())
tree_graph = {}
scores = {}
for e in range(1, num_nodes):
	edge = [int(n) for n in input().strip().split(' ')]
	add_edge(tree_graph, edge[0], edge[1])
log('tree: %s' % tree_graph)
num_queries = int(input())
for e in range(num_queries):
	query = input().strip().split(' ')
	log('query: %s' % query)
	if query[0] == 'U':
		update(tree_graph, scores, None, int(query[1]), int(query[2]), formula(int(query[3]), int(query[4])))
	elif query[0] == 'R':
		total = sum_score(tree_graph, scores, None, int(query[1]), int(query[2]), 0)
		log('total = %d' % total)
		print(total % int(query[3]))


from collections import defaultdict

def build_graph(edges):
	graph = defaultdict(list)
	for edge in edges:
		(a, b) = (edge[0], edge[1])
		graph[a].append(b)
		graph[b].append(a)
	for g in graph:
		graph[g].append(0)
	return graph

def addEdges(edges, node1, node2):
	edges.append([node1, node2])

def putValue(graph, r, t, value):
	nodes = graph[t]
	if not nodes:
		return
	nodes[-1] = value
	for n in nodes[0:-1]:
		if n != r:
			putValue(graph, t, n, value)

def getSumOfValues(graph, r, t):
	nodes = graph[t]
	if not nodes:
		return 0
	total = nodes[-1]
	for n in nodes[0:-1]:
		if n != r:
			total += getSumOfValues(graph, t, n)
	return total
edges = []
for i in range(int(input()) - 1):
	nodes = input().strip().split()
	addEdges(edges, nodes[0], nodes[1])
graph = build_graph(edges)
for i in range(int(input())):
	query = input().strip().split()
	if query[0] == 'U':
		r = query[1]
		t = query[2]
		a = int(query[3])
		b = int(query[4])
		value = a ** b + (a + 1) ** b + (b + 1) ** a
		putValue(graph, r, t, value)
	else:
		r = query[1]
		t = query[2]
		report = getSumOfValues(graph, r, t) % int(query[3])
		print(report)


def implementOps(n, ops):
	arr = [0] * n
	res = []
	for op in ops:
		z = op[0]
		if z == 'U':
			(x, y, a, b) = list(map(int, op[1:]))
			t = a ** b + (a + 1) ** b + (b + 1) ** a
			if int(x) > int(y):
				for i in range(y):
					arr[i] += t
			else:
				for i in range(x, len(arr)):
					arr[i] += t
		else:
			(x, y, m) = list(map(int, op[1:]))
			if int(x) > int(y):
				res.append(sum(arr[:y]) % m)
			else:
				res.append(sum(arr[x:]) % m)
	return res
n = int(input())
edges = []
for i in range(n - 1):
	edges.append(list(map(int, input().split())))
q = int(input())
ops = []
for i in range(q):
	ops.append(input().split())
res = implementOps(n, ops)
for v in res:
	print(v)


class Node:

	def __init__(self, data, next=None, prev=None, value=0):
		self.data = data
		self.next = next
		self.prev = prev
		self.value = value
n = int(input())
head = None
hn = None
for i in range(n - 1):
	(x, y) = map(int, input().split())
	if hn:
		if hn.data == x:
			nodey = Node(y)
			nodey.prev = hn
			hn.next = nodey
			hn = nodey
	else:
		nodex = Node(x)
		nodey = Node(y)
		nodex.next = nodey
		nodey.prev = nodex
	if head is None:
		head = nodex
		hn = nodey
q = int(input())
for i in range(q):
	cmd = [i for i in input().split()]
	if cmd[0] == 'U':
		(r, t, a, b) = (int(cmd[1]), int(cmd[2]), int(cmd[3]), int(cmd[4]))
		this = head
		while this:
			if this.data == r:
				root = this
			this = this.next
		nop = None
		if root.next.data == t:
			sub_tree = root.next
			nop = 'next'
		else:
			sub_tree = root.prev
			nop = 'prev'
		if nop == 'next':
			nthis = sub_tree
			while nthis:
				nthis.value += a ** b + (a + 1) ** b + (b + 1) ** a
				nthis = nthis.next
		if nop == 'prev':
			pthis = sub_tree
			while pthis:
				pthis.value += a ** b + (a + 1) ** b + (b + 1) ** a
				pthis = pthis.prev
	if cmd[0] == 'R':
		(r, t, m) = (int(cmd[1]), int(cmd[2]), int(cmd[3]))
		this = head
		while this:
			if this.data == r:
				root = this
			this = this.next
		nop = None
		if root.next:
			if root.next.data == t:
				sub_tree = root.next
				nop = 'next'
		else:
			sub_tree = root.prev
			nop = 'prev'
		s = 0
		if nop == 'next':
			nthis = sub_tree
			while nthis:
				s += nthis.value
				nthis = nthis.next
		if nop == 'prev':
			pthis = sub_tree
			while pthis:
				s += pthis.value
				pthis = pthis.prev
		print(s % m)


node_count = int(input())
neighbors = [[] for _ in range(node_count)]
values = [0 for _ in range(node_count)]
for x in range(node_count - 1):
	(n1, n2) = (int(x) - 1 for x in input().split())
	neighbors[n1].append(n2)
	neighbors[n2].append(n1)

def add_to_tree(root, tree, amt):
	stack = [(False, root)]
	visited = set()
	while stack:
		(is_child, node) = stack.pop()
		is_child = is_child or node == tree
		if is_child:
			values[node] += amt
		visited.add(node)
		stack.extend(((is_child, n) for n in neighbors[node] if n not in visited))

def sum_tree(root, tree, mod):
	stack = [(False, root)]
	visited = set()
	total = 0
	while stack:
		(is_child, node) = stack.pop()
		is_child = is_child or node == tree
		if is_child:
			total = (total + values[node]) % mod
		visited.add(node)
		stack.extend(((is_child, n) for n in neighbors[node] if n not in visited))
	return total
for x in range(int(input())):
	(q, *nums) = input().split()
	nums = [int(num) for num in nums]
	r = nums[0] - 1
	t = nums[1] - 1
	if q == 'U':
		(a, b) = nums[2:]
		add_amount = a * b + (a + 1) ** b + (b + 1) ** a
		add_to_tree(r, t, add_amount)
	elif q == 'R':
		print(sum_tree(r, t, nums[2]))


from collections import defaultdict
import sys
N = int(input())
edges = defaultdict(lambda : set())
values = [0 for n in range(N)]
for _ in range(N - 1):
	(x, y) = [int(n) for n in input().split()]
	edges[x - 1].add(y - 1)
	edges[y - 1].add(x - 1)
Q = int(input())

def find_parent_of(r, t):
	visited = set()
	remainder = [r]
	while remainder:
		i = remainder.pop()
		visited.add(i)
		for child in edges[i]:
			if child == t:
				return i
			elif child not in visited:
				remainder.append(child)

def traverse(parent, t):
	yield t
	for child in edges[t]:
		if child != parent:
			yield from traverse(t, child)

def traverse_rooted(r, t):
	parent = find_parent_of(r, t)
	yield from traverse(parent, t)

def update(r, t, a, b):
	for i in traverse_rooted(r, t):
		values[i] += a * b + (a + 1) ** b + (b + 1) ** a

def report(r, t, m):
	total = 0
	for i in traverse_rooted(r, t):
		total += values[i]
	return total % m
for _ in range(Q):
	(op, rest) = input().split(' ', 1)
	if op == 'U':
		(r, t, a, b) = [int(v) for v in rest.split()]
		update(r - 1, t - 1, a, b)
	elif op == 'R':
		(r, t, m) = [int(v) for v in rest.split()]
		print(report(r - 1, t - 1, m))


def implementOps(n, ops):
	arr = [0] * n
	res = []
	for op in ops:
		z = op[0]
		if z == 'U':
			(x, y, a, b) = list(map(int, op[1:]))
			t = a ** b + (a + 1) ** b + (b + 1) ** a
			if int(x) > int(y):
				for i in range(y):
					arr[i] += t
			else:
				for i in range(x, len(arr)):
					arr[i] += t
		else:
			(x, y, m) = list(map(int, op[1:]))
			if int(x) > int(y):
				res.append(sum(arr[:y]) % m)
			else:
				res.append(sum(arr[x:]) % m)
	return res
n = int(input())
edges = []
for i in range(n - 1):
	edges.append(list(map(int, input().split())))
q = int(input())
ops = []
for i in range(q):
	ops.append(input().split())
res = implementOps(n, ops)
for v in res:
	print(v)


N = int(input())
T = [[] for _ in range(N)]
for _ in range(N - 1):
	(a, b) = [int(_) - 1 for _ in input().split()]
	T[a].append(b)
	T[b].append(a)
S = [None] * N
stack = [(0, None)]
L = []
while stack:
	(i, p) = stack.pop()
	L.append(i)
	S[i] = [p, [], [], 0]
	for c in T[i]:
		if c != p:
			stack.append((c, i))
			S[i][1].append(c)
for i in L[::-1]:
	S[i][3] = 1 + sum((S[c][3] for c in S[i][1]))

def update(r, t, a, b):
	c = getTopChild(t, r)
	if c == None:
		S[t][2].append((1, a, b))
	else:
		S[0][2].append((1, a, b))
		S[c][2].append((-1, a, b))

def request(r, t, m):
	c = getTopChild(t, r)
	if c == None:
		return getCount(t, m)
	else:
		return (getCount(0, m) - getCount(c, m)) % m

def getTopChild(r, t):
	c = t
	while c != None and S[c][0] != r:
		c = S[c][0]
	return c

def getCount(r, m):
	count = 0
	p = S[r][0]
	while p != None:
		for (s, a, b) in S[p][2]:
			count += S[r][3] * s * (pow(a, b, m) + pow(a + 1, b, m) + pow(b + 1, a, m))
		p = S[p][0]
	stack = [r]
	while stack:
		c = stack.pop()
		for (s, a, b) in S[c][2]:
			count += S[c][3] * s * (pow(a, b, m) + pow(a + 1, b, m) + pow(b + 1, a, m))
		stack.extend(S[c][1])
	return count % m
Q = int(input())
for _ in range(Q):
	q = input().split()
	if q[0] == 'U':
		(r, t, a, b) = [int(_) for _ in q[1:]]
		update(r - 1, t - 1, a, b)
	elif q[0] == 'R':
		(r, t, m) = [int(_) for _ in q[1:]]
		print(request(r - 1, t - 1, m))


class Node:

	def __init__(self, id):
		self.id = id
		self.near = []
		self.val = 0

	def update(self, val, parent):
		self.val += val
		for child in filter(lambda x: x != parent, self.near):
			child.update(val, self)

	def report(self, parent):
		acc = self.val
		for child in filter(lambda x: x != parent, self.near):
			acc += child.report(self)
		return acc

def calcVal(a, b):
	return a ** b + (a + 1) ** b + (b + 1) ** a

def findSubParent(root, callingParent, target):
	if root == target:
		return callingParent
	for child in filter(lambda x: x != callingParent, root.near):
		found = findSubParent(child, root, target)
		if found != None:
			return found
	return None
numNodes = int(input())
nodes = {i: Node(i) for i in range(1, numNodes + 1)}
for i in range(numNodes - 1):
	(a, b) = [int(val) for val in input().split()]
	nodes[a].near.append(nodes[b])
	nodes[b].near.append(nodes[a])
numOps = int(input())
for i in range(numOps):
	args = input().split()
	if args[0] == 'U':
		(rootNode, subTreeNode) = [nodes[int(val)] for val in args[1:3]]
		parent = findSubParent(rootNode, None, subTreeNode)
		(a, b) = [int(val) for val in args[3:5]]
		updateVal = calcVal(a, b)
		subTreeNode.update(updateVal, parent)
	else:
		(rootNode, subTreeNode) = [nodes[int(val)] for val in args[1:3]]
		parent = findSubParent(rootNode, None, subTreeNode)
		modulo = int(args[3])
		print(subTreeNode.report(parent) % modulo)