B. Google Search (Hard)
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This is the hard version of the problem. In this version, $$$n, q \le 10^5$$$.

After years of competitive programming, Pacha is officially tired. Too many WAs, too many TLs, too many "elegant" data structures that only work in editorials. So he decided to do something different: build his own web search engine.

In a real search engine, searches are usually stored in a huge trie that grows with every new query. Pacha thought about doing it that way, and then remembered he had already suffered enough. To avoid dying with tries, he decided to reduce the problem to a simpler structure.

His search engine is modeled as a fixed tree with $$$n$$$ nodes. Each node represents a search category and stores a counter of how many times it has been searched. Initially, all counters are $$$0$$$.

The tree never changes shape or grows. The only thing that happens over time is that searches accumulate.

During $$$q$$$ days, events of two types are recorded:

  • Type $$$1$$$: a category receives new searches and its counter increases.
  • Type $$$2$$$: Pacha wants to know the $$$5$$$ most searched categories, in non-increasing order, within a part of his search engine represented by a subtree.

The tree is rooted at node $$$1$$$. The subtree of a node $$$v$$$ includes $$$v$$$ itself and all of its descendants.

Your task is to process all events and correctly answer every query.

Input

The first line contains an integer $$$n$$$ ($$$2 \le n \le 10^5$$$), the number of nodes of the tree.

Each of the next $$$n-1$$$ lines contains two integers $$$a_i, b_i$$$ ($$$1 \le a_i, b_i \le n$$$, $$$a_i \ne b_i$$$), meaning there is an edge between $$$a_i$$$ and $$$b_i$$$. It is guaranteed that the edges form a tree.

The next line contains an integer $$$q$$$ ($$$1 \le q \le 10^5$$$), the number of recorded events.

Each of the next $$$q$$$ lines describes an event. There are two possible types of events:

  • 1 $$$v$$$ $$$x$$$ — increase the counter of node $$$v$$$ by $$$x$$$ ($$$1 \le v \le n$$$, $$$1 \le x \le 10^3$$$).
  • 2 $$$v$$$ — query: report the $$$5$$$ largest values, in non-increasing order, within the subtree of $$$v$$$ ($$$1 \le v \le n$$$).
Output

For each query of type $$$2$$$, print a line with exactly $$$5$$$ integers in non-increasing order.

Note: if the subtree of node $$$v$$$ contains fewer than $$$5$$$ nodes, repeat the smallest value present in the subtree as many times as needed to complete the $$$5$$$ values.

Example
Input
7
1 2
1 3
2 4
2 5
3 6
3 7
9
1 4 10
1 5 3
1 2 6
2 2
1 6 8
1 7 8
2 3
1 1 100
2 1
Output
10 6 3 3 3 
8 8 0 0 0 
100 10 8 8 6