Chinese Version

Russian Version

You are given a tree with N nodes and each has a value associated with it. You are given Q queries, each of which is either an update or a retrieval operation. 

The update query is of the format

i j X

This means you'd have to add a GP series to the nodes which lie in the path from node i to node j (both inclusive) with first term of the GP as X on node i and the common ratio as R (given in the input)

The retrieval query is of the format

i j

You need to return the sum of the node values (S) lying in the path from node i to node j modulo 100711433. 

Input Format 

The first line contains two integers (N and R respectively) separated by a space. 

In the next N-1 lines, the$ i^{th}$ line describes the $i^{th} $edge: a line with two integers a b separated by a single space denotes an edge between a, b. 

The next line contains 2 space separated integers (U and Q respectively) representing the number of Update and Query operations to follow. 

U lines follow. Each of the next U lines contains 3 space separated integers (i,j, and X respectively). 

Each of the next Q lines contains 2 space separated integers, i and j respectively. 

Output Format 

It contains exactly Q lines and each line containing the answer of the$ i^{th}$ query.

Constraints

2 <= N <= 100000 

2 <= R <= $10^{9}$ 

1 <= U <= 100000 

1 <= Q <= 100000 

1 <= X <= 10 

1 <= a, b, i, j <= N  

Sample Input  

6 2
1 2
1 4
2 6
4 5
4 3
2 2
1 6 3
5 3 5
6 4
5 1

Sample Output

31
18

Explanation

The node values after the first updation becomes :  

3 6 0 0 0 12  

The node values after second updation becomes :  

3 6 20 10 5 12  

Answer to Query #1: 12 + 6 + 3 + 10 = 31 

Answer to Query #2: 5 + 10 +3 = 18

Difficulty: MEDIUM_HARD
Tags: Data structures
Skill types: Data structures

Starter code:

Solutions:
class Node:

	def __init__(self, data):
		self.data = data
		self.neighbors = []

	def add(self, neighbor):
		self.neighbors.append(neighbor)

	def __str__(self):
		return '(' + str(self.data) + ', ' + str(self.parent) + ')'

def path(a, b):
	s = set()
	q = [[b]]
	s.add(b)
	i = 0
	while i < len(q):
		p = q[i]
		if p[0] == a:
			return p
		for n in nodes[p[0]].neighbors:
			if n not in s:
				s.add(n)
				q.append([n] + p)
		i += 1
	raise Exception
(n, r) = map(int, input().split())
nodes = [Node(0) for _ in range(n)]
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	nodes[a - 1].add(b - 1)
	nodes[b - 1].add(a - 1)
(u, q) = map(int, input().split())
for _ in range(u):
	(i, j, x) = map(int, input().split())
	for asdf in path(i - 1, j - 1):
		node = nodes[asdf]
		node.data += x
		x *= r
for _ in range(q):
	(i, j) = map(int, input().split())
	print(sum((nodes[node].data for node in path(i - 1, j - 1))) % 100711433)


class Node:

	def __init__(self, id, val):
		self.id = id
		self.value = val
		self.connected_nodes = set()

	def add_node(self, node):
		self.connected_nodes.add(node)
		node.connected_nodes.add(self)

	def __str__(self):
		return str(self.id) + ' (' + str(self.value) + ')'
nodeMap = {}

def dfs(nodeF, nodeL):
	depth_stack = []
	visited_nodes = set()
	result_path = []
	parent_map = {}
	depth_stack.append(nodeF)
	visited_nodes.add(nodeF)
	while depth_stack:
		next = depth_stack.pop()
		if next is nodeL:
			break
		for neighbor in next.connected_nodes:
			if neighbor not in visited_nodes:
				visited_nodes.add(neighbor)
				depth_stack.append(neighbor)
				parent_map[neighbor] = next
	result_path.append(nodeL)
	next_parent = parent_map[nodeL]
	while next_parent in parent_map:
		result_path.append(next_parent)
		next_parent = parent_map[next_parent]
	result_path.append(next_parent)
	return result_path

def find_path(nodeF, nodeL):
	return dfs(nodeF, nodeL)
line = input().split(' ')
n = int(line[0])
r = int(line[1])

def get_node_safe(a):
	if a in nodeMap:
		return nodeMap[a]
	else:
		nodeA = Node(a, 0)
		nodeMap[a] = nodeA
		return nodeA
for i in range(n - 1):
	line = input().split(' ')
	a = int(line[0])
	b = int(line[1])
	nodeA = get_node_safe(a)
	nodeB = get_node_safe(b)
	nodeA.add_node(nodeB)
line = input().split(' ')
u = int(line[0])
q = int(line[1])
for i in range(u):
	line = input().split(' ')
	s = int(line[0])
	t = int(line[1])
	x = int(line[2])
	nodeS = nodeMap[s]
	nodeT = nodeMap[t]
	found_path = find_path(nodeS, nodeT)
	for each in reversed(found_path):
		each.value = each.value + x
		x = x * r
for i in range(q):
	line = input().split(' ')
	s = int(line[0])
	t = int(line[1])
	nodeS = nodeMap[s]
	nodeT = nodeMap[t]
	found_path = find_path(nodeS, nodeT)
	res = 0
	for each in reversed(found_path):
		res = res + each.value
		res = res % 100711433
	print(res)


(n, r) = input().strip().split(' ')
(n, r) = [int(n), int(r)]
g = {}
gv = {}
edge = []
for c in range(n - 1):
	(i, j) = input().strip().split(' ')
	edge.append([i, j])
for c in range(1, n + 1):
	if str(c) not in g.keys():
		g[str(c)] = []
		gv[str(c)] = 0
	for e in edge:
		if e[0] == str(c):
			g[str(c)].append(e[1])
		elif e[1] == str(c):
			g[str(c)].append(e[0])

def find_path(graph, start, end, path=[]):
	path = path + [start]
	if start == end:
		return path
	if start not in graph.keys():
		return None
	for node in graph[start]:
		if node not in path:
			newpath = find_path(graph, node, end, path)
			if newpath:
				return newpath
	return None
(u, p) = input().strip().split(' ')
(u, p) = [int(u), int(p)]
for c in range(u):
	(i, j, x) = input().strip().split(' ')
	(i, j, x) = [str(i), str(j), int(x)]
	path = find_path(g, i, j)
	for pa in path:
		gv[pa] = gv[pa] + x
		x *= r
for c in range(p):
	(i, j) = input().strip().split(' ')
	path = find_path(g, i, j)
	s = 0
	for p in path:
		s += gv[p]
	print(s % 100711433)


import sys
sys.setrecursionlimit(10000000)
(n, r) = input().strip().split(' ')
(n, r) = [int(n), int(r)]
g = {}
gv = {}
edge = []
for c in range(1, n):
	(i, j) = input().strip().split(' ')
	if i not in g.keys():
		g[i] = []
		gv[i] = 0
	if j not in g.keys():
		g[j] = []
		gv[j] = 0
	g[i].append(j)
	g[j].append(i)

def find_path(graph, start, end, path=[]):
	path = path + [start]
	if start == end:
		return path
	if start not in graph.keys():
		return None
	for node in graph[start]:
		if node not in path:
			newpath = find_path(graph, node, end, path)
			if newpath:
				return newpath
	return None
(u, p) = input().strip().split(' ')
(u, p) = [int(u), int(p)]
for c in range(u):
	(i, j, x) = input().strip().split(' ')
	(i, j, x) = [str(i), str(j), int(x)]
	path = find_path(g, i, j)
	for pa in path:
		gv[pa] = gv[pa] + x
		x *= r
for c in range(p):
	(i, j) = input().strip().split(' ')
	path = find_path(g, i, j)
	s = 0
	for p in path:
		s += gv[p]
	print(s % 100711433)


import sys
sys.setrecursionlimit(10000000)
(n, r) = input().strip().split(' ')
(n, r) = [int(n), int(r)]
g = {}
gv = {}
edge = []
for c in range(1, n):
	(i, j) = input().strip().split(' ')
	if i not in g.keys():
		g[i] = []
		gv[i] = 0
	if j not in g.keys():
		g[j] = []
		gv[j] = 0
	g[i].append(j)
	g[j].append(i)

def find_path(graph, start, end, path=[]):
	path = path + [start]
	if start == end:
		return path
	if start not in graph.keys():
		return None
	for node in graph[start]:
		if node not in path:
			newpath = find_path(graph, node, end, path)
			if newpath:
				return newpath
	return None
(u, p) = input().strip().split(' ')
(u, p) = [int(u), int(p)]
for c in range(u):
	(i, j, x) = input().strip().split(' ')
	(i, j, x) = [str(i), str(j), int(x)]
	path = find_path(g, i, j)
	for pa in path:
		gv[pa] = gv[pa] + x
		x *= r
for c in range(p):
	(i, j) = input().strip().split(' ')
	path = find_path(g, i, j)
	s = 0
	for p in path:
		s += gv[p]
	print(s % 100711433)


import sys
sys.setrecursionlimit(10000000)
(n, r) = input().strip().split(' ')
(n, r) = [int(n), int(r)]
g = {}
gv = {}
edge = []
for c in range(1, n):
	(i, j) = input().strip().split(' ')
	if i not in g.keys():
		g[i] = []
		gv[i] = 0
	if j not in g.keys():
		g[j] = []
		gv[j] = 0
	g[i].append(j)
	g[j].append(i)

def find_path(graph, start, end, path=[]):
	path = path + [start]
	if start == end:
		return path
	if start not in graph.keys():
		return None
	for node in graph[start]:
		if node not in path:
			newpath = find_path(graph, node, end, path)
			if newpath:
				return newpath
	return None
(u, p) = input().strip().split(' ')
(u, p) = [int(u), int(p)]
for c in range(u):
	(i, j, x) = input().strip().split(' ')
	(i, j, x) = [str(i), str(j), int(x)]
	path = find_path(g, i, j)
	for pa in path:
		gv[pa] = gv[pa] + x
		x *= r
for c in range(p):
	(i, j) = input().strip().split(' ')
	path = find_path(g, i, j)
	s = 0
	for p in path:
		s += gv[p]
	print(s % 100711433)


import sys
sys.setrecursionlimit(10000000)
(n, r) = input().strip().split(' ')
(n, r) = [int(n), int(r)]
g = {}
gv = {}
edge = []
for c in range(1, n):
	(i, j) = input().strip().split(' ')
	if i not in g.keys():
		g[i] = []
		gv[i] = 0
	if j not in g.keys():
		g[j] = []
		gv[j] = 0
	g[i].append(j)
	g[j].append(i)

def find_path(graph, start, end, path=[]):
	path = path + [start]
	if start == end:
		return path
	if start not in graph.keys():
		return None
	for node in graph[start]:
		if node not in path:
			newpath = find_path(graph, node, end, path)
			if newpath:
				return newpath
	return None
(u, p) = input().strip().split(' ')
(u, p) = [int(u), int(p)]
for c in range(u):
	(i, j, x) = input().strip().split(' ')
	(i, j, x) = [str(i), str(j), int(x)]
	path = find_path(g, i, j)
	for pa in path:
		gv[pa] = gv[pa] + x
		x *= r
for c in range(p):
	(i, j) = input().strip().split(' ')
	path = find_path(g, i, j)
	s = 0
	for p in path:
		s += gv[p]
	print(s % 100711433)


import sys
sys.setrecursionlimit(10000000)
(n, r) = input().strip().split(' ')
(n, r) = [int(n), int(r)]
g = {}
gv = {}
edge = []
for c in range(1, n):
	(i, j) = input().strip().split(' ')
	if i not in g.keys():
		g[i] = []
		gv[i] = 0
	if j not in g.keys():
		g[j] = []
		gv[j] = 0
	g[i].append(j)
	g[j].append(i)

def find_path(graph, start, end, path=[]):
	path = path + [start]
	if start == end:
		return path
	if start not in graph.keys():
		return None
	for node in graph[start]:
		if node not in path:
			newpath = find_path(graph, node, end, path)
			if newpath:
				return newpath
	return None
(u, p) = input().strip().split(' ')
(u, p) = [int(u), int(p)]
for c in range(u):
	(i, j, x) = input().strip().split(' ')
	(i, j, x) = [str(i), str(j), int(x)]
	path = find_path(g, i, j)
	for pa in path:
		gv[pa] = gv[pa] + x
		x *= r
for c in range(p):
	(i, j) = input().strip().split(' ')
	path = find_path(g, i, j)
	s = 0
	for p in path:
		s += gv[p]
	print(s % 100711433)


import sys
sys.setrecursionlimit(10000000)
(n, r) = input().strip().split(' ')
(n, r) = [int(n), int(r)]
g = {}
gv = {}
edge = []
for c in range(1, n):
	(i, j) = input().strip().split(' ')
	if i not in g.keys():
		g[i] = []
		gv[i] = 0
	if j not in g.keys():
		g[j] = []
		gv[j] = 0
	g[i].append(j)
	g[j].append(i)

def find_path(graph, start, end, path=[]):
	path = path + [start]
	if start == end:
		return path
	if start not in graph.keys():
		return None
	for node in graph[start]:
		if node not in path:
			newpath = find_path(graph, node, end, path)
			if newpath:
				return newpath
	return None
(u, p) = input().strip().split(' ')
(u, p) = [int(u), int(p)]
for c in range(u):
	(i, j, x) = input().strip().split(' ')
	(i, j, x) = [str(i), str(j), int(x)]
	path = find_path(g, i, j)
	for pa in path:
		gv[pa] = gv[pa] + x
		x *= r
for c in range(p):
	(i, j) = input().strip().split(' ')
	path = find_path(g, i, j)
	s = 0
	for p in path:
		s += gv[p]
	print(s % 100711433)


import sys
sys.setrecursionlimit(10000000)
(n, r) = input().strip().split(' ')
(n, r) = [int(n), int(r)]
g = {}
gv = {}
edge = []
for c in range(1, n):
	(i, j) = input().strip().split(' ')
	if i not in g.keys():
		g[i] = []
		gv[i] = 0
	if j not in g.keys():
		g[j] = []
		gv[j] = 0
	g[i].append(j)
	g[j].append(i)

def find_path(graph, start, end, path=[]):
	path = path + [start]
	if start == end:
		return path
	if start not in graph.keys():
		return None
	for node in graph[start]:
		if node not in path:
			newpath = find_path(graph, node, end, path)
			if newpath:
				return newpath
	return None
(u, p) = input().strip().split(' ')
(u, p) = [int(u), int(p)]
for c in range(u):
	(i, j, x) = input().strip().split(' ')
	(i, j, x) = [str(i), str(j), int(x)]
	path = find_path(g, i, j)
	for pa in path:
		gv[pa] = gv[pa] + x
		x *= r
for c in range(p):
	(i, j) = input().strip().split(' ')
	path = find_path(g, i, j)
	s = 0
	for p in path:
		s += gv[p]
	print(s % 100711433)


import sys
sys.setrecursionlimit(10000000)
(n, r) = input().strip().split(' ')
(n, r) = [int(n), int(r)]
g = {}
gv = {}
edge = []
for c in range(1, n):
	(i, j) = input().strip().split(' ')
	if i not in g.keys():
		g[i] = []
		gv[i] = 0
	if j not in g.keys():
		g[j] = []
		gv[j] = 0
	g[i].append(j)
	g[j].append(i)

def find_path(graph, start, end, path=[]):
	path = path + [start]
	if start == end:
		return path
	if start not in graph.keys():
		return None
	for node in graph[start]:
		if node not in path:
			newpath = find_path(graph, node, end, path)
			if newpath:
				return newpath
	return None
(u, p) = input().strip().split(' ')
(u, p) = [int(u), int(p)]
for c in range(u):
	(i, j, x) = input().strip().split(' ')
	(i, j, x) = [str(i), str(j), int(x)]
	path = find_path(g, i, j)
	for pa in path:
		gv[pa] = gv[pa] + x
		x *= r
for c in range(p):
	(i, j) = input().strip().split(' ')
	path = find_path(g, i, j)
	s = 0
	for p in path:
		s += gv[p]
	print(s % 100711433)


import sys
sys.setrecursionlimit(10000000)
(n, r) = input().strip().split(' ')
(n, r) = [int(n), int(r)]
g = {}
gv = {}
edge = []
for c in range(1, n):
	(i, j) = input().strip().split(' ')
	if i not in g.keys():
		g[i] = []
		gv[i] = 0
	if j not in g.keys():
		g[j] = []
		gv[j] = 0
	g[i].append(j)
	g[j].append(i)

def find_path(graph, start, end, path=[]):
	path = path + [start]
	if start == end:
		return path
	if start not in graph.keys():
		return None
	for node in graph[start]:
		if node not in path:
			newpath = find_path(graph, node, end, path)
			if newpath:
				return newpath
	return None
(u, p) = input().strip().split(' ')
(u, p) = [int(u), int(p)]
for c in range(u):
	(i, j, x) = input().strip().split(' ')
	(i, j, x) = [str(i), str(j), int(x)]
	path = find_path(g, i, j)
	for pa in path:
		gv[pa] = gv[pa] + x
		x *= r
for c in range(p):
	(i, j) = input().strip().split(' ')
	path = find_path(g, i, j)
	s = 0
	for p in path:
		s += gv[p]
	print(s % 100711433)


def findPath(adj, start, end, path):
	stack = [start]
	visited = {start: True}
	parent = {}
	while len(stack) > 0:
		if stack[-1] == end:
			break
		cur = stack.pop()
		for neig in adj[cur]:
			if neig not in visited:
				stack.append(neig)
				visited[neig] = True
				parent[neig] = cur
	cur = end
	while cur != start:
		path.append(cur)
		cur = parent[cur]
	path.append(start)

def solve(adj, updates, queries):
	n = len(adj) + 1
	values = [0] * n
	for (start, end, x) in updates:
		path = []
		findPath(adj, start, end, path)
		w = x
		for i in reversed(range(len(path))):
			values[path[i]] += w
			w *= r
	result = []
	for (start, end) in queries:
		path = []
		findPath(adj, start, end, path)
		total = 0
		for i in range(len(path)):
			total += values[path[i]]
		result.append(total % 100711433)
	return result
(n, r) = map(int, input().rstrip().split())
adj = [[] for _ in range(n)]
for _ in range(n - 1):
	(a, b) = map(int, input().rstrip().split())
	adj[a - 1].append(b - 1)
	adj[b - 1].append(a - 1)
(num_u, num_q) = map(int, input().rstrip().split())
updates = []
queries = []
for _ in range(num_u):
	(a, b, x) = map(int, input().rstrip().split())
	updates.append([a - 1, b - 1, x])
for _ in range(num_q):
	(a, b) = map(int, input().rstrip().split())
	queries.append([a - 1, b - 1])
result = solve(adj, updates, queries)
print(*result, sep='\n')


import sys
sys.setrecursionlimit(10000000)
(n, r) = input().strip().split(' ')
(n, r) = [int(n), int(r)]
g = {}
gv = {}
edge = []
for c in range(1, n):
	(i, j) = input().strip().split(' ')
	if i not in g.keys():
		g[i] = []
		gv[i] = 0
	if j not in g.keys():
		g[j] = []
		gv[j] = 0
	g[i].append(j)
	g[j].append(i)

def find_path(graph, start, end, path=[]):
	path = path + [start]
	if start == end:
		return path
	if start not in graph.keys():
		return None
	for node in graph[start]:
		if node not in path:
			newpath = find_path(graph, node, end, path)
			if newpath:
				return newpath
	return None
(u, p) = input().strip().split(' ')
(u, p) = [int(u), int(p)]
for c in range(u):
	(i, j, x) = input().strip().split(' ')
	(i, j, x) = [str(i), str(j), int(x)]
	path = find_path(g, i, j)
	for pa in path:
		gv[pa] = gv[pa] + x
		x *= r
for c in range(p):
	(i, j) = input().strip().split(' ')
	path = find_path(g, i, j)
	s = 0
	for p in path:
		s += gv[p]
	print(s % 100711433)


import sys
sys.setrecursionlimit(10000000)
(n, r) = input().strip().split(' ')
(n, r) = [int(n), int(r)]
g = {}
gv = {}
edge = []
for c in range(1, n):
	(i, j) = input().strip().split(' ')
	if i not in g.keys():
		g[i] = []
		gv[i] = 0
	if j not in g.keys():
		g[j] = []
		gv[j] = 0
	g[i].append(j)
	g[j].append(i)

def find_path(graph, start, end, path=[]):
	path = path + [start]
	if start == end:
		return path
	if start not in graph.keys():
		return None
	for node in graph[start]:
		if node not in path:
			newpath = find_path(graph, node, end, path)
			if newpath:
				return newpath
	return None
(u, p) = input().strip().split(' ')
(u, p) = [int(u), int(p)]
for c in range(u):
	(i, j, x) = input().strip().split(' ')
	(i, j, x) = [str(i), str(j), int(x)]
	path = find_path(g, i, j)
	for pa in path:
		gv[pa] = gv[pa] + x
		x *= r
for c in range(p):
	(i, j) = input().strip().split(' ')
	path = find_path(g, i, j)
	s = 0
	for p in path:
		s += gv[p]
	print(s % 100711433)


import sys
sys.setrecursionlimit(10000000)
(n, r) = input().strip().split(' ')
(n, r) = [int(n), int(r)]
g = {}
gv = {}
edge = []
for c in range(1, n):
	(i, j) = input().strip().split(' ')
	if i not in g.keys():
		g[i] = []
		gv[i] = 0
	if j not in g.keys():
		g[j] = []
		gv[j] = 0
	g[i].append(j)
	g[j].append(i)

def find_path(graph, start, end, path=[]):
	path = path + [start]
	if start == end:
		return path
	if start not in graph.keys():
		return None
	for node in graph[start]:
		if node not in path:
			newpath = find_path(graph, node, end, path)
			if newpath:
				return newpath
	return None
(u, p) = input().strip().split(' ')
(u, p) = [int(u), int(p)]
for c in range(u):
	(i, j, x) = input().strip().split(' ')
	(i, j, x) = [str(i), str(j), int(x)]
	path = find_path(g, i, j)
	for pa in path:
		gv[pa] = gv[pa] + x
		x *= r
for c in range(p):
	(i, j) = input().strip().split(' ')
	path = find_path(g, i, j)
	s = 0
	for p in path:
		s += gv[p]
	print(s % 100711433)


import sys
inputs = sys.stdin.readlines()
(n, r) = inputs[0].split()
(n, r) = (int(n), int(r))
graph = {}
for i in range(0, n):
	graph[i] = []
vals = [0 for i in graph]
for i in range(1, n):
	(index, index2) = map(lambda x: int(x) - 1, inputs[i].split())
	graph[index].append(index2)
	graph[index2].append(index)
(update, query) = map(int, inputs[n].split())
import queue

def ucs(start, end):
	visited = set()
	q = queue.PriorityQueue()
	q.put((0, start, [start]))
	while not q.empty():
		(cost, current, path) = q.get()
		if current not in visited:
			visited.add(current)
			if current == end:
				return path
			for child in graph[current]:
				if child not in visited:
					q.put((cost + 1, child, path + [child]))
for i in range(n + 1, n + update + 1):
	(start, end, first) = map(int, inputs[i].split())
	begin = start - 1
	yeet = end - 1
	path = ucs(begin, yeet)
	for node in path:
		vals[node] = vals[node] + first
		first *= r
for i in range(n + update + 1, n + update + 1 + query):
	(start, end) = map(int, inputs[i].split())
	begin = start - 1
	yeet = end - 1
	path = ucs(begin, yeet)
	s = 0
	for node in path:
		s += vals[node]
	print(s % 100711433)


import sys
sys.setrecursionlimit(10000000)
(n, r) = input().strip().split(' ')
(n, r) = [int(n), int(r)]
g = {}
gv = {}
edge = []
for c in range(1, n):
	(i, j) = input().strip().split(' ')
	if i not in g.keys():
		g[i] = []
		gv[i] = 0
	if j not in g.keys():
		g[j] = []
		gv[j] = 0
	g[i].append(j)
	g[j].append(i)

def find_path(graph, start, end, path=[]):
	path = path + [start]
	if start == end:
		return path
	if start not in graph.keys():
		return None
	for node in graph[start]:
		if node not in path:
			newpath = find_path(graph, node, end, path)
			if newpath:
				return newpath
	return None
(u, p) = input().strip().split(' ')
(u, p) = [int(u), int(p)]
for c in range(u):
	(i, j, x) = input().strip().split(' ')
	(i, j, x) = [str(i), str(j), int(x)]
	path = find_path(g, i, j)
	for pa in path:
		gv[pa] = gv[pa] + x
		x *= r
for c in range(p):
	(i, j) = input().strip().split(' ')
	path = find_path(g, i, j)
	s = 0
	for p in path:
		s += gv[p]
	print(s % 100711433)


import sys
sys.setrecursionlimit(10000000)
(n, r) = input().strip().split(' ')
(n, r) = [int(n), int(r)]
g = {}
gv = {}
edge = []
for c in range(1, n):
	(i, j) = input().strip().split(' ')
	if i not in g.keys():
		g[i] = []
		gv[i] = 0
	if j not in g.keys():
		g[j] = []
		gv[j] = 0
	g[i].append(j)
	g[j].append(i)

def find_path(graph, start, end, path=[]):
	path = path + [start]
	if start == end:
		return path
	if start not in graph.keys():
		return None
	for node in graph[start]:
		if node not in path:
			newpath = find_path(graph, node, end, path)
			if newpath:
				return newpath
	return None
(u, p) = input().strip().split(' ')
(u, p) = [int(u), int(p)]
for c in range(u):
	(i, j, x) = input().strip().split(' ')
	(i, j, x) = [str(i), str(j), int(x)]
	path = find_path(g, i, j)
	for pa in path:
		gv[pa] = gv[pa] + x
		x *= r
for c in range(p):
	(i, j) = input().strip().split(' ')
	path = find_path(g, i, j)
	s = 0
	for p in path:
		s += gv[p]
	print(s % 100711433)


import sys
sys.setrecursionlimit(10000000)
(n, r) = input().strip().split(' ')
(n, r) = [int(n), int(r)]
g = {}
gv = {}
edge = []
for c in range(1, n):
	(i, j) = input().strip().split(' ')
	if i not in g.keys():
		g[i] = []
		gv[i] = 0
	if j not in g.keys():
		g[j] = []
		gv[j] = 0
	g[i].append(j)
	g[j].append(i)

def find_path(graph, start, end, path=[]):
	path = path + [start]
	if start == end:
		return path
	if start not in graph.keys():
		return None
	for node in graph[start]:
		if node not in path:
			newpath = find_path(graph, node, end, path)
			if newpath:
				return newpath
	return None
(u, p) = input().strip().split(' ')
(u, p) = [int(u), int(p)]
for c in range(u):
	(i, j, x) = input().strip().split(' ')
	(i, j, x) = [str(i), str(j), int(x)]
	path = find_path(g, i, j)
	for pa in path:
		gv[pa] = gv[pa] + x
		x *= r
for c in range(p):
	(i, j) = input().strip().split(' ')
	path = find_path(g, i, j)
	s = 0
	for p in path:
		s += gv[p]
	print(s % 100711433)


import sys
sys.setrecursionlimit(10000000)
(n, r) = input().strip().split(' ')
(n, r) = [int(n), int(r)]
g = {}
gv = {}
edge = []
for c in range(1, n):
	(i, j) = input().strip().split(' ')
	if i not in g.keys():
		g[i] = []
		gv[i] = 0
	if j not in g.keys():
		g[j] = []
		gv[j] = 0
	g[i].append(j)
	g[j].append(i)

def find_path(graph, start, end, path=[]):
	path = path + [start]
	if start == end:
		return path
	if start not in graph.keys():
		return None
	for node in graph[start]:
		if node not in path:
			newpath = find_path(graph, node, end, path)
			if newpath:
				return newpath
	return None
(u, p) = input().strip().split(' ')
(u, p) = [int(u), int(p)]
for c in range(u):
	(i, j, x) = input().strip().split(' ')
	(i, j, x) = [str(i), str(j), int(x)]
	path = find_path(g, i, j)
	for pa in path:
		gv[pa] = gv[pa] + x
		x *= r
for c in range(p):
	(i, j) = input().strip().split(' ')
	path = find_path(g, i, j)
	s = 0
	for p in path:
		s += gv[p]
	print(s % 100711433)


import sys
sys.setrecursionlimit(10000000)
(n, r) = input().strip().split(' ')
(n, r) = [int(n), int(r)]
g = {}
gv = {}
edge = []
for c in range(1, n):
	(i, j) = input().strip().split(' ')
	if i not in g.keys():
		g[i] = []
		gv[i] = 0
	if j not in g.keys():
		g[j] = []
		gv[j] = 0
	g[i].append(j)
	g[j].append(i)

def find_path(graph, start, end, path=[]):
	path = path + [start]
	if start == end:
		return path
	if start not in graph.keys():
		return None
	for node in graph[start]:
		if node not in path:
			newpath = find_path(graph, node, end, path)
			if newpath:
				return newpath
	return None
(u, p) = input().strip().split(' ')
(u, p) = [int(u), int(p)]
for c in range(u):
	(i, j, x) = input().strip().split(' ')
	(i, j, x) = [str(i), str(j), int(x)]
	path = find_path(g, i, j)
	for pa in path:
		gv[pa] = gv[pa] + x
		x *= r
for c in range(p):
	(i, j) = input().strip().split(' ')
	path = find_path(g, i, j)
	s = 0
	for p in path:
		s += gv[p]
	print(s % 100711433)


import sys
sys.setrecursionlimit(10000000)
(n, r) = input().strip().split(' ')
(n, r) = [int(n), int(r)]
g = {}
gv = {}
edge = []
for c in range(1, n):
	(i, j) = input().strip().split(' ')
	if i not in g.keys():
		g[i] = []
		gv[i] = 0
	if j not in g.keys():
		g[j] = []
		gv[j] = 0
	g[i].append(j)
	g[j].append(i)

def find_path(graph, start, end, path=[]):
	path = path + [start]
	if start == end:
		return path
	if start not in graph.keys():
		return None
	for node in graph[start]:
		if node not in path:
			newpath = find_path(graph, node, end, path)
			if newpath:
				return newpath
	return None
(u, p) = input().strip().split(' ')
(u, p) = [int(u), int(p)]
for c in range(u):
	(i, j, x) = input().strip().split(' ')
	(i, j, x) = [str(i), str(j), int(x)]
	path = find_path(g, i, j)
	for pa in path:
		gv[pa] = gv[pa] + x
		x *= r
for c in range(p):
	(i, j) = input().strip().split(' ')
	path = find_path(g, i, j)
	s = 0
	for p in path:
		s += gv[p]
	print(s % 100711433)


import sys
sys.setrecursionlimit(10000000)
(n, r) = input().strip().split(' ')
(n, r) = [int(n), int(r)]
g = {}
gv = {}
edge = []
for c in range(1, n):
	(i, j) = input().strip().split(' ')
	if i not in g.keys():
		g[i] = []
		gv[i] = 0
	if j not in g.keys():
		g[j] = []
		gv[j] = 0
	g[i].append(j)
	g[j].append(i)

def find_path(graph, start, end, path=[]):
	path = path + [start]
	if start == end:
		return path
	if start not in graph.keys():
		return None
	for node in graph[start]:
		if node not in path:
			newpath = find_path(graph, node, end, path)
			if newpath:
				return newpath
	return None
(u, p) = input().strip().split(' ')
(u, p) = [int(u), int(p)]
for c in range(u):
	(i, j, x) = input().strip().split(' ')
	(i, j, x) = [str(i), str(j), int(x)]
	path = find_path(g, i, j)
	for pa in path:
		gv[pa] = gv[pa] + x
		x *= r
for c in range(p):
	(i, j) = input().strip().split(' ')
	path = find_path(g, i, j)
	s = 0
	for p in path:
		s += gv[p]
	print(s % 100711433)


import sys
sys.setrecursionlimit(10000000)
(n, r) = input().strip().split(' ')
(n, r) = [int(n), int(r)]
g = {}
gv = {}
edge = []
for c in range(1, n):
	(i, j) = input().strip().split(' ')
	if i not in g.keys():
		g[i] = []
		gv[i] = 0
	if j not in g.keys():
		g[j] = []
		gv[j] = 0
	g[i].append(j)
	g[j].append(i)

def find_path(graph, start, end, path=[]):
	path = path + [start]
	if start == end:
		return path
	if start not in graph.keys():
		return None
	for node in graph[start]:
		if node not in path:
			newpath = find_path(graph, node, end, path)
			if newpath:
				return newpath
	return None
(u, p) = input().strip().split(' ')
(u, p) = [int(u), int(p)]
for c in range(u):
	(i, j, x) = input().strip().split(' ')
	(i, j, x) = [str(i), str(j), int(x)]
	path = find_path(g, i, j)
	for pa in path:
		gv[pa] = gv[pa] + x
		x *= r
for c in range(p):
	(i, j) = input().strip().split(' ')
	path = find_path(g, i, j)
	s = 0
	for p in path:
		s += gv[p]
	print(s % 100711433)


import sys
sys.setrecursionlimit(10000000)
(n, r) = input().strip().split(' ')
(n, r) = [int(n), int(r)]
g = {}
gv = {}
edge = []
for c in range(1, n):
	(i, j) = input().strip().split(' ')
	if i not in g.keys():
		g[i] = []
		gv[i] = 0
	if j not in g.keys():
		g[j] = []
		gv[j] = 0
	g[i].append(j)
	g[j].append(i)

def find_path(graph, start, end, path=[]):
	path = path + [start]
	if start == end:
		return path
	if start not in graph.keys():
		return None
	for node in graph[start]:
		if node not in path:
			newpath = find_path(graph, node, end, path)
			if newpath:
				return newpath
	return None
(u, p) = input().strip().split(' ')
(u, p) = [int(u), int(p)]
for c in range(u):
	(i, j, x) = input().strip().split(' ')
	(i, j, x) = [str(i), str(j), int(x)]
	path = find_path(g, i, j)
	for pa in path:
		gv[pa] = gv[pa] + x
		x *= r
for c in range(p):
	(i, j) = input().strip().split(' ')
	path = find_path(g, i, j)
	s = 0
	for p in path:
		s += gv[p]
	print(s % 100711433)


import sys
sys.setrecursionlimit(10000000)
(n, r) = input().strip().split(' ')
(n, r) = [int(n), int(r)]
g = {}
gv = {}
edge = []
for c in range(1, n):
	(i, j) = input().strip().split(' ')
	if i not in g.keys():
		g[i] = []
		gv[i] = 0
	if j not in g.keys():
		g[j] = []
		gv[j] = 0
	g[i].append(j)
	g[j].append(i)

def find_path(graph, start, end, path=[]):
	path = path + [start]
	if start == end:
		return path
	if start not in graph.keys():
		return None
	for node in graph[start]:
		if node not in path:
			newpath = find_path(graph, node, end, path)
			if newpath:
				return newpath
	return None
(u, p) = input().strip().split(' ')
(u, p) = [int(u), int(p)]
for c in range(u):
	(i, j, x) = input().strip().split(' ')
	(i, j, x) = [str(i), str(j), int(x)]
	path = find_path(g, i, j)
	for pa in path:
		gv[pa] = gv[pa] + x
		x *= r
for c in range(p):
	(i, j) = input().strip().split(' ')
	path = find_path(g, i, j)
	s = 0
	for p in path:
		s += gv[p]
	print(s % 100711433)


import sys
sys.setrecursionlimit(10000000)
(n, r) = input().strip().split(' ')
(n, r) = [int(n), int(r)]
g = {}
gv = {}
edge = []
for c in range(1, n):
	(i, j) = input().strip().split(' ')
	if i not in g.keys():
		g[i] = []
		gv[i] = 0
	if j not in g.keys():
		g[j] = []
		gv[j] = 0
	g[i].append(j)
	g[j].append(i)

def find_path(graph, start, end, path=[]):
	path = path + [start]
	if start == end:
		return path
	if start not in graph.keys():
		return None
	for node in graph[start]:
		if node not in path:
			newpath = find_path(graph, node, end, path)
			if newpath:
				return newpath
	return None
(u, p) = input().strip().split(' ')
(u, p) = [int(u), int(p)]
for c in range(u):
	(i, j, x) = input().strip().split(' ')
	(i, j, x) = [str(i), str(j), int(x)]
	path = find_path(g, i, j)
	for pa in path:
		gv[pa] = gv[pa] + x
		x *= r
for c in range(p):
	(i, j) = input().strip().split(' ')
	path = find_path(g, i, j)
	s = 0
	for p in path:
		s += gv[p]
	print(s % 100711433)


import sys
sys.setrecursionlimit(10000000)
(n, r) = input().strip().split(' ')
(n, r) = [int(n), int(r)]
g = {}
gv = {}
edge = []
for c in range(1, n):
	(i, j) = input().strip().split(' ')
	if i not in g.keys():
		g[i] = []
		gv[i] = 0
	if j not in g.keys():
		g[j] = []
		gv[j] = 0
	g[i].append(j)
	g[j].append(i)

def find_path(graph, start, end, path=[]):
	path = path + [start]
	if start == end:
		return path
	if start not in graph.keys():
		return None
	for node in graph[start]:
		if node not in path:
			newpath = find_path(graph, node, end, path)
			if newpath:
				return newpath
	return None
(u, p) = input().strip().split(' ')
(u, p) = [int(u), int(p)]
for c in range(u):
	(i, j, x) = input().strip().split(' ')
	(i, j, x) = [str(i), str(j), int(x)]
	path = find_path(g, i, j)
	for pa in path:
		gv[pa] = gv[pa] + x
		x *= r
for c in range(p):
	(i, j) = input().strip().split(' ')
	path = find_path(g, i, j)
	s = 0
	for p in path:
		s += gv[p]
	print(s % 100711433)


import sys
sys.setrecursionlimit(10000000)
(n, r) = input().strip().split(' ')
(n, r) = [int(n), int(r)]
g = {}
gv = {}
edge = []
for c in range(1, n):
	(i, j) = input().strip().split(' ')
	if i not in g.keys():
		g[i] = []
		gv[i] = 0
	if j not in g.keys():
		g[j] = []
		gv[j] = 0
	g[i].append(j)
	g[j].append(i)

def find_path(graph, start, end, path=[]):
	path = path + [start]
	if start == end:
		return path
	if start not in graph.keys():
		return None
	for node in graph[start]:
		if node not in path:
			newpath = find_path(graph, node, end, path)
			if newpath:
				return newpath
	return None
(u, p) = input().strip().split(' ')
(u, p) = [int(u), int(p)]
for c in range(u):
	(i, j, x) = input().strip().split(' ')
	(i, j, x) = [str(i), str(j), int(x)]
	path = find_path(g, i, j)
	for pa in path:
		gv[pa] = gv[pa] + x
		x *= r
for c in range(p):
	(i, j) = input().strip().split(' ')
	path = find_path(g, i, j)
	s = 0
	for p in path:
		s += gv[p]
	print(s % 100711433)


import sys
sys.setrecursionlimit(10000000)
(n, r) = input().strip().split(' ')
(n, r) = [int(n), int(r)]
g = {}
gv = {}
edge = []
for c in range(1, n):
	(i, j) = input().strip().split(' ')
	if i not in g.keys():
		g[i] = []
		gv[i] = 0
	if j not in g.keys():
		g[j] = []
		gv[j] = 0
	g[i].append(j)
	g[j].append(i)

def find_path(graph, start, end, path=[]):
	path = path + [start]
	if start == end:
		return path
	if start not in graph.keys():
		return None
	for node in graph[start]:
		if node not in path:
			newpath = find_path(graph, node, end, path)
			if newpath:
				return newpath
	return None
(u, p) = input().strip().split(' ')
(u, p) = [int(u), int(p)]
for c in range(u):
	(i, j, x) = input().strip().split(' ')
	(i, j, x) = [str(i), str(j), int(x)]
	path = find_path(g, i, j)
	for pa in path:
		gv[pa] = gv[pa] + x
		x *= r
for c in range(p):
	(i, j) = input().strip().split(' ')
	path = find_path(g, i, j)
	s = 0
	for p in path:
		s += gv[p]
	print(s % 100711433)


import sys
sys.setrecursionlimit(10000000)
(n, r) = input().strip().split(' ')
(n, r) = [int(n), int(r)]
g = {}
gv = {}
edge = []
for c in range(1, n):
	(i, j) = input().strip().split(' ')
	if i not in g.keys():
		g[i] = []
		gv[i] = 0
	if j not in g.keys():
		g[j] = []
		gv[j] = 0
	g[i].append(j)
	g[j].append(i)

def find_path(graph, start, end, path=[]):
	path = path + [start]
	if start == end:
		return path
	if start not in graph.keys():
		return None
	for node in graph[start]:
		if node not in path:
			newpath = find_path(graph, node, end, path)
			if newpath:
				return newpath
	return None
(u, p) = input().strip().split(' ')
(u, p) = [int(u), int(p)]
for c in range(u):
	(i, j, x) = input().strip().split(' ')
	(i, j, x) = [str(i), str(j), int(x)]
	path = find_path(g, i, j)
	for pa in path:
		gv[pa] = gv[pa] + x
		x *= r
for c in range(p):
	(i, j) = input().strip().split(' ')
	path = find_path(g, i, j)
	s = 0
	for p in path:
		s += gv[p]
	print(s % 100711433)


import sys
sys.setrecursionlimit(10000000)
(n, r) = input().strip().split(' ')
(n, r) = [int(n), int(r)]
g = {}
gv = {}
edge = []
for c in range(1, n):
	(i, j) = input().strip().split(' ')
	if i not in g.keys():
		g[i] = []
		gv[i] = 0
	if j not in g.keys():
		g[j] = []
		gv[j] = 0
	g[i].append(j)
	g[j].append(i)

def find_path(graph, start, end, path=[]):
	path = path + [start]
	if start == end:
		return path
	if start not in graph.keys():
		return None
	for node in graph[start]:
		if node not in path:
			newpath = find_path(graph, node, end, path)
			if newpath:
				return newpath
	return None
(u, p) = input().strip().split(' ')
(u, p) = [int(u), int(p)]
for c in range(u):
	(i, j, x) = input().strip().split(' ')
	(i, j, x) = [str(i), str(j), int(x)]
	path = find_path(g, i, j)
	for pa in path:
		gv[pa] = gv[pa] + x
		x *= r
for c in range(p):
	(i, j) = input().strip().split(' ')
	path = find_path(g, i, j)
	s = 0
	for p in path:
		s += gv[p]
	print(s % 100711433)


import sys
sys.setrecursionlimit(10000000)
(n, r) = input().strip().split(' ')
(n, r) = [int(n), int(r)]
g = {}
gv = {}
edge = []
for c in range(1, n):
	(i, j) = input().strip().split(' ')
	if i not in g.keys():
		g[i] = []
		gv[i] = 0
	if j not in g.keys():
		g[j] = []
		gv[j] = 0
	g[i].append(j)
	g[j].append(i)

def find_path(graph, start, end, path=[]):
	path = path + [start]
	if start == end:
		return path
	if start not in graph.keys():
		return None
	for node in graph[start]:
		if node not in path:
			newpath = find_path(graph, node, end, path)
			if newpath:
				return newpath
	return None
(u, p) = input().strip().split(' ')
(u, p) = [int(u), int(p)]
for c in range(u):
	(i, j, x) = input().strip().split(' ')
	(i, j, x) = [str(i), str(j), int(x)]
	path = find_path(g, i, j)
	for pa in path:
		gv[pa] = gv[pa] + x
		x *= r
for c in range(p):
	(i, j) = input().strip().split(' ')
	path = find_path(g, i, j)
	s = 0
	for p in path:
		s += gv[p]
	print(s % 100711433)


import sys
sys.setrecursionlimit(10000000)
(n, r) = input().strip().split(' ')
(n, r) = [int(n), int(r)]
g = {}
gv = {}
edge = []
for c in range(1, n):
	(i, j) = input().strip().split(' ')
	if i not in g.keys():
		g[i] = []
		gv[i] = 0
	if j not in g.keys():
		g[j] = []
		gv[j] = 0
	g[i].append(j)
	g[j].append(i)

def find_path(graph, start, end, path=[]):
	path = path + [start]
	if start == end:
		return path
	if start not in graph.keys():
		return None
	for node in graph[start]:
		if node not in path:
			newpath = find_path(graph, node, end, path)
			if newpath:
				return newpath
	return None
(u, p) = input().strip().split(' ')
(u, p) = [int(u), int(p)]
for c in range(u):
	(i, j, x) = input().strip().split(' ')
	(i, j, x) = [str(i), str(j), int(x)]
	path = find_path(g, i, j)
	for pa in path:
		gv[pa] = gv[pa] + x
		x *= r
for c in range(p):
	(i, j) = input().strip().split(' ')
	path = find_path(g, i, j)
	s = 0
	for p in path:
		s += gv[p]
	print(s % 100711433)


import sys
sys.setrecursionlimit(10000000)
(n, r) = input().strip().split(' ')
(n, r) = [int(n), int(r)]
g = {}
gv = {}
edge = []
for c in range(1, n):
	(i, j) = input().strip().split(' ')
	if i not in g.keys():
		g[i] = []
		gv[i] = 0
	if j not in g.keys():
		g[j] = []
		gv[j] = 0
	g[i].append(j)
	g[j].append(i)

def find_path(graph, start, end, path=[]):
	path = path + [start]
	if start == end:
		return path
	if start not in graph.keys():
		return None
	for node in graph[start]:
		if node not in path:
			newpath = find_path(graph, node, end, path)
			if newpath:
				return newpath
	return None
(u, p) = input().strip().split(' ')
(u, p) = [int(u), int(p)]
for c in range(u):
	(i, j, x) = input().strip().split(' ')
	(i, j, x) = [str(i), str(j), int(x)]
	path = find_path(g, i, j)
	for pa in path:
		gv[pa] = gv[pa] + x
		x *= r
for c in range(p):
	(i, j) = input().strip().split(' ')
	path = find_path(g, i, j)
	s = 0
	for p in path:
		s += gv[p]
	print(s % 100711433)


import sys
sys.setrecursionlimit(10000000)
(n, r) = input().strip().split(' ')
(n, r) = [int(n), int(r)]
g = {}
gv = {}
edge = []
for c in range(1, n):
	(i, j) = input().strip().split(' ')
	if i not in g.keys():
		g[i] = []
		gv[i] = 0
	if j not in g.keys():
		g[j] = []
		gv[j] = 0
	g[i].append(j)
	g[j].append(i)

def find_path(graph, start, end, path=[]):
	path = path + [start]
	if start == end:
		return path
	if start not in graph.keys():
		return None
	for node in graph[start]:
		if node not in path:
			newpath = find_path(graph, node, end, path)
			if newpath:
				return newpath
	return None
(u, p) = input().strip().split(' ')
(u, p) = [int(u), int(p)]
for c in range(u):
	(i, j, x) = input().strip().split(' ')
	(i, j, x) = [str(i), str(j), int(x)]
	path = find_path(g, i, j)
	for pa in path:
		gv[pa] = gv[pa] + x
		x *= r
for c in range(p):
	(i, j) = input().strip().split(' ')
	path = find_path(g, i, j)
	s = 0
	for p in path:
		s += gv[p]
	print(s % 100711433)


import sys
sys.setrecursionlimit(10000000)
(n, r) = input().strip().split(' ')
(n, r) = [int(n), int(r)]
g = {}
gv = {}
edge = []
for c in range(1, n):
	(i, j) = input().strip().split(' ')
	if i not in g.keys():
		g[i] = []
		gv[i] = 0
	if j not in g.keys():
		g[j] = []
		gv[j] = 0
	g[i].append(j)
	g[j].append(i)

def find_path(graph, start, end, path=[]):
	path = path + [start]
	if start == end:
		return path
	if start not in graph.keys():
		return None
	for node in graph[start]:
		if node not in path:
			newpath = find_path(graph, node, end, path)
			if newpath:
				return newpath
	return None
(u, p) = input().strip().split(' ')
(u, p) = [int(u), int(p)]
for c in range(u):
	(i, j, x) = input().strip().split(' ')
	(i, j, x) = [str(i), str(j), int(x)]
	path = find_path(g, i, j)
	for pa in path:
		gv[pa] = gv[pa] + x
		x *= r
for c in range(p):
	(i, j) = input().strip().split(' ')
	path = find_path(g, i, j)
	s = 0
	for p in path:
		s += gv[p]
	print(s % 100711433)


import sys
sys.setrecursionlimit(10000000)
(n, r) = input().strip().split(' ')
(n, r) = [int(n), int(r)]
g = {}
gv = {}
edge = []
for c in range(1, n):
	(i, j) = input().strip().split(' ')
	if i not in g.keys():
		g[i] = []
		gv[i] = 0
	if j not in g.keys():
		g[j] = []
		gv[j] = 0
	g[i].append(j)
	g[j].append(i)

def find_path(graph, start, end, path=[]):
	path = path + [start]
	if start == end:
		return path
	if start not in graph.keys():
		return None
	for node in graph[start]:
		if node not in path:
			newpath = find_path(graph, node, end, path)
			if newpath:
				return newpath
	return None
(u, p) = input().strip().split(' ')
(u, p) = [int(u), int(p)]
for c in range(u):
	(i, j, x) = input().strip().split(' ')
	(i, j, x) = [str(i), str(j), int(x)]
	path = find_path(g, i, j)
	for pa in path:
		gv[pa] = gv[pa] + x
		x *= r
for c in range(p):
	(i, j) = input().strip().split(' ')
	path = find_path(g, i, j)
	s = 0
	for p in path:
		s += gv[p]
	print(s % 100711433)


import sys
sys.setrecursionlimit(10000000)
(n, r) = input().strip().split(' ')
(n, r) = [int(n), int(r)]
g = {}
gv = {}
edge = []
for c in range(1, n):
	(i, j) = input().strip().split(' ')
	if i not in g.keys():
		g[i] = []
		gv[i] = 0
	if j not in g.keys():
		g[j] = []
		gv[j] = 0
	g[i].append(j)
	g[j].append(i)

def find_path(graph, start, end, path=[]):
	path = path + [start]
	if start == end:
		return path
	if start not in graph.keys():
		return None
	for node in graph[start]:
		if node not in path:
			newpath = find_path(graph, node, end, path)
			if newpath:
				return newpath
	return None
(u, p) = input().strip().split(' ')
(u, p) = [int(u), int(p)]
for c in range(u):
	(i, j, x) = input().strip().split(' ')
	(i, j, x) = [str(i), str(j), int(x)]
	path = find_path(g, i, j)
	for pa in path:
		gv[pa] = gv[pa] + x
		x *= r
for c in range(p):
	(i, j) = input().strip().split(' ')
	path = find_path(g, i, j)
	s = 0
	for p in path:
		s += gv[p]
	print(s % 100711433)


import sys
sys.setrecursionlimit(10000000)
(n, r) = input().strip().split(' ')
(n, r) = [int(n), int(r)]
g = {}
gv = {}
edge = []
for c in range(1, n):
	(i, j) = input().strip().split(' ')
	if i not in g.keys():
		g[i] = []
		gv[i] = 0
	if j not in g.keys():
		g[j] = []
		gv[j] = 0
	g[i].append(j)
	g[j].append(i)

def find_path(graph, start, end, path=[]):
	path = path + [start]
	if start == end:
		return path
	if start not in graph.keys():
		return None
	for node in graph[start]:
		if node not in path:
			newpath = find_path(graph, node, end, path)
			if newpath:
				return newpath
	return None
(u, p) = input().strip().split(' ')
(u, p) = [int(u), int(p)]
for c in range(u):
	(i, j, x) = input().strip().split(' ')
	(i, j, x) = [str(i), str(j), int(x)]
	path = find_path(g, i, j)
	for pa in path:
		gv[pa] = gv[pa] + x
		x *= r
for c in range(p):
	(i, j) = input().strip().split(' ')
	path = find_path(g, i, j)
	s = 0
	for p in path:
		s += gv[p]
	print(s % 100711433)


import sys
sys.setrecursionlimit(10000000)
(n, r) = input().strip().split(' ')
(n, r) = [int(n), int(r)]
g = {}
gv = {}
edge = []
for c in range(1, n):
	(i, j) = input().strip().split(' ')
	if i not in g.keys():
		g[i] = []
		gv[i] = 0
	if j not in g.keys():
		g[j] = []
		gv[j] = 0
	g[i].append(j)
	g[j].append(i)

def find_path(graph, start, end, path=[]):
	path = path + [start]
	if start == end:
		return path
	if start not in graph.keys():
		return None
	for node in graph[start]:
		if node not in path:
			newpath = find_path(graph, node, end, path)
			if newpath:
				return newpath
	return None
(u, p) = input().strip().split(' ')
(u, p) = [int(u), int(p)]
for c in range(u):
	(i, j, x) = input().strip().split(' ')
	(i, j, x) = [str(i), str(j), int(x)]
	path = find_path(g, i, j)
	for pa in path:
		gv[pa] = gv[pa] + x
		x *= r
for c in range(p):
	(i, j) = input().strip().split(' ')
	path = find_path(g, i, j)
	s = 0
	for p in path:
		s += gv[p]
	print(s % 100711433)


import sys
sys.setrecursionlimit(10000000)
(n, r) = input().strip().split(' ')
(n, r) = [int(n), int(r)]
g = {}
gv = {}
edge = []
for c in range(1, n):
	(i, j) = input().strip().split(' ')
	if i not in g.keys():
		g[i] = []
		gv[i] = 0
	if j not in g.keys():
		g[j] = []
		gv[j] = 0
	g[i].append(j)
	g[j].append(i)

def find_path(graph, start, end, path=[]):
	path = path + [start]
	if start == end:
		return path
	if start not in graph.keys():
		return None
	for node in graph[start]:
		if node not in path:
			newpath = find_path(graph, node, end, path)
			if newpath:
				return newpath
	return None
(u, p) = input().strip().split(' ')
(u, p) = [int(u), int(p)]
for c in range(u):
	(i, j, x) = input().strip().split(' ')
	(i, j, x) = [str(i), str(j), int(x)]
	path = find_path(g, i, j)
	for pa in path:
		gv[pa] = gv[pa] + x
		x *= r
for c in range(p):
	(i, j) = input().strip().split(' ')
	path = find_path(g, i, j)
	s = 0
	for p in path:
		s += gv[p]
	print(s % 100711433)


import sys
sys.setrecursionlimit(10000000)
(n, r) = input().strip().split(' ')
(n, r) = [int(n), int(r)]
g = {}
gv = {}
edge = []
for c in range(1, n):
	(i, j) = input().strip().split(' ')
	if i not in g.keys():
		g[i] = []
		gv[i] = 0
	if j not in g.keys():
		g[j] = []
		gv[j] = 0
	g[i].append(j)
	g[j].append(i)

def find_path(graph, start, end, path=[]):
	path = path + [start]
	if start == end:
		return path
	if start not in graph.keys():
		return None
	for node in graph[start]:
		if node not in path:
			newpath = find_path(graph, node, end, path)
			if newpath:
				return newpath
	return None
(u, p) = input().strip().split(' ')
(u, p) = [int(u), int(p)]
for c in range(u):
	(i, j, x) = input().strip().split(' ')
	(i, j, x) = [str(i), str(j), int(x)]
	path = find_path(g, i, j)
	for pa in path:
		gv[pa] = gv[pa] + x
		x *= r
for c in range(p):
	(i, j) = input().strip().split(' ')
	path = find_path(g, i, j)
	s = 0
	for p in path:
		s += gv[p]
	print(s % 100711433)


import sys
sys.setrecursionlimit(10000000)
(n, r) = input().strip().split(' ')
(n, r) = [int(n), int(r)]
g = {}
gv = {}
edge = []
for c in range(1, n):
	(i, j) = input().strip().split(' ')
	if i not in g.keys():
		g[i] = []
		gv[i] = 0
	if j not in g.keys():
		g[j] = []
		gv[j] = 0
	g[i].append(j)
	g[j].append(i)

def find_path(graph, start, end, path=[]):
	path = path + [start]
	if start == end:
		return path
	if start not in graph.keys():
		return None
	for node in graph[start]:
		if node not in path:
			newpath = find_path(graph, node, end, path)
			if newpath:
				return newpath
	return None
(u, p) = input().strip().split(' ')
(u, p) = [int(u), int(p)]
for c in range(u):
	(i, j, x) = input().strip().split(' ')
	(i, j, x) = [str(i), str(j), int(x)]
	path = find_path(g, i, j)
	for pa in path:
		gv[pa] = gv[pa] + x
		x *= r
for c in range(p):
	(i, j) = input().strip().split(' ')
	path = find_path(g, i, j)
	s = 0
	for p in path:
		s += gv[p]
	print(s % 100711433)


import sys
sys.setrecursionlimit(10000000)
(n, r) = input().strip().split(' ')
(n, r) = [int(n), int(r)]
g = {}
gv = {}
edge = []
for c in range(1, n):
	(i, j) = input().strip().split(' ')
	if i not in g.keys():
		g[i] = []
		gv[i] = 0
	if j not in g.keys():
		g[j] = []
		gv[j] = 0
	g[i].append(j)
	g[j].append(i)

def find_path(graph, start, end, path=[]):
	path = path + [start]
	if start == end:
		return path
	if start not in graph.keys():
		return None
	for node in graph[start]:
		if node not in path:
			newpath = find_path(graph, node, end, path)
			if newpath:
				return newpath
	return None
(u, p) = input().strip().split(' ')
(u, p) = [int(u), int(p)]
for c in range(u):
	(i, j, x) = input().strip().split(' ')
	(i, j, x) = [str(i), str(j), int(x)]
	path = find_path(g, i, j)
	for pa in path:
		gv[pa] = gv[pa] + x
		x *= r
for c in range(p):
	(i, j) = input().strip().split(' ')
	path = find_path(g, i, j)
	s = 0
	for p in path:
		s += gv[p]
	print(s % 100711433)


import sys
sys.setrecursionlimit(10000000)
(n, r) = input().strip().split(' ')
(n, r) = [int(n), int(r)]
g = {}
gv = {}
edge = []
for c in range(1, n):
	(i, j) = input().strip().split(' ')
	if i not in g.keys():
		g[i] = []
		gv[i] = 0
	if j not in g.keys():
		g[j] = []
		gv[j] = 0
	g[i].append(j)
	g[j].append(i)

def find_path(graph, start, end, path=[]):
	path = path + [start]
	if start == end:
		return path
	if start not in graph.keys():
		return None
	for node in graph[start]:
		if node not in path:
			newpath = find_path(graph, node, end, path)
			if newpath:
				return newpath
	return None
(u, p) = input().strip().split(' ')
(u, p) = [int(u), int(p)]
for c in range(u):
	(i, j, x) = input().strip().split(' ')
	(i, j, x) = [str(i), str(j), int(x)]
	path = find_path(g, i, j)
	for pa in path:
		gv[pa] = gv[pa] + x
		x *= r
for c in range(p):
	(i, j) = input().strip().split(' ')
	path = find_path(g, i, j)
	s = 0
	for p in path:
		s += gv[p]
	print(s % 100711433)


import sys
sys.setrecursionlimit(10000000)
(n, r) = input().strip().split(' ')
(n, r) = [int(n), int(r)]
g = {}
gv = {}
edge = []
for c in range(1, n):
	(i, j) = input().strip().split(' ')
	if i not in g.keys():
		g[i] = []
		gv[i] = 0
	if j not in g.keys():
		g[j] = []
		gv[j] = 0
	g[i].append(j)
	g[j].append(i)

def find_path(graph, start, end, path=[]):
	path = path + [start]
	if start == end:
		return path
	if start not in graph.keys():
		return None
	for node in graph[start]:
		if node not in path:
			newpath = find_path(graph, node, end, path)
			if newpath:
				return newpath
	return None
(u, p) = input().strip().split(' ')
(u, p) = [int(u), int(p)]
for c in range(u):
	(i, j, x) = input().strip().split(' ')
	(i, j, x) = [str(i), str(j), int(x)]
	path = find_path(g, i, j)
	for pa in path:
		gv[pa] = gv[pa] + x
		x *= r
for c in range(p):
	(i, j) = input().strip().split(' ')
	path = find_path(g, i, j)
	s = 0
	for p in path:
		s += gv[p]
	print(s % 100711433)


import sys
sys.setrecursionlimit(10000000)
(n, r) = input().strip().split(' ')
(n, r) = [int(n), int(r)]
g = {}
gv = {}
edge = []
for c in range(1, n):
	(i, j) = input().strip().split(' ')
	if i not in g.keys():
		g[i] = []
		gv[i] = 0
	if j not in g.keys():
		g[j] = []
		gv[j] = 0
	g[i].append(j)
	g[j].append(i)

def find_path(graph, start, end, path=[]):
	path = path + [start]
	if start == end:
		return path
	if start not in graph.keys():
		return None
	for node in graph[start]:
		if node not in path:
			newpath = find_path(graph, node, end, path)
			if newpath:
				return newpath
	return None
(u, p) = input().strip().split(' ')
(u, p) = [int(u), int(p)]
for c in range(u):
	(i, j, x) = input().strip().split(' ')
	(i, j, x) = [str(i), str(j), int(x)]
	path = find_path(g, i, j)
	for pa in path:
		gv[pa] = gv[pa] + x
		x *= r
for c in range(p):
	(i, j) = input().strip().split(' ')
	path = find_path(g, i, j)
	s = 0
	for p in path:
		s += gv[p]
	print(s % 100711433)


import sys
sys.setrecursionlimit(10000000)
(n, r) = input().strip().split(' ')
(n, r) = [int(n), int(r)]
g = {}
gv = {}
edge = []
for c in range(1, n):
	(i, j) = input().strip().split(' ')
	if i not in g.keys():
		g[i] = []
		gv[i] = 0
	if j not in g.keys():
		g[j] = []
		gv[j] = 0
	g[i].append(j)
	g[j].append(i)

def find_path(graph, start, end, path=[]):
	path = path + [start]
	if start == end:
		return path
	if start not in graph.keys():
		return None
	for node in graph[start]:
		if node not in path:
			newpath = find_path(graph, node, end, path)
			if newpath:
				return newpath
	return None
(u, p) = input().strip().split(' ')
(u, p) = [int(u), int(p)]
for c in range(u):
	(i, j, x) = input().strip().split(' ')
	(i, j, x) = [str(i), str(j), int(x)]
	path = find_path(g, i, j)
	for pa in path:
		gv[pa] = gv[pa] + x
		x *= r
for c in range(p):
	(i, j) = input().strip().split(' ')
	path = find_path(g, i, j)
	s = 0
	for p in path:
		s += gv[p]
	print(s % 100711433)


class Node:

	def __init__(self, data):
		self.data = data
		self.neighbors = []

	def add(self, neighbor):
		self.neighbors.append(neighbor)

	def __str__(self):
		return '(' + str(self.data) + ', ' + str(self.parent) + ')'

def path(a, b):
	s = set()
	q = [[b]]
	s.add(b)
	i = 0
	while i < len(q):
		p = q[i]
		if p[0] == a:
			return p
		for n in nodes[p[0]].neighbors:
			if n not in s:
				s.add(n)
				q.append([n] + p)
		i += 1
	raise Exception
(n, r) = map(int, input().split())
nodes = [Node(0) for _ in range(n)]
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	nodes[a - 1].add(b - 1)
	nodes[b - 1].add(a - 1)
(u, q) = map(int, input().split())
for _ in range(u):
	(i, j, x) = map(int, input().split())
	for asdf in path(i - 1, j - 1):
		node = nodes[asdf]
		node.data += x
		x *= r
for _ in range(q):
	(i, j) = map(int, input().split())
	print(sum((nodes[node].data for node in path(i - 1, j - 1))) % 100711433)


class Node:

	def __init__(self, data):
		self.data = data
		self.neighbors = []

	def add(self, neighbor):
		self.neighbors.append(neighbor)

	def __str__(self):
		return '(' + str(self.data) + ', ' + str(self.parent) + ')'

def path(a, b):
	s = set()
	q = [[b]]
	s.add(b)
	i = 0
	while i < len(q):
		p = q[i]
		if p[0] == a:
			return p
		for n in nodes[p[0]].neighbors:
			if n not in s:
				s.add(n)
				q.append([n] + p)
		i += 1
	raise Exception
(n, r) = map(int, input().split())
nodes = [Node(0) for _ in range(n)]
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	nodes[a - 1].add(b - 1)
	nodes[b - 1].add(a - 1)
(u, q) = map(int, input().split())
for _ in range(u):
	(i, j, x) = map(int, input().split())
	for asdf in path(i - 1, j - 1):
		node = nodes[asdf]
		node.data += x
		x *= r
for _ in range(q):
	(i, j) = map(int, input().split())
	print(sum((nodes[node].data for node in path(i - 1, j - 1))) % 100711433)


import sys
sys.setrecursionlimit(10000000)
(n, r) = input().strip().split(' ')
(n, r) = [int(n), int(r)]
g = {}
gv = {}
edge = []
for c in range(1, n):
	(i, j) = input().strip().split(' ')
	if i not in g.keys():
		g[i] = []
		gv[i] = 0
	if j not in g.keys():
		g[j] = []
		gv[j] = 0
	g[i].append(j)
	g[j].append(i)

def find_path(graph, start, end, path=[]):
	path = path + [start]
	if start == end:
		return path
	if start not in graph.keys():
		return None
	for node in graph[start]:
		if node not in path:
			newpath = find_path(graph, node, end, path)
			if newpath:
				return newpath
	return None
(u, p) = input().strip().split(' ')
(u, p) = [int(u), int(p)]
for c in range(u):
	(i, j, x) = input().strip().split(' ')
	(i, j, x) = [str(i), str(j), int(x)]
	path = find_path(g, i, j)
	for pa in path:
		gv[pa] = gv[pa] + x
		x *= r
for c in range(p):
	(i, j) = input().strip().split(' ')
	path = find_path(g, i, j)
	s = 0
	for p in path:
		s += gv[p]
	print(s % 100711433)


import sys
sys.setrecursionlimit(10000000)
(n, r) = input().strip().split(' ')
(n, r) = [int(n), int(r)]
g = {}
gv = {}
edge = []
for c in range(1, n):
	(i, j) = input().strip().split(' ')
	if i not in g.keys():
		g[i] = []
		gv[i] = 0
	if j not in g.keys():
		g[j] = []
		gv[j] = 0
	g[i].append(j)
	g[j].append(i)

def find_path(graph, start, end, path=[]):
	path = path + [start]
	if start == end:
		return path
	if start not in graph.keys():
		return None
	for node in graph[start]:
		if node not in path:
			newpath = find_path(graph, node, end, path)
			if newpath:
				return newpath
	return None
(u, p) = input().strip().split(' ')
(u, p) = [int(u), int(p)]
for c in range(u):
	(i, j, x) = input().strip().split(' ')
	(i, j, x) = [str(i), str(j), int(x)]
	path = find_path(g, i, j)
	for pa in path:
		gv[pa] = gv[pa] + x
		x *= r
for c in range(p):
	(i, j) = input().strip().split(' ')
	path = find_path(g, i, j)
	s = 0
	for p in path:
		s += gv[p]
	print(s % 100711433)


class Node:

	def __init__(self, data):
		self.data = data
		self.neighbors = []

	def add(self, neighbor):
		self.neighbors.append(neighbor)

	def __str__(self):
		return '(' + str(self.data) + ', ' + str(self.parent) + ')'

def path(a, b):
	s = set()
	q = [[b]]
	s.add(b)
	i = 0
	while i < len(q):
		p = q[i]
		if p[0] == a:
			return p
		for n in nodes[p[0]].neighbors:
			if n not in s:
				s.add(n)
				q.append([n] + p)
		i += 1
	raise Exception
(n, r) = map(int, input().split())
nodes = [Node(0) for _ in range(n)]
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	nodes[a - 1].add(b - 1)
	nodes[b - 1].add(a - 1)
(u, q) = map(int, input().split())
for _ in range(u):
	(i, j, x) = map(int, input().split())
	for asdf in path(i - 1, j - 1):
		node = nodes[asdf]
		node.data += x
		x *= r
for _ in range(q):
	(i, j) = map(int, input().split())
	print(sum((nodes[node].data for node in path(i - 1, j - 1))) % 100711433)


class Node:

	def __init__(self, data):
		self.data = data
		self.neighbors = []

	def add(self, neighbor):
		self.neighbors.append(neighbor)

	def __str__(self):
		return '(' + str(self.data) + ', ' + str(self.parent) + ')'

def path(a, b):
	s = set()
	q = [[b]]
	s.add(b)
	i = 0
	while i < len(q):
		p = q[i]
		if p[0] == a:
			return p
		for n in nodes[p[0]].neighbors:
			if n not in s:
				s.add(n)
				q.append([n] + p)
		i += 1
	raise Exception
(n, r) = map(int, input().split())
nodes = [Node(0) for _ in range(n)]
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	nodes[a - 1].add(b - 1)
	nodes[b - 1].add(a - 1)
(u, q) = map(int, input().split())
for _ in range(u):
	(i, j, x) = map(int, input().split())
	for asdf in path(i - 1, j - 1):
		node = nodes[asdf]
		node.data += x
		x *= r
for _ in range(q):
	(i, j) = map(int, input().split())
	print(sum((nodes[node].data for node in path(i - 1, j - 1))) % 100711433)


class Node:

	def __init__(self, data):
		self.data = data
		self.neighbors = []

	def add(self, neighbor):
		self.neighbors.append(neighbor)

	def __str__(self):
		return '(' + str(self.data) + ', ' + str(self.parent) + ')'

def path(a, b):
	s = set()
	q = [[b]]
	s.add(b)
	i = 0
	while i < len(q):
		p = q[i]
		if p[0] == a:
			return p
		for n in nodes[p[0]].neighbors:
			if n not in s:
				s.add(n)
				q.append([n] + p)
		i += 1
	raise Exception
(n, r) = map(int, input().split())
nodes = [Node(0) for _ in range(n)]
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	nodes[a - 1].add(b - 1)
	nodes[b - 1].add(a - 1)
(u, q) = map(int, input().split())
for _ in range(u):
	(i, j, x) = map(int, input().split())
	for asdf in path(i - 1, j - 1):
		node = nodes[asdf]
		node.data += x
		x *= r
for _ in range(q):
	(i, j) = map(int, input().split())
	print(sum((nodes[node].data for node in path(i - 1, j - 1))) % 100711433)


class Node:

	def __init__(self, data):
		self.data = data
		self.neighbors = []

	def add(self, neighbor):
		self.neighbors.append(neighbor)

	def __str__(self):
		return '(' + str(self.data) + ', ' + str(self.parent) + ')'

def path(a, b):
	s = set()
	q = [[b]]
	s.add(b)
	i = 0
	while i < len(q):
		p = q[i]
		if p[0] == a:
			return p
		for n in nodes[p[0]].neighbors:
			if n not in s:
				s.add(n)
				q.append([n] + p)
		i += 1
	raise Exception
(n, r) = map(int, input().split())
nodes = [Node(0) for _ in range(n)]
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	nodes[a - 1].add(b - 1)
	nodes[b - 1].add(a - 1)
(u, q) = map(int, input().split())
for _ in range(u):
	(i, j, x) = map(int, input().split())
	for asdf in path(i - 1, j - 1):
		node = nodes[asdf]
		node.data += x
		x *= r
for _ in range(q):
	(i, j) = map(int, input().split())
	print(sum((nodes[node].data for node in path(i - 1, j - 1))) % 100711433)


import sys
sys.setrecursionlimit(10000000)
(n, r) = input().strip().split(' ')
(n, r) = [int(n), int(r)]
g = {}
gv = {}
edge = []
for c in range(1, n):
	(i, j) = input().strip().split(' ')
	if i not in g.keys():
		g[i] = []
		gv[i] = 0
	if j not in g.keys():
		g[j] = []
		gv[j] = 0
	g[i].append(j)
	g[j].append(i)

def find_path(graph, start, end, path=[]):
	path = path + [start]
	if start == end:
		return path
	if start not in graph.keys():
		return None
	for node in graph[start]:
		if node not in path:
			newpath = find_path(graph, node, end, path)
			if newpath:
				return newpath
	return None
(u, p) = input().strip().split(' ')
(u, p) = [int(u), int(p)]
for c in range(u):
	(i, j, x) = input().strip().split(' ')
	(i, j, x) = [str(i), str(j), int(x)]
	path = find_path(g, i, j)
	for pa in path:
		gv[pa] = gv[pa] + x
		x *= r
for c in range(p):
	(i, j) = input().strip().split(' ')
	path = find_path(g, i, j)
	s = 0
	for p in path:
		s += gv[p]
	print(s % 100711433)


class Node:

	def __init__(self, data):
		self.data = data
		self.neighbors = []

	def add(self, neighbor):
		self.neighbors.append(neighbor)

	def __str__(self):
		return '(' + str(self.data) + ', ' + str(self.parent) + ')'

def path(a, b):
	s = set()
	q = [[b]]
	s.add(b)
	i = 0
	while i < len(q):
		p = q[i]
		if p[0] == a:
			return p
		for n in nodes[p[0]].neighbors:
			if n not in s:
				s.add(n)
				q.append([n] + p)
		i += 1
	raise Exception
(n, r) = map(int, input().split())
nodes = [Node(0) for _ in range(n)]
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	nodes[a - 1].add(b - 1)
	nodes[b - 1].add(a - 1)
(u, q) = map(int, input().split())
for _ in range(u):
	(i, j, x) = map(int, input().split())
	for asdf in path(i - 1, j - 1):
		node = nodes[asdf]
		node.data += x
		x *= r
for _ in range(q):
	(i, j) = map(int, input().split())
	print(sum((nodes[node].data for node in path(i - 1, j - 1))) % 100711433)


import sys
sys.setrecursionlimit(10000000)
(n, r) = input().strip().split(' ')
(n, r) = [int(n), int(r)]
g = {}
gv = {}
edge = []
for c in range(1, n):
	(i, j) = input().strip().split(' ')
	if i not in g.keys():
		g[i] = []
		gv[i] = 0
	if j not in g.keys():
		g[j] = []
		gv[j] = 0
	g[i].append(j)
	g[j].append(i)

def find_path(graph, start, end, path=[]):
	path = path + [start]
	if start == end:
		return path
	if start not in graph.keys():
		return None
	for node in graph[start]:
		if node not in path:
			newpath = find_path(graph, node, end, path)
			if newpath:
				return newpath
	return None
(u, p) = input().strip().split(' ')
(u, p) = [int(u), int(p)]
for c in range(u):
	(i, j, x) = input().strip().split(' ')
	(i, j, x) = [str(i), str(j), int(x)]
	path = find_path(g, i, j)
	for pa in path:
		gv[pa] = gv[pa] + x
		x *= r
for c in range(p):
	(i, j) = input().strip().split(' ')
	path = find_path(g, i, j)
	s = 0
	for p in path:
		s += gv[p]
	print(s % 100711433)


class Node:

	def __init__(self, data):
		self.data = data
		self.neighbors = []

	def add(self, neighbor):
		self.neighbors.append(neighbor)

	def __str__(self):
		return '(' + str(self.data) + ', ' + str(self.parent) + ')'

def path(a, b):
	s = set()
	q = [[b]]
	s.add(b)
	i = 0
	while i < len(q):
		p = q[i]
		if p[0] == a:
			return p
		for n in nodes[p[0]].neighbors:
			if n not in s:
				s.add(n)
				q.append([n] + p)
		i += 1
	raise Exception
(n, r) = map(int, input().split())
nodes = [Node(0) for _ in range(n)]
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	nodes[a - 1].add(b - 1)
	nodes[b - 1].add(a - 1)
(u, q) = map(int, input().split())
for _ in range(u):
	(i, j, x) = map(int, input().split())
	for asdf in path(i - 1, j - 1):
		node = nodes[asdf]
		node.data += x
		x *= r
for _ in range(q):
	(i, j) = map(int, input().split())
	print(sum((nodes[node].data for node in path(i - 1, j - 1))) % 100711433)


class Node:

	def __init__(self, data):
		self.data = data
		self.neighbors = []

	def add(self, neighbor):
		self.neighbors.append(neighbor)

	def __str__(self):
		return '(' + str(self.data) + ', ' + str(self.parent) + ')'

def path(a, b):
	s = set()
	q = [[b]]
	s.add(b)
	i = 0
	while i < len(q):
		p = q[i]
		if p[0] == a:
			return p
		for n in nodes[p[0]].neighbors:
			if n not in s:
				s.add(n)
				q.append([n] + p)
		i += 1
	raise Exception
(n, r) = map(int, input().split())
nodes = [Node(0) for _ in range(n)]
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	nodes[a - 1].add(b - 1)
	nodes[b - 1].add(a - 1)
(u, q) = map(int, input().split())
for _ in range(u):
	(i, j, x) = map(int, input().split())
	for asdf in path(i - 1, j - 1):
		node = nodes[asdf]
		node.data += x
		x *= r
for _ in range(q):
	(i, j) = map(int, input().split())
	print(sum((nodes[node].data for node in path(i - 1, j - 1))) % 100711433)


class Node:

	def __init__(self, data):
		self.data = data
		self.neighbors = []

	def add(self, neighbor):
		self.neighbors.append(neighbor)

	def __str__(self):
		return '(' + str(self.data) + ', ' + str(self.parent) + ')'

def path(a, b):
	s = set()
	q = [[b]]
	s.add(b)
	i = 0
	while i < len(q):
		p = q[i]
		if p[0] == a:
			return p
		for n in nodes[p[0]].neighbors:
			if n not in s:
				s.add(n)
				q.append([n] + p)
		i += 1
	raise Exception
(n, r) = map(int, input().split())
nodes = [Node(0) for _ in range(n)]
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	nodes[a - 1].add(b - 1)
	nodes[b - 1].add(a - 1)
(u, q) = map(int, input().split())
for _ in range(u):
	(i, j, x) = map(int, input().split())
	for asdf in path(i - 1, j - 1):
		node = nodes[asdf]
		node.data += x
		x *= r
for _ in range(q):
	(i, j) = map(int, input().split())
	print(sum((nodes[node].data for node in path(i - 1, j - 1))) % 100711433)


import sys
sys.setrecursionlimit(10000000)
(n, r) = input().strip().split(' ')
(n, r) = [int(n), int(r)]
g = {}
gv = {}
edge = []
for c in range(1, n):
	(i, j) = input().strip().split(' ')
	if i not in g.keys():
		g[i] = []
		gv[i] = 0
	if j not in g.keys():
		g[j] = []
		gv[j] = 0
	g[i].append(j)
	g[j].append(i)

def find_path(graph, start, end, path=[]):
	path = path + [start]
	if start == end:
		return path
	if start not in graph.keys():
		return None
	for node in graph[start]:
		if node not in path:
			newpath = find_path(graph, node, end, path)
			if newpath:
				return newpath
	return None
(u, p) = input().strip().split(' ')
(u, p) = [int(u), int(p)]
for c in range(u):
	(i, j, x) = input().strip().split(' ')
	(i, j, x) = [str(i), str(j), int(x)]
	path = find_path(g, i, j)
	for pa in path:
		gv[pa] = gv[pa] + x
		x *= r
for c in range(p):
	(i, j) = input().strip().split(' ')
	path = find_path(g, i, j)
	s = 0
	for p in path:
		s += gv[p]
	print(s % 100711433)


class Node:

	def __init__(self, data):
		self.data = data
		self.neighbors = []

	def add(self, neighbor):
		self.neighbors.append(neighbor)

	def __str__(self):
		return '(' + str(self.data) + ', ' + str(self.parent) + ')'

def path(a, b):
	s = set()
	q = [[b]]
	s.add(b)
	i = 0
	while i < len(q):
		p = q[i]
		if p[0] == a:
			return p
		for n in nodes[p[0]].neighbors:
			if n not in s:
				s.add(n)
				q.append([n] + p)
		i += 1
	raise Exception
(n, r) = map(int, input().split())
nodes = [Node(0) for _ in range(n)]
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	nodes[a - 1].add(b - 1)
	nodes[b - 1].add(a - 1)
(u, q) = map(int, input().split())
for _ in range(u):
	(i, j, x) = map(int, input().split())
	for asdf in path(i - 1, j - 1):
		node = nodes[asdf]
		node.data += x
		x *= r
for _ in range(q):
	(i, j) = map(int, input().split())
	print(sum((nodes[node].data for node in path(i - 1, j - 1))) % 100711433)


class Node:

	def __init__(self, data):
		self.data = data
		self.neighbors = []

	def add(self, neighbor):
		self.neighbors.append(neighbor)

	def __str__(self):
		return '(' + str(self.data) + ', ' + str(self.parent) + ')'

def path(a, b):
	s = set()
	q = [[b]]
	s.add(b)
	i = 0
	while i < len(q):
		p = q[i]
		if p[0] == a:
			return p
		for n in nodes[p[0]].neighbors:
			if n not in s:
				s.add(n)
				q.append([n] + p)
		i += 1
	raise Exception
(n, r) = map(int, input().split())
nodes = [Node(0) for _ in range(n)]
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	nodes[a - 1].add(b - 1)
	nodes[b - 1].add(a - 1)
(u, q) = map(int, input().split())
for _ in range(u):
	(i, j, x) = map(int, input().split())
	for asdf in path(i - 1, j - 1):
		node = nodes[asdf]
		node.data += x
		x *= r
for _ in range(q):
	(i, j) = map(int, input().split())
	print(sum((nodes[node].data for node in path(i - 1, j - 1))) % 100711433)


class Node:

	def __init__(self, data):
		self.data = data
		self.neighbors = []

	def add(self, neighbor):
		self.neighbors.append(neighbor)

	def __str__(self):
		return '(' + str(self.data) + ', ' + str(self.parent) + ')'

def path(a, b):
	s = set()
	q = [[b]]
	s.add(b)
	i = 0
	while i < len(q):
		p = q[i]
		if p[0] == a:
			return p
		for n in nodes[p[0]].neighbors:
			if n not in s:
				s.add(n)
				q.append([n] + p)
		i += 1
	raise Exception
(n, r) = map(int, input().split())
nodes = [Node(0) for _ in range(n)]
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	nodes[a - 1].add(b - 1)
	nodes[b - 1].add(a - 1)
(u, q) = map(int, input().split())
for _ in range(u):
	(i, j, x) = map(int, input().split())
	for asdf in path(i - 1, j - 1):
		node = nodes[asdf]
		node.data += x
		x *= r
for _ in range(q):
	(i, j) = map(int, input().split())
	print(sum((nodes[node].data for node in path(i - 1, j - 1))) % 100711433)


import sys
sys.setrecursionlimit(10000000)
(n, r) = input().strip().split(' ')
(n, r) = [int(n), int(r)]
g = {}
gv = {}
edge = []
for c in range(1, n):
	(i, j) = input().strip().split(' ')
	if i not in g.keys():
		g[i] = []
		gv[i] = 0
	if j not in g.keys():
		g[j] = []
		gv[j] = 0
	g[i].append(j)
	g[j].append(i)

def find_path(graph, start, end, path=[]):
	path = path + [start]
	if start == end:
		return path
	if start not in graph.keys():
		return None
	for node in graph[start]:
		if node not in path:
			newpath = find_path(graph, node, end, path)
			if newpath:
				return newpath
	return None
(u, p) = input().strip().split(' ')
(u, p) = [int(u), int(p)]
for c in range(u):
	(i, j, x) = input().strip().split(' ')
	(i, j, x) = [str(i), str(j), int(x)]
	path = find_path(g, i, j)
	for pa in path:
		gv[pa] = gv[pa] + x
		x *= r
for c in range(p):
	(i, j) = input().strip().split(' ')
	path = find_path(g, i, j)
	s = 0
	for p in path:
		s += gv[p]
	print(s % 100711433)


import sys
sys.setrecursionlimit(10000000)
(n, r) = input().strip().split(' ')
(n, r) = [int(n), int(r)]
g = {}
gv = {}
edge = []
for c in range(1, n):
	(i, j) = input().strip().split(' ')
	if i not in g.keys():
		g[i] = []
		gv[i] = 0
	if j not in g.keys():
		g[j] = []
		gv[j] = 0
	g[i].append(j)
	g[j].append(i)

def find_path(graph, start, end, path=[]):
	path = path + [start]
	if start == end:
		return path
	if start not in graph.keys():
		return None
	for node in graph[start]:
		if node not in path:
			newpath = find_path(graph, node, end, path)
			if newpath:
				return newpath
	return None
(u, p) = input().strip().split(' ')
(u, p) = [int(u), int(p)]
for c in range(u):
	(i, j, x) = input().strip().split(' ')
	(i, j, x) = [str(i), str(j), int(x)]
	path = find_path(g, i, j)
	for pa in path:
		gv[pa] = gv[pa] + x
		x *= r
for c in range(p):
	(i, j) = input().strip().split(' ')
	path = find_path(g, i, j)
	s = 0
	for p in path:
		s += gv[p]
	print(s % 100711433)