cf 463E

/* cf 463E */

/*I'll post my solution for E and try to do a "mini-editorial" for it. You can easily notice that the value for any node is maximum 2*10^6. We can keep a binary search tree (Set in c++) for every number from 1 to 2*10^6. In each set we will keep a pair (depth[node], node) in order to find in O(1) the deepest node which has the divisor according to the set.

Example: node = 1; value[node] = 6; ( 6 = 2*3 ) depth[node] = 2;

At one point we will have: (2,1) in Set[2] and
                  (2,1) in Set[3]
We modify these sets in the DFS as follows:

void DFS (int node)
{
    ans[node] = pair(-1,-1) /// we might not have an answer for this node

    for ( every prime divisor of value[node] )
        if ( Set[ prime divisor] not empty ) /// we have found a node x that has the same divisor and our node
        ans[node] = max( ans[node], last_element_in_set );

    for ( every prime divisor of value[node] )
        Set[ prime divisor ].insert( pair( depth[node], node ) );

    for ( every every child of node )
        DFS(child)

    for ( every prime divisor of value[node] )
        Set[ prime divisor ].erase( pair( depth[node], node ) );
}
!!!Node: these sets are gives the nodes sorted by their depth

When we find an update query we just run DFS(1) and done! If something is not clear just ask!*/

int prime[MAX],p,arr[MAX];vi Div[MAX];pii ans[MAX];
set<pii>S[MAX];vi v[MAX];
void sieve(int n){
    double z = sqrt(n);
    for(int i = 3;i<=z;i+=2){
        if(!arr[i]){
            for(ll j = (i*i);j<=n;j+=i+i)arr[j] = 1;
        }
    }
    prime[p++] = 2;
    for(int i = 3;i<=n;i+=2)if(!arr[i])prime[p++] = i;
}

void fact(int n){
    int root = n;
    Div[root].clear();
    for(int i = 0;prime[i]*prime[i]<=n;i++){
        if(n%prime[i]==0){
            Div[root].pb(prime[i]);
            while(n%prime[i]==0)n/=prime[i];
        }
    }
    if(n>1)Div[root].pb(n);
}

void dfs(int n,int depth,int p = 0){
    ans[n] = {-1,-1};
    for(auto it : Div[arr[n]]){
        if((int)S[it].size()!=0){
            ans[n] = max(ans[n],*S[it].rbegin());
        }
    }
    for(auto it : Div[arr[n]]){
        S[it].insert({depth,n});
    }
    for(auto it : v[n]){
        if(it!=p)dfs(it,depth+1,n);
    }
    for(auto it : Div[arr[n]]){
        S[it].erase({depth,n});
    }
}

int main()
{
    booster()
   // read("input.txt");
    sieve(2000000);
    int n,q;
    cin>>n>>q;
    for(int i = 1;i<=n;i++){
        cin>>arr[i];
        fact(arr[i]);
    }
    for(int i = 0;i<n-1;i++){
        int a,b;
        cin>>a>>b;
        v[a].pb(b);
        v[b].pb(a);
    }

    dfs(1,0);
    for(int i = 1;i<=q;i++){
        int a;
        cin>>a;
        if(a==1){
            int node;
            cin>>node;
            cout<<ans[node].ss<<endl;
        }
        else {
            int node,val;
            cin>>node>>val;
            arr[node] = val;
            fact(val);
            dfs(1,0);
        }
    }

    return 0;
}