Given a tree with n nodes labeled 1,2,…,n and an initial root r equal to 1, each node i is associated with a pair of integers ai and bi that represent the line equation ai⋅x+bi. There are q queries of the following types:
- Type 1: 1 x Update the root of the tree to node x (1≤x≤n).
- Type 2: 2 u x Consider the tree T with the current root r. In the subtree of node u within T, find the node v such that avâ‹…x+bv is maximized. Let this maximum value be ans, and print max(ans,0).
Your task is to process and respond to the given queries.
- The first line contains two positive integers n and q.
- The second line contains n integers a1,a2,…,an.
- The third line contains n integers b1,b2,…,bn.
- The next n−1 lines, each containing two positive integers ui,vi, describe the edges of the tree.
- The following q lines each describe one of the two query types.
Output
- For each query of type 2, output the result.
Constraints
- 1≤n,q≤2⋅105.
- −106≤ai,bi≤106 for all 1≤i≤n.
- −106≤x≤106 for all values of x in type 2 queries.
Example
Input
5 5
3 1 4 3 -1
2 2 -5 1 2
1 2
1 3
3 4
2 5
2 1 2
2 2 3
1 4
2 5 1
2 4 4
Output
8
5
1
14