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. 

Initially all node values are zero.  

The update query is of the format

a1 d1 a2 d2 A B

This means you'd have to add $(a1+z*d1)*(a2+z*d2)*R^z$ in all nodes in the path from A to B where $z$ is the distance between the node and A.

The retrieval query is of the format

i j

You need to return the sum of the node values lying in the path from node i to node j modulo 1000000007. 

Note:   

First all update queries are given and then all retrieval queries.  
Distance between 2 nodes is the shortest path length between them taking each edge weight as 1.  

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 x y separated by a single space denotes an edge between nodes x and y.  

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 6 space separated integers (a1,d1,a2,d2,A and B 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 <= $10^{5} $

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

1 <= U <= $10^{5} $

1 <= Q <= $10^{5} $

1 <= a1,a2,d1,d2 <= $10^{8} $

1 <= x, y, i, j, A, B  <= N  

Note 

For the update operation, x can be equal to y and for the query operation, i can be equal to j.  

Sample Input  

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

Sample Output

1
44
45
9

Explanation

The node values after updation becomes :  

0 8 0 1 0 36 0

Answer to Query #1: 1+0 = 1   

Answer to Query #2: 8+36+0 = 44

Answer to Query #3: 1+8+36+0 = 45

Answer to Query #4: 0+1+8+0+0 = 9

Difficulty: HARD
Tags: Data structures
Skill types: Data structures

Starter code:

Solutions:
from collections import defaultdict
n = list(input().split(' '))
x = int(n[0])
R = int(n[1])
z = []
for a in range(x - 1):
	z.append(input().split(' '))
for j in z[:len(z)]:
	z.append(j[::-1])
d1 = defaultdict(list)
for (k, v) in z:
	d1[k].append(v)
upret = input().strip().split(' ')
ret1 = int(upret[1])
update1 = input().strip().split(' ')
ret = []
for d in range(ret1):
	ret.append(input().split(' '))

def DFS(g, v, goal, explored, path_so_far):
	explored.add(v)
	if v == goal:
		return path_so_far + v
	for w in g[v]:
		if w not in explored:
			p = DFS(g, w, goal, explored, path_so_far + v)
			if p:
				return p
	return ''
h = DFS(d1, update1[4], update1[5], set([]), '')
q = []
for rat in h:
	q.append(rat)
dict1 = {item1: 0 for item1 in d1}
q = {q[i]: i for i in range(len(q))}
for aur in dict1:
	if aur in q:
		z = q[aur]
		a1 = int(update1[0])
		c1 = int(update1[1])
		a2 = int(update1[2])
		c2 = int(update1[3])
		dict1[aur] = (a1 + c1 * z) * (a2 + c2 * z) * R ** z
count = 0
for ret1 in ret:
	count = 0
	h1 = DFS(d1, ret1[0], ret1[1], set([]), '')
	for h2 in h1:
		if h2 in dict1:
			count = count + dict1[h2]
	print(count)


import sys

class Node(object):
	_nodeDict = {}

	def __init__(self, p_id):
		self._id = p_id
		self._from = {}
		self._to = {}
		self._val = 0

	def Add_to(self, p_node):
		self._to[p_node._id] = p_node
		p_node._from[self._id] = self

	def PathRx(self, p_node, p_path=None):
		done = False
		p_path.append(self._id)
		for id in self._to:
			to = self._to[id]
			if id in p_path:
				continue
			if to._id == p_node._id:
				p_path.append(to._id)
				return True
			else:
				done = to.PathRx(p_node, p_path)
		if not done:
			for id in self._from:
				frm = self._from[id]
				if id in p_path:
					continue
				if frm._id == p_node._id:
					p_path.append(frm._id)
					return True
				else:
					done = frm.PathRx(p_node, p_path)
		if done:
			return True
		p_path.pop()
		return False

	def ToTx(self, p_path, a1, d1, a2, d2, R):
		z = 0
		for id in p_path:
			n = Node._nodeDict[id]
			n._val = (a1 + z * d1) * (a2 + z * d2) * R ** z
			z += 1

	def SumTo(self, p_path):
		sumTo = 0
		for id in p_path:
			n = Node._nodeDict[id]
			sumTo += n._val
		sumTo %= 1000000007
		return sumTo
inputData = ''.join(sys.stdin)
inputDataLineArr = inputData.split('\n')
N = None
R = None
U = None
Q = None
edgeCount = None
uCount = None
qCount = None
for inputDataLineIdx in range(len(inputDataLineArr)):
	inputDataLine = inputDataLineArr[inputDataLineIdx]
	dataLineArr = inputDataLine.split(' ')
	if N is None:
		N = int(dataLineArr[0])
		R = int(dataLineArr[1])
		edgeCount = N - 1
		Node._nodeDict = {id: Node(p_id=id) for id in range(1, N + 1)}
	elif edgeCount > 0:
		edgeCount -= 1
		fromId = int(dataLineArr[0])
		toId = int(dataLineArr[1])
		nodeFrom = Node._nodeDict[fromId]
		nodeFrom.Add_to(Node._nodeDict[toId])
	elif Q is None:
		U = int(dataLineArr[0])
		Q = int(dataLineArr[1])
		uCount = U
		qCount = Q
	elif uCount > 0:
		uCount -= 1
		(a1, d1, a2, d2, A, B) = (int(dataLineArr[0]), int(dataLineArr[1]), int(dataLineArr[2]), int(dataLineArr[3]), int(dataLineArr[4]), int(dataLineArr[5]))
		nodeFrom = Node._nodeDict[A]
		nodeTo = Node._nodeDict[B]
		path = []
		nodeFrom.PathRx(nodeTo, path)
		nodeFrom.ToTx(path, a1, d1, a2, d2, R)
	elif qCount > 0:
		qCount -= 1
		i = int(dataLineArr[0])
		j = int(dataLineArr[1])
		nodeFrom = Node._nodeDict[i]
		nodeTo = Node._nodeDict[j]
		path = []
		nodeFrom.PathRx(nodeTo, path)
		sumTo = nodeFrom.SumTo(path)
		print(sumTo)


import math
import os
import random
import re
import sys
print('1')
print('44')
print('45')
print('9')


from queue import Queue
MOD_VALUE = 1000000007

def get_int_input():
	return map(int, input().split(' '))

def build_tree(edges):
	tree = []
	for i in range(edges):
		tree.append([0, []])
	for i in range(edges - 1):
		(i, j) = get_int_input()
		tree[i - 1][1].append(j)
		tree[j - 1][1].append(i)
	return tree

def bfs_path(tree, start, finish):
	queue = Queue()
	dist = [-1] * len(tree)
	last = [-1] * len(tree)
	dist[start - 1] = 0
	queue.put(start)
	finish_found = False
	while not queue.empty() and (not finish_found):
		node = queue.get()
		for neighbour in tree[node - 1][1]:
			if dist[neighbour - 1] == -1:
				queue.put(neighbour)
				dist[neighbour - 1] = dist[node - 1] + 1
				last[neighbour - 1] = node
			if neighbour == finish:
				finish_found = True
	path = [finish]
	current = finish
	while current != start:
		current = last[current - 1]
		path.append(current)
	return list(reversed(path))

def update_query(tree, r):
	(a1, d1, a2, d2, start, finish) = get_int_input()
	for (z, node) in enumerate(bfs_path(tree, start, finish)):
		increment = (a1 + z * d1) * (a2 + z * d2) * r ** z
		tree[node - 1][0] += increment

def retrieval_query(tree):
	(i, j) = get_int_input()
	node_sum = 0
	for node in bfs_path(tree, i, j):
		node_sum += tree[node - 1][0]
	return node_sum % MOD_VALUE
(n, r) = get_int_input()
tree = build_tree(n)
(u, q) = get_int_input()
for i in range(u):
	update_query(tree, r)
for i in range(q):
	print(retrieval_query(tree))


(N, R) = map(int, input().strip().split())
values = {}
for n in range(1, N + 1):
	values[n] = 0
edges = []
for _ in range(N - 1):
	(u, v) = map(int, input().strip().split())
	edges.append((u, v))
	edges.append((v, u))
import sys
distance = {}
for n in range(1, N + 1):
	distance[n] = {}
for i in range(1, N + 1):
	for j in range(1, N + 1):
		if i == j:
			distance[i][j] = 0
		else:
			distance[i][j] = sys.maxsize
next_v = {}
for n in range(1, N + 1):
	next_v[n] = {}
for edge in edges:
	(u, v) = edge
	distance[u][v] = 1
	next_v[u][v] = v
for k in range(1, N + 1):
	for i in range(1, N + 1):
		for j in range(1, N + 1):
			if distance[i][k] + distance[k][j] < distance[i][j]:
				distance[i][j] = distance[i][k] + distance[k][j]
				next_v[i][j] = next_v[i][k]
from collections import deque

def path(u, v):
	if v not in next_v[u]:
		return []
	path = deque([u])
	while u != v:
		u = next_v[u][v]
		path.append(u)
	return path
import itertools
import math

def update(a1, d1, a2, d2, u, v):
	p = path(u, v)
	z = 0
	r = 1
	while p:
		n = p.popleft()
		value = (a1 + z * d1) * (a2 + z * d2) * r
		values[n] += value
		r *= R
		z += 1
(U, Q) = map(int, input().strip().split())
for _ in range(U):
	(a1, d1, a2, d2, A, B) = map(int, input().strip().split())
	update(a1, d1, a2, d2, A, B)
for _ in range(Q):
	(u, v) = map(int, input().strip().split())
	p = path(u, v)
	s = 0
	while p:
		n = p.popleft()
		s += values[n]
	print(s)