Given a BST, modify it so that all greater values in the given BST are added to every node.
Example 1:
Input:
           50
         /    \
        30    70
      /   \   / \  
     20   40 60  80
Output: 350 330 300 260 210 150 80
Explanation:The tree should be modified to
following:
             260
          /       \
        330      150
       /   \   /     \
    350   300 210    80
Example 2:
Input:
          2
        /   \
       1     5
            /  \
           4    7
Output: 19 18 16 12 7
Your Task:
You don't need to read input or print anything. Your task is to complete the function modify() which takes one argument: root of the BST. The function should contain the logic to modify the BST so that in the modified BST, every node has a value equal to the sum of its value in the original BST and values of all the elements larger than it in the original BST. Return the root of the modified BST. The driver code will print the inorder traversal of the returned BST/
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(Height of the BST).
Constraints:
1<=N<=100000
Note: The Input/Output format and Example is given are used for the system's internal purpose, and should be used by a user for Expected Output only. As it is a function problem, hence a user should not read any input from the stdin/console. The task is to complete the function specified, and not to write the full code.

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Tree algorithms

Data structures

Range queries

Starter code: #User function Template for python3

'''
# Tree Node
class Node:
    def __init__(self, val):
        self.right = None
        self.data = val
        self.left = None
'''

# modify the BST and return its root
def modify(root):
    #code here


Solutions:
def util(root):
	global v
	if root == None:
		return
	util(root.right)
	root.data += v
	v = root.data
	util(root.left)

def modify(root):
	global v
	v = 0
	util(root)
	return root


def modify(root):
	helper(root, 0)
	return root

def helper(root, runningSum):
	if root is None:
		return runningSum
	runningSum = helper(root.right, runningSum)
	root.data += runningSum
	runningSum = root.data
	return helper(root.left, runningSum)


def solve(root, ans):
	if root == None:
		return
	solve(root.right, ans)
	root.data = ans[0] + root.data
	ans[0] = root.data
	solve(root.left, ans)

def modify(root):
	ans = [0]
	solve(root, ans)
	return root


def _modify(root, sum):
	if root != None:
		_modify(root.right, sum)
		sum[0] += root.data
		root.data = sum[0]
		_modify(root.left, sum)

def modify(root):
	sum = [0]
	_modify(root, sum)
	return root


def modify(root):
	p = root
	s = []
	curr = 0
	while len(s) > 0 or p:
		if not p:
			p = s[-1]
			s.pop()
			p.data += curr
			curr = p.data
			p = p.left
		elif p:
			s.append(p)
			p = p.right
	return root


def modify(root):
	a = [0]

	def fun(root):
		if root:
			fun(root.right)
			a[0] += root.data
			root.data = a[0]
			fun(root.left)
	fun(root)
	return root


def func(root, ans):
	if root is None:
		return
	func(root.right, ans)
	ans[0] += root.data
	root.data = ans[0]
	func(root.left, ans)

def modify(root):
	ans = [0]
	func(root, ans)
	return root


def rinord(root, sum):
	if not root:
		return
	rinord(root.right, sum)
	sum[0] += root.data
	root.data = sum[0]
	rinord(root.left, sum)

def modify(root):
	rinord(root, [0])
	return root


def modify(root):

	def inorder(root):
		if not root:
			return
		inorder(root.left)
		res.append(root.data)
		inorder(root.right)

	def update(root):
		nonlocal j, ans
		if not root:
			return
		update(root.left)
		root.data = ans[j]
		j += 1
		update(root.right)
	res = []
	inorder(root)
	tot = 0
	ans = []
	for i in range(len(res) - 1, -1, -1):
		tot += res[i]
		ans.append(tot)
	j = 0
	ans.reverse()
	update(root)
	return root


def modify(root):
	_modify(root, [0])
	return root

def _modify(node, pre):
	if node:
		_modify(node.right, pre)
		aux = node.data
		node.data += pre[0]
		pre[0] += aux
		_modify(node.left, pre)


def SumModify(root, sum):
	if root == None:
		return
	SumModify(root.right, sum)
	sum[0] += root.data
	root.data = sum[0]
	SumModify(root.left, sum)

def modify(root):
	sum = [0]
	SumModify(root, sum)
	return root


def util(root, sm=0):
	if not root:
		return 0
	right = util(root.right, sm)
	root.data += right + sm
	left = util(root.left, root.data)
	return left + root.data - sm

def modify(root):
	util(root)
	return root


def solve(root, sm):
	if root is None:
		return
	solve(root.right, sm)
	root.data += sm[0]
	sm[0] = root.data
	solve(root.left, sm)

def modify(root):
	sm = [0]
	solve(root, sm)
	return root


def helper(root, sum):
	if root == None:
		return
	helper(root.right, sum)
	sum[0] = sum[0] + root.data
	root.data = sum[0]
	helper(root.left, sum)

def modify(root):
	sum = [0]
	helper(root, sum)
	return root


def modify(root):

	def mod(root, prev=0):
		if root is None:
			return 0
		right = mod(root.right, prev)
		root.data += right + prev
		left = mod(root.left, root.data)
		return left + root.data - prev
	mod(root)
	return root


def modify(root):
	a = [0] * 1

	def fun(root):
		if root == None:
			return
		fun(root.right)
		a[0] += root.data
		root.data = a[0]
		fun(root.left)
	fun(root)
	return root


def modify(root):
	arr = items(root)
	store = {}
	summa = 0
	for item in arr:
		summa += item
		store[item] = summa
	stack = [root]
	while stack:
		tree = stack.pop()
		if not tree:
			continue
		temp = tree.data
		tree.data = store[temp]
		stack.append(tree.left)
		stack.append(tree.right)
	return root

def items(root):
	if root is None:
		return []
	output = []
	output += items(root.right)
	output += [root.data]
	output += items(root.left)
	return output


def recur(root, ans):
	if not root:
		return
	recur(root.right, ans)
	ans[0] += root.data
	root.data = ans[0]
	recur(root.left, ans)

def modify(root):
	recur(root, [0])
	return root


def modify(root):
	sum = [0]
	if root is None:
		return
	addingVal(root, sum)
	return root

def addingVal(root, sum):
	if root is None:
		return
	addingVal(root.right, sum)
	sum[0] = sum[0] + root.data
	root.data = sum[0]
	addingVal(root.left, sum)


class Solution:

	def __init__(self):
		self.s = 0

	def io(self, a):
		if a == None:
			return
		self.io(a.right)
		a.data += self.s
		self.s = a.data
		self.io(a.left)

def modify(root):
	o = Solution()
	o.io(root)
	return root


class Node:

	def __init__(self, val):
		self.right = None
		self.data = val
		self.left = None

def modify(root):
	Sum = [0]
	modifyBSTUtil(root, Sum)
	return root

def modifyBSTUtil(root, Sum):
	if root == None:
		return
	modifyBSTUtil(root.right, Sum)
	Sum[0] = Sum[0] + root.data
	root.data = Sum[0]
	modifyBSTUtil(root.left, Sum)


class Node:

	def __init__(self, val):
		self.right = None
		self.data = val
		self.left = None

def modify(root):
	global sum
	sum = 0
	modifyUtil(root)
	return root

def modifyUtil(root):
	global sum
	if root is None:
		return
	modifyUtil(root.right)
	root.data += sum
	sum = root.data
	modifyUtil(root.left)


def modify(root):
	q = []
	cur = root
	temp = 0
	while True:
		if cur is not None:
			q.append(cur)
			cur = cur.right
		elif q:
			cur = q.pop()
			cur.data += temp
			temp = cur.data
			cur = cur.left
		else:
			break
	return root


def modify(r):
	sum = [d(r)]
	T(r, sum)
	return r

def T(r, sum):
	if r:
		T(r.left, sum)
		sum[0] -= r.data
		r.data = sum[0] + r.data
		T(r.right, sum)

def d(r):
	if r:
		return r.data + d(r.left) + d(r.right)
	return 0


def modify(root):
	total = 0
	stack = []
	n = root
	while n or stack:
		if not n:
			n = stack.pop()
		else:
			while n.right:
				stack.append(n)
				n = n.right
		total += n.data
		n.data = total
		n = n.left
	return root


def modify(root):

	def traversal(root):
		nonlocal sum1
		if root == None:
			return None
		if root.right:
			traversal(root.right)
		sum1 += root.data
		root.data = sum1
		if root.left:
			traversal(root.left)
	sum1 = 0
	traversal(root)
	return root


def root_inorder(root, maxi):
	if not root:
		return None
	root_inorder(root.right, maxi)
	root.data += maxi[0]
	maxi[0] = root.data
	root_inorder(root.left, maxi)

def modify(root):
	root_inorder(root, [0])
	return root


def modify(root):
	if not root:
		return

	def help(root, sum):
		if not root:
			return sum
		sum = help(root.right, sum)
		sum += root.data
		root.data = sum
		sum = help(root.left, sum)
		return sum
	help(root, 0)
	return root


def modify(root):
	summ = [0]
	util(root, summ)
	return root

def util(root, summ):
	if not root:
		return
	util(root.right, summ)
	summ[0] += root.data
	root.data = summ[0]
	util(root.left, summ)


def modify(root):
	(arr, dic1, sum1, q, pos, len1) = ([], {}, 0, [root], 0, 1)
	while pos < len1:
		arr.append(q[pos].data)
		dic1[q[pos].data] = [0, q[pos]]
		sum1 += q[pos].data
		if q[pos].left:
			q.append(q[pos].left)
			len1 += 1
		if q[pos].right:
			q.append(q[pos].right)
			len1 += 1
		pos += 1
	arr.sort()
	dic1[arr[0]][0] = dic1[arr[0]][1].data = sum1
	for i in range(1, len1):
		dic1[arr[i]][0] = dic1[arr[i]][1].data = dic1[arr[i - 1]][0] - arr[i - 1]
	return root


def modifyBSTUtil(root, Sum):
	if root == None:
		return
	modifyBSTUtil(root.right, Sum)
	Sum[0] = Sum[0] + root.data
	root.data = Sum[0]
	modifyBSTUtil(root.left, Sum)

def modify(root):
	modifyBSTUtil(root, [0])
	return root


def treeinorder(root, l):
	if root == None:
		return []
	else:
		treeinorder(root.left, l)
		l.append(root.data)
		treeinorder(root.right, l)
	return l

def solve(root, d):
	if root == None:
		return None
	else:
		root.data = d[root.data]
		solve(root.left, d)
		solve(root.right, d)
	return root

def modify(root):
	l = []
	treeinorder(root, l)
	d = {}
	a = sum(l)
	b = l[0]
	d[l[0]] = a
	for i in range(1, len(l)):
		d[l[i]] = a - b
		b = b + l[i]
	return solve(root, d)


def postOrder(root):
	l = []
	q = set()
	cur = root
	while cur and cur not in q:
		if cur.left and cur.left not in q:
			cur = cur.left
		elif cur.right and cur.right not in q:
			cur = cur.right
		else:
			q.add(cur)
			l.append(cur.data)
			cur = root
	return l

def modify(root):
	q = []
	cur = root
	temp = 0
	while True:
		if cur is not None:
			q.append(cur)
			cur = cur.right
		elif q:
			cur = q.pop()
			cur.data += temp
			temp = cur.data
			cur = cur.left
		else:
			break
	return root


def modify(root):
	store = [0]
	modifyUtil(root, store)
	return root

def modifyUtil(root, store):
	if root.right:
		modifyUtil(root.right, store)
	x = root.data
	root.data += store[0]
	store[0] += x
	if root.left:
		modifyUtil(root.left, store)


def modify(root):
	arr = []

	def getInorder(root):
		if root == None:
			return
		getInorder(root.left)
		arr.append(root.data)
		getInorder(root.right)
	getInorder(root)
	s = 0
	for i in range(len(arr) - 1, -1, -1):
		s += arr[i]
		arr[i] = s
	index = 0

	def modify(root):
		if root == None:
			return
		modify(root.left)
		if len(arr) > 0:
			root.data = arr[0]
			del arr[0]
		modify(root.right)
	modify(root)
	return root


def modify(root):
	traver(root, 0)
	return root

def traver(root, n):
	if root is None:
		return n
	n = traver(root.right, n)
	n += root.data
	root.data = n
	n = traver(root.left, n)
	return n


def modify(root):
	ar = inor(root, [])
	ar = ar[::-1]
	su = ar[0]
	arr = []
	arr.append(su)
	for i in range(1, len(ar)):
		su = su + ar[i]
		arr.append(su)
	arr = arr[::-1]
	ans = tree(0, len(arr) - 1, arr)
	return ans

def inor(root, a):
	if root == None:
		return
	inor(root.left, a)
	a.append(root.data)
	inor(root.right, a)
	return a

def tree(s, e, arr):
	if s > e:
		return None
	mid = (s + e) // 2
	root = Node(arr[mid])
	root.left = tree(s, mid - 1, arr)
	root.right = tree(mid + 1, e, arr)
	return root


def modify(root):

	def ino(root, A):
		if root == None:
			return ([], 0)
		tot = 0
		(l, lt) = ino(root.left, [])
		A.extend(l)
		tot += lt
		A.append(root)
		tot += root.data
		(r, rt) = ino(root.right, [])
		tot += rt
		A.extend(r)
		return (A, tot)
	left = 0
	(arr, right) = ino(root, [])
	for node in arr:
		prev = node.data
		node.data = right - left
		left += prev
	return root


def modify(root):
	sum = [0]
	modifyUtil(root, sum)
	return root

def modifyUtil(root, Sum):
	if root == None:
		return
	modifyUtil(root.right, Sum)
	Sum[0] = Sum[0] + root.data
	root.data = Sum[0]
	modifyUtil(root.left, Sum)


def total(root):
	s = 0
	if root:
		s += root.data
		s += total(root.left)
		s += total(root.right)
	return s

def modify(root):
	temp = root
	total_sum = total(root)
	curr_sum = 0

	def updated_values(root, total_sum):
		nonlocal curr_sum
		if root:
			updated_values(root.left, total_sum)
			copy = root.data
			root.data = total_sum - curr_sum
			curr_sum += copy
			updated_values(root.right, total_sum)
	updated_values(root, total_sum)
	return root


class Node:

	def __init__(self, val):
		self.right = None
		self.data = val
		self.left = None

def modify(root):
	l = [0]
	update(root, l)
	return root

def update(root, l):
	if root:
		update(root.right, l)
		l[0] += root.data
		root.data = l[0]
		update(root.left, l)


def modify(root):
	l = [0]
	update(root, l)
	return root

def update(root, l):
	if root:
		update(root.right, l)
		l[0] += root.data
		root.data = l[0]
		update(root.left, l)


def modify(root):
	l = fn(root)
	l.reverse()
	foo = []
	sm = 0
	for i in l:
		sm += i
		foo += [sm]
	foo.reverse()
	pointer = [0]
	updatetree(root, foo, pointer)
	return root

def fn(r):
	if not r:
		return []
	return fn(r.left) + [r.data] + fn(r.right)

def updatetree(root, foo, pointer):
	if root:
		updatetree(root.left, foo, pointer)
		root.data = foo[pointer[0]]
		pointer[0] += 1
		updatetree(root.right, foo, pointer)


class Node:

	def __init__(self, val):
		self.right = None
		self.data = val
		self.left = None

def modify(root):
	cursum = 0

	def inorder(root):
		if root is None:
			return None
		else:
			nonlocal cursum
			inorder(root.right)
			temp = root.data
			root.data += cursum
			cursum += temp
			inorder(root.left)
		return root
	return inorder(root)


def modify(root):
	ans = []
	sum = 0

	def dfs(root):
		nonlocal sum
		if not root:
			return
		dfs(root.right)
		sum += root.data
		root.data = sum
		dfs(root.left)
	dfs(root)
	return root


def modify(root):
	val = [0]
	rec(root, val)
	return root

def rec(root, val):
	if not root:
		return 0
	rec(root.right, val)
	root.data += val[0]
	val[0] = root.data
	rec(root.left, val)


def helper(root, node_sum):
	if root == None:
		return
	helper(root.right, node_sum)
	node_sum[0] += root.data
	root.data = node_sum[0]
	helper(root.left, node_sum)

def modify(root):
	node_sum = [0]
	helper(root, node_sum)
	return root


def modify(root):

	def rec(root, curr_sum):
		if not root:
			return curr_sum
		right_sum = rec(root.right, curr_sum)
		root.data += right_sum
		left_sum = rec(root.left, root.data)
		return left_sum
	rec(root, 0)
	return root


def modify(root):

	def _solve(nd, pt):
		if not nd:
			return None
		X = _solve(nd.right, pt)
		if X is not None:
			add = X
		elif pt is not None:
			add = pt.data
		else:
			add = 0
		nd.data += add
		Y = _solve(nd.left, nd)
		return nd.data if Y is None else Y
	_solve(root, None)
	return root


def modify(root):
	sumi = [0]

	def ino(nod, flag):
		if nod is None:
			return
		ino(nod.left, flag)
		if flag == 0:
			sumi[0] += nod.data
		else:
			k = nod.data
			nod.data = sumi[0]
			sumi[0] -= k
		ino(nod.right, flag)
	ino(root, 0)
	ino(root, 1)
	return root


def modify(root):
	s = [0]

	def postOrder(r):
		if not r:
			return
		postOrder(r.right)
		s[0] += r.data
		r.data = s[0]
		postOrder(r.left)
	postOrder(root)
	return root


def help(root, x):
	if root is None:
		return
	help(root.right, x)
	root.data = root.data + x[0]
	x[0] = root.data
	help(root.left, x)

def modify(root):
	x = [0]
	help(root, x)
	return root


def modify(root):
	req = 0
	stack = []
	cur = root
	while 1:
		if cur:
			stack.append(cur)
			cur = cur.right
		elif stack:
			cur = stack.pop()
			temp = cur.data
			cur.data += req
			req += temp
			cur = cur.left
		else:
			break
	return root


def modify(root):
	stack = []
	curr = root
	res = 0
	while stack or curr:
		if curr:
			stack.append(curr)
			curr = curr.right
		else:
			curr = stack.pop()
			curr.data += res
			res = curr.data
			curr = curr.left
	return root


def modify(root):
	left_s = 0

	def solve(root):
		nonlocal left_s
		if root:
			solve(root.right)
			root.data += left_s
			left_s = root.data
			solve(root.left)
		return
	solve(root)
	return root


def modify(root):
	seh = 0

	def dfs(root, seh):
		if not root:
			return
		if root.right:
			seh = dfs(root.right, seh)
		root.data += seh
		seh = root.data
		if root.left:
			seh = dfs(root.left, seh)
		return seh
	dfs(root, seh)
	return root


def modify(root):
	msum = 0

	def dfs(root):
		nonlocal msum
		if not root:
			return
		dfs(root.right)
		root.data += msum
		msum = root.data
		dfs(root.left)
	dfs(root)
	return root


def ino(r, l):
	if r is None:
		return
	ino(r.left, l)
	l.append(r)
	ino(r.right, l)

def modify(root):
	l = []
	ino(root, l)
	n = len(l)
	s = 0
	for i in range(n - 1, -1, -1):
		g = l[i].data
		l[i].data += s
		s += g
	return root


def modify(root):

	def f(root):
		if root == None:
			return 0
		f(root.right)
		summ[0] += root.data
		root.data = summ[0]
		f(root.left)
	summ = []
	summ.append(0)
	f(root)
	return root


def modify(root):
	s = 0

	def inorder(root):
		nonlocal s
		if not root:
			return
		inorder(root.right)
		s += root.data
		root.data = s
		inorder(root.left)
	inorder(root)
	return root


def modify(root):

	def rrl(node, sm):
		if node:
			rrl(node.right, sm)
			node.data += sm[0]
			sm[0] = node.data
			rrl(node.left, sm)
	rrl(root, [0])
	return root


def modify(root):
	num = [0]

	def fun(root, num):
		if root == None:
			return
		fun(root.right, num)
		root.data += num[0]
		num[0] = root.data
		fun(root.left, num)
	fun(root, num)
	return root


def modify(root):
	total = 0

	def traverse(root):
		nonlocal total
		if root == None:
			return
		traverse(root.right)
		total += root.data
		root.data = total
		traverse(root.left)
	traverse(root)
	return root


def modify(r):
	s = []
	t = r
	while t:
		s.append(t)
		t = t.right
	t = 0
	while s:
		x = s.pop(-1)
		x.data += t
		t = x.data
		if x.left:
			s.append(x.left)
			x = s[-1]
			while x.right:
				s.append(x.right)
				x = x.right
	return r


def modifyS(root, sum):
	if root == None:
		return
	modifyS(root.right, sum)
	sum[0] = sum[0] + root.data
	root.data = sum[0]
	modifyS(root.left, sum)

def modify(root):
	modifyS(root, [0])
	return root


def solve(root, summ):
	if root == None:
		return
	solve(root.right, summ)
	summ[0] = summ[0] + root.data
	root.data = summ[0]
	solve(root.left, summ)

def modify(root):
	summ = [0]
	solve(root, summ)
	return root


def modify(root):

	def inorder1(root, arr):
		if not root:
			return 0
		inorder1(root.right, arr)
		arr[0] = arr[0] + root.data
		root.data = arr[0]
		inorder1(root.left, arr)
	arr = [0]
	inorder1(root, arr)
	return root


def modify(root):
	global i
	i = 0

	def inorder1(root, arr):
		global i
		if not root:
			return 0
		inorder1(root.left, arr)
		root.data = arr.pop(0)
		inorder1(root.right, arr)

	def inorder(root):
		if not root:
			return []
		return inorder(root.left) + [root.data] + inorder(root.right)
	arr = inorder(root)
	prev = 0
	sum1 = sum(arr)
	for i in range(len(arr)):
		a = arr[i]
		arr[i] = sum1 - prev
		prev += a
	inorder1(root, arr)
	return root


def inor(root):
	s = []
	ans = []
	curr = root
	while True:
		if curr != None:
			s.append(curr)
			curr = curr.left
		elif curr == None and s != []:
			curr = s.pop()
			ans.append(curr.data)
			curr = curr.right
		else:
			break
	return ans

def modify(root):
	nodes = inor(root)
	n = len(nodes)
	for i in range(n - 2, -1, -1):
		nodes[i] += nodes[i + 1]
	i = 0
	s = []
	curr = root
	while True:
		if curr != None:
			s.append(curr)
			curr = curr.left
		elif curr == None and s != []:
			curr = s.pop()
			curr.data = nodes[i]
			i += 1
			curr = curr.right
		else:
			break
	return root


def inorder1(root):
	if not root:
		return 0
	nsum = 0
	nsum += inorder1(root.left)
	nsum += root.data
	nsum += inorder1(root.right)
	return nsum

def modify(root):
	global nsum
	nsum = inorder1(root)

	def solve(root):
		global nsum
		if not root:
			return
		solve(root.left)
		nsum -= root.data
		root.data += nsum
		solve(root.right)
	solve(root)
	return root


def inorder1(root, arr):
	if not root:
		return
	inorder1(root.left, arr)
	arr.append(root.data)
	inorder1(root.right, arr)
	return arr

def modify(root):
	arr = inorder1(root, [])
	global nsum
	nsum = sum(arr)

	def solve(root):
		global nsum
		if not root:
			return
		solve(root.left)
		nsum -= root.data
		root.data += nsum
		solve(root.right)
	solve(root)
	return root


def modify(root):
	summ = [0]
	modifyBST(root, summ)
	return root

def modifyBST(root, summ):
	if not root:
		return
	modifyBST(root.right, summ)
	summ[0] += root.data
	root.data = summ[0]
	modifyBST(root.left, summ)


def getSum(root, tot):
	if root == None:
		return
	getSum(root.right, tot)
	tot[0] += root.data
	root.data = tot[0]
	getSum(root.left, tot)

def modify(root):
	if root == None:
		return root
	tot = [0]
	getSum(root, tot)
	return root
from collections import deque

class Node:

	def __init__(self, val):
		self.right = None
		self.data = val
		self.left = None

def buildTree(s):
	if len(s) == 0 or s[0] == 'N':
		return None
	ip = list(map(str, s.split()))
	root = Node(int(ip[0]))
	size = 0
	q = deque()
	q.append(root)
	size = size + 1
	i = 1
	while size > 0 and i < len(ip):
		currNode = q[0]
		q.popleft()
		size = size - 1
		currVal = ip[i]
		if currVal != 'N':
			currNode.left = Node(int(currVal))
			q.append(currNode.left)
			size = size + 1
		i = i + 1
		if i >= len(ip):
			break
		currVal = ip[i]
		if currVal != 'N':
			currNode.right = Node(int(currVal))
			q.append(currNode.right)
			size = size + 1
		i = i + 1
	return root

def inorder(root):
	if root != None:
		inorder(root.left)
		print(root.data, end=' ')
		inorder(root.right)
if __name__ == '__main__':
	t = int(input())
	for _ in range(0, t):
		s = input()
		root = buildTree(s)
		root = modify(root)
		inorder(root)
		print()