Processing math: 100%
Line tree - MarisaOJ: Marisa Online Judge

Line tree

Time limit: 1000 ms
Memory limit: 256 MB

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.

Input

  • 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
Topic
Tree
Data structure
Rating 2000
Solution (1) Solution